java - token 向前看的语法限制

Question

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

1. 文法不能有任何左递归产生式
2. 语法不能要求超过标记前瞻。

我理解第一个限制，但对第二个限制有点迷茫。为什么这种限制是必要的，没有它生产还能存在吗？

Answer 1

通过要求解析器可以根据前 k 标记(而不是基于单个标记)来决定使用哪个产生式，可以稍微放宽第二个限制。这允许针对此类语法的高效(即线性时间)解析算法(参见 Recursive descent parser)。

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

由产生式 S -> A | 组成的文法B, A -> a A b | eps 和 B -> a B b b | eps 是一个非歧义非LL(1) 语法的示例，因为解析器无法根据单个标记决定使用哪个产生式。 (取自 here 。)