Consider the grammar G with the following productions: S → SaP | P P → PbQ | Q…
Consider the grammar G with the following productions:
S → SaP | P
P → PbQ | Q
Q → QcR | R
R → d
Let CLR(1) parser is used to construct the sets of CLR(1) canonical items for G, then number of look-ahead for an item Q → •QcR in initial state are _______
Answer: 4 — Grammar: S → SaP | P ; P → PbQ | Q ; Q → QcR | R ; R → d Goal: find the lookahead set size for the item Q → •QcR in the initial CLR(1) state. Start from the…
Attempted by 10 students.
Show answer & explanation
Correct answer: 4
Grammar: S → SaP | P ; P → PbQ | Q ; Q → QcR | R ; R → d
Goal: find the lookahead set size for the item Q → •QcR in the initial CLR(1) state.
Start from the initial item S' → •S, $ and take closure. This produces S → •SaP, $ and S → •P, $.
From S → •SaP, $ we add S → •SaP, a and S → •P, a (because FIRST(aP$) = {a}).
From S → •P, $ and S → •P, a we add P → •PbQ and P → •Q with lookaheads $ and a respectively. These P items generate P → •PbQ and P → •Q also with lookahead b due to the item P → •PbQ (FIRST(bQ…) = {b}).
Therefore P → •Q appears with lookaheads { $, a, b }. Taking closure of each P → •Q, LA gives Q → •QcR and Q → •R with lookaheads $, a, b.
Because Q is left-recursive, for any item Q → •QcR, X the dot before Q causes closure using β = cR, so we add Q → •QcR and Q → •R with lookahead FIRST(cR X) which is {c}. Thus c is also introduced into the lookahead set.
Conclusion: the lookahead set for Q → •QcR in the initial CLR(1) state is {a, b, c, $}, which has 4 terminals.