(→Expanding G in F) |
(→Expanding G in F) |
||
Line 46: | Line 46: | ||
F -> a c F" | b F' | F -> a c F" | b F' | ||
F' -> c b F' | (eps) | F' -> c b F' | (eps) | ||
− | F | + | F" -> d b F' | F e F' |
Note that we still have common prefixes to factor in G and a non-terminal left-corner in F''. The next step will handle those cases: | Note that we still have common prefixes to factor in G and a non-terminal left-corner in F''. The next step will handle those cases: | ||
Line 53: | Line 53: | ||
G' -> F" c | d | G' -> F" c | d | ||
F' -> c b F' | (eps) | F' -> c b F' | (eps) | ||
− | F | + | F" -> d b F' | a c F" e F' | b F' e F' |
F was eliminated because it became unreachable from the start symbol. The grammar still has a non-terminal left corner in G', so we need to eliminate it. | F was eliminated because it became unreachable from the start symbol. The grammar still has a non-terminal left corner in G', so we need to eliminate it. | ||
Line 60: | Line 60: | ||
G' -> d b F' c | a c F" e F' c | b F' e F' c | d | G' -> d b F' c | a c F" e F' c | b F' e F' c | d | ||
F' -> c b F' | (eps) | F' -> c b F' | (eps) | ||
− | F | + | F" -> d b F' | a c F" e F' | b F' e F' |
Factoring prefixes in G', we get to the final version: | Factoring prefixes in G', we get to the final version: | ||
Line 68: | Line 68: | ||
G'' -> b F' c | (eps) | G'' -> b F' c | (eps) | ||
F' -> c b F' | (eps) | F' -> c b F' | (eps) | ||
− | F | + | F" -> d b F' | a c F" e F' | b F' e F' |
[[category:Compilers]] | [[category:Compilers]] | ||
[[category:Teaching]] | [[category:Teaching]] |
Consider the following grammar, where F is the initial symbol and {a,b,c,d,e} is the set of terminal symbols:
O -> a G -> F c | O c d | (eps) F -> G b | O c F e
Something to keep in mind at all times: never eliminate the rules corresponding to the initial symbol
There are two ways of handling the mutual recursion: either expand F in G or G in F.
Initial grammar:
O -> a G -> F c | O c d | (eps) F -> G b | O c F e
Eliminating the singularity (O->a):
G -> F c | a c d | (eps) F -> G b | a c F e
Expanding G in F:
G -> F c | a c d | (eps) F -> F c b | a c d b | b | a c F e
Eliminate left recursion in F:
G -> F c | a c d | (eps) F -> a c d b F' | b F' | a c F e F' F' -> c b F' | (eps)
Factor F prefixes and expand it in G:
G -> a c F" c | b F' c | a c d | (eps) F -> a c F" | b F' F' -> c b F' | (eps) F" -> d b F' | F e F'
Note that we still have common prefixes to factor in G and a non-terminal left-corner in F. The next step will handle those cases:
G -> a c G' | b F' c | (eps) G' -> F" c | d F' -> c b F' | (eps) F" -> d b F' | a c F" e F' | b F' e F'
F was eliminated because it became unreachable from the start symbol. The grammar still has a non-terminal left corner in G', so we need to eliminate it.
G -> a c G' | b F' c | (eps) G' -> d b F' c | a c F" e F' c | b F' e F' c | d F' -> c b F' | (eps) F" -> d b F' | a c F" e F' | b F' e F'
Factoring prefixes in G', we get to the final version:
G -> a c G' | b F' c | (eps) G' -> d G" | a c F" e F' c | b F' e F' c G -> b F' c | (eps) F' -> c b F' | (eps) F" -> d b F' | a c F" e F' | b F' e F'