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 nonterminal 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 I_{0} = CLOSURE ({[S' → ·S]}). The number of items in the set GOTO (I_{0} , 〈 ) is: _____.
4  
5  
6  
7 
Hence, the set GOTO (I_{0} , 〈 ) has 5 items.
Question 4 
stmt → if expr then expr else expr; stmt  ȯ
expr → term relop term  term
term → id  number
id → a  b  c
number → [09]
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 e_{1} then e_{2} else e_{3} has 2 control flow paths, e_{1} → e_{2} and e_{1} → e_{3}.
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 = 2^{10} = 1024
Question 5 
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 6 
Which one of the following is True at any valid state in shiftreduce 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 7 
Among simple LR (SLR), canonical LR, and lookahead 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 8 
Consider the following grammar G.
S → F ⎪ H F → p ⎪ c H → d ⎪ c
Where S, F and H are nonterminal 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 RR 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 shiftreduce conflict and a reducereduce conflict.  
a shiftreduce conflict but not a reducereduce conflict.  
a reducereduce conflict but not a shiftreduce conflict.  
neither a shiftreduce nor a reducereduce conflict. 
But if it would have asked about “>” then it will be a SR conflict.
Question 10 
What is the maximum number of reduce moves that can be taken by a bottomup parser for a grammar with no epsilon and unitproduction (i.e., of type A → є and A → a) to parse a string with n tokens?
n/2  
n1  
2n1  
2^{n} 
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 bottomup 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 unitproduction (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 11 
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 nonterminals 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 12 
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 13 
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 14 
The grammar S → aSabSc 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 15 
Which of the following statements are TRUE?

I.There exist parsing algorithms for some programming languages whose complexities are less than θ(n^{3}).
II.A programming language which allows recursion can be implemented with static storage.
III.No Lattributed definition can be evaluated in the framework of bottomup 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 16 
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 17 
Which one of the following is a topdown parser?
Recursive descent parser.  
Operator precedence parser.  
An LR(k) parser.
 
An LALR(k) parser. 
Question 18 
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 19 
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 20 
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 21 
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 22 
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 23 
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 24 
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 25 
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 26 
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 27 
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 28 
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 29 
Which of the following statements is false?
An unambiguous grammar has same leftmost and rightmost derivation  
An LL(1) parser is a topdown 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.
Question 30 
Consider the following grammar with terminal alphabet ∑{a,(,),+,*} and start symbol E. The production rules of the grammar are:
E → aA E → (E) A → +E A → *E A → ε
(a) Compute the FIRST and FOLLOW sets for E and A.
(b) Complete the LL(1) parse table for the grammar.
Theory Explanation is given below. 
Question 31 
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 32 
Which of the following is the most powerful parsing method?
LL (1)  
Canonical LR  
SLR  
LALR 
LR > LALR > SLR
Question 33 
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 34 
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 35 
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 36 
Consider the SLR(1) and LALR (1) parsing tables for a context free grammar. Which of the following statements is/are true?
The go to part of both tables may be different.  
The shift entries are identical in both the tables.  
The reduce entries in the tables may be different.  
The error entries in the tables may be different.  
B, C and D. 
Reduce entry and error entry may be different due to conflicts.
Question 37 
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 38 
Merging states with a common core may produce __________ conflicts and does not produce ___________ conflicts in an LALR purser.
ReduceReduce, ShiftReduce 
Question 39 
An operator precedence parser is a
Bottomup parser.  
Topdown parser.  
Back tracking parser.  
None of the above. 
Question 40 
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 41 
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 42 
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 43 
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 44 
5 
Question 45 
80 
Question 46 
Topdown parsers  
Bottomup parsers  
Predictive parsers  
None of the above 
→ Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.
Question 47 
Rightmost Derivation  
Rightmost derivation in reverse  
Leftmost derivation  
Leftmost derivation in reverse 
→ The inclusive choice is used to accommodate ambiguity by expanding all alternative righthandsides of grammar rules.
Question 48 
bottom up parsing  
top down parsing  
recursive parsing  
predictive parsing 
→ The parsing methods most commonly used for parsing programming languages, LR parsing and its variations, are shiftreduce methods.
Question 49 
S → Aa  b
A → Ac  Sd  ε
S → Aa  b A → bdA’ A’ → A’c  A’ba  A  ε  
S → Aa  b A → A’  bdA’, A’ → cA’  adA’  ε  
S → Aa  b A → A’c  A’d A’ → bdA’  cA  ε  
S → Aa  b A → cA’  adA’  bdA’ A’ → A  ε 
Question 50 
SLR parsing table  
Canonical LR parsing table  
LALR parsing table  
None of these 
● It is a Look Ahead LefttoRight (LALR) parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specifically a LALR parser, based on an analytic grammar written in a notation similar to Backus–Naur Form (BNF)
Question 51 
n/2  
n1  
2n1  
2^{n} 
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 bottomup parsing where strings are parsed finding the rightmost derivation of a given string backwards. So here we are concentrating on deriving rightmost derivations only.
We can write the grammar which accepts this string which in accordance to the question, (i.e., with no epsilon and unitproduction (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 52 
The grammar S ⟶ (S)  SS  ∈ is not suitable for predictive parsing because the grammar is
An Operator Grammar
 
Right Recursive
 
Left Recursive  
Ambiguous

Question 53 
Consider the following Grammar G :
S➝ A  B A➝ a  c B➝ b  c
Where {S,A,B} is the set of nonterminals, {a,b,c} is the set of terminals.
Which of the following statement(s) is/are correct ?
 S_{1} : LR(1) can parse all strings that are generated using grammar G.
S_{2} : LL(1) can parse all strings that are generated using grammar G.
Choose the correct answer from the code given below :
Code :Both S_{1} and S_{2}
 
Only S_{2}
 
Neither S_{1} nor S_{2}
 
Only S_{1}

Since the grammar is Ambiguous so the strings generated by the grammar G can’t be parsed by LR(1) or LL(1) parser.
Question 54 
1 only  
1 and 2 only  
1 and 3 only  
1 and 4 only 
i) On RHS it contains two adjacent nonterminals.
ii) Have nullable values.
Question 55 
Recursive descent parser  
Shift left associative parser  
SLR(k) parser  
LR(k) parser 
Question 56 
yet accept compiler constructs  
yet accept compiler compiler  
yet another compiler construct  
yet another compiler compiler 
→ It is a Look Ahead LefttoRight (LALR) parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specifically a LALR parser, based on an analytic grammar written in a notation similar to BackusNaur Form (BNF)
Question 57 
LALR parser is more powerful and costly as compare to other parsers  
All CFG’s are LP and not all grammars are uniquely defined  
Every SLR grammar is unambiguous but not every unambiguous grammar is SLR  
LR(K) is the most general backtracking shift reduce parsing method 
OptionA: LR > LALR > SLR
Canonical LR parser is more powerful than LALR parser. So, it FALSE
OptionB: Here, LP is linear precedence. Every grammar generated by LP are CFG but all CFG's are not LP. So, it is false
OptionC: TRUE
OptionD: LR(K) is general non backtracking shift reduce parsing method. So, It is false
Question 58 
With respect to compiler design, "recursive descent" is a ____ parsing technique that reads the inputs from ____.
topdown, right to left
 
topdown, left to right
 
bottom up, right to left  
bottom up, left to right

→ Top down parsers reads the input from left to right and bottom up parsers are reads the input from left to right and reverse.
Question 59 
Which of the following is NOT a bottom up, shift reduce parser?
LR parser
 
LL parser  
SLR parser
 
LALR parser

1. SLR
2. LALR
3. CLR
4. LR(0)
Top Down parser:
1. Recursive descent
2. Non Recursive descent(LL(1))
Question 60 
Which of the following phases of the compilation process is also known as parsing?
Lexical analysis
 
Code optimization
 
Syntax analysis
 
Semantic analysis

Question 61 
if FIRST(u) ∩ FIRST(v) is empty then the CFG has to be LL(1)  
If the CFG is LL(1) then FIRST(u) ∩ FIRST(v) has to be empty  
Both (A) and (B)  
None of the above 
Theorem: A context free grammar G=(V _{T} , V_{ N} , S,P) is LL(1) if and if only if for every nonterminal A and every strings of symbols ⍺,β such that ⍺≠β and A → ⍺,β we have
1. First(⍺) ∩ First (β) ∩ Follow(A)=Θ.
2. If ⍺ *⇒ ε then First(β) ∩ Follow(A)= Θ.
If grammar is epsilon free then condition 2 is not required.
Now as per condition 1, for every nonterminal A, if we have A → u and A→v
And First(u) First(v) = φ and CFG is epsilon free then it must be LL(1) and if epsilon free CFG is LL(1) then it must satisfy the condition 1.
Question 62 
The grammar S → a Sb bSaSS∈, where S is the only nonterminal symbol and ∈ is the null string, is ambiguous.  
SLR is powerful than LALR.  
An LL(1) parser is a topdown parser.  
YACC tool is an LALR(1) parser generator. 
In this grammar we are having two different parse trees For string "aabb" using leftmost derivation only.
Statement B is wrong because in LALR we use lookahead symbols to put the reduce entries into the parsing table. Because of which number of blank entries in LALR parser are more than that of SLR parser which in turn increases the error detection capability of LALR parser. So LALR parser is more powerful than SLR.
Statement C is true because LL(1) parser is a topdown parser
Statement D is also true because YACC(Yet Another Compiler Compiler) is a tool which generates LALR parser for a given grammar.
Question 63 
Topdown parsers are LL parsers where first L stands for left  to  right scan and second L stands for a leftmost derivation.  
(000)* is a regular expression that matches only strings containing an odd number of zeroes, including the empty string.  
Bottomup parsers are in the LR family, where L stands for left  to  right scan and R stands for rightmost derivation.  
The class of context  free languages is closed under reversal. That is, if L is any context free language, then the language L R = {w R : w∈L} is context  free. 
FALSE: (000)* is a regular expression that matches any string containing at least 3 number of zeroes, including the empty string.
TRUE: Bottomup parsers are in the LR family, where L stands for left  to  right scan and R stands for rightmost derivation.
TRUE: The class of context  free languages is closed under reversal. That is, if L is any context  free language, then the language L ^{R} = {w^{ R} : w∈L} is context  free.
Question 64 
LALR parser is Bottom up parser  
A parsing algorithm which performs a left to right scanning and a right most deviation is RL (1)  
LR parser is Bottom up parser.  
In LL(1), the 1 indicates that there is a one  symbol look  ahead. 
TRUE: LR parser is Bottom up parser. It has SLR, LALR and SLR.
TRUE: In LL(1), the 1 indicates that there is a one  symbol look  ahead.
FALSE: A parsing algorithms scans right to left and reverse order.
Question 65 
Leftmost derivation  
Rightmost derivation  
Rightmost derivation in reverse  
Leftmost derivation in reverse 
→ Inclusive choice is used to accommodate ambiguity by expanding all alternative righthandsides of grammar rules.
Question 66 
0  
1  
2  
None of these 
→ Typically k is 1 and is not mentioned. The name LR is often preceded by other qualifiers, as in SLR and LALR. The LR(k) condition for a grammar was suggested by Knuth to stand for "translatable from left to right with bound k."
Question 67 
LALR  
LR  
SLR  
LLR 
It is a Look Ahead LefttoRight (LALR) parser generator, generating a parser, the part of a compiler that tries to make syntactic sense of the source code, specifically a LALR parser, based on an analytic grammar written in a notation similar to Backus–Naur Form (BNF).
**YACC builds up LALR parsing table.
Question 68 
Syntax analysis  
Lexical analysis  
Interpretation analysis  
Uniform symbol generation 
Question 69 
Shift step that advances in the input stream by K(K > 1) symbols and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.  
Shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.  
Shift step that advances in the input stream by K(K = 2) symbols and Reduce step that applies a completed grammar rule to form a single tree.  
Shift step that does not advance in the input stream and Reduce step that applies a completed grammar rule to form a single tree. 
Question 70 
Canonical LR parser is LR (1) parser with single look ahead terminal  
All LR(K) parsers with K > 1 can be transformed into LR(1) parsers.  
Both (A) and (B)  
None of the above 
TRUE: All LR(K) parsers with K > 1 can be transformed into LR(1) parsers.
Question 71 
 First (α) ∩ First (β) ≠ {a} where a is some terminal symbol of the grammar.
 First (α) ∩ First (β) ≠ λ
I and II  
I and III  
II and III  
I, II and III 
A → α  β
1. First (α) and First (β) must be disjoint if none of α and β contains NULL move.
2. At most one of the strings α or β can drive NULL move i.e. α → NULL(since First (α) and First (β) are disjoint). In this case, First (β) and Follow(A) must be disjoint.
Hence the answer is option(D).
Question 72 
Removing left recursion alone  
Removing the grammar alone  
Removing left recursion and factoring the grammar  
None of the above 
→ To convert an arbitrary CFG to an LL(1) grammar we need to remove the left recursion and as well as left factoring without that we cannot convert.
Question 73 
shift reduce conflict only  
reduce reduce conflict only  
both shift reduce conflict and reduce reduce conflict  
shift handle and reduce handle conflicts 
A shiftreduce parser works by doing some combination of Shift steps and Reduce steps, hence the name.
→ A Shift step advances in the input stream by one symbol. That shifted symbol becomes a new singlenode parse tree.
→ A Reduce step applies a completed grammar rule to some of the recent parse trees, joining them together as one tree with a new root symbol.
*** A shift reduce parser suffers from both shift reduce conflict and reduce reduce conflict.
Question 74 
An Operator Grammar  
Right Recursive  
Left Recursive  
Ambiguous 
Question 75 
S ➝ A  B
A➝ a  c
B➝ b  c
Where {S,A,B} is the set of nonterminals, {a,b,c} is the set of terminals.
Which of the following statement(s) is/are correct ?
S 1 : LR(1) can parse all strings that are generated using grammar G.
S 2 : LL(1) can parse all strings that are generated using grammar G.
Both S 1 and S 2  
Only S 2  
Neither S 1 nor S 2  
Only S 1 
Since the grammar is Ambiguous so the strings generated by the grammar G can’t be parsed by LR(1) or LL(1) parser.
Question 76 
Leftmost derivation in reverse  
Rightmost derivation in reverse  
Leftmost derivation  
Rightmost derivation 
Question 77 
Remove left recursion alone  
Factoring grammar alone  
Both of the above  
None of the above 
→ Since for converting a grammar to LL(1) 3 conditions mentioned above are required.
→ Unambiguous grammar is not mentioned in options. So option (D) is the correct.
Question 78 
LL(I)  
Canonical LR  
SLR  
LALR 
LR > LALR > SLR.
But real time compilers using LALR only
Question 79 
S1: SLR uses follow information to guide reductions. In case of LR and LALR parsers, the lookaheads are associated with the items and they make use of the left context available to the parser.
S2: LR grammar is a larger subclass of context free grammar as compared to that SLR and LALR grammars.
Which of the following is true ?
S1 is not correct and S2 is not correct.  
S1 is not correct and S2 is correct.  
S1 is correct and S2 is not correct.  
S1 is correct and S2 is correct. 
Question 80 
Leftmost derivation  
Leftmost derivation traced out in reverse  
Rightmost derivation traced out in reverse  
Rightmost derivation 
→ Bottom up parsers using rightmost derivation in reverse.
Question 81 
S1 : First(α) = { t  α⇒ *tβ for some string β}⇒ *tβ
S2 : Follow(X) = { a  S⇒ *αXaβ for some strings α and β}
Both statements S1 and S2 are incorrect.  
S1 is incorrect and S2 is correct.  
S1 is correct and S2 is incorrect.  
Both statements S1 and S2 are correct. 
→ So if alpha after some step has t as first symbol (terminal) in some sentential form , then first(alpha) must be {t}
Statement2:
α→∗tβ Here First(α) = {*} .
S→∗αXaβ
Follow(X) = {a}
So Statement S2 is correct.
Question 82 
(A + B) * C  
A + * BC  
A + B * C  
A * C + B 
Question 83 
A → a A b, A → b A b, A → a , A →b  
A → a A a, A → a A b, A → c  
A → A + A, A → a  
Both (A) and (B) 
Option(A):
Since here we are having no Reducereduce OR shiftreduce conflict so it is CLR(1).
Question 84 
tokens are identified.  
set of instructions are identified.
 
the syntactic groups are identified.  
machine instructions are identified 
1. tokens are identified
2. whether the given code is syntactically correct or not is identified.
Question 85 
it shows attribute values at each node.  
there are no inherited attributes.  
it has synthesized nodes as terminal nodes.  
every nonterminal nodes is an inherited attribute. 
Features:
1. High level specification
2. Hides implementation details
3. Explicit order of evaluation is not specified
Question 86 
next tokens are predicted.  
length of the parse tree is predicted beforehand  
lowest node in the parse tree is predicted.  
next lower level of the parse tree is predicted. 
→ Predictive parser is a recursive descent parser, which has the capability to predict which production is to be used to replace the input string.
→ The predictive parser does not suffer from backtracking.
→ Predictive parsing uses a stack and a parsing table to parse the input and generate a parse tree.
Question 87 
Top  down parsing  
Recursive  descent parsing  
Predicative  
Syntax tree 
→ Predictive parser is a recursive descent parser, which has the capability to predict which production is to be used to replace the input string.
→ The predictive parser does not suffer from backtracking.
→ Predictive parsing uses a stack and a parsing table to parse the input and generate a parse tree.
Question 88 
Rightmost derivation.  
Rightmost derivation, in reverse.  
Leftmost derivation.  
Leftmost derivation in reverse. 
→ A bottom up parser generates rightmost derivation, in reverse.
Question 89 
(a) input buffer
(b) stack
(c) parse table
choose the correct option from those given below:
(a) and (b) only  
(a) and (c) only  
(c) only  
(a), (b) and (c) 
(a) input buffer
(b) stack
(c) parse table
Question 90 
Which of the following is/are FALSE?
I) Operator precedence parser works on ambiguous grammar
II) Topdown parser works on left recursive, unambiguous and deterministic grammar
III) LL(I) is a nonrecursive descent parser
IV) CLR(I) is the most powerful parser
Only II  
I, II, III and IV  
ll and IV  
I, III and IV 
II) FALSE: Topdown parser works on left recursive, unambiguous and deterministic grammar
Ill) TRUE: LL(I) is a nonrecursive descent parser
IV) TRUE: CLR(I) is the most powerful parser
Question 91 
E>TE’
E’>+TE’/ε
T>FT’
T’>*FT’/ε
F>id/(E)
First(E)={id, (,ε},follow(E)={ε,) }, First(F)={id,),$}, Follow(F)={*,$,(}  
First(E)={id, ( },follow(E)={$,) }, First(F)={id,(}, Follow(F)={*,$,),+}  
First(E)={id, (,ε},follow(E)={ε,) }, First(F)={id,)}, Follow(F)={*,$,(,+ }  
First(E)={id, )},follow(E)={$,) }, First(F)={id,(,$}, Follow(F)={*,$,),+} 
First (∊) = { id, ( }
Follow (∊) = { $, ) }
First (F) = { id, ( }
Follow (F) = { *, +, $, ) }
Question 92 
Which of the following statements is TRUE for the grammar given below?
S>(L)/a
L>L.S/S
The grammar can be parsed by LR(0) parser only  
The grammar can be parsed by LR(0) and SLR(1) parsers
 
