Discussion
Consider the canonical \(LR(0)\) parsing of the grammar below using terminals \(\{a, b, c\}\) and non-terminals \(\{A, B, C, S\}\) with \(S\) as the start symbol.
\(S \rightarrow ACB\)
\(A \rightarrow aA \mid \epsilon\)
\(C \rightarrow cC \mid \epsilon\)
\(B \rightarrow bB \mid b\)
Which one of the following options gives the number of shift-reduce conflicts that will occur in the \(LR(0)\) ACTION table?
Answer: D
The LR(0) ACTION table has 5 shift-reduce conflicts.
LR(0) reduces on every terminal whenever a state contains a complete item, so a state with both a complete item and an item that shifts a terminal has a conflict. Building the canonical LR(0) collection:
- I0 holds S′ → .S, S → .ACB, A → .aA and the complete item A → . (from A → ε): shift on a against reduce A → ε.
- After a: A → a.A, A → .aA, A → . : the same conflict on a.
- After A from I0: S → A.CB, C → .cC, C → . : shift on c against reduce C → ε.
- After c: C → c.C, C → .cC, C → . : the same conflict on c.
- After b from S → AC.B: B → b.B, B → b., B → .bB, B → .b : shift on b against reduce B → b.
The remaining states (S → AC.B, the states with a single complete item such as A → aA., C → cC., B → bB., S → ACB., and the accept state) have no conflict. That makes 5, not 2, 3 or 4.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development