Consider the following grammar:S → Aa | bAc | dc | bdaA → eWhich of the following is correct about the above grammar?a)LALR(1) but not SLR(1)b)SLR(1) and CLR(1)c)LL(1) and LALR(1)d)Only CLR(1)Correct answer is option 'B'. Can you explain this answer?

Question

Answer

SLR(1) and CLR(1)

To determine if the given grammar is SLR(1) and CLR(1), let's analyze the grammar based on the properties of these parsing techniques.

SLR(1)
SLR(1) parsing requires that the grammar be unambiguous and have no shift-reduce or reduce-reduce conflicts. It also requires that for each state in the parsing table, there should be at most one action for each terminal symbol and at most one goto action for each non-terminal symbol.

Let's construct the SLR(1) parsing table for the given grammar:

Grammar:
S → Aa | bAc | dc | b
A → e

First and Follow Sets:
First(S) = {b, d}
First(A) = {e}
Follow(S) = {$, a}
Follow(A) = {a}

Canonical LR(0) Items:
S' → .S
S → .Aa
S → .bAc
S → .dc
S → .b
A → .e

LR(0) Closure:
Closure({S' → .S}) = {S' → .S}
Closure({S → .Aa}) = {S → .Aa, A → .e}
Closure({S → .bAc}) = {S → .bAc}
Closure({S → .dc}) = {S → .dc}
Closure({S → .b}) = {S → .b}
Closure({A → .e}) = {A → .e}

LR(0) Transitions:
Closure({S' → .S})
- On 'S': Go to {S' → S.}
Closure({S → .Aa, A → .e})
- On 'a': Go to {S → A.a, A → .e}
Closure({S → .bAc})
- On 'b': Go to {S → b.Ac}
Closure({S → .dc})
- On 'd': Go to {S → d.c}
Closure({S → .b})
- On 'b': Go to {S → b.}
Closure({A → .e})
- No transitions

SLR(1) Parsing Table:

State | a | b | c | d | $ |
------|---|---|---|---|---|
0 | | s1| | s3| |
1 | | | | | acc |
2 | | r5| s4| | r5|
3 | | | | | r4|
4 | | | | | r3|

s -> shift
r -> reduce
acc -> accept

SLR(1) Analysis:
- There are no shift-reduce or reduce-reduce conflicts in the parsing table.
- The table has at most one action for each terminal symbol and at most one goto action for each non-terminal symbol.

Therefore, the given grammar is SLR(1).

CLR(1)
CLR(1) parsing requires that the grammar be unambiguous and have no shift-reduce or reduce-reduce conflicts. It also requires that for each state in the parsing table

Similar GATE Doubts

Consider the following grammar :S→ aAb | ScA→ d | Sd | SThe above grammar is

Consider the following grammar:S -> aBAA ->aAE | EB ->bBC | bC -> cCD | DD ->aDCE ->ED | eE | eF -> SeFAfter removal of useless symbols, how many productions violate the rules ofgreibach normal form? Correct answer is '1'. Can you explain this answer?

Consider the following expression grammar G.E - E - T | TT - T + F | FF - (E) | idQ.Which of the following grammars are not left recursive, but equivalent to G.

Consider the following augmented grammarS→aAb |ebA→e |fFind the number of states in LR(0) construction.

Top Courses for GATE

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Other Engg Branches

Related Exams

Company