The grammar can be parsed by LL(1) parser only  
The grammar can be parsed by LL(1) and LR(0) parsers 
Question 93 
The number of tokens in the following
“C” language statement is:
printf(“The number of tokens are %d”, &tcount);
8  
9  
10  
11 
Question 94 
s→ T*S  T
T → U + T  U
U → a  b
Which of the following statements is wrong?
Grammar is not ambiguous  
Priority of + over * is ensured  
Right to left evaluation of * and + happens  
None of these 
S> T*S , since S has right recursion so * is right associative
T> U+T , since T has right recursion so + is right associative
Hence right to left evaluation of * and + will happen.
+ is having more precedence than * so the precedence of + and * is clearly defined.
Question 95 
It is left recursive  
It is right recursive  
It is ambiguous  
It is not contextfree 
Question 96 
a  b  $  
S  E1  E2  S>ε 
A  A>S  A>S  error 
B  B>S  B>S  E3 
FIST(A)=(a,b,$)
FIRST(A)={A,B} FIRST(B) = {a,b,ε}
FOLLOW(A)={A,B} FOLLOW(A) = {A,b}
FOLLOW(B)={A,b,$) FOLLOW(B) = {$}
FIRST(B) = {a,b,ε}
FOLLOW(A) = {A,b}
 
