Solution

Any bottom up parser scans input from left to right and constructs a rightmost derivation in reverse.

Solution

Solution

Total 7 reduce moves

Solution

CLR is more powerful than LL parser. Every SLR(1) grammar is also an LALR(1) grammar as LALR is more powerful than SLR. Every LL(1) must be CLR(1) but every LL(1) need not be LALR(1).

Solution

The two sets in CLR(1) items can be merged (in LALR(1)) if they only differ with look aheads symbols, so statement I is false. In the given CLR(1) items there is not any reduced move, so after merging it will not have SR conflict and hence statement II and statement III are false.

Statement 4 is also wrong, because goto is carried on Non-Terminals symbols, not on terminal symbols, and “a” is a terminal symbol.

Hence all statements are false.

Solution

The given grammar is not CLR(1), hence it cannot be LALR(1), SLR(1) or LR(0)

Solution

S1 is false. For example grammar

S->Sa | ε is an LR(0) grammar

S2 is false. For example

Grammar: S-> aA | aB

A→ε

B→ε

Generate a language which has only one string { a} but the grammar is ambiguous as it generates two parse trees for string “a”.

Solution

Every CLR(1) grammar must be unambiguous but every unambiguous grammar need not be CLR(1). For example the grammar S-> 0S0 | 1S1 | ε is unambiguous but it is not CLR(1).

Solution

Solution

The grammar G1, S → aSa | bSb | ε (language is even length palindrome) is unambiguous but the language is not DCFL hence S1 is false.

The grammar G2, S->SS | aSb | bSa| ε (language is L=(anbn)*) is DCFL but the grammar is ambiguous, hence S2 is also false.

Solution

G1 is an ambiguous grammar, as it has two parse trees for string “id+id+id”, so it can’t be LR(1), while it is an operator grammar. G2 can’t be operator grammar as in operator grammar two variables can’t be together. But G2 is unambiguous grammar as well as LR(1) grammar.

Solution

The grammar is CLR(1) as well as LALR(1).

The canonical collection of LR(1) items.

No two states differ by only lookahead hence this is also LALR(1).

The grammar is not SLR(1)

S→ Aw (r1)

S→ xAy (r2)

S→ zy (r3)

S→ xzw (r4)

A→z (r5)

The canonical collection of LR(0) items

Follow(A)={w,y}

Follow(S)={ $}

The SLR(1) parsing table

One SR conflict hence not SLR(1).

Solution

Solution

If I is the set of one item {[ E’→.E]}, then CLOSURE(I) contains the set of items I₀

Solution

If I is the set of one item {[ S’→.S]}, then CLOSURE(I) contains the set of items I₀

First(PQ)= FIRST(P) U FIRST(Q) {when P→ϵ}

FIRST(P)={ c} U FIRST(Q)

FIRST(Q) ={d} U FIRST(PS)

FIRST(Q) ={d} U FIRST(S) {when P→ϵ}

FIRST(S)={a, b}

Hence, First(PQ)= FIRST(P) U FIRST(Q) U FIRST(S) ={a,b,c,d}

So we have set CLOSURE(I) as