LL(1) 解析器需要一个前瞻符号才能决定使用哪个产生式。这就是为什么我一直认为使用术语“前瞻”的原因,当解析器查看下一个输入标记而不“消耗”它时(即它仍然可以通过下一个操作从输入中读取)。然而,LR(0) 解析器让我怀疑这是正确的:
我见过的每个 LR(0) 解析器示例也使用下一个输入标记来决定是移位还是减少。在减少的情况下,不消耗输入令牌。
我使用免费软件工具“ParsingEmu”生成 LR 表并在下面对“aab”一词执行 LR 评估。如您所见,列标题包含标记。从评估中,您可以看到解析器通过查看下一个输入标记来决定使用哪一列。但是当解析器在步骤 4 - 6 中减少时,输入不会改变(尽管解析器在执行到下一个状态的转换时需要知道下一个输入标记“$”)。
语法:
S -> A
A -> aA
A -> b
桌子:
评估:
由于我的困惑,现在我做了以下假设:
我对“前瞻”定义的假设(前瞻 = 未使用输入令牌)是错误的。对于 LL 解析器或 LR 解析器,前瞻只是意味着两种不同的东西。如果是这样,那么如何定义“前瞻”呢?
LR 解析器(从理论的角度来看,当您使用下推自动机时)具有额外的内部状态,它们通过将输入标记放在堆栈上来消耗输入标记,因此只需查看即可做出移位减少决策在堆栈上。
上面显示的评估是 LR(1)。如果为真,LR(0) 评估会是什么样子?
现在什么是正确的,1、2 或 3 还是完全不同的?