|
|
| (10 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 B¹ | v x u v x B¹
| |
| B¹ -> v B¹ | y v B¹ | y v x B¹ | ε
| |
| | |
| Factoring...
| |
| | |
| S -> u B z
| |
| B -> v B²
| |
| B¹ -> v B¹ | y v B³ | ε
| |
| B² -> u v B¹ | x u v x B¹
| |
| B³ -> B¹ | x B¹
| |
| | |
| Eliminating the left corner in B³ (note that we do not completely replace B¹, since a new factorization would be needed):
| |
| | |
| S -> u B z
| |
| B -> v B²
| |
| B¹ -> v B¹ | y v B³ | ε
| |
| B² -> u v B¹ | x u v x B¹
| |
| B³ -> v B¹ | y v B³ | x B¹ | ε
| |
| | |
| The FIRST and FOLLOW sets are as follows:
| |
| | |
| FIRST(S) = FIRST(u B z) = {u}
| |
| FIRST(B) = FIRST(v B²) = {v}
| |
| FIRST(B¹) = FIRST(v B¹) ∪ FIRST(y v B³) ∪ {ε} = {v, y, ε}
| |
| FIRST(B²) = FIRST(u v B¹) ∪ FIRST(x u v x B¹) = {u, x}
| |
| FIRST(B³) = FIRST(v B¹) ∪ FIRST(y v B³) ∪ FIRST(x B¹) ∪ {ε} = {v, x, y, ε}
| |
| | |
| FOLLOW(S) = {$} FOLLOW(B¹) ⊇ FOLLOW(B²) FOLLOW(B²) ⊇ FOLLOW(B) FOLLOW(B³) ⊇ FOLLOW(B¹)
| |
| FOLLOW(B) = {z} FOLLOW(B¹) ⊇ FOLLOW(B³)
| |
| FOLLOW(B¹) = FOLLOW(B²) = FOLLOW(B³) = FOLLOW(B) = {z}
| |
| | |
| [[category:Compilers]]
| |
| [[category:Teaching]]
| |