Compiler Design GATE PYQ 1992-2007 (Q 2.1 to 2.24) With Detailed Solutions
Q 2.1 [GATE 1992 : 2 Marks] SLR(1) vs LALR(1) Parsing Table
Question: Consider the SLR(1) and LALR(1) parsing tables for a context free grammar. Which of the following statements is/are true?
(a) The goto 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.
Answer: (b), (c), (d)
Solution: SLR and LALR both use same LR(0) automaton, so GOTO part is same. Shift entries are identical. But due to lookahead merging in LALR, reduce and error entries may differ.
Q 2.2 [GATE 1995 : 2 Marks] SDT Translation
Question: 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 translation of xxxxyzz? using the
(syntax directed transalation scheme described by the above rule? a) 23131 (b) 11233 (c) 32131 (d) 33211
Answer: (a) 23131
Solution: Bottom-up: y->S prints 2, then S+z->W prints 3, then xxW->S prints 1. So sequence 2 3 1 3 1.
2.3 [1996 : 1 Mark] – Two Pass Assembler Pass Numbers
Question: The pass numbers for each of the following activities (i) object code generation (ii) literals added to literal table (iii) listing printed (iv) address resolution of local symbols that occur in a two pass assembler respectively are
(a) 1,2,1,2 (b) 2,1,2,1 (c) 2,1,1,2 (d) 1,2,2,2
Answer: (b) 2, 1, 2, 1
Detailed Solution:(ii) Literals added to literal table -> Pass 1
(iv) Address resolution of local symbols -> Pass 1
(i) Object code generation -> Pass 2
(iii) Listing printed -> Pass 2
So order (i)(ii)(iii)(iv) = 2,1,2,1
2.4 [1998 : 1 Mark] – Which Parser is More Powerful
Which of the following statements is true?
(a) SLR parser is more powerful than LALR
(b) LALR parser is more powerful than Canonical LR
(c) Canonical LR parser is more powerful than LALR parser
(d) Parsers SLR, Canonical LR, and LALR have same power
Answer: (c) Canonical LR parser is more powerful than LALR parser
Detailed Solution: Power hierarchy: Canonical LR(1) > LALR(1) > SLR(1) > LR(0)
Isliye Canonical LR, LALR se zyada powerful hai.
2.5 [2001 : 1 Mark] – Relocation Process
The process of assigning load addresses to the various parts of the program and adjusting the code and data in the program to reflect the assigned addresses is called
(a) Assembly (b) Parsing (c) Relocation (d) Symbol resolution
Answer: (c) RelocationDetailed
Solution: Jab program ko memory mein load kiya jata hai, loader usko actual load addresses deta hai aur sare address references ko adjust karta hai – is process ko Relocation kehte hain.
2.6 [2001: 1 Mark] – Top-Down Parser vs LR Parser
Question: 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
Answer: (a)
Solution Option (a) galat hai. Unambiguous grammar me leftmost aur rightmost derivation alag-alag hote hain, lekin unka parse tree same hota hai. Same derivation nahi hota. Baaki (b), (c), (d) teeno statements sahi hain. LL(1) top-down hota hai aur LALR, SLR se jyada powerful hota hai.
2.7 [2001: 1 Mark] – LL(1) Conversion
Question: Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
(a) Removing left recursion alone
(b) Factoring the grammar alone
(c) Removing left recursion and factoring the grammar
(d) None of the above
Answer: (d) None of the above
Solution: Sirf left recursion hatane aur factoring karne se koi bhi CFG, LL(1) nahi ban jati. Kai grammars aise hote hain jo in dono steps ke baad bhi LL(1) ke rules ko satisfy nahi karte. Isliye correct answer None of the above hai.
Answer: (d) None of the above
Solution (Apne shabdon me): Sirf left recursion hatane aur factoring karne se koi bhi CFG, LL(1) nahi ban jati. Kai grammars aise hote hain jo in dono steps ke baad bhi LL(1) ke rules ko satisfy nahi karte. Isliye correct answer None of the above hai.
2.8 [2003: 1 Mark] – SLR vs LALR States
Question: 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
Answer: (b) n1 is necessarily equal to n2
Solution (Apne shabdon me): SLR aur LALR dono LR(0) items se hi bante hain. Farak sirf lookahead ka hota hai. LALR me LR(1) states ko merge kiya jata hai jisse states ki sankhya SLR ke barabar hi reh jati hai. Isliye n1 = n2 hota hai.
2.9 [2003: 2 Marks] – Predictive Parse Table (Dangling Else)
Question: 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’ -> ε}
Answer: (d)
Solution (Apne shabdon me): Ye dangling-else wali grammar hai. S’ ke liye FIRST(e S) = e hai aur FOLLOW(S’) me e aur $ dono aate hain. Isliye M[S’, e] me do entries aayengi – e S wali aur epsilon wali, aur M[S’, $] me sirf epsilon wali entry aayegi.
Q 2.10 [2003: 2 Marks] – LL(1) vs SLR(1)
Question: Consider the grammar shown below.
S -> C C
C -> c C | d
This 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)
Answer: (b) SLR(1) but not LL(1)
Detailed Solution (Apne shabdon me): Ye grammar LL(1) nahi hai kyunki C ke liye FIRST me conflict hai. Lekin SLR(1) me koi shift-reduce conflict nahi hai, isliye ye SLR(1) hai.
Q 2.11 [2003: 2 Marks] – Operator Grammar
Question: Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are non-terminals and r, s, t are terminals.
(i) P -> Q R
(ii) P -> Q s R
(iii) P -> Q
(iv) P -> Q s r
(a) (i) only
(b) (i) and (iii) only
(c) (ii) and (iii) only
(d) (iii) and (iv) only
Answer: (b) (i) and (iii) only
Detailed Solution: Operator grammar me do non-terminal ek saath nahi aa sakte aur epsilon / single non-terminal production allowed nahi hai. Rule (i) P->QR me do NT saath hain aur (iii) P->Q single NT hai, dono violate karte hain.
Q 2.12 [2004: 1 Mark] – Predictive Parsing
Question: The grammar A -> AA | (A) | epsilon is not suitable for predictive parsing because the grammar is
(a) Ambiguous
(b) Left-recursive
(c) Right-recursive
(d) An operator-grammar
Answer: (a) Ambiguous
Detailed Solution: Is grammar me Left-recursion hai A->AA ki wajah se, saath hi ye Ambiguous bhi hai. Predictive parsing ke liye grammar ko left-recursion free aur unambiguous hona chahiye, isliye ye suitable nahi hai.
Q 2.13 [2005: 1 Mark] – States in Parsers
Question: 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, n3 respectively. The following relationship holds good
(a) n1 < n2 < n3
(b) n1 = n3 < n2
(c) n1 = n2 = n3
(d) n1 < n3 < n2
Answer: (b) n1 = n3 < n2
Detailed Solution: Is grammar ke liye SLR(1) aur LALR(1) me states equal hote hain, aur LR(1) me sabse zyada states hote hain. Isliye n1 = n3 < n2.
Q 2.14 [2005: 2 Marks] – Parse Tree
Linked Data for Q 2.14 & Q 2.15:
Consider the context-free grammar
E -> E + E
E -> E * E
E -> id
where E is the starting symbol, the set of terminals is {id, +, *, (, ) }.
Question: Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?
(a) id + id + id + id
(b) id + (id * (id + id))
(c) (id * id + id) + id
(d) (id + id) * id + id * id
Answer: (a) id + id + id + id
Detailed Solution: Ye grammar ambiguous hai kyunki + aur * ke liye precedence / associativity defined nahi hai. id+id+id+id ko 2 tarah se parse kiya ja sakta hai (left ya right associative), isliye iske ek se zyada parse tree hain.
Q 2.15 [2006: 2 Marks] – Number of Parse Trees
Question: For the terminal string with more than one parse tree in Q 2.14 above, how many parse trees are possible?
(a) 5
(b) 4
(c) 3
(d) 2
Answer: (a) 5
Detailed Solution: id+id+id+id ke liye 5 alag-alag parse tree possible hain, kyunki 3 plus operators ko 5 tarah se parenthesize kiya ja sakta hai (Catalan number).
Q 2.16 [2006: 2 Marks] – LR(0) Items
Question: Consider the following grammar:
S -> S * E
S -> E
E -> F + E
E -> F
F -> id
Consider the following LR(0) items to the grammar above.
(i) S -> S * . E
(ii) E -> F . + E
(iii) F -> . id
Given the items above, which two of them will appear in the same set in the canonical LR(0) collection?
(a) (i) and (ii)
(b) (ii) and (iii)
(c) (i) and (iii)
(d) None of these
Answer: (b) (ii) and (iii)
Detailed Solution: Canonical collection banane par E -> F. + E aur F -> .id same state me closure ki wajah se ayenge, isliye ye dono same set me honge.
Q 2.17 [2006: 1 Mark] – Predictive Parser Table
Question: Consider the following grammar:
S -> F R
R -> * S | epsilon
F -> id
In the predictive parser table, M of the grammar the entries M[S, id] and M[R, $] respectively are
(a) {S -> F R} and {R -> epsilon}
(b) {S -> F R} and {}
(c) {S -> F R} and {R -> * S}
(d) {F -> id} and {R -> epsilon}
Answer: (a) {S -> F R} and {R -> epsilon}
Detailed Solution: M[S,id] me S->FR ayega kyunki FIRST(FR)=id hai. M[R,$] me R->epsilon ayega kyunki $ FOLLOW(R) me hai.
Q 2.18 & Q 2.19 [2006: 2 Marks] – Language L = {a^i b^j | i != j}
Question: Which one of the following grammars generates the language L = {a^i b^j | i != j}?
(a) S -> A C | C B
C -> a C b | a A | b B
A -> a A | epsilon
B -> B b | epsilon
(b) S -> a S | S b | a | b
(c) S -> A C | C B
C -> a C b | epsilon
A -> a A | epsilon
B -> B b | epsilon
(d) S -> aA | bB
A -> aA | epsilon
B -> Bb | epsilon
Answer: (a)
Detailed Solution (Apne shabdon me): i != j ka matlab hai ya to a zyada hone chahiye ya b zyada hone chahiye. Option (a) wali grammar hi a==b wale cases ko exclude karti hai aur i!=j generate karti hai.
2.19 [2006: 2 Marks] – Derivation Length for a^l b^m
Question: In the correct grammar above [for L = {a^i b^j | i != j}], what is the length of the derivation (number of steps starting from S) to generate the string a^l b^m with l != m?
(a) max(l, m) + 2
(b) l + m + 2
(c) l + m + 3
(d) max(l, m) + 3
Answer: (a) max(l, m) + 2
Solution : Agar l > m hai to pehle m baar C -> aCb use hoga, fir C -> aA, fir bache hue (l-m-1) baar A -> aA aur last me A -> epsilon. Total steps ginne par max(l,m)+2 aata hai. Same m > l ke liye bhi.
2.20 [2006: 2 Marks] – Top-Down Parser
Question: 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
Answer: (a) Recursive descent parser
Solution: Recursive descent top-down hota hai kyunki ye start symbol se shuru karke input ko derive karta hai. Baki Operator, LR(k), LALR(k) sab bottom-up parsers hain.
2.21 [2007: 1 Mark] – LL(1) Ambiguity
Question: Consider the grammar with non-terminals N = {S, C, S1}, terminals T = {a, b, i, t, e}, with S as the start symbol and rules
S -> i C t S S1 | a
S1 -> e S | epsilon
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
Answer: (c) It is ambiguous
Solution: Ye famous dangling-else grammar hai. Isme e ke liye parse table me conflict aata hai, isliye ye ambiguous hai aur LL(1) nahi ho sakti. LL(1) ke liye unambiguous hona zaruri hai.
2.22 [2007: 2 Marks] – Regular Grammar vs LR(1)
Question: Consider the following two statements:
P: Every regular grammar is LL(1)
Q: Every regular set has 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
Answer: (c) P is false and Q is true
Solution: Har regular grammar LL(1) nahi hoti, isliye P false hai. Lekin har regular language ke liye hum LR(1) grammar bana sakte hain, isliye Q true hai.
Q 2.23 [GATE 2007 Q78 : 2 Marks] Which String Generated?
Common Data for Q2.23& Q2.24:
Consider the CFG with {S, A, B} as the non-terminal alphabet, {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules
S -> aB | bA
A -> a | aS | bAA
B -> b | bS | aBB
Question: Which string is generated?
(A) aaaabb (B) aabbbb (C) aabbab (D) abbbba
Answer: (C) aabbab
Solution: This grammar generates L = { w | na(w) = nb(w) }. Only option C has 3 a’s and 3 b’s equal. Derivation: S => aB => abS => abbA => abbbAA => aabbab.
The process of assigning load addresses to the various parts of the program and adjusting the code and data in the program to reflect the assigned addresses is called
Q 2.24 [GATE 2007 Q79 : 2 Marks] Number of Derivation Trees
Question: For correct string aabbab from Q2.23, how many derivation trees are there?
(A) 1 (B) 2 (C) 3 (D) 4
Answer: (B) 2
Solution: Grammar is ambiguous due to A -> bAA and B -> aBB. Two different leftmost derivations possible for same string. Official GATE Key = 2 trees.