生成等效的 LL(1) 语言

Question

我需要将上下文无关文法 G 转换为 LL(1) 类型的等效文法，但我无法满足该文法属于 LL(1) 类型的条件。我已经执行了左分解和左递归删除，但这还不够。我该如何解决这个问题？

G: S -> a Y | ( S ) Y | u Y | v Y | z S Y

Y -> Z S | epsilon 

Z -> b S | c S 

我计算了每个非终结符的 FIRST 和 FOLLOW 并构建了解析表，但结果发现在单元格 [Y,b] 和 [Y,c] 中有两个产生式，具体为

Y -> Z Y

、

Y -> epsilon

Answer 1

鉴于：

S -> a Y
   | ( S ) Y
   | u Y 
   | v Y
   | z S Y

Y -> Z S
   | epsilon

Z -> b S 
   | c S

没有理由认为它不是 LL(1)。

对

Y

派生

epsilon

的担忧通过观察到

Y

只出现在产生式中最右边的符号而得到缓解。因此，我们知道

FOLLOW(Y)

是

{ EOF }

。

我们可以计算所有的集合：

FIRST(a Y) = { a }
FIRST(( s ) Y) = { ( }
FIRST(u Y) = { u }
FIRST(v Y) = { v }
FIRST(z S Y) = { z }

FIRST(Z S) = { b, c }
FIRST(epsilon) = { epsilon }

FIRST(b S) = { b }
FIRST(c S) = { c }

FOLLOW(S) = { ), b, c, EOF }
FOLLOW(Y) = { EOF }
FOLLOW(Z) = { a, (, u, v, z }

那么预测解析器表看起来就干净了：

     (           a       b       c      u       v       z         EOF
  +-----------+-------+-------+-------+-------+-------+---------+---------+
S |  ( S ) Y  |  a Y  |       |       |  u Y  |  v Y  |  z S Y  |         |
  +-----------+-------+-------+-------+-------+-------+---------+---------+
Y |           |       |  Z S  |  Z S  |       |       |         | epsilon |
  +-----------+-------+-------+-------+-------+-------+---------+---------+
Z |           |       |  b S  |  c S  |       |       |         |         |
  +-----------+-------+-------+-------+-------+-------+---------+---------+

解析器仅在面对

Y

时遵循

EOF

的 epsilon 规则。