象征性前瞻的语法限制

Question

我知道对递归下降语法分析器使用的语法有两种类型的限制。

1. 语法不能有任何左递归生成
2. 语法要求的内容不能超过"向前看"

我理解第一个限制，但对第二个限制有点不知所措。为什么这种限制是必要的，没有它生产也能存在？

Answer 1

第二个限制可以通过要求解析器可以基于第一个k令牌（而不是基于单个令牌）来决定使用哪个产品来有所放宽。这为这类语法提供了高效的（即线性时间）解析算法（请参阅递归下降语法分析器）。

在实践中选择k=1的主要原因似乎是LL(1)语法的解析器更容易构建。显然，许多计算机语言都是由LL(1)语法生成的。请参阅LL解析器。

由生成S -> A | B、A -> a A b | eps和B -> a B b b | eps组成的语法是非歧义非LL(1)语法的一个示例，因为解析器不能基于单个令牌来决定使用哪个生成。（取自此处。）