|
|
| (9 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == Problem ==
| | #REDIRECT [[ist:Top-Down Parsing/Example 2]] |
| | |
| Consider the following grammar, where '''<tt>S</tt>''' is the initial symbol and '''<tt>{d,e,f,g,h}</tt>''' is the set of terminal symbols:
| |
| | |
| S -> A B d | C d
| |
| A -> C d h | S e
| |
| C -> g B | h f
| |
| B -> g | ε
| |
| | |
| # 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>hfded</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 S and A. Also, there are left corners that may hide ambiguity (C).
| |
| | |
| The first step, then, is to rewrite the grammar so that multual recursion is eliminated (A becomes unreachable and can be removed from the grammar):
| |
| | |
| S -> C d h B d | S e B d | C d
| |
| <font color="red">A -> C d h | S e</font>
| |
| C -> g B | h f
| |
| B -> g | ε
| |
| | |
| Now we handle the left corner (C in S) (C also becomes unreachable and can be removed from the grammar):
| |
| | |
| S -> g B d h B d | h f d h B d | S e B d | g B d | h f d
| |
| <font color="red">C -> g B | h f</font>
| |
| B -> g | ε
| |
| | |
| Now, left recursion can be eliminated:
| |
| | |
| S -> g B d h B d S' | h f d h B d S' | g B d S' | h f d S'
| |
| S' -> e B d S' | ε
| |
| B -> g | ε
| |
| | |
| Factoring...
| |
| | |
| S -> g B d S" | h f d S"
| |
| S' -> e B d S' | ε
| |
| S" -> h B d S' | S'
| |
| B -> g | ε
| |
| | |
| Removing the left corner S' from S":
| |
| | |
| S -> g B d S" | h f d S"
| |
| S' -> e B d S' | ε
| |
| S" -> h B d S' | e B d S' | ε
| |
| B -> g | ε
| |
| | |
| The FIRST and FOLLOW sets are as follows:
| |
| | |
| FIRST(S) = FIRST(g B d S") ∪ FIRST(h f d S") = {g, h}
| |
| FIRST(S') = FIRST(e B d S') ∪ {ε} = {e, ε}
| |
| FIRST(S") = FIRST(h B d S') ∪ FIRST(e B d S') ∪ {ε} = {e, h, ε}
| |
| FIRST(B) = FIRST(g) ∪ {ε} = {g, ε}
| |
| | |
| FOLLOW(S) = {$}
| |
| FOLLOW(S') ⊇ FOLLOW(S") ⊇ FOLLOW(S)
| |
| FOLLOW(S') = FOLLOW(S") = {$}
| |
| FOLLOW(B) = {d}
| |
| | |
| | |
| [[category:Compilers]]
| |
| [[category:Teaching]]
| |