如何简化递归下降语法分析器

Question

我有以下简单的LL(1(语法，它描述了一种只有三个有效句子的语言：""、"x y"和"z x y":

S -> A x y | ε .
A -> z | ε .

我构建了下面的解析表；天真的"；递归下降解析器：

| x          | y | z          | $
S | S -> A x y |   | S -> A x y | S -> ε
A | A -> ε     |   | A -> z     |
func S():
if next() in ['x', 'z']:
A()
expect('x')
expect('y')
expect('$')
elif next() == '$':
pass
else:
error()
func A():
if next() == 'x':
pass
elif next() == 'z':
expect('z')
else:
error()

然而，函数A似乎比必要的更复杂。如果简化为：，我所有的测试仍然通过

func A():
if next() == 'z':
expect('z')

这是对A的有效简化吗？如果是这样的话，对于什么时候进行这样的简化是有效的，有什么通用规则吗？

Answer 1

这种简化当然是有效的(而且非常常见(。

主要区别在于没有与生产A相关的代码→ε。如果有一些语义需要实现，则需要测试条件。如果您只需要忽略可为null的生产，那么您当然可以直接返回。

合并错误和epsilon乘积还有另一个区别：错误(例如，在输入y中(稍后在A()返回后检测到。有时这会使生成好的错误消息变得更加困难(有时则不然(。