Chapter 6: Syntax-Directed Definitions and Translations

5.7 EXAMPLES

The examples that follow further illustrate the concepts covered within this chapter.

EXAMPLE 5.3

Construct an SLR(1) parsing table for the following grammar:

First, augment the given grammar by adding a production S 1 ’ S to the grammar. Therefore, the augmented grammar is:

Next, we obtain the canonical collection of sets of LR(0) items, as follows :

 

The transition diagram of this DFA is shown in Figure 5.19.

Figure 5.19: Transition diagram for the canonical collection of sets of LR(0) items in Example 5.3.

The FOLLOW sets of the various nonterminals are FOLLOW( S ₁ ) = {$}. Therefore:

1. Using S ₁ ’ S , we get FOLLOW( S ) = FOLLOW( S ₁ ) = {$}

2. Using S ’ xAy , we get FOLLOW( A ) = { y }

3. Using S ’ xBy , we get FOLLOW( B ) = { y }

4. Using S ’ xAz , we get FOLLOW( A ) = { z }

Therefore, FOLLOW( A ) = { y, z }. Using A ’ qS , we get FOLLOW( S ) = FOLLOW( A ) = { y, z }. Therefore, FOLLOW( S ) = { y, z , $}. Let the productions of the grammar be numbered as follows:

The SLR parsing table for the productions above is shown in Table 5.11.

Table 5.11: SLR(1) Parsing Table

Action Table						GOTO Table
	x	Y	Z	q	$	S	A	B
I	S 2	R 3 / R 4				1
I 1			Accept
I 2				S 5			3	4
I 3		S 6	S 7
I 4		S 8
I 5	S 2	R 5 / R 6	R 5			9
I 6		R 1	R 1		R 1
I 7		R 3	R 3		R 3
I 8		R 2	R 2		R 2
I 9		R 4	R 4

EXAMPLE 5.4

Construct an SLR(1) parsing table for the following grammar:

First, augment the given grammar by adding the production S ₁ ’ S to the grammar. The augmented grammar is:

Next, we obtain the canonical collection of sets of LR(0) items, as follows:

 

The transition diagram of the DFA is shown in Figure 5.20.

Figure 5.20: DFA transition diagram for Example 5.4.

The FOLLOW sets of the various nonterminals are FOLLOW( S ₁ ) = {$}. Therefore:

1. Using S ₁ ’ S , we get FOLLOW(S) = FOLLOW( S ₁ ) = {$}

2. Using S ’ S 0, we get FOLLOW( S ) = { 0 }

3. Using S ’ 1 S 1, we get FOLLOW( S ) = {1}

So, FOLLOW( S ) = {0, 1, $}. Let the productions be numbered as follows:

The SLR parsing table for the production set above is shown in Table 5.12.

Table 5.12: SLR Parsing Table for Example 5.4

Action Table			GOTO Table
		1	$	S
I	S 2	S 3		1
I 1				accept
I 2	S 2	S 3		4
I 3	S 6	S 3		5
I 4	S 7
I 5		S 8
I 6	S 2/ R 3	S 3 / R 3	R 3	4
I 7	R 1	R 1		R 1
I 8	R 2	R 2		R 2

EXAMPLE 5.5

Consider the following grammar, and construct the LR(1) parsing table.

 

The augmented grammar is:

The canonical collection of sets of LR(1) items is:

The parsing table for the production above is shown in Table 5.13.

Table 5.13: Parsing Table for Example 5.5

Action Table			GOTO Table
	A	B	$	S
I	S 2	S 3	R 3	1
I 1			Accept
I 2	S 5	S 6 / R 3		4
I 3	S 8 / R 3	S 9		7
I 4		S 10
I 5	S 5	S 6 / R 3		11
I 6	S 8 / R 3	S 9		12
I 7	S 13
I 8	S 5	S 6 / R 3		14
I 9	S 8 / R 3	S 9		15
I 10	S 2	S 3	R 3	16
I 11		S 17
I 12	S 18
I 13	S 2	S 3	R 3	19
I 14		S 20
I 15		S 21
I 16			R 1
I 17	S 5	S 6 / R 3		22
I 18	S 5	S 6 / R 3		23
I 19			R 2
I 20	S 8 / R 3	S 9		24
I 21	S 8 / R 3	S 9		25
I 22		R 1
I 23		R 2
I 24	R 1
I 25	R 2

The productions for the grammar are numbered as shown below:

EXAMPLE 5.6

Construct an LALR(1) parsing table for the following grammar:

The augmented grammar is:

The canonical collection of sets of LR(1) items is:

 

There no sets of LR(1) items in the canonical collection that have identical LR(0)-part items and that differ only in their lookaheads. So, the LALR(1) parsing table for the above grammar is as shown in Table 5.14.

Table 5.14: LALR(1) Parsing Table for Example 5.5

Action Table						GOTO Table
	a	b	c	d	$	S	A
I		S 3		S 4		1	2
I 1					Accept
I 2	S 5
I 3				S 7		1
I 4	R 5		S 8
I 5					R 1
I 6	S 10		S 9
I 7			R 5
I 8					R 3
I 9					R 2
I 10					R 4

The productions of the grammar are numbered as shown below:

1. S ’ Aa

2. S ’ bAc

3. S ’ dc

4. S ’ bda

5. A ’ d

EXAMPLE 5.7

Construct an LALR(1) parsing table for the following grammar:

The augmented grammar is:

The canonical collection of sets of LR(1) items is:

 

Since no sets of LR(1) items in the canonical collection have identical LR(0)-part items and differ only in their lookaheads, the LALR(1) parsing table for the above grammar is as shown in Table 5.15.

Table 5.15: LALR(1) Parsing Table for Example 5.6

Action Table						GOTO Table
	a	b	c	d	$	S	A	B
I	S 4	S 5		S 6		1	2	3
I 1					Accept
I 2	S 7
I 3			S 8
I 4				S 10			9
I 5				S 12				11
I 6	R 5		R 6
I 7					R 1
I 8					R 3
I 9			S 13
I 10			R 5
I 11	S 14
I 12	R 6
I 13					R 2
I 14					R 4

The productions of the grammar are numbered as shown below:

1. S ’ Aa

2. S ’ aAc

3. S ’ Bc

4. S ’ bBa

5. A ’ d

6. B ’ d

EXAMPLE 5.8

Construct the nonempty sets of LR(1) items for the following grammar:

 

The collection of nonempty sets of LR(1) items is shown in Figure 5.21.

Figure 5.21: Collection of nonempty sets of LR(1) items for Example 5.7.