Parsers
Question 1 
Consider the following grammar.
S → aSBd B → b
The number of reduction steps taken by a bottomup parser while accepting the string aaadbbb is _______.
7 
7 reductions total.
Question 2 
The LALR (1) parser for a grammar G cannot have reducereduce conflict if the LR (1) parser for G does not have reducereduce conflict.  
Symbol table is accessed only during the lexical analysis phase.  
Data flow analysis is necessary for runtime memory management.  
LR (1) parsing is sufficient for deterministic contextfree languages. 
Symbol table is accessed in all the phases of compiler and not only in lexical analysis phase.
Data flow analysis is done in the control flow graph, in the code optimization phase. If LR(1) parses a grammar then definitely it is DCFL, so LR(1) parsing is sufficient for deterministic contextfree languages.
Question 3 
5 
Question 4 
80 
Question 5 
Which of the following statements is true?
SLR parser is more powerful than LALR  
LALR parser is more powerful than Canonical LR parser  
Canonical LR parser is more powerful than LALR parser  
The parsers SLR, Canonical CR, and LALR have the same power 
Canonical LR parser is more powerful than LALR parser.
Question 6 
Which of the following is the most powerful parsing method?
LL (1)  
Canonical LR  
SLR  
LALR 
LR > LALR > SLR
Question 7 
Which of the following derivations does a topdown parser use while parsing an input string? The input is assumed to be scanned in left to right order.
Leftmost derivation  
Leftmost derivation traced out in reverse  
Rightmost derivation  
Rightmost derivation traced out in reverse 
BottomUp parser  Reverse of rightmost derivation
Question 8 
Assume that the SLR parser for a grammar G has n_{1} states and the LALR parser for G has n_{2} states. The relationship between n_{1} and n_{2} is:
n_{1} is necessarily less than n_{2}  
n_{1} is necessarily equal to n_{2}
 
n_{1} is necessarily greater than n_{2}
 
None of the above 
Question 9 
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 10 
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 11 
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 nonterminals.
ii) Have nullable values.
Question 12 
The grammar A → AA  (A)  ε is not suitable for predictiveparsing because the grammar is:
ambiguous  
leftrecursive  
rightrecursive  
an operatorgrammar 
It have A → AA has left recursion.
Question 13 
Consider the grammar:
S → (S)  a
Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n_{1}, n_{2} and n_{3} respectively. The following relationship holds good:
n_{1} < n_{2} < n_{3}  
n_{1} = n_{3} < n_{2}  
n_{1} = n_{2} = n_{3}  
n_{1} ≥ n_{3} ≥ n_{2} 
→ 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)
n_{1} = (n_{3}) < (n_{2})
Question 14 
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 15 
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 setsofitems for the grammar?
(i) and (ii)  
(ii) and (iii)  
(i) and (iii)  
None of the above 
Question 16 
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 17 
A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar
S → xxW {print "1"} S → y {print "2"} W → Sz {print "3"}
What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?
23131  
11233  
11231  
33211 
⇒ 23131
Note SR is bottom up parser.
Question 18 
S’ ⟶ S
S ⟶ S#cS
S ⟶ SS
S ⟶ S@
S ⟶ < S >
S ⟶ a
S ⟶ b
S ⟶ c
Let I_{0}=CLOSURE({S' ⟶.S}). The number of items in the set GOTO(GOTO(I0, <), <) is ____________.
8 
Question 19 
S_{1}:Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).
S_{2}: For any contextfree grammar, there is a parser that takes at most O(n^{3} )
Which one of the following options is correct?
S_{1}is true and S_{2}is true
 
S_{1}is true and S_{2}is false  
S_{1}is false and S_{2}is true  
S_{1}is false and S_{2}is false 
Every unambiguous grammar need not be SLR(1). As we know some unambiguous grammar which is CLR(1) but not SLR(1). So S1 is true.
Any CFG (which is in CNF form) can be parsed by CYK algorithm in O(n^{3}) where n is length of string. Although it is not given that CFG is in CNF form but since we can convert any CFG in CNF form so S2 is true
Question 20 
Which one of the following choices represents the correct combination for the numbered cells in the parsing table (“blank” denotes that the corresponding cell is empty)?
① S ⟶ Rf ② S ⟶ Rf ③ T ⟶ ∊ ④ T ⟶ ∊
 
① blank ② S ⟶ Rf ③ T ⟶ ∊ ④ T ⟶ ∊  
① S ⟶ Rf ② blank ③ blank ④ T ⟶ ∊  
① blank ② S ⟶ Rf ③ blank ④ blank 
Question 21 
An operator precedence parser is a
Bottomup parser.  
Topdown parser.  
Back tracking parser.  
None of the above. 
Question 22 
Merging states with a common core may produce __________ conflicts and does not produce ___________ conflicts in an LALR purser.
ReduceReduce, ShiftReduce 
Question 23 
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Indicate all the true statements from the following:
Recursive descent parsing cannot be used for grammar with left recursion.  
The intermediate form the representing expressions which is best suited for code optimization is the post fix form.  
A programming language not supporting either recursion or pointer type does not need the support of dynamic memory allocation.  
Although C does not support call by name parameter passing, the effect can be correctly simulated in C.
 
No feature of Pascal violates strong typing in Pascal.  
A and D 
(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 24 
The go to part of both tables may be different.  
The shift entries are identical in both tables.  
The reduce entries in the tables may be different.  
The error entries in the tables may be different. 
Reduce entry and error entry may be different due to conflicts.
Question 25 
Which one of the following is a topdown parser?
Recursive descent parser.  
Operator precedence parser.  
An LR(k) parser.
 
An LALR(k) parser. 
Question 26 
Consider the grammar with nonterminals N = {S,C,S_{1}},terminals T = {a,b,i,t,e}, with S as the start symbol, and the following set of rules:
S > iCtSS_{1}a S_{1} > eSϵ C > b
The grammar is NOT LL(1) because:
it is left recursive  
it is right recursive  
it is ambiguous  
it is not contextfree 
This grammar has two parse tree for string “ibt ibt aea”.
Question 27 
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 28 
Which of the following describes a handle (as applicable to LRparsing) appropriately?
It is the position in a sentential form where the next shift or reduce operation will occur.
 
It is nonterminal 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 29 
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.