FOLLOW(B) = {$}
 
FIRST(A) = {a,b,ε} = FIRST(B)  
FIRST(A) = {A,B} = FIRST(B)
FOLLOW(A)={a,b} FOLLOW(A)={a,b} 
Question 97 
Recursive descent parser.  
Operator precedence parser.  
An LR(k) parser.  
An LALR(k) parser 
Question 98 
Viable preflxes 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 
Question 99 
Consider the following grammar
S → m  mn  mnoChoose correct statement from the following:
The grammar is LL(4)
 
The grammar is LL(3)  
The grammar is LL(2)  
The grammar is LL(1)

Intersection of second() of second and third production of S is ‘n’ which is not equal to {empty}, so not LL(2).
Intersection of third() of any two production of S is equal to {empty}, so yes LL(3).
Question 100 
Which of the following derivations does a topdown parser use while parsing a input string?
The input is assumed to be scanned in left to right order.
Topmost derivation  
Leftmost derivation traced out in reverse
 
Leftmost derivation  
Rightmost derivation

Question 101 
Which of the following statement is true?
The parsers canonical LR and LALR have the same power
 
LALR parser is more important than canonical LR parser
 
SLR parser is more powerful than LALR parser
 
Canonical LR parser is more powerful than LALR parser

CLR > LALR > SLR
Question 102 
Which grammar rules violate the requirement of the operator grammar? A,B,C are variables and a,b,c are terminals.
I. A → BC II. A → CcBb III. A → BaC IV. A → ε
I only
 
