DESKTOP

# Algorithms for Compiler Design: EXAMPLES for Bottom-up Parsing

7/24/2010 7:48:36 PM
##### 5.7 EXAMPLES EXAMPLE 1 Construct an SLR(1) parsing table for the following grammar: First, augment the given grammar by adding a production S1 → 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 1. The FOLLOW sets of the various nonterminals are FOLLOW(S1) = {\$}. Therefore: Using S1 → S, we get FOLLOW(S) = FOLLOW(S1) = {\$} Using S → xAy, we get FOLLOW(A) = {y} Using S → xBy, we get FOLLOW(B) = {y} 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 ����� EXAMPLE 2 Construct an SLR(1) parsing table for the following grammar: First, augment the given grammar by adding the production S1 → 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 2. The FOLLOW sets of the various nonterminals are FOLLOW(S1) = {\$}. Therefore: Using S1 → S, we get FOLLOW(S) = FOLLOW(S1) = {\$} Using S → 0S0, we get FOLLOW(S) = { 0 } 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 EXAMPLE 3 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 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: EXAMPLE 4 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 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: S → Aa S → bAc S → dc S → bda A → d EXAMPLE 5 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. 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: S → Aa S → aAc S → Bc S → bBa A → d B → d EXAMPLE 6 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 3. var sc_project=11388663; var sc_invisible=1; var sc_security="7db37af3"; var scJsHost = (("https:" == document.location.protocol) ? "https://secure." : "http://www."); document.write("<sc"+"ript type='text/javascript' src='" + scJsHost+ "statcounter.com/counter/counter.js'></"+"script>");
 Other

 Top 10
 REVIEW
- First look: Apple Watch

- 3 Tips for Maintaining Your Cell Phone Battery (part 1)

- 3 Tips for Maintaining Your Cell Phone Battery (part 2)