自底向上分析之LR分析法
说明：以老师PPT为标准，借鉴部分教材内容，AlvinZH学习笔记。
基本概念
1. LR分析：从左到右扫描(L)自底向上进行规约(R)，是规范规约，也即最右推导（规范推导），是自底向上分析方法的高度概括和集中。
2. LR（k）文法确定的分析器适用于一大类上下文无关文法的语法分析，基本上包括了所有无二义性的上下文无关文法的集合，包括了前面讨论的LL（k）和算符优先文法。
3. 优缺点
- 适合文法类足够大，适用于所有上下文无关文法
- 分析效率高
- 报错及时
- 可以自动生成
- 但手工实现工作量大
4. LR分析器的组成：状态栈、分析表、控制程序。
- 状态栈：放置分析器状态和文法符号；
- 分析表：由两个矩阵组成，其功能是指示分析器的动作，是移进还是规约，根据不同的文法类要采用不同的构造方法。
- 控制程序：执行分析表所规定的动作，对栈进行操作。
不同的LR分析器区别在于分析表的构造方法，状态栈和控制程序都是一样的。
5. 不同文法类层次结构
下面我们讲讨论LR（0）、SLR（1）、LR（1）、LALR（1）。
- LR（0）：
- SLR（1）：简单LR方法，最容易实现，功能最弱，适应文法范围较小，大师具有较高的实用价值；
- LR（1）：规范的LR方法，功能最强，适应的文法范围最大，但实现的代价最高，故使用价值不大。
- LALR（1）：向前看的LR方法，适用文法范围介于上述两者之间，可用于大多数程序设计语言，用途最广。
注：三种方法对应三种分析表构造方法，三种分析表分别对应三类文法。一个SLR文法必定是LALR文法和LR文法。
LR分析器
1. LR分析器为一个输入串逆向构造了一个最右推导。通过考虑现有符号串（句型）以及向前看未处理的前k个字符就能识别出句柄（最左简单短语），成该文法为LR（k）文法。
2. 活前缀
规范句型：通过规范规约得到的句型。
规范句型前缀：将输入串的剩余部分与其连结起来就构成了规范句型。对于复返句型 \(αβt\)，\(αβ\)即是一个前缀。
活前缀：对于句型 \(αβt\)， \(β\) 表示句柄，如果 \(αβ = u1 u2 … ur\)，那么符号串u1 u2 …ui (1≤i≤r)即是句型 \(αβt\) 的活前缀。
举个例子：
3. 分析表：两个矩阵，状态转移表（GOTO表）和分析动作表（ACTION表）。
GOTO表：行为分析器的状态，列为文法符号（Vn+Vt）。GOTO[Si-1, xi] = Si，表示当前栈顶状态 Si-1 遇到新的栈顶符号 xi 要转移到新的栈顶状态 Si。可以看出，GOTO表定义了一个以文法符号集为字母表的有穷自动机，该自动机识别文法所有规范句型的活前缀。
ACTION表：ACTION[ Si , a ] =分析动作。分析动作有四种：移进、规约、接受。出错。
两个表可以融合，方便查表。
4. 控制程序：根据栈顶状态和现行输入符号，查分析动作表(ACTION表)，执行由分析表所规定的操作；并根据GOTO表设置新的栈顶状态（即实现状态转移）。
5. 分析过程：每次规约总是规约当前句型的句柄，是规范规约！分析的每一步栈内符号串均是规范句型的活前缀，且与输入串的剩余部分构成规范句型。
构造LR分析表
1. 方法：根据文法构造识别规范句型活前缀的有穷自动机 DFA。再由由DFA构造LR分析表。
DFA定义五元式：M = ( S, V, GOTO, S0, Z )
S：有穷状态集
V：文法字汇表（Vn+Vt）
GOTO：状态转移表对应的转移函数
S0：初始状态
Z：终态集，在这里除了S0以外其余状态都是终态。
2. DFA中的有穷状态集S在此，S = LR（0）项目集规范族。
项目集规范族：每个元素为项目组成的集合。
项目：在文法G的产生式右部某处加点的产生式，如对于产生式 \(A→XY\)，有项目
\(A→.XY\) 、\(A→X.Y\) 、\(A→XY.\) 三个项目。特别的，对于 \(A→ε\)，存在唯一项目 \(A→.\)。
LR（0）分析法
1. 求解单个的项目集，对应DFA中的单个元素。
闭包运算，如果I是文法G的项目集，那么closure（I）由一下两条规则求得：
- 初始时，将I的每个项目放入closure（I）中；
- 如果 \(A→α.Bβ\)在closure（I）中，且存在产生式 \(B→γ\)，则将 \(B→.γ\) 加入closure（I）中。
2. goto函数：goto（I，X）中I是项目集，X是文法符号，goto（I，X）定义为所有形如 \([A→αX.β]\)项目集的闭包，前提是 \([A→α.Xβ]\) 在I中。
即有goto（I，X）= closure（J），右部分仍是项目集。直观地说，这一步之后，找到了DFA中从状态 \(I\) 经过 \(X\) 弧转移到状态 closure（J）。
SLR（1）
LR（1）
LALR（1）
本节内容太多了，考完再写了，对不起~
引用说明
- 邵老师课堂PDF
- 《编译原理级编译程序构造》