I and II
 
I and III  
I and IV

(I) violates the operator grammar condition as it contains two adjacent non terminals on LHS.
(IV) violates the operator grammar condition as it contains epsilon.
Question 103 
Write true (T) / false (F) for each of the following statements:
A. Symbol table is used only in the first phase of a compiler.
B. A pretty printer analyses a program and prints it in such a way that the structure of the program becomes early visible.
C. YACC build up LALR parsing table
D. If a grammar is LALR(1), it is not necessarily SLR(1)
T T F T
 
F T T T  
T T T F
 
F T T F 
B True.
C True, YACC is a tool to build the LALR parsing table.
D True. If a grammar is LALR(1), it is not necessarily SLR(1). Below diagram is the parsers according to their powers and it justifies the given statement.
Question 104 
The following grammar is:
S → Aa  bAc  Bc  bBa A → d B → d
Not LR(1) but LALR(1)  
Neither LR(1) nor LALR(1)  
LR(1) and LALR(1)
 
LR(1) but not LALR(1)

Since there is no RR or SR conflict hence the given grammar is LR(1).
Now, for LALR(1) let’s combine I_{1} & I_{3},
Since there is RR conflict in state I13, hence not LALR(1).
Question 105 
Consider the grammar
S > AbBaCc ε A > aAb  ba B > bBC  cb C > cCa  acFind the first() of S
{a, b, ε}  
{ε}  
{a,ε}  
{a,b,c,ε}

