换挡和前瞻之间的区别

Question

给出一个简单的语法,就像

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

转移前三个令牌,然后查看第四个令牌以查看要减少哪个规则,并简单地执行三个令牌的前瞻以查看要减少哪个规则之间有什么区别？

Answer 1

在shift/reduce解析器中,前瞻不用于确定正在考虑哪个生产,而是用于确定解析器是应该移动下一个令牌还是采取某种reduce操作.如果您有上述语法的shift/reduce解析器,解析器总是会在决定是否减少之前移动四个令牌; 请记住,在LR解析器中,仅当适当的符号系列位于解析堆栈顶部时才执行缩减.如果解析器无法判断它是否应该减少它所拥有的四个标记,或者继续移动更多符号并在以后减少,那么Lookahead只在这里是必要的.

具体来说,解析器可能会执行以下操作:

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解析器中,解析器通过检查更多令牌来工作,直到它看到它正在查找的内容变得舒适,然后减少(移位/减少解析).在这种情况下,根本不需要前瞻.Lookahead仅在LR解析器中需要确定解析器是否已经看到句柄的末尾(要减少的字符串),或者它是否在句柄的中间并且必须保持移位.这就是为什么,例如,一些有趣的语法可以显示为LR(0),但唯一的LL(0)语法是语法,其中每个非终结者只有一个与之相关的生成; 前瞻性在自上而下与自下而上的解析中有着根本不同的用途.

一般来说,自上而下的解析器可以处理比自下而上的解析器更少的语法,实际上任何LL(k)语法都保证是LR(k),但不是相反.

希望这可以帮助!