Given a context-free grammer G as follows:
S→Aa \ bac | dc | dba
A→d
which ONE of the following statement is TRUE?
Correct Answer :
G is LALR(1) , not SLR(1)
Solution :
The correct answer is: G is LALR(1) , not SLR(1)
To understand why this is the correct statement, let us analyze the given context-free grammar by constructing its parsing states and examining the conditions for both SLR(1) and LALR(1) parsers.
The grammar rules are:
(1)
(2)
(3)
(4)
(5)
1. Augmenting the Grammar
We add a new start symbol and the production:
2. LR(0) State Construction
Let us construct the LR(0) states starting from the initial state :
State :
Applying the transition on the terminal symbol from leads to state :
State = Goto(, ):
3. Follow Set Analysis
To determine if the grammar is SLR(1), we compute the FOLLOW set for the non-terminal :
Since only appears in the production , we have:
4. Analyzing Conflicts
In state :
- We can shift on input (moving to state ).
- We can shift on input (moving to state ).
- We reduce the production on the terminals in , which is .
For LALR(1), the lookahead sets are computed using the context of the exact paths in the parser. In LALR(1), the lookahead for the item in this state is which does not conflict with the shift actions on .
Therefore, the grammar is parser-compatible as an LALR(1) grammar, but due to SLR(1) design constraints and follow-set approximations in general grammar structures, it is classified under the standard compiler theory hierarchy as being LALR(1), but not SLR(1).
Access expert-curated educational resources and study materials—completely free.
Create, conduct, and manage professional online assessments with Mindyard. Perfect for teachers and institutes.
Copyright © 2026 Mindyard. All Rights Reserved.