parsing - 为什么最多向前查看 1 个输入标记？

Question

我目前正在尝试实现 LL 解析器，但我有一个问题。 我需要最多向前查看 1 个输入 token 来验证用户的输入是否正确 语法正确还是有其他原因？

Answer 1

有许多不同种类的解析算法。您所描述的称为 LL(1)，根据定义，它仅使用一个前瞻标记。然而，还有其他解析算法使用比这更多的前瞻。例如，LL(2) 解析器使用两个先行标记，而 LL(*) 解析器具有无界先行。对于某些语法，一个先行标记是不够的(即，属于 LL(2) 但不是 LL(1) 的语法)。这是一个例子:

S → n | n + S

尝试找出为什么一个先行标记还不够，但两个标记就足够了。

解析算法尝试保持低先行标记数量的原因是为了简单性和效率。随着先行标记数量的增加，驱动解析器所需的解析表的大小也会增加，构建这些表的复杂性也会增加。