移位和向前看的区别

Question

给出一个简单的语法，如

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

移动前三个令牌，然后查看第四个以查看要减少哪个规则，与简单地提前执行三个令牌以查看要减少哪个规则之间的区别是什么?

Answer 1

在shift/reduce解析器中，前瞻不是用来确定正在考虑哪个结果，而是用来决定解析器是应该移动下一个令牌还是采取某种reduce操作。如果你有一个针对上述语法的shift/reduce解析器，解析器在决定是否减少之前总是会移动四个标记;请记住，在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解析器中，解析器通过检查更多的令牌来工作，直到它确定看到了要查找的内容，然后减少(shift/reduce解析)。在这种情况下，根本不需要前瞻性。只有在LR解析器中需要向前看，以确定解析器是否已经看到句柄的末尾(要减少的字符串)，或者它是否在句柄的中间并且必须继续移动。这就是为什么，例如，一些有趣的语法可以显示为LR(0)，但唯一显示为LL(0)的语法是每个非终结符只有一个与之相关的结果的语法;在自顶向下和自底向上解析中，前瞻具有根本不同的用途。

一般来说，自顶向下解析器可以处理的语法比自底向上解析器处理的语法少，事实上，任何LL(k)语法都保证是LR(k)，而不是LR(k)。

希望这对你有帮助!