First(A) = {a,b}
∴ First(S) = {a,b} ∪ {∊}
= {a,b,∊}
Question 106 
The following grammar is:
S → Aa  b Ac  dc  bda A → a
Neither LALR(1) nor SLR(1)
 
LALR(1) but not SLR(1)
 
Not LALR(1) but SLR(1)
 
LALR(1) and SLR(1)

No SR or RR conflict, hence SLR(1).
Every SLR(1) grammar is LALR(1).
Hence given grammar is also LALR(1).
Question 107 
An unambiguous grammar has the same leftmost and rightmost derivation  
An LL(1) parser is a topdown parser  
LALR is more powerful than SLR  
An unambiguous grammar can never be LR(k) for any k 
4 is false because the correct statement is an ambiguous grammar can never be LR(K) for any k.
Question 108 
Leftmost Derivation  
Leftmost Derivation traced out in reverse  
Rightmost Derivation  
Rightmost Derivation traced out in reverse 
Question 109 
Ambiguous  
Left  Recursive  
Right Recursive  
An operator grammar 
Since for the given string two parse trees are possible. So the given grammar is ambiguous.
Question 110 
S→AS/b A→SA / a then Closure (S'→.S,$) is:
S^{1}→.S,$ S→.AS,$ / a/b S→.b,$/a/b A→.SA, a/b A→.a,a /b  
S^{1}→.S,$ S→.AS,$ s/ b S→.b,$ / b  
S^{1}→.S,$ S→.AS,$ / a/b S→.AS,$ / a/b S→.b,$ / a/b  
S^{1}→.S,$ S→.AS,$ S→.b,$ 
S → ASb
A → SAa
Now closure for S →.S, $,
S’ → .S, $
S → .AS.b, $
A → .SA.a, ab
S → .AS.b, ab
⇓
S → .S, $
S → .AS.b, $ab
A → .SA.a, ab
Question 111 
Assume that * has higher precedence than +, − and operators associate right to left (i.e. a + b + c =(a + (b + c))). Consider
(i) 2 + a − b
(ii) 2 + a − b ∗ a + b
(iii) (2 + ((a − b) ∗ (a + b)))
(iv) 2 + (a − b) ∗ (a + b)
The parse tree corresponds to
Expression (i)  
Expression (ii)  
Expression (iv) only  
Expression (ii), (iii) and (iv)  
Expressions (iii) and (iv) only 
Question 112 
The input string is alternately scanned left to right and right to left with k reversals.  
Input string is scanned once Left to Right with rightmost derivation and k symbol lookahead  
LR(k) grammers are expressively as powerful as contextfree grammers.  
Parser makes k lefttoright passes over input string  
Input string is scanned from left to right once with k symbol to the right as lookahead to give leftmost
derivation. 
Question 113 
Reverse of the Right Most Derivation  
Right Most Derivation  
Left Most Derivation  
None of the options 
It is a bottom up parsing technique.
Question 114 
Both same in power  
Both simulate reverse of rightmost derivation  
Both simulate reverse of left most derivation  
Incomparable 
LL(0) is a Bottom up parser that parses the reverse of rightmost derivation.
Question 115 
Shiftreduce conflict  
ShiftShift conflict  
Both Shiftreduce conflict & ShiftShift conflict  
None of the options 
Question 116 
n1 is necessarily less than n2  
n1 is necessarily equal to n2  
n1 is necessarily greater than n2  
none of the options 