7

给定一个简单的语法，比如

rule1
    := token1 token2 token3 token4
    || token1 token2 token3 token3;

移动前三个标记，然后查看第四个标记以查看要减少的规则，以及简单地执行三个标记的前瞻以查看要减少的规则有什么区别？

4

1 回答 1

9

在移位/归约解析器中，前瞻不用于确定正在考虑哪个产生式，而是用于决定解析器是否应该移动下一个标记或采取某种归约动作。如果您有上述语法的移位/归约解析器，解析器总是会在决定是否归约之前移动四个标记；请记住，在 LR 解析器中，仅当适当的符号系列位于解析堆栈顶部时才执行归约。只有当解析器无法判断它是否应该减少它拥有的四个标记或继续移动更多符号并在以后减少时，这里才需要前瞻。

具体来说，解析器可能会做这样的事情：

Stack                           Input                        Action
-------------------------------------------------------------------------------
                                token1 token2 token3 token4  Shift
token1                                 token2 token3 token4  Shift
token1 token2                                 token3 token4  Shift
token1 token2 token3                                 token4  Shift
token1 token2 token3 token4                                  Reduce, Option 1
rule1                                                        Accept

或者

Stack                           Input                        Action
-------------------------------------------------------------------------------
                                token1 token2 token3 token3  Shift
token1                                 token2 token3 token3  Shift
token1 token2                                 token3 token3  Shift
token1 token2 token3                                 token3  Shift
token1 token2 token3 token3                                  Reduce, Option 2
rule1                                                        Accept

请注意，这与像 LL(k) 解析器这样的自顶向下解析器形成对比，后者通过尝试预测要使用的产生式来工作。在这种情况下，将需要四个前瞻标记，因为解析器正在猜测产生式，然后检查其猜测（预测/匹配解析）。例如，在自上而下的解析器（这里必须是 LL(4)）中，它会执行以下操作：

Stack                           Input                             Action
----------------------------------------------------------------------------------
rule1                           token1 token2 token3 token4 $$$$  Predict, Option 1
token1 token2 token3 token4     token1 token2 token3 token4 $$$$  Match
token2 token3 token4            token2 token3 token4 $$$$         Match
token3 token4                   token3 token4 $$$$                Match
token4                          token4 $$$$                       Match
                                $$$$                              Accept

或者

Stack                           Input                             Action
----------------------------------------------------------------------------------
rule1                           token1 token2 token3 token3 $$$$  Predict, Option 2
token1 token2 token3 token3     token1 token2 token3 token3 $$$$  Match
token2 token3 token3            token2 token3 token3 $$$$         Match
token3 token3                   token3 token3 $$$$                Match
token3                          token3 $$$$                       Match
                                $$$$                              Accept

请注意如何需要先行来预测要使用的产生式，因此解析器必须有四个先行标记。在 LR 解析器中，解析器通过检查更多标记来工作，直到它可以看到它正在寻找的内容，然后减少（移位/减少解析）。在这种情况下，根本不需要前瞻。仅在 LR 解析器中需要先行来确定解析器是否已经看到句柄的结尾（要归约的字符串），或者它是否在句柄的中间并且必须不断移动。这就是为什么，例如，一些有趣的文法可以显示为 LR(0)，但唯一的文法是 LL(0)，其中每个非终结符都有一个与之相关的产生式。前瞻在自上而下和自下而上的解析中有着根本不同的用途。

一般来说，自顶向下解析器可以处理的语法比自底向上解析器要少，实际上任何 LL(k) 语法都保证为 LR(k)，但反之则不行。

希望这可以帮助！

于 2011-12-13T00:00:10.613 回答