Algorithms for Compiler Design: EXAMPLES for Bottom-up Parsing

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

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 1.

Table 1: SLR(1) Parsing Table

Action Table						GOTO Table
�	x	Y	Z	q	$	S	A	B
I0	S2	R3/R4	�	�	�	1	�	�
I1	�	�	Accept	�	�	�	�	�
I2	�	�	�	S5	�	�	3	4
I3	�	S6	S7	�	�	�	�	�
I4	�	S8	�	�	�	�	�	�
I5	S2	R5/R6	R5	�	�	9	�	�
I6	�	R1	R1	�	R1	�	�	�
I7	�	R3	R3	�	R3	�	�	�
I8	�	R2	R2	�	R2	�	�	�
I9	�	R4	R4	�	�	�	�	�

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

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

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

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

3. Using S → 1S1, 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 2.

Table 2: SLR Parsing Table for Example 1

Action Table			GOTO Table
�	0	1	$	S
I0	S2	S3	�	1
I1	�	�	�	accept
I2	S2	S3	�	4
I3	S6	S3	�	5
I4	S7	�	�	�
I5	�	S8	�	�
I6	S2/R3	S3/R3	R3	4
I7	R1	R1	�	R1
I8	R2	R2	�	R2

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 3.

Table 3: Parsing Table for Example 2

Action Table			GOTO Table
�	A	B	$	S
I0	S2	S3	R3	1
I1	�	�	Accept	�
I2	S5	S6/R3	�	4
I3	S8/R3	S9	�	7
I4	�	S10	�	�
I5	S5	S6/R3	�	11
I6	S8/R3	S9	�	12
I7	S13	�	�	�
I8	S5	S6/R3	�	14
I9	S8/R3	S9	�	15
I10	S2	S3	R3	16
I11	�	S17	�	�
I12	S18	�	�	�
I13	S2	S3	R3	19
I14	�	S20	�	�
I15	�	S21	�	�
I16	�	�	R1	�
I17	S5	S6/R3	�	22
I18	S5	S6/R3	�	23
I19	�	�	R2	�
I20	S8/R3	S9	�	24
I21	S8/R3	S9	�	25
I22	�	R1	�	�
I23	�	R2	�	�
I24	R1	�	�	�
I25	R2	�	�	�

The productions for the grammar are numbered as shown below:

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 4.

Table 4: LALR(1) Parsing Table for Example 3

Action Table						GOTO Table
�	a	b	c	d	$	S	A
I0	�	S3	�	S4	�	1	2
I1	�	�	�	�	Accept	�	�
I2	S5	�	�	�	�	�	�
I3	�	�	�	S7	�	1	�
I4	R5	�	S8	�	�	�	�
I5	�	�	�	�	R1	�	�
I6	S10	�	S9	�	�	�	�
I7	�	�	R5	�	�	�	�
I8	�	�	�	�	R3	�	�
I9	�	�	�	�	R2	�	�
I10	�	�	�	�	R4	�	�

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

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.

Table 5: LALR(1) Parsing Table for Example 4

Action Table						GOTO Table
�	a	b	c	d	$	S	A	B
I0	S4	S5	�	S6	�	1	2	3
I1	�	�	�	�	Accept	�	�	�
I2	S7	�	�	�	�	�	�	�
I3	�	�	S8	�	�	�	�	�
I4	�	�	�	S10	�	�	9	�
I5	�	�	�	S12	�	�	�	11
I6	R5	�	R6	�	�	�	�	�
I7	�	�	�	�	R1	�	�	�
I8	�	�	�	�	R3	�	�	�
I9	�	�	S13	�	�	�	�	�
I10	�	�	R5	�	�	�	�	�
I11	S14	�	�	�	�	�	�	�
I12	R6	�	�	�	�	�	�	�
I13	�	�	�	�	R2	�	�	�
I14	�	�	�	�	R4	�	�	�

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

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