Q. Which of the following statements are TRUE?

I. There exist parsing algorithms for some programming languages
whose complexities are less than O(n^3).
II. A programming language which allows recursion can be implemented
with static storage allocation.
III. No L-attributed definition can be evaluated in The framework
of bottom-up parsing.
IV. Code improving transformations can be performed at both source
language and intermediate code level.

View solution

Q. Which of the following describes a handle (as applicable to LR-parsing) appropriately?

View solution

Q. An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if

View solution

Q. Which one of the following is a top-down parser?

View solution

Q. Consider the grammar with non-terminals N = {S,C,S1 },terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:

S --> iCtSS1|a
S1 --> eS|ϵ
C --> b

The grammar is NOT LL(1) because:

View solution

Q. Consider the following two statements:

P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?

View solution

Q. Consider the following grammar.

S -> S * E
S -> E
E -> F + E
E -> F
F -> id

Consider the following LR(0) items corresponding to the grammar above.

(i) S -> S * .E
(ii) E -> F. + E
(iii) E -> F + .E

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

View solution

Q. A canonical set of items is given below

S --> L. > R
Q --> R.

On input symbol < the set has

View solution

Q. Consider the grammar defined by the following production rules, with two operators ∗ and +

S --> T * P
T --> U | T * U
P --> Q + P | Q
Q --> Id
U --> Id

Which one of the following is TRUE?

View solution

Q. Consider the following grammar:

S → FR
R → S | ε
F → id

In the predictive parser table, M, of the grammar the entries M[S, id] and M[R, $] respectively

View solution

Q. Consider the following translation scheme. S → ER R → *E{print("*");}R | ε E → F + E {print("+");} | F F → (S) | id {print(id.value);} Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints

View solution

Q. The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is

View solution

Q. Consider the grammar

E → E + n | E × n | n

For a sentence n + n × n, the handles in the right-sentential form of the reduction are

View solution

Q. Consider the grammar

S → (S) | a

Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good

View solution

Q. Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production.

E → number E.val = number. val
| E '+' E E(1).val = E(2).val + E(3).val
| E '×' E E(1).val = E(2).val × E(3).val

The above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?

View solution

Q. Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production.

E → number E.val = number. val
| E '+' E E(1).val = E(2).val + E(3).val
| E '×' E E(1).val = E(2).val × E(3).val

Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?

View solution

Q. Which of the following grammar rules violate the requirements of an operator grammar ? P, Q, R are nonterminals, and r, s, t are terminals.

1. P → Q R
2. P → Q s R
3. P → ε
4. P → Q t R r

View solution

Q. Consider the grammar with the following translation rules and E as the start symbol.

E → E1 # T { E.value = E1.value * T.value }
| T{ E.value = T.value }
T → T1 & F { T.value = T1.value + F.value }
| F{ T.value = F.value }
F → num { F.value = num.value }

Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.

View solution

Q. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?

View solution

Q. Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is:

View solution