2.25 [2007: 2 Marks] – Handle in LR Parsing
Question: 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 a 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
Answer: (d)
Solution: Handle ka matlab hota hai wo production jo agle step me reduce hone wala hai, saath me uska RHS kahan par hai sentential form me. Isliye option (d) sahi definition hai. Ye right-most derivation ka hissa hota hai.
2.26 [2008: 1 Mark] – LALR(1) Conflicts
Question: An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
(a) the SLR(1) parser for G has S-R conflicts
(b) the LR(1) parser for G has S-R conflicts
(c) the LR(0) parser for G has S-R conflicts
(d) the LALR(1) parser for G has reduce-reduce conflicts
Answer: (b) the LR(1) parser for G has S-R conflicts
Solution : LALR(1) me shift-reduce conflict tabhi aata hai jab LR(1) me bhi ho. Kyunki LALR merging me S-R conflict create nahi hota, sirf R-R conflict create ho sakta hai. Isliye LALR ka S-R conflict, LR(1) ke S-R conflict ke barabar hota hai.
2.27 [2008: 2 Marks] – LL(1) and LR(1) Grammar
Question: The grammar S -> aSa | bS | c is
(a) LL(1) but not LR(1)
(b) LR(1) but not LL(1)
(c) Both LL(1) and LR(1)
(d) Neither LL(1) nor LR(1)
Answer: (c) Both LL(1) and LR(1)
Solution : Is grammar me S ke teen productions ka FIRST set alag-alag hai – a, b, c. Koi common nahi hai isliye LL(1) hai. Aur har LL(1) grammar LR(1) bhi hoti hai, isliye ye Both hai.
Linked Data Questions 2.28 and 2.29 [2010: 2 Marks]
Common Data: 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 -> a A b B | b A a B | ε
A -> S
B -> S
Note: Iske aage ka table wala part next photo me hai. Agla photo bhej do to 2.28 aur 2.29 ke blocks bana dunga.
2.28 [2010: 2 Marks] – FIRST and FOLLOW (Linked Q)
Common Grammar:
S -> a A b B | b A a B | ε
A -> S
B -> S
LL(1) Table:
| a | b | $
S | E1 | E2 | S -> ε
A | A->S | A->S | error
B | B->S | B->S | E3
Question: The FIRST and FOLLOW sets for the non-terminals A and B are
(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}
Answer: (a)
Solution : S ka FIRST {a, b, ε} hai, to A->S aur B->S se FIRST(A) aur FIRST(B) bhi same hoga. FOLLOW(A) me a,b aata hai kyunki S -> a A b B aur b A a B me A ke baad b aur a hai. FOLLOW(B) me {a, b, $} aata hai kyunki B last me bhi hai aur S ka FOLLOW $ bhi include hota hai.
2.29 [2012: 2 Marks] – LL(1) Table Entries E1, E2, E3
Question: The appropriate entries for E1, E2 and E3 are
(a) E1: S -> aAbB, A -> S | E2: S -> bAaB, B -> S | E3: B -> S
(b) E1: S -> aAbB, S -> ε | E2: S -> bAaB, B -> ε | 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
Answer: (c) E1: S -> aAbB, S -> ε | E2: S -> bAaB, S -> ε | E3: B -> S
Solution : E1 = column ‘a’ row ‘S’ hai. S -> aAbB to aayega hi, plus S -> ε bhi aayega kyunki FIRST(A) me ε hai aur a, b FOLLOW me hai. Same E2 me S -> bAaB + S -> ε. E3 = column ‘$’ row ‘B’ me B -> S aayega kyunki $ FOLLOW(B) me hai.
2.30 [2012: 2 Marks] – Max Reduces in Bottom-Up Parser
Question: What is the maximum number of reduces moves that can be taken by a bottom-up parser for a grammar without epsilon and unit productions (i.e. of type A -> ε and A -> a) to parse a string with n tokens?
(a) n/2
(b) n-1
(c) 2n-1
(d) 2^n
Answer: (c) 2n-1
Solution : Bina epsilon aur unit production ke, har reduce se kam se kam ek token ya length badhti hai. n tokens ke liye worst case me pehle n-1 reduces se binary tree jaisa structure banega aur fir n reduces, total 2n-1 maximum hota hai. Isliye bottom-up me itna hi limit hota hai.
2.31 [2013: 2 Marks] – LALR Merging Concept
Question: Consider two LR(1) item sets:
Set-1: X -> c.X, c/d | X -> .cX, c/d | X -> .d, c/d
Set-2: X -> c.X, $ | X -> cX, $ | X -> .d, $
Which of the following statement related to merging of the two sets in the corresponding LALR parser is/are FALSE?
- Cannot be merged since look aheads are different.
- Can be merged but will result in S-R conflict.
- Can be merged but will result in R-R conflict.
- Cannot be merged since goto on c will lead to two different sets.
(a) 1 only
(b) 2 only
(c) 1 and 4 only
(d) 1, 2, 3 and 4
Answer: (d) 1, 2, 3 and 4
Solution : LR(1) me same core wale sets ko LALR me merge kar dete hain, lookahead alag hone se farak nahi padta. Is example me dono sets ka core same hai isliye merge ho jayenge aur koi S-R ya R-R conflict nahi ayega. Goto par bhi same set jayega. Isliye charo statements FALSE hain.
2.32 [2013: 2 Marks] – LR(0) Conflict Check
Question: 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.
Answer: (d) neither a shift-reduce nor a reduce-reduce conflict.
Solution : Is set me S -> L . > R me > par shift hai aur Q -> R. me > FOLLOW me nahi hai ya sirf ek reduce hai, isliye > symbol par koi conflict nahi hai. Na S-R na R-R.
2.33 [2014 (Set-1): 2 Marks] – Associativity
Question: Consider the grammar defined by the following production rules, with two operators * and +
S -> T * P
T -> U | T * U
P -> Q + P | Q
Q -> Id
U -> Id
Which one of the following is TRUE?
(a) + is left associative, while * is right associative
(b) + is right associative, while * is left associative
(c) Both + and * are right associative
(d) Both + and * are left associative
Answer: (b) + is right associative, while * is left associative
Solution : T -> T * U left recursion hai isliye * left associative hua. P -> Q + P right recursion hai isliye + right associative hua. Isliye (b) sahi hai.
2.34 [2015 (Set-1): 1 Mark] – Shift-Reduce & Viable Prefix
Question: 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
Answer: (c)
Solution (Apne shabdon me): Shift-reduce parser ka stack hamesha viable prefix hi rakhta hai. Isliye stack ka pura content viable prefix ka set hota hai, yehi parsing ka base hai.
2.35 [2015 (Set-2): 1 Mark] – Matching
Question: Match the following:
List-I
A. Lexical analysis
B. Parsing
C. Register allocation
D. Expression evaluation
List-II
- Graph coloring
- DFA minimization
- Post-order traversal
- Production tree
Codes:
A B C D
(a) 2 3 1 4
(b) 2 1 4 3
(c) 2 4 1 3
(d) 2 3 4 1
Answer: (c) 2 4 1 3
Solution : Lexical = DFA minimization, Parsing = Production tree / parse tree, Register allocation = Graph coloring, Expression evaluation = Post-order traversal. Isliye A-2, B-4, C-1, D-3.
2.36 [2015 (Set-3): 1 Mark] – SLR vs LALR vs CLR Power
Question: 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
Answer: (c) SLR, canonical LR
Solution (Apne shabdon me): Implement karne me sabse easy SLR hai, aur power me sabse zyada powerful Canonical LR (LR1) hai. LALR beech me hai.
2.37 [2015 (Set-3): 2 Marks] – LL(1) and LR(1) Parsing
Question: Consider the following grammar G.
S -> F | H
F -> p | c
H -> d | c
Where S, F and H are non-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 G.
(a) Only S1
(b) Only S2
(c) Both S1 and S2
(d) Neither S1 and S2
Answer: (d) Neither S1 and S2
Solution : Ye grammar ambiguous hai kyunki ‘c’ dono F aur H se derive ho raha hai. LL(1) me FIRST(F) aur FIRST(H) me c common hai to conflict. Ye ambiguous grammar LR(1) bhi nahi hai. Isliye na LL(1) na LR(1) parse kar payega.
2.38 [2017 (Set-1): 1 Mark] – FOLLOW(Q)
Question: Consider the following grammar:
P -> x Q R S
Q -> y z | z
R -> w | ε
S -> y
What is FOLLOW(Q)?
(a) {R}
(b) {w}
(c) {w, y}
(d) {w, $}
Answer: (c) {w, y}
Solution (Apne shabdon me): Q ke baad R S hai. FIRST(R S) = {w, y} kyunki R -> w ya ε aur S -> y. R epsilon ho sakta hai to S ka FIRST y bhi aayega. Isliye FOLLOW(Q) = {w, y}.
2.39 [2017 (Set-2): 1 Mark] – Parser Power
Question: 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
Answer: (a) I only
Solution : Power order hai: CLR > LALR > SLR. Isliye Canonical LR, SLR se zyada powerful hai. Statement I sahi hai, II aur III galat hai.
2.40 [2017 (Set-2): 2 Marks] – Removing Left Recursion
Question: Consider the following expression grammar G:
E -> E – T | T
T -> T + F | F
F -> (E) | id
Which of the following grammars is not left recursive, but is equivalent to G?
(a) E -> E – T | T, T -> T + F | F, F -> (E) | id
(b) E -> T E’, E’ -> – T E’ | ε, T -> F | F, F -> (E) | id [distorted]
(c) E -> T X, X -> – T X | ε, T -> F Y, Y -> + F Y | ε, F -> (E) | id
(d) E -> T X | (T X), X -> – T X | + T X | ε, T -> id
Answer: (c)
Solution : Left recursion hatane ke liye E -> E – T ko E -> T X aur X -> – T X | ε me badalte hain. Same T -> T + F ko T -> F Y aur Y -> + F Y | ε me. Isse grammar left recursion free ho jata hai par language same rehti hai. Isliye option (c) sahi hai.
2.41 [2019: 1 Mark] – FOLLOW(B) Index
Question: Consider the grammar given below:
S -> A a
A -> B D
B -> b | ε
D -> d | ε
Let a, b, d and $ be indexed as follows:
a=3, b=2, d=1, $=0
Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, $}, then the answer should be 3210)
Answer: 31
Solution (Apne shabdon me): S -> A a se FOLLOW(A) = {a}. A -> B D se FOLLOW(B) = FIRST(D) + FOLLOW(A). FIRST(D) = {d, ε}. ε hatake d ayega aur D ε ho sakta hai to FOLLOW(A)=a bhi ayega. Isliye FOLLOW(B) = {d, a}. Index descending a=3, d=1 => 31.
2.42 [2019: 1 Mark] – Derivation in LR Parser
Question: Which one of the following kinds of derivation is used by LR parsers?
(a) Rightmost
(b) Rightmost in reverse
(c) Leftmost
(d) Leftmost in reverse
Answer: (b) Rightmost in reverse
Solution : LR parser bottom-up hota hai aur right-most derivation ko ulta (reverse) me banata hai. Isliye isko Rightmost in reverse kehte hain.
2.43 [2019: 2 Marks] – GOTO Items Count
Question: Consider the augmented grammar given below:
S’ -> S
S -> | id
L -> L, S | S
Let I0 = CLOSURE({[S’ -> S]}). The number of items in the set GOTO(I0, <) is __.
Answer: 5
Solution (Apne shabdon me): I0 me S’ -> .S, S -> ., S -> .id hoga. ‘<‘ par GOTO lene se S -> <.L> ayega. L ka closure karne se L -> .L,S, L -> .S, S -> ., S -> .id total 5 items banenge.
2.44 [2020: 1 Mark] – Number of Reductions
Question: Consider the following grammar:
S -> a S B | d
B -> b
The number of reduction steps taken by a bottom-up parser while accepting the string a a a d b b b is __.
Answer: 7
Solution : String aaadbbb ke liye derivation: S => aSB => aaSBB => aaaSBBB => aaadBBB => aaad b BB => aaadbbB => aaadbbb. Isme S->aSB 3 baar, S->d 1 baar, B->b 3 baar = total 7 productions, isliye 7 reduction steps.