(→Solution) |
|||
Line 15: | Line 15: | ||
Singularity M in S: | Singularity M in S: | ||
− | + | ||
− | S → z y S x | x y S x | L y | ε | + | S → z y S x | x y S x | L y | ε |
− | L → w L | S v | + | L → w L | S v |
− | |||
Non-terminal left-corner L in S (also: mutual recursion): | 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 | ε | |
− | S → z y S x | x y S x | w L y | S v y | ε | + | L → w L | S v |
− | L → w L | S v | ||
− | |||
Elimination of left recursion in S: | Elimination of left recursion in S: | ||
− | + | S → z y S x S' | x y S x S' | w L y S' | S' | |
− | S → z y S x S' | x y S x S' | w L y S' | S' | + | S' → v y S' | ε |
− | S' → v y S' | ε | + | L → w L | S v |
− | L → w L | S v | ||
− | |||
S' in S and S in L: | 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 → z y S x S' | x y S x S' | w L y S' | v y S' | ε | + | 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 |
− | 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): | 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 → 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 |
− | 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 → 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 |
− | L' → y S' v | ε 12|13 | ||
− | |||
FIRST and FOLLOW sets for the transformed grammar: | FIRST and FOLLOW sets for the transformed grammar: | ||
− | + | FIRST(S) = { v, w, x, z, ε } FOLLOW(S) = { $, x } | |
− | FIRST(S) = { v, w, x, z, ε } FOLLOW(S) = { $, x } | + | FIRST(S') = { v, ε } FOLLOW(S') = { $, v, x } |
− | FIRST(S') = { v, ε } FOLLOW(S') = { $, v, x } | + | FIRST(L) = { v, w, x, z } FOLLOW(L) = { y } |
− | FIRST(L) = { v, w, x, z } FOLLOW(L) = { y } | + | FIRST(L') = { y, ε } FOLLOW(L') = { y } |
− | FIRST(L') = { y, ε } FOLLOW(L') = { y } | ||
− | |||
Parse table (note the ambiguities): | Parse table (note the ambiguities): | ||
− | <text> | + | <source lang="text"> |
| v | w | x | y | z | $ | | | v | w | x | y | z | $ | | ||
-------+-------+-------+-------+-------+-------+-------+ | -------+-------+-------+-------+-------+-------+-------+ | ||
Line 64: | Line 53: | ||
L | 11 | 8 | 10 | | 9 | | | L | 11 | 8 | 10 | | 9 | | | ||
L' | | | | 12/13 | | | | L' | | | | 12/13 | | | | ||
− | </ | + | </source> |
Input analysis: | Input analysis: | ||
− | <text> | + | <source lang="text"> |
STACK | INPUT | ACTION | STACK | INPUT | ACTION | ||
--------------------------- | --------------------------- | ||
Line 80: | Line 69: | ||
S'$ | $ | 7 | S'$ | $ | 7 | ||
$ | $ | ACCEPT | $ | $ | ACCEPT | ||
− | </ | + | </source> |
[[category:Compiladores]] | [[category:Compiladores]] | ||
[[category:Ensino]] | [[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