Parsers
Question 1 |
S → Aa
A → BD
B → b | ε
D → d | ε
Let a, b, d and $ be indexed as follows:
Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, $}, then the answer should be 3210)
30 | |
31 | |
10 | |
21 |
{Follow(B) = Follow(A) when D is epsilon}
Follow(B) = {d} Union {a} = {a,d}
Hence Answer is : 31
Question 2 |
Which one of the following kinds of derivation is used by LR parsers?
Leftmost in reverse | |
Rightmost in reverse | |
Leftmost | |
Rightmost |
Question 3 |
Consider the augmented grammar given below:
S' → S
S → 〈L〉 | id
L → L,S | S
Let I0 = CLOSURE ({[S' → ·S]}). The number of items in the set GOTO (I0 , 〈 ) is: _____.
4 | |
5 | |
6 | |
7 |

Hence, the set GOTO (I0 , 〈 ) has 5 items.
Question 4 |
Which of the following statements about parser is/are CORRECT?
I. Canonical LR is more powerful than SLR.
II. SLR is more powerful than LALR.
III. SLR is more powerful than Canonical LR.
I only | |
II only | |
III only | |
II and III only |
The power in increasing order is:
LR(0) < SLR < LALR < CLR
Hence only I is true.
Question 5 |
Which one of the following is True at any valid state in shift-reduce parsing?
Viable prefixes appear only at the bottom of the stack and not inside | |
Viable prefixes appear only at the top of the stack and not inside | |
The stack contains only a set of viable prefixes | |
The stack never contains viable prefixes |
A viable prefixes is prefix of the handle and so can never extend to the right of handle, i.e., top of stack.
So set of viable prefixes is in stack.
Question 6 |
Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?
SLR, LALR | |
Canonical LR, LALR | |
SLR, canonical LR | |
LALR, canonical LR |
Question 7 |
stmt → if expr then expr else expr; stmt | ȯ
expr → term relop term | term
term → id | number
id → a | b | c
number → [0-9]
where relop is a relational operator (e.g., <, >, …), ȯ refers to the empty statement, and if, then, else are terminals.
Consider a program P following the above grammar containing ten if terminals. The number of control flow paths in P is ________. For example, the program
if e1 then e2 else e3 has 2 control flow paths, e1 → e2 and e1 → e3.
1024 | |
1025 | |
1026 | |
1027 |
if
if
:
:
:
(keep doing 10 times to get 10 'if')
We know that every if statement has 2 control flows as given in question. Hence,
We have 2 control flow choices for 1st 'if'
We have 2 control flow choices for 2nd 'if'
:
:
:
We have 2 control flow choices for 10th 'if'
Since all the choices are in one single structure or combination, so total choices are
2 × 2 × 2 × ........ 10 times = 210 = 1024
Question 8 |
Consider the following grammar G.
S → F ⎪ H F → p ⎪ c H → d ⎪ c
Where S, F and H are non-terminal symbols, p, d and c are terminal symbols. Which of the following statement(s) is/are correct?
- S1: LL(1) can parse all strings that are generated using grammar G.
S2: LR(1) can parse all strings that are generated using grammar
Only S1 | |
Only S2 | |
Both S1 and S2 | |
Neither S1 nor S2 |
For first production,
So, there is 'c' common in both the first(s) in the production of S. So not LL(1).
For LR(1),
Since R-R conflict is present. So, not LR(1).
Hence, Option (D) is the correct answer.
Question 9 |
A canonical set of items is given below
S --> L. > R Q --> R.
On input symbol < the set has
a shift-reduce conflict and a reduce-reduce conflict. | |
a shift-reduce conflict but not a reduce-reduce conflict. | |
a reduce-reduce conflict but not a shift-reduce conflict. | |
neither a shift-reduce nor a reduce-reduce conflict. |
But if it would have asked about “>” then it will be a SR conflict.
Question 10 |
Consider two binary operators ‘↑’ and ‘↓’ with the precedence of operator ↓ being lower than that of the operator ↑. Operator ↑ is right associative while operator ↓, is left associative. Which one of the following represents the parse tree for expression (7↓3↑4↑3↓2)?
![]() | |
![]() | |
![]() | |
![]() |
⇒ 7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2
⇒ 7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative
Question 11 |
The grammar S → aSa|bS|c is
LL(1) but not LR(1) | |
LR(1) but not LR(1) | |
Both LL(1) and LR(1) | |
Neither LL(1) nor LR(1) |

As there is no conflict in LL(1) parsing table, hence the given grammar is LL(1) and since every LL(1) is LR(1) also, so the given grammar is LL(1) as well as LR(1).
Question 12 |
Which of the following describes a handle (as applicable to LR-parsing) appropriately?
It is the position in a sentential form where the next shift or reduce operation will occur.
| |
It is non-terminal whose production will be used for reduction in the next step. | |
It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur.
| |
It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found.
|
Question 13 |
Which one of the following is a top-down parser?
Recursive descent parser. | |
Operator precedence parser. | |
An LR(k) parser.
| |
An LALR(k) parser. |
Question 14 |
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:
it is left recursive | |
it is right recursive | |
it is ambiguous | |
it is not context-free |
This grammar has two parse tree for string “ibt ibt aea”.
Question 15 |
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A → є and A → a) to parse a string with n tokens?
n/2 | |
n-1 | |
2n-1 | |
2n |
1) epsilon production
2) production of the form A → a
Consider the grammar:
S → Sa | a
If we were to derive the string “aaa” whose length is 3 then the number of reduce moves that would have been required are shown below:
S → Sa
→ Saa
→ aaa
This shows us that it has three reduce moves. The string length is 3 and the number of reduce moves is also 3. So presence of such kinds of production might give us the answer “n” for maximum number of reduce moves. But these productions are not allowed as per the question.
Also note that if a grammar does not have unit production then the maximum number of reduce moves can not exceed “n” where “n” denotes the length of the string.
3) No unit productions
Consider the grammar:
S → A
A → B
B → C
C → a
If we were to derive the string “a” whose length is 1 then the number of reduce moves that would have been required are shown below:
S → A
A → B
B → C
C → a
This shows us that it has four reduce moves. The string length is 1 and the number of reduce moves is 4. So presence of such kind of productions might give us the answer “n+1” or even more, for maximum number of reduce moves. But these productions are not allowed as per the question.
Now keeping in view the above points suppose we want to parse the string “abcd”. (n = 4) using bottom-up parsing where strings are parsed finding the rightmost derivation of a given string backwards. So here we are concentrating on deriving right most derivations only.
We can write the grammar which accepts this string which in accordance to the question, (i.e., with no epsilon- and unit-production (i.e., of type A → є and A → B) and no production of the form A → a) as follows:
S → aB
B → bC
C → cd
The Right Most Derivation for the above is:
S → aB (Reduction 3)
→ abC (Reduction 2)
→ abcd (Reduction 1)
We can see here the number of reductions present is 3.
We can get less number of reductions with some other grammar which also doesn’t produce unit or epsilon productions or production of the form A → a
S → abA
A → cd
The Right Most Derivation for the above is:
S → abA (Reduction 2)
→ abcd (Reduction 1)
Hence 2 reductions.
But we are interested in knowing the maximum number of reductions which comes from the 1st grammar. Hence total 3 reductions as maximum, which is (n – 1) as n = 4 here.
Question 16 |
For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.
S → aAbB | bAaB | ε A → S B → S
The FIRST and FOLLOW sets for the non-terminals A and B are
FIRST(A) = {a,b,ε} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = {a,b,$} | |
FIRST(A) = {a,b,$} FIRST(B) = {a,b,ε} FOLLOW(A) = {a,b} FOLLOW(B) = {$} | |
FIRST(A) = {a,b,ε} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = ∅ | |
FIRST(A) = {a,b} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = {a,b} |
FOLLOW(P): is the set of terminals that can appear immediately to the right of P in some sentential form.
FIRST(A) = FIRST (S)
FIRST (S) = FIRST (aAbB) and FIRST (bAaB) and FIRST (ϵ)
FIRST(S) = {a, b, ϵ}
FIRST (B) = FIRST (S) = {a, b, ϵ} = FIRST (A)
FOLLOW(A) = {b} // because of production S→a A b B
FOLLOW(A) = {a} // because of production S→ b A a B
So FOLLOW (A) = {a, b}
FOLLOW (B) = FOLLOW (S) // because of production S→ a A b B
FOLLOW (S) = FOLLOW (A) // because of production S → A
So FOLLOW (S) = {$, a, b} = FOLLOW(B)
Question 17 |
For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.
S → aAbB | bAaB | ε A → S B → S
The appropriate entries for E1, E2, and E3 are
E1: S → aAbB,A → S E2: S → bAaB,B→S E3: B → S | |
E1: S → aAbB,S→ ε E2: S → bAaB,S → ε E3: S → ε | |
E1: S → aAbB,S → ε E2: S → bAaB,S→ε E3: B → S | |
E1: A → S,S →ε E2: B → S,S → ε E3: B →S |
S→ aAbB | bAaB | ε
The production S→ aAbB will go under column FIRST (aAbB) = a, so S→ aAbB will be in E1.
S→ bAaB will go under column FIRST(bAaB) = b, so S→ bAaB will be in E2.
S→ ε will go under FOLLOW (S) = FOLLOW(B) = {a, b, $ } , So S→ ε will go in E1, E2 and under column of $.
So E1 will have: S→ aAbB and S→ ε.
E2 will have S→ bAaB and S→ ε.
Now, B→ S will go under FIRST (S) = {a, b, ε}
Since FIRST(S) = ε so B→ S will go under FOLLOW (B) = {a, b, $}
So E3 will contain B→ S.
Question 18 |
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?
(i) and (ii) | |
(ii) and (iii) | |
(i) and (iii) | |
None of the above |
Question 19 |
The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is:
ambiguous | |
left-recursive | |
right-recursive | |
an operator-grammar |
It have A → AA has left recursion.
Question 20 |
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:
n1 < n2 < n3 | |
n1 = n3 < n2 | |
n1 = n2 = n3 | |
n1 ≥ n3 ≥ n2 |
→ LR(1) be the states of LR(1) items.
→ LR(0) items never be greater than LR(1) items then SLR(1) = LALR(1) < LR(1)
n1 = (n3) < (n2)
Question 21 |
Consider the following expression grammar. The semantic 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>sup>(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?
It detects recursion and eliminates recursion
| |
It detects reduce-reduce conflict, and resolves
| |
It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action | |
It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action
|
Question 22 |
Which of the following statements are TRUE?
-
I.There exist parsing algorithms for some programming languages whose complexities are less than θ(n3).
II.A programming language which allows recursion can be implemented with static storage.
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.
I and II
| |
I and IV | |
III and IV | |
I, III and IV |
Statement I is true, as the bottom up and top down parser take O(n) time to parse the string , i.e. only one scan of input is required.
Statement IV is true,Code improving transformations can be performed at both source language and intermediate code level. For example implicit type casting is also a kind of code improvement which is done during semantic analysis phase and intermediate code optimization is a topic itself which uses various techniques to improve the code such as loop unrolling, loop invariant.
Question 23 |
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
the SLR(1) parser for G has S-R conflicts | |
the LR(1) parser for G has S-R conflicts
| |
the LR(0) parser for G has S-R conflicts | |
the LALR(1) parser for G has reduce-reduce conflicts
|
Consider a state in LR(1) parser:
S-> x.yA, a
A-> x. , y
This has both shift and reduce conflict on symbol “y”.
Since LR(1) already has SR conflict , so resulting LALR(1) (after merging) will also have SR conflict.
Now if LR(1) doesn’t have SR conflict then it is guaranteed that the LALR(1) will never have SR conflict. The reason behind this is, as we merge those state only which has same set of canonical items except look ahead and the LR(1) canonical items has DFA (means from one state to other state the transition is from unique symbol) , so after merging also we will never see any shift conflict, only reduce-reduce may occur.
Hence An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if the LR(1) parser for G has S-R conflicts.
Question 24 |
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?
Both P and Q are true | |
P is true and Q is false | |
P is false and Q is true | |
Both P and Q are false |
For ex: Consider a regular grammar
S -> aS | a | ϵ
this grammar is ambiguous as for string "a" two parse tree is possible.
Hence it is regular but not LL(1).
But every regular set has a language accept or as DFA , so every regular set must have atleast one grammar which is unambiguous.
Hence, every regular set has LR(1) grammar.
Question 25 |
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.
{S → FR} and {R → ε}
| |
{S → FR} and { } | |
{S → FR} and {R → *S} | |
{F → id} and {R → ε} |
The representation M[X,Y] means X represents Variable (rows) and Y represents terminals (columns).
The productions are filled in parsing table by the below mentioned rules:
For every production P → α, we have:
Rule 1: If P → α is a production then add this production for each terminal “t” which is in FIRST of [α] i.e., ADD P → α to M[P, a]
Rule 2: If “ϵ” belongs to FIRST of [P] then add P → α to M[P, b] where “b” represents terminals FOLLOW[P].
By the above rules, we can see that production S → FR will go M[S, a] where “a” is FIRST [FR] which is equal to FIRST[F] = id, So S → FR will go in M[S,id].
Since in the production R→ϵ , FIRST[ϵ] = ϵ, hence the production will go in M[R, b] where “b” represents terminals FOLLOW[R] and FOLLOW[R] = $, so production R→ϵ will go in M[R,$]
Question 26 |
Consider the following expression grammar. The semantic 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>sup>(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?
Equal precedence and left associativity; expression is evaluated to 7
| |
Equal precedence and right associativity; expression is evaluated to 9 | |
Precedence of '×' is higher than that of '+', and both operators are left associative; expression is evaluated to 7 | |
Precedence of '+' is higher than that of '×', and both operators are left associative; expression is evaluated to 9 |

Hence, the answer is 9 and right associative.
Question 27 |
Which of the following grammar rules violate the requirements of an operator grammar? P,Q,R are nonterminals, and r,s,t are terminals.
- (i) P → Q R
(ii) P → Q s R
(iii) P → ε
(iv) P → Q t R r
(i) only | |
(i) and (iii) only | |
(ii) and (iii) only | |
(iii) and (iv) only |
i) On RHS it contains two adjacent non-terminals.
ii) Have nullable values.
Question 28 |
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:
n1 is necessarily less than n2 | |
n1 is necessarily equal to n2
| |
n1 is necessarily greater than n2
| |
None of the above |
Question 29 |
Consider the grammar shown below
S → i E t S S' | a S' → e S | ε E → b
In the predictive parse table. M, of this grammar, the entries M[S', e] and M[S', $] respectively are
{S'→e S} and {S'→ε} | |
{S'→e S} and { } | |
{S'→ε} and {S'→ε} | |
{S'→e S, S'→ε} and {S'→ε} |
First(S') = {e,ε}
First(E) = {b}
Follow(S') = {e,$}
Only when 'First' contains ε, we need to consider FOLLOW for getting the parse table entry.

Hence, option (D) is correct.
Question 30 |
Consider the grammar shown below.
S → C C C → c C | d
The grammar is
LL(1) | |
SLR(1) but not LL(1)
| |
LALR(1) but not SLR(1) | |
LR(1) but not LALR(1)
|

Hence, it is LL(1).
Question 31 |
Which of the following statements is false?
An unambiguous grammar has same leftmost and rightmost derivation | |
An LL(1) parser is a top-down parser | |
LALR is more powerful than SLR | |
An ambiguous grammar can never be LR(k) for any k |
Option C: LALR is more powerful than SLR.
Option D: An ambiguous grammar can never be LR (k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is.




