java - 对令牌的语法限制前瞻

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)文法的一个示例，因为解析器无法根据单个标记决定使用哪个产生式。（取自这里。）