LR算法中反向最右推导（Reverse RightMost Derivation）

概述最右(Rightmost)指的是在推导中总是选择扩展最右边的非终结符。这种推导方式产生的是最右推导反向(Reverse): 这指的是在归约过程中做的事恰好是最右推导的逆过程简单来说LR分析器通过模拟最右推导的逆过程来进行语法分析例子使用一个非常简单的文法来描述“括号内包含一个标识符”的概念S - (S) S - id目标 分析输入字符串( id )第1步构造一个“最右推导”(Rightmost Derivation)要理解LR 分析器在做什么首先需要知道一个“正确”的句子是如何通过最右推导产生的从开始符号S开始查看当前字符串并选择最右边的非终结符进行扩展应用规则: S - (S)推导序列: S - (S)现在字符串 S. 最右边的非终结符是 S应用规则 S - id推导序列S - ( S ) - ( id )所以最右推荐导序列是: S - ( S ) - ( id )LR分析器的“反向”归约Reverse ReductionLR 分析器的工作方式与推导完全相反。它从输入字符串开始不断地将右侧符号(根据文法规则) 归约 为左侧的非终结符直到最终归约为开始符号 S它使用一个栈和一个状态机来跟踪当前的位置。下面模拟一个简化的LR分析过程重点关注栈的内容的归约工作输入流: ( id )步骤栈内容 (底部 - 顶部)输入流动作解释1[ ]( id )初始状态栈为空。2[ ( ]id )移入 将 ( 从输入流移入栈顶3[ (, id ])移入 将 id 移入栈顶4[ (, S ])归约 栈顶的 id 匹配了规则 S - id 的右侧。我们将 id 归约为 S。 (注意这对应了最右推导的最后一步 ( S ) ( id ) 的逆过程)5[ (, S, ) ]$ (结束符)移入 将 ) 移入栈顶6[ S ]$归约 栈顶的 ( S ) 匹配了规则 S - ( S ) 的右侧。我们将 ( S ) 归约为 S。 (注意这对应了最右推导的第一步 S ( S ) 的逆过程)7接受栈顶是开始符号 S输入流已结束分析成功关键对比与解释现在我们把两个过程放在一起看方向过程步骤序列正向最右推导 (人类编写句子的思维)S ( S ) ( id )反向LR归约 (分析器理解句子的思维)( id ) ( S ) S“最右”体现在哪里在最右推导 S ( S ) ( id ) 中第二步我们选择扩展的是第二个 S它是当时最右边的非终结符在LR分析器中我们最先归约的就是这个最后被扩展出来的部分 idLR分析器总是能找到并归约那个“句柄”而这个“句柄”正是在最右推导中最后被生成的那个子串“反向”体现在哪里LR分析器的归约步骤序列 ( id ) - ( S ) - S恰好是最右推导序列 S - ( S ) - ( id ) 的逆序结论所以“R代表反向Reverse和最右Rightmost” 这句话的含义是LR分析器通过构造一个自动机来识别并逆向遍历输入串所对应的最右推导步骤从而完成语法分析最右 定义了分析器所遵循的语法模型最右推导规范反向 定义了分析器的工作方式从句子归约到开始符号