(→Solution) |
|||
Line 14: | Line 14: | ||
= Solution = | = Solution = | ||
− | + | <text> | |
+ | Singularity M in S: | ||
+ | <text> | ||
+ | S → z y S x | x y S x | L y | ε | ||
+ | L → w L | S v | ||
+ | </text> | ||
+ | |||
+ | Non-terminal left-corner L in S (also: mutual recursion): | ||
+ | <text> | ||
+ | S → z y S x | x y S x | w L y | S v y | ε | ||
+ | L → w L | S v | ||
+ | </text> | ||
+ | |||
+ | Elimination of left recursion in S: | ||
+ | <text> | ||
+ | S → z y S x S' | x y S x S' | w L y S' | S' | ||
+ | S' → v y S' | ε | ||
+ | L → w L | S v | ||
+ | </text> | ||
+ | |||
+ | S' in S and S in L: | ||
+ | <text> | ||
+ | S → z y S x S' | x y S x S' | w L y S' | v y S' | ε | ||
+ | S' → v y S' | ε | ||
+ | L → w L | z y S x S' v | x y S x S' v | w L y S' v | v y S' v | v | ||
+ | </text> | ||
+ | |||
+ | Identifying common prefixes in L (final grammar form): | ||
+ | <text> | ||
+ | S → z y S x S' | x y S x S' | w L y S' | v y S' | ε 1|2|3|4|5 | ||
+ | S' → v y S' | ε 6|7 | ||
+ | L → w L L' | z y S x S' v | x y S x S' v | v L' 8|9|10|11 | ||
+ | L' → y S' v | ε 12|13 | ||
+ | </text> | ||
+ | |||
+ | FIRST and FOLLOW sets for the transformed grammar: | ||
+ | <text> | ||
+ | FIRST(S) = { v, w, x, z, ε } FOLLOW(S) = { $, x } | ||
+ | FIRST(S') = { v, ε } FOLLOW(S') = { $, v, x } | ||
+ | FIRST(L) = { v, w, x, z } FOLLOW(L) = { y } | ||
+ | FIRST(L') = { y, ε } FOLLOW(L') = { y } | ||
+ | </text> | ||
+ | |||
+ | Parse table (note the ambiguities): | ||
+ | <text> | ||
+ | | v | w | x | y | z | $ | | ||
+ | -------+-------+-------+-------+-------+-------+-------+ | ||
+ | S | 4 | 3 | 2/5 | | 1 | 5 | | ||
+ | S' | 6/7 | | 7 | | | 7 | | ||
+ | L | 10 | 11 | 9 | | 8 | | | ||
+ | L' | | | | 12/13 | | | | ||
+ | </text> | ||
+ | |||
+ | Input analysis: | ||
+ | <text> | ||
+ | STACK | INPUT | ACTION | ||
+ | --------------------------- | ||
+ | S$ | zyvyx$ | 1 | ||
+ | zySxS'$ | zyvyx$ | (z) | ||
+ | ySxS'$ | yvyx$ | (y) | ||
+ | SxS'$ | vyx$ | 4 | ||
+ | vyS'xS'$ | vyx$ | (v) | ||
+ | yS'xS'$ | yx$ | (y) | ||
+ | S'xS'$ | x$ | 7 | ||
+ | xS'$ | x$ | (x) | ||
+ | S'$ | $ | 7 | ||
+ | $ | $ | ACCEPT | ||
+ | </text> | ||
[[category:Teaching]] | [[category:Teaching]] | ||
[[category:Compilers]] | [[category:Compilers]] |
Contents |
Consider the following grammar, where S is the initial symbol and {v, w, x, y, z} is the set of terminal symbols:
S → M y S x | L y | ε L → w L | S v M → z | x
<text> Singularity M in S: <text> S → z y S x | x y S x | L y | ε L → w L | S v </text>
Non-terminal left-corner L in S (also: mutual recursion): <text> S → z y S x | x y S x | w L y | S v y | ε L → w L | S v </text>
Elimination of left recursion in S: <text> S → z y S x S' | x y S x S' | w L y S' | S' S' → v y S' | ε L → w L | S v </text>
S' in S and S in L: <text> S → z y S x S' | x y S x S' | w L y S' | v y S' | ε S' → v y S' | ε L → w L | z y S x S' v | x y S x S' v | w L y S' v | v y S' v | v </text>
Identifying common prefixes in L (final grammar form): <text> S → z y S x S' | x y S x S' | w L y S' | v y S' | ε 1|2|3|4|5 S' → v y S' | ε 6|7 L → w L L' | z y S x S' v | x y S x S' v | v L' 8|9|10|11 L' → y S' v | ε 12|13 </text>
FIRST and FOLLOW sets for the transformed grammar: <text> FIRST(S) = { v, w, x, z, ε } FOLLOW(S) = { $, x } FIRST(S') = { v, ε } FOLLOW(S') = { $, v, x } FIRST(L) = { v, w, x, z } FOLLOW(L) = { y } FIRST(L') = { y, ε } FOLLOW(L') = { y } </text>
Parse table (note the ambiguities): <text>
| v | w | x | y | z | $ |
S | 4 | 3 | 2/5 | | 1 | 5 | S' | 6/7 | | 7 | | | 7 | L | 10 | 11 | 9 | | 8 | | L' | | | | 12/13 | | | </text>
Input analysis: <text>
STACK | INPUT | ACTION
S$ | zyvyx$ | 1 zySxS'$ | zyvyx$ | (z) ySxS'$ | yvyx$ | (y) SxS'$ | vyx$ | 4
vyS'xS'$ | vyx$ | (v)
yS'xS'$ | yx$ | (y) S'xS'$ | x$ | 7 xS'$ | x$ | (x) S'$ | $ | 7 $ | $ | ACCEPT
</text>