Question

Consider the following context-free grammar G:

E ® T +

E ® * T i

E ® f i

E ® * f +

T ® +

Questions:

1. (5 points) Compute the Canonical LR(1) Closure set for state I₀ for grammar G.
2. (10 points) Compute (draw) the DFA that recognizes the Canonical LR(1) sets of items for grammar G.
3. (5 points) Construct the corresponding Canonical LR(1) parsing table.
4. (10 points) Compute (draw) the DFA for LALR(1).
5. (5 points) Construct LALR(1) parsing table.

Answer 1

The given grammar is :

E -> T+

E -> * T i

E -> f i

E ->  * f +

T -> +

1.

The Canonical LR(1) Closure set for state I₀ for grammar is computed as follows :

Step 1 :

At first an augmented production E ' -> E has to be included with lookahead $.

In LALR,

if the productions are of the form,

R' -> .AB/ $

Then, the lookahead of production

A -> T is First of ( B / $ ) and not FIrst of ( AB/ $ )

I0 =

E ' -> . E / $

E -> . T+ / $

E -> . * T i / $

E -> . f i / $

E -> . * f + / $

T -> . + / +

2.

In order to draw the DFA that recognizes the Canonical LR(1) sets of items for grammar G, the closure set has to be computed for each state.

It must be noted that the after a transition from one state to another, the lookahead will remain same.

The closure set is :

I0 =

E ' -> . E / $

E -> . T+ / $

E -> . * T i / $

E -> . f i / $

E -> . * f + / $

T -> . + / +

I1 = goto(I0, E)

E ' -> E . / $

I2 = goto(I0, T )

E -> T.+ / $

I3 = goto(I0, *)

E -> * . T i / $

T -> . + / i

E -> * .f + / $

I4 = goto(I0, f)

E -> f.i / $

I5 = goto(I0, +)

E -> +. / +

I6 = goto(I2, +)

E -> T+. / $

I7 = goto(I3, T )

E -> * T . i / $

I8 = goto(I3, + )

E -> +. / i

I9 = goto(I3, f)

E -> *f . + / $

I10 = goto(I4, i )

E -> fi . / $

I11 = goto(I7, i)

E -> *Ti. / $

I12 = goto(I9, +)

E -> *f+. / $

Hence, the required DFA is :

3.

In order to compute the corresponding Canonical LR(1) parsing table, the following steps are taken :

Step 1 :

Mark the production numbers of the given context free grammar :

E -> T+ .....................................1

E -> * T i ...................................2

E -> f i ......................................3

E ->  * f +..................................4

T -> +........................................5

This numbering is helpful when the reduction operation is performed.

Step 2 :

Here, si means shift to state i and ri means reduction caused to production number i with respect to the given lookahead of a particular state.

The parsing table is :

State	+	i	*	f	$	E	T
I0	s5		s3	s4		I1	I2
I1					accept
I2	s6
I3	s8			s9		I7
I4		s10
I5					r5
I6					r1
I7		s11
I8		r5
I9	s12
I10					r3
I11					r2
I12					r4

4.

The DFA for LALR(1) is same as that of CLR(1) parser except the states which are only different in lookaheads but similar in all other aspects are combined into one state.

So, the state I5 and I8 are combined into one state which can be called I58.

Hence, the required DFA is :

5.

The required parsing table is :

State	+	i	*	f	$	E	T
I0	s58		s3	s4		I1	I2
I1					accept
I2	s6
I3	s8			s9		I7
I4		s10
I5		r5			r5
I6					r1
I7		s11
I9	s12
I10					r3
I11					r2
I12					r4