# 语法分析-自底向上 使用最左规约（最右推导，与自顶向下的最左推导相反）方式，将输入串w归约为文法开始符号S的过程 ## 移入-归约分析（Shift-Reduce Parsing）  简单的移入-规约分析不能解决许多问题，最典型的就是无法区分最长匹配和较短的匹配。因此引入LR分析。 ## LR分析过程简述   - 首先准备两个平行栈，分别压入状态序号和文法符号（称为S栈和X栈），以及两个以状态枚举为行，分别以终结符和非终结符枚举为列的表格（称为ACTION表和GOTO表） - 状态机从状态0开始，对一个输入符号串进行语法分析 - 在每个时刻，**检测ACTION表中S栈顶对应状态行，输入缓冲区的下一个符号α对应列的值**： - 如果为`s[i]`，则执行 - **移入 α** - **然后进入第`i`状态** - 如果为`r[i]`，则执行 - **按照第`i`号产生式进行归约，从X栈顶弹出对应产生式右部的元素，并从S栈顶平行弹出对应个数元素** - **然后将产生式左部（一个非终结符）压入X栈** - **将GOTO表中新的S栈顶对应状态行，产生式左部对应列的值（代表状态序号）压入S栈** - 如果为`acc`，则表明已接收（accept）该输入串 - 如果为空或`e[i]`，则说明出错，可执行第`i`个错误处理例程 ## LR(0)分析 不关注后续符号，只关注当前符号。以产生式右部中插入的一个圆点（·）表示当前状态对应的位置，称为LR(0)项目： ### LR(0)项目  ### 增广文法 LR分析一般都使用一种增广文法，即在以原文法的初始符号S为左部的产生式不唯一时，定义一个新初始符号S'，S'只有唯一一个产生式即S'→S。这样保证了最终接收状态具有确定性。 ### 后继项目 圆点后移一位即成后继项目，例：S→a·b是S→·ab的后继项目 ### 等价项目和项目集闭包 所有等待一个非终结符（即·后跟非终结符）的待约项目，都与任意以该非终结符为左部的移进项目等价。如S→a·A等价于A→·a等价于A→·B，又等价于B→·b，它们实际上代表同一个状态（但等待的状态转移可能不同）。 一组无遗漏的等价项目集构成一个项目集闭包，称为I，其直接成为状态机的一个状态。 ### 画出LR(0)状态机图并构造分析表 - 从初始符号所在的项目集开始，依次将各个项目集闭包推导出来，并列出其状态转移条件，可得一个不完整的状态机图（缺少归约操作的状态转移弧） - 再根据状态转移条件，分为两大类：由终结符触发状态转移的，为ACTION类转移，而由非终结符的，为GOTO类转移 - 对ACTION类状态转移，以如下方式填充ACTION表： - 在原状态行、触发终结符对应列上填入`s[目标状态序号]` - 若目标状态的闭包中仅含有归约项目，再额外填充： - 若不归约到初始符号S'，则在ACTION表的目标状态行、全部列上填入`r[归约生成式序号]` - 若归约到初始符号S'，则在ACTION表的目标状态行、`$`列上填入`acc` - 对GOTO类状态转移，以如下方式填充GOTO表： - 在原状态行、触发非终结符对应列上填入`目标状态序号` - 如此即得到LR(0)分析表  ### LR(0)的局限性 LR(0)分析法，在一些文法中会产生 移进-归约冲突 和 归约-归约冲突： - 移进-归约冲突：在同一个闭包中同时存在归约项目和非归约项目 - 归约-归约冲突：在同一个闭包中同时存在归约到不同非终结符的归约项目 恰好不产生以上冲突的文法，可称LR(0)文法 ## SLR分析 给传统的LR(0)分析额外添加一个判定过程：**对包含项目A→α·的闭包，只有在下一个输入符号$\in$FOLLOW(A)时，才能进行该归约**。 这个判定可以避免一部分错误的归约。然而，这个判定在同一个闭包内同时存在某些等待FOLLOW(A)内元素的非归约项目的时候，显然会失效。  **SLR对应的分析表中，原先LR(0)分析表全部填充同一个r操作的行，现在可以拥有不同的r操作甚至s操作和err操作了。**  ## LR(1)分析 针对SLR无脑使用FOLLOW集的做法进一步进行改良，基于**同一非终结符在句型的不同位置可以进行的归约是不同的**，提出**展望符(Lookahead)的概念**——将一个非终结符后跟不同终结符的情况视为不同状态，最终**每个状态在归约相同的非终结符时都只能在后跟具体终结符的情况下进行**。一个状态允许归约时的后继终结符集称展望符集，展望符集$\subseteq$FOLLOW集。 ### LR(1)项目  ### 等价LR(1)项目 一个LR(1)项目的等价LR(1)项目的第一分量与LR(0)分析时是一致的，而第二分量（展望符集）不一定与其自身相同，根据符号串$\beta$是否为空，会出现两种情况，具体见下图：  ### LR(1)分析表 LR(1)的分析表整体形式上与SLR基本一致，但由于比SLR做到了更细致的状态划分，因此排除掉了大部分状态转移产生冲突的情况，但同时也大幅增加了状态数量。 ## LALR(1) ### 合并相同核心的LR(1)项目    - 合并可能引入归约-归约冲突（不引入则说明符合LALR语法） - LALR的移入-归约算法与LR(1)相同 - LALR的状态机规模与LR(0)、SLR相同 ## 对二义性文法的LR分析 每个二义性文法都不是LR的，但是可以通过引入额外的人工规则，来将其适配LR，最典型的例子如： - 引入符号优先级解决表达式的二义性问题： - 对包含`E→E+E`和`E→E*E`产生式的文法，给定如下规则： - 已进栈`E+E`，输入`*`则移入，输入`+`则归约 - 已进栈`E*E`，输入`*`或`+`都归约 - 引入就近原则解决if-else结构的二义性问题： - 对包含`if<cond>then<S>else<S>`的文法，给定如下规则： - 已进栈`if<cond>then<S>`，若后跟`else`则移入，否则归约