Project ForgeConsider the following two sets of LR(1) items of an LR(1) grammar.
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 statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different. 2. Can be merged but will result in S-R conflict. 3. Can be merged but will result in R-R conflict. 4. Cannot be merged since goto on c will lead to two different sets.
- A1 only
- B2 only
- C1 and 4 only
- 1, 2, 3 and 4
Explanation
These two states share the same core (only their lookahead sets differ), so LALR construction DOES merge them (by design — statement 1 is false). After merging, the grammar X→cX|d is simple right recursion: the merged state's completed items (X→d. and later X→cX.) don't end up sharing a state with any conflicting shift or reduce action, so no S-R conflict arises (statement 2 false) and no R-R conflict arises (statement 3 false). The goto on c from both original states leads to structurally identical successor states that also merge consistently, so goto does NOT diverge into two different sets (statement 4 false). All four statements are false — this grammar is a case where LALR merging is completely safe.
Source: GATE CS 2013 (2013)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.