SLR Parser Examples

Example 1:

Parsing of the input string id * id + id using the SLR parser table for the grammar

1. E → E + T

2. E → T

3. T → T * F

4. T → F

5. F → ( E )

6. F → id

	Stack	Input	Next
1	0	id * id + id $	Shift
2	0 id5	* id + id $	reduce by F →id
3	0 F3	* id + id $	reduce by T → F
4	0 T2	* id + id $	shift
5	0 T2 * 7	id + id $	shift
6	0 T2 * 7 id 5	+ id $	Reduce by F → id
7	0 T2 * 7 F 10	+ id $	Reduce by T → T * F
8	0 T2	+ id $	Reduce by E → T
9	0 E 1	+ id $	Shift
10	0 E 1 + 6	id $	Shift
11	0 E1 + 6 id 5	i $	Reduce by F → id
12	0 E1 + 6 F 3	$	Reduce by T → F
13	0 E1 + 6 T 9	$	E → E + T
14	0 E1	$	Accept

Example 2:

Construct SLR parser for S → (S)S | ε

The augmented grammar is, S’ → S   S → (S)S   S → ε

The canonical collection of LR(0) items are

I0:

S’ → .S

S → .(S)

S’ → .

I1:

S’ → S.

I2:

S → (.S)S

S → .(S)S

S → .

I3:

S → (S.)S

I4:

S → (S).S

S → .(S)S

S → .

I5:

S → (S)S.

DFA from Canonical collection of LR(0) items:

The GOTO function of the canonical collection of set of items defines a DFA that recognizes the viable prefixes of the grammar

Each set of item becomes a state in the DFA

The DFA for the example 2 from its items is

 Construction SLR Parsing Table for Example 2

States	ACTION			GOTO
	(	)	$	S
0	S2	r2	r2	1
1			Accept	-
2	S2	r2	r2	3
3		S4
4	S2	r2	r2	5
5		r1	r1

Parsing the Input String for Example 2

Stack	Input String	Action
$ 0	( ) $	Shift
$ 0 ( 2 ) $	) $	Reduce S → E, goto[2, S] = 3
$ 0 ( 2 S 3	) $	Shift
$ 0 ( 2 S 3 ) 4	$	Reduce S → E, goto[4, S] = 5
$ 0 ( 2 S 3 ) 4 S 5	$	Reduce S → (S)S, goto[0, S] = 1
$ 0 S 1	$	Accept

Example 3:

Construct SLR Parser for S → CC, C → Cc | d

Example 4:

Show that the grammar S → xAy | xBy | xAz   A → qS | q  B → q is not SLR(1)

Example 5:

Show that the grammar S → 0S0 | 1S1 | 10 is not SLR(1)

Example 6:

Show that the grammar S → AaAb | BbBa   A → ε  is not SLR(1)

Example 7:

Show that the grammar S → AS | b   A → SA | a is not SLR(1)

Example 8:

Show that S → L = R | R the grammar is not SLR(1),

                                                L → *  R |id

                                                R → L

LR Parsers

Home

LR Parsers Introduction