(→ELimination of Mutual Recursion: Expanding F in G) |
(→Elimination of Mutual Recursion: Expanding F in G) |
||
Line 126: | Line 126: | ||
F' -> a c F' e F" | b F" e F" | d G' b | F' -> a c F' e F" | b F" e F" | d G' b | ||
F" -> c G' b | (eps) | F" -> c G' b | (eps) | ||
+ | |||
+ | === FIRST & FOLLOW sets === | ||
+ | |||
+ | FIRST(G) = { a, b, (eps) } | ||
+ | FIRST(G') = { b, (eps) } | ||
+ | FIRST(G") = { a, b, d } | ||
+ | FIRST(F') = { a, b, d } | ||
+ | FIRST(F") = { c, (eps) } | ||
+ | |||
+ | FOLLOW(G) = { $ } | ||
+ | FOLLOW(G') = { $, b } | ||
+ | FOLLOW(G") = { $ } | ||
+ | FOLLOW(F') = { e } | ||
+ | FOLLOW(F") = { e } | ||
[[category:Compilers]] | [[category:Compilers]] | ||
[[category:Teaching]] | [[category:Teaching]] |
Consider the following grammar, where G 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
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 F in G:
G -> G b c | a c F e c | a c d | (eps) F -> G b | a c F e
Eliminating left recursion in G:
G -> a c F e c G' | a c d G' | G' G' -> b c G' | (eps) F -> G b | a c F e
Factoring G prefixes:
G -> a c G" | b c G' | (eps) G' -> b c G' | (eps) G" -> F e c G' | d G' F -> a c G" b | b c G' b | b | a c F e
Factoring F prefixes:
G -> a c G" | b c G' | (eps) G' -> b c G' | (eps) G" -> F e c G' | d G' F -> a c F' | b F" F' -> G" b | F e F" -> c G' b | (eps)
Eliminating non-terminal left corners (note that F becomes unreachable):
G -> a c G" | b c G' | (eps) G' -> b c G' | (eps) G" -> a c F' e c G' | b F" e c G' | d G' F' -> a c F' e c G' b | b F" e c G' b | d G' b | a c F' e | b F" e F" -> c G' b | (eps)
Factoring F' prefixes, we get to the final version:
G -> a c G" | b c G' | (eps) G' -> b c G' | (eps) G" -> a c F' e c G' | b F" e c G' | d G' F' -> a c F' e F" | b F" e F" | d G' b F" -> c G' b | (eps)
FIRST(G) = { a, b, (eps) } FIRST(G') = { b, (eps) } FIRST(G") = { a, b, d } FIRST(F') = { a, b, d } FIRST(F") = { c, (eps) }
FOLLOW(G) = { $ } FOLLOW(G') = { $, b } FOLLOW(G") = { $ } FOLLOW(F') = { e } FOLLOW(F") = { e }