## Parsers

 Question 1
Consider the following grammar.
S->aSB| d
B->b
The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is _______.
 A 7
Compiler-Design       Parsers       GATE 2020
Question 1 Explanation:

7 reductions total.
 Question 2

Consider the following grammar:

    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.

 A 1024 B 1025 C 1026 D 1027
Compiler-Design       Parsers       Gate 2017 set-01
Question 2 Explanation:
To get 10 'if' we need to use grammar to get,
if then else ; stmt
if then else ; if then else . stmt
:
:
:
(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 3

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.
 A I only B II only C III only D II and III only
Compiler-Design       Parsers       GATE 2017(set-02)
Question 3 Explanation:
Canonical LR is more powerful than SLR as every grammar which can be parsed by SLR parser, can also be parsed by CLR parser.
The power in increasing order is:
LR(0) < SLR < LALR < CLR
Hence only I is true.
 Question 4

Which one of the following is True at any valid state in shift-reduce parsing?

 A Viable prefixes appear only at the bottom of the stack and not inside B Viable prefixes appear only at the top of the stack and not inside C The stack contains only a set of viable prefixes D The stack never contains viable prefixes
Compiler-Design       Parsers       GATE 2015 (Set-01)
Question 4 Explanation:
A handle is actually on the top of the stack.
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 5
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?
 A SLR, LALR B Canonical LR, LALR C SLR, canonical LR D LALR, canonical LR
Compiler-Design       Parsers       GATE 2015(Set-03)
Question 5 Explanation:
SLR is very easy to implement and CLR is most powerful method.
 Question 6
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

 A Only S1 B Only S2 C Both S1 and S2 D Neither S1 nor S2
Compiler-Design       Parsers       GATE 2015(Set-03)
Question 6 Explanation:
For LL(1),
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 7
A canonical set of items is given below
S --> L. > R
Q --> R.
On input symbol < the set has
 A a shift-reduce conflict and a reduce-reduce conflict. B a shift-reduce conflict but not a reduce-reduce conflict. C a reduce-reduce conflict but not a shift-reduce conflict. D neither a shift-reduce nor a reduce-reduce conflict.
Compiler-Design       Parsers       GATE 2014(Set-01)
Question 7 Explanation:
The input symbol is “<” which is not in canonical set of item, so it is neither a shift-reduce nor a reduce-reduce conflict with reference to “<” symbol.
But if it would have asked about “>” then it will be a SR conflict.
 Question 8

 A FIRST(A) = {a,b,ε} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = {a,b,$} B FIRST(A) = {a,b,$} FIRST(B) = {a,b,ε} FOLLOW(A) = {a,b} FOLLOW(B) = {$} C FIRST(A) = {a,b,ε} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = ∅ D FIRST(A) = {a,b} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = {a,b} Compiler-Design Parsers Gate 2012 Question 8 Explanation: FIRST (P): is the set of terminals that begin the strings derivable from non terminal P. If P derives epsilon then we include epsilon in FIRST(P). 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 A → S So FOLLOW (S) = {$, a, b}= FOLLOW(B)
 Question 9
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. Note:In the table second column first row it's not "A" it's "a".  A E1: S → aAbB,A → S E2: S → bAaB,B→S E3: B → S B E1: S → aAbB,S→ ε E2: S → bAaB,S → ε E3: S → ε C E1: S → aAbB,S → ε E2: S → bAaB,S→ε E3: B → S D E1: A → S,S →ε E2: B → S,S → ε E3: B →S Compiler-Design Parsers Gate 2012 Question 9 Explanation: The entries in E1, E2 and E3 is related to S and B, so we have to take only those production which have S and B in LHS. 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 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 (73432)?
 A B C D
Compiler-Design       Parsers       Gate 2011
Question 10 Explanation:
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
 A LL(1) but not LR(1) B LR(1) but not LR(1) C Both LL(1) and LR(1) D Neither LL(1) nor LR(1)
Compiler-Design       Parsers       2010
Question 11 Explanation:
The LL(1) parsing table for the given grammar is:

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 statements are TRUE? I.There exist parsing algorithms for some programming languages whose complexities are less than q (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
 A I and II B I and IV C III and IV D I, III and IV
Compiler-Design       Parsers       2009
Question 12 Explanation:
Statement II is false, as a programming language which allows recursion requires dynamic storage allocation. Statement III is false, as L-attributed definition (assume for instance the L-attributed definition has synthesized attribute only) can be evaluated in bottom up framework.
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 13
Which of the following describes a handle (as applicable to LR-parsing) appropriately?
 A It is the position in a sentential form where the next shift or reduce operation will occur. B It is non-terminal whose production will be used for reduction in the next step. C 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. D 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.
Compiler-Design       Parsers       Gate-2008
Question 13 Explanation:
A handle 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 14
Which one of the following is a top-down parser?
 A Recursive descent parser. B Operator precedence parser. C An LR(k) parser. D An LALR(k) parser.
Compiler-Design       Parsers       Gate-2007
Question 14 Explanation:
Recursive descent parser is top down parser, while others are bottom up parser.
 Question 15
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:
 A it is left recursive B it is right recursive C it is ambiguous D it is not context-free
Compiler-Design       Parsers       Gate-2007
Question 15 Explanation:
The given grammar is not left recursive and also it is context free (Type 2 grammar), so option A and D is wrong. Being a right recursive grammar is not an issue for LL(1) grammar. So even if given grammar is right recursive, this is not a reason for NOT LL(1).
This grammar has two parse tree for string “ibt ibt aea”.
 Question 16
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?
 A Both P and Q are true B P is true and Q is false C P is false and Q is true D Both P and Q are false
Compiler-Design       Parsers       Gate-2007
Question 16 Explanation:
Every regular grammar is LL(1) is false, as the grammar may have left recursion or left factoring or also it is possible that grammar is ambiguous.
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 acceptor as DFA , so every regular set must have atleast one grammar which is unambiguous.
Hence, every regular set has LR(1) grammar.
 Question 17
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?
 A (i) and (ii) B (ii) and (iii) C (i) and (iii) D None of the above
Compiler-Design       Parsers       Gate-2006
Question 17 Explanation:
As we can see in the below given LR(0) items, that all three belongs to different state (sets).
 Question 18
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.  A {S → FR} and {R → ε} B {S → FR} and { } C {S → FR} and {R → *S} D {F → id} and {R → ε} Compiler-Design Parsers Gate-2006 Question 18 Explanation: Predictive parsing table for the mentioned grammar: 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 19 The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is:  A ambiguous B left-recursive C right-recursive D an operator-grammar Compiler-Design Parsers Gate-2005 Question 19 Explanation: The given grammar can be turned into a infinite parse tree. So it is ambiguous. It have A → AA has left recursion.  Question 20 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?  A Equal precedence and left associativity; expression is evaluated to 7 B Equal precedence and right associativity; expression is evaluated to 9 C Precedence of '×' is higher than that of '+', and both operators are left associative; expression is evaluated to 7 D Precedence of '+' is higher than that of '×', and both operators are left associative; expression is evaluated to 9 Compiler-Design Parsers Gate-2005 Question 20 Explanation: First of all, it is ambiguous grammar. Hence, equal precedence and associativity. Now as Yacc resolved it with shift move we will shift until the last operator and then we will start reducing. Hence, the answer is 9 and right associative.  Question 21 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  A n1 < n2 < n3 B n1 = n3 < n2 C n1 = n2 = n3 D n1 ≥ n3 ≥ n2 Compiler-Design Parsers Gate-2005 Question 21 Explanation: → SLR(1) and LALR(1) both are be the states of LR(0) items then SLR(1) = LALR(1). → 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 22  A (i) only B (i) and (iii) only C (ii) and (iii) only D (iii) and (iv) only Compiler-Design Parsers Gate-2004 Question 22 Explanation: Operator values doesn't contains nullable values and two adjacent non-terminals on RHS production. i) On RHS it contains two adjacent non-terminals. ii) Have nullable values.  Question 23 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  A n1 is necessarily less than n2 B n1 is necessarily equal to n2 C n1 is necessarily greater than n2 D None of the above Compiler-Design Parsers Gate-2003 Question 23 Explanation: No. of states in SLR and LALR are equal and no. of states in SLR and LALR are less than or equal to LR(1).  Question 24 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
 A {S'→e S} and {S'→ε} B {S'→e S} and { } C {S'→ε} and {S'→ε} D {S'→e S, S'→ε} and {S'→ε}
Compiler-Design       Parsers       Gate-2003
Question 24 Explanation:
First(S) = {1,a}
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 25
Consider the grammar shown below.
S → C C
C → c C | d
The grammar is
 A LL(1) B SLR(1) but not LL(1) C LALR(1) but not SLR(1) D LR(1) but not LALR(1)
Compiler-Design       Parsers       Gate-2003
Question 25 Explanation:

Hence, it is LL(1).
 Question 26
Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.
 A Leftmost derivation B Leftmost derivation traced out in reverse C Rightmost derivation D Rightmost derivation traced out in reverse
Compiler-Design       Parsers       Gate-2000
Question 26 Explanation:
Top-down parser - Leftmost derivation
Bottom-Up parser - Reverse of rightmost derivation
 Question 27
Which of the following is the most powerful parsing method?
 A LL (1) B Canonical LR C SLR D LALR
Compiler-Design       Parsers       Gate-1999
Question 27 Explanation:
Canonical LR is most powerful.
LR > LALR > SLR
 Question 28
Which of the following statements is true?
 A SLR parser is more powerful than LALR B LALR parser is more powerful than Canonical LR parser C Canonical LR parser is more powerful than LALR parser D The parsers SLR, Canonical CR, and LALR have the same power
Compiler-Design       Parsers       Gate-1998
Question 28 Explanation:
LR > LALR > SLR
Canonical LR parser is more powerful than LALR parser.
 Question 29

 A 23131 B 11233 C 11231 D 33211
Compiler-Design       Parsers       Gate-1995
Question 29 Explanation:

⇒ 23131
Note SR is bottom up parser.
 Question 30
Consider the SLR(1) and LALR (1) parsing tables for a context free grammar. Which of the following statements is/are true?
 A The go to part of both tables may be different. B The shift entries are identical in both the tables. C The reduce entries in the tables may be different. D The error entries in the tables may be different. E B, C and D.
Compiler-Design       Parsers       Gate-1992
Question 30 Explanation:
Goto parts and shift entry must be same.
Reduce entry and error entry may be different due to conflicts.
 Question 31
Which of the following statements is false?
 A An unambiguous grammar has same leftmost and rightmost derivation B An LL(1) parser is a top-down parser C LALR is more powerful than SLR D An ambiguous grammar can never be LR(k) for any k
Compiler-Design       Parsers       Gate-2001
Question 31 Explanation:
Option B: LL parser is a top-down parser for a subset of context-free languages. It parses the input from Left to right, performing Left most derivation of the sentence.
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.
 Question 32

 A Theory Explanation is given below.
Compiler-Design       Parsers       Gate-2001
 Question 33

 A Recursive descent parsing cannot be used for grammar with left recursion. B The intermediate form the representing expressions which is best suited for code optimization is the post fix form. C A programming language not supporting either recursion or pointer type does not need the support of dynamic memory allocation. D Although C does not support call by name parameter passing, the effect can be correctly simulated in C. E No feature of Pascal violates strong typing in Pascal. F A and D
Compiler-Design       Parsers       Gate-1991
Question 33 Explanation:
(A) It is true. Left recursive grammar if used directly in recursive descent parsing causes an infinite loop. So, left recursion must be removed before giving to a recursive descent parser.
(B) False.
(C) It is false. The language can have dynamic data types which required dynamically growing memory when data type size increases.
(D) Is true and using macro we can do this.
(E) Out of syllabus now.
 Question 34
Merging states with a common core may produce __________ conflicts and does not produce ___________ conflicts in an LALR purser.
 A Reduce-Reduce, Shift-Reduce
Compiler-Design       Parsers       Gate-1989
Question 34 Explanation:
Merge states with a common core may produce Reduce-Reduce conflicts and does not produce Shift-Reduce conflicts in an LALR parser.
 Question 35
An operator precedence parser is a
 A Bottom-up parser. B Top-down parser. C Back tracking parser. D None of the above.
Compiler-Design       Parsers       GATE-1987
Question 35 Explanation:
An operator precedence parser is a Bottom-up parser.
There are 35 questions to complete.