(6 intermediate revisions by the same user not shown) | |||
Line 14: | Line 14: | ||
= Solution = | = Solution = | ||
− | + | Singularity M in S: | |
− | [[category: | + | S → z y S x | x y S x | L y | ε |
− | [[category: | + | L → w L | S v |
+ | |||
+ | Non-terminal left-corner L in S (also: mutual recursion): | ||
+ | S → z y S x | x y S x | w L y | S v y | ε | ||
+ | L → w L | S v | ||
+ | |||
+ | Elimination of left recursion in S: | ||
+ | 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 | ||
+ | |||
+ | S' in S and S in L: | ||
+ | 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 | ||
+ | |||
+ | Identifying common prefixes in L (final grammar form): | ||
+ | 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 | ||
+ | |||
+ | FIRST and FOLLOW sets for the transformed grammar: | ||
+ | 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 } | ||
+ | |||
+ | Parse table (note the ambiguities): | ||
+ | <source lang="text"> | ||
+ | | v | w | x | y | z | $ | | ||
+ | -------+-------+-------+-------+-------+-------+-------+ | ||
+ | S | 4 | 3 | 2/5 | | 1 | 5 | | ||
+ | S' | 6/7 | | 7 | | | 7 | | ||
+ | L | 11 | 8 | 10 | | 9 | | | ||
+ | L' | | | | 12/13 | | | | ||
+ | </source> | ||
+ | |||
+ | Input analysis: | ||
+ | <source lang="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 | ||
+ | </source> | ||
+ | |||
+ | [[category:Compiladores]] | ||
+ | [[category:Ensino]] |
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
Singularity M in S:
S → z y S x | x y S x | L y | ε L → w L | S v
Non-terminal left-corner L in S (also: mutual recursion):
S → z y S x | x y S x | w L y | S v y | ε L → w L | S v
Elimination of left recursion in S:
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
S' in S and S in L:
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
Identifying common prefixes in L (final grammar form):
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
FIRST and FOLLOW sets for the transformed grammar:
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 }
Parse table (note the ambiguities):
| v | w | x | y | z | $ |
-------+-------+-------+-------+-------+-------+-------+
S | 4 | 3 | 2/5 | | 1 | 5 |
S' | 6/7 | | 7 | | | 7 |
L | 11 | 8 | 10 | | 9 | |
L' | | | | 12/13 | | |
Input analysis:
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