(→Solution) |
(→Solution) |
||
Line 36: | Line 36: | ||
B -> v u E B1 | v x u E B1 | B -> v u E B1 | v x u E B1 | ||
B1 -> v B1 | y E B1 | ε | B1 -> v B1 | y E B1 | ε | ||
+ | E -> v | v x | ||
Factoring... | Factoring... | ||
Line 43: | Line 44: | ||
B1 -> v B1 | y E B1 | ε | B1 -> v B1 | y E B1 | ε | ||
B2 -> u E B1 | x u E B1 | B2 -> u E B1 | x u E B1 | ||
+ | E -> v E1 | ||
+ | E1 -> x | ε | ||
The FIRST and FOLLOW sets are as follows: | The FIRST and FOLLOW sets are as follows: | ||
Line 50: | Line 53: | ||
FIRST(B1) = FIRST(v B1) ∪ FIRST(y E B1) ∪ {ε} = {v, y, ε} | FIRST(B1) = FIRST(v B1) ∪ FIRST(y E B1) ∪ {ε} = {v, y, ε} | ||
FIRST(B2) = FIRST(u E B1) ∪ FIRST(x u E B1) = {u, x} | FIRST(B2) = FIRST(u E B1) ∪ FIRST(x u E B1) = {u, x} | ||
+ | FIRST(E) = FIRST(v E1) = {v} | ||
+ | FIRST(E1) = {x} ∪ {ε} = {x, ε} | ||
− | FOLLOW(S) = {$} FOLLOW(B1) ⊇ FOLLOW(B2) | + | FOLLOW(S) = {$} FOLLOW(B) = {z} FOLLOW(B1) ⊇ FOLLOW(B2) FOLLOW(B2) ⊇ FOLLOW(B) |
− | |||
− | |||
FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B) = {z} | FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B) = {z} | ||
+ | FOLLOW(E) = FIRST(B1)\{ε} ∪ FOLLOW(B1) ∪ FOLLOW(B2) = {v, y, z} | ||
+ | FOLLOW(E1) = FOLLOW(E) = {v, y, z} | ||
[[category:Compilers]] | [[category:Compilers]] | ||
[[category:Teaching]] | [[category:Teaching]] |
Consider the following grammar, where S is the initial symbol and {u,v,x,y,z} 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
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 D -> E u E | B y E E -> v | v x
Now we handle the left corner (E in B) (since E is not completely replaced, it cannot be removed from the grammar):
S -> u B z B -> B v | v u E | v x u E | B y E E -> v | v x
Now, left recursion can be eliminated:
S -> u B z B -> v u E B1 | v x u E B1 B1 -> v B1 | y E B1 | ε E -> v | v x
Factoring...
S -> u B z B -> v B2 B1 -> v B1 | y E B1 | ε B2 -> u E B1 | x u E B1 E -> v E1 E1 -> x | ε
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 E B1) ∪ {ε} = {v, y, ε} FIRST(B2) = FIRST(u E B1) ∪ FIRST(x u E B1) = {u, x} FIRST(E) = FIRST(v E1) = {v} FIRST(E1) = {x} ∪ {ε} = {x, ε}
FOLLOW(S) = {$} FOLLOW(B) = {z} FOLLOW(B1) ⊇ FOLLOW(B2) FOLLOW(B2) ⊇ FOLLOW(B) FOLLOW(B1) = FOLLOW(B2) = FOLLOW(B) = {z} FOLLOW(E) = FIRST(B1)\{ε} ∪ FOLLOW(B1) ∪ FOLLOW(B2) = {v, y, z} FOLLOW(E1) = FOLLOW(E) = {v, y, z}