(→Expanding G in F) |
(→Expanding G in F) |
||
Line 66: | Line 66: | ||
G -> a c G' | b F' c | (eps) | G -> a c G' | b F' c | (eps) | ||
G' -> d G" | a c F" e F' c | b F' e F' c | G' -> d G" | a c F" e F' c | b F' e F' c | ||
− | G | + | G" -> b F' c | (eps) |
F' -> c b F' | (eps) | F' -> c b F' | (eps) | ||
F" -> d b F' | a c F" e F' | b F' e F' | F" -> d b F' | a c F" e F' | b F' e F' |
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'