Question Details

Given a context-free grammer G as follows:

S→Aa \ bac | dc | dba

A→d


which ONE of the following statement is TRUE?

Options

A

G is neither LALR(1) nor SLR(1)

B

G is CLR(1) not LALR(1)

C

G is LALR(1) , not SLR(1)

D

G is LALR(1) , also SLR(1)

Show Answer

Correct Answer :

Option C

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 G by constructing its parsing states and examining the conditions for both SLR(1) and LALR(1) parsers.

The grammar rules are:
(1) SAa
(2) Sbac
(3) Sdc
(4) Sdba
(5) Ad

1. Augmenting the Grammar
We add a new start symbol S and the production:
SS

2. LR(0) State Construction
Let us construct the LR(0) states starting from the initial state I0:

State I0:
S·S
S·Aa
S·bac
S·dc
S·dba
A·d

Applying the transition on the terminal symbol d from I0 leads to state I4:

State I4 = Goto(I0, d):
Sd·c
Sd·ba
Ad·

3. Follow Set Analysis
To determine if the grammar is SLR(1), we compute the FOLLOW set for the non-terminal A:
Since A only appears in the production SAa, we have:
FOLLOW(A)={a}

4. Analyzing Conflicts
In state I4:
- We can shift on input c (moving to state Sdc·).
- We can shift on input b (moving to state Sdb·a).
- We reduce the production Ad on the terminals in FOLLOW(A), which is {a}.

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 Ad· in this state is {a} which does not conflict with the shift actions on {b,c}.

Therefore, the grammar G 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).

Unlock Our Free Library

Access expert-curated educational resources and study materials—completely free.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...