|
|
| (9 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == Problem ==
| | #REDIRECT [[ist:Top-Down Parsing/Example 3]] |
| | |
| Consider the following grammar, where '''<tt>S</tt>''' is the initial symbol and '''<tt>{u,v,x,y,z}</tt>''' is the set of terminal symbols:
| |
| | |
| S -> u B z
| |
| B -> B v | D
| |
| D -> E u E | B y E
| |
| E -> v | v x
| |
| | |
| # Examine the grammar and rewrite it so that an LL(1) predictive parser can be built for the corresponding language. | |
| # Compute the FIRST and FOLLOW sets for all non-terminal symbols in the new grammar and build the parse table.
| |
| # Show the analysis table (stack, input, and actions) for the parsing process of the '''<tt>uvuvxz</tt>''' input sequence.
| |
| | |
| == Solution ==
| |
| | |
| The grammar can be parsed by an LL(1) parser if it does not have left recursion and no ambiguity is present (i.e., the LOOKAHEADs for all productions of each non-terminal are disjoint).
| |
| | |
| A simple inspection of the grammar shows that indirect left recursion is present in rules B and D. Also, there are left corners that may hide ambiguity (E).
| |
| | |
| The first step, then, is to rewrite the grammar so that mutual recursion is eliminated (A becomes unreachable and can be removed from the grammar):
| |
| | |
| S -> u B z
| |
| B -> B v | E u E | B y E
| |
| <font color="red">D -> E u E | B y E</font>
| |
| E -> v | v x
| |
| | |
| Now we handle the left corner (E in B) (E also becomes unreachable and can be removed from the grammar):
| |
| | |
| S -> u B z
| |
| B -> B v | v u v | v x u v x | B y v | B y v x
| |
| <font color="red">E -> v | v x</font>
| |
| | |
| Now, left recursion can be eliminated:
| |
| | |
| S -> u B z
| |
| B -> v u v B1 | v x u v x B1
| |
| B1 -> v B1 | y v B1 | y v x B1 | ε
| |
| | |
| Factoring...
| |
| | |
| S -> u B z
| |
| B -> v B2
| |
| B1 -> v B1 | y v B3 | ε
| |
| B2 -> u v B1 | x u v x B1
| |
| B3 -> B1 | x B1
| |
| | |
| Eliminating the left corner in B3 (note that we do not completely replace B1, since a new factorization would be needed):
| |
| | |
| S -> u B z
| |
| B -> v B2
| |
| B1 -> v B1 | y v B3 | ε
| |
| B2 -> u v B1 | x u v x B1
| |
| B3 -> v B1 | y v B3 | x B1 | ε
| |
| | |
| The FIRST and FOLLOW sets are as follows:
| |
| | |
| FIRST(S) = FIRST(u B z) = {u}
| |
| FIRST(B) = FIRST(v B2) = {v}
| |
| FIRST(B1) = FIRST(v B1) ∪ FIRST(y v B3) ∪ {ε} = {v, y, ε}
| |
| FIRST(B2) = FIRST(u v B1) ∪ FIRST(x u v x B1) = {u, x}
| |
| FIRST(B3) = FIRST(v B1) ∪ FIRST(y v B3) ∪ FIRST(x B1) ∪ {ε} = {v, x, y, ε}
| |
| | |
| FOLLOW(S) = {$} FOLLOW(B1) ⊇ FOLLOW(B2) FOLLOW(B2) ⊇ FOLLOW(B) FOLLOW(B3) ⊇ FOLLOW(B1)
| |
| FOLLOW(B) = {z} FOLLOW(B1) ⊇ FOLLOW(B3)
| |
| FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B3) = FOLLOW(B) = {z}
| |
| | |
| [[category:Compilers]]
| |
| [[category:Teaching]]
| |