|
|
| (14 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' | ε
| |
| | |
| [[category:Compilers]]
| |
| [[category:Teaching]]
| |