(→Solution) |
(→Solution) |
||
Line 53: | Line 53: | ||
B³ -> v B¹ | y v B³ | 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: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) (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 E -> v | v x
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}