ch4.（2）自下而上语法分析（续）
上回，为了解决移进-规约时的几个问题，引入了几个定义：
短语：
设有文法G[Z]，w=xuy是它的一个句型，如果有： Z ⇒ ∗ x U y Z\mathop\Rightarrow\limits^* xUy Z⇒∗xUy并且 U ⇒ + u U\mathop\Rightarrow\limits^+u U⇒+u，则称句型xuy中子串u为句型xuy(相对于非终结符号U)的短语
特别地，如果是 Z ⇒ ∗ x U y Z\mathop\Rightarrow\limits^* xUy Z⇒∗xUy并且 U ⇒ u U\mathop\Rightarrow u U⇒u，则称u为句型xuy的直接(简单)短语
句柄：
句型的最左直接短语称为句柄
根据定义，短语、直接短语和句柄，都和语法树有关系：
1、语法树子树的末端结点符号串即是语法树所描述句型（相对于子树的根）的短语
2、简单子树（只有父子两代）的末端结点符号串即是直接短语
3、最左简单子树的末端结点符号串即是句柄
光从文字来看，这样的定义还是太抽象了。这个定义应该对后面的自下而上分析方法很重要，所以不得不看懂。然而这三行看了很久都没看懂，看书也看不懂，最后看了https://icode.blog.csdn.net/article/details/93236597这篇文章才勉强搞懂。现进行举例：
对于文法G[S]：
S → A B A → A a ∣ b B B → a ∣ S b \begin{aligned}S&\rightarrow AB\\ A&\rightarrow Aa|bB\\ B&\rightarrow a|Sb\end{aligned} SAB→AB→Aa∣bB→a∣Sb
现打算要求句型baSb的短语、直接短语和句柄。首先使用最左推导的方法，构造出语法树：
除叶结点单独形成的子树之外，这棵语法树共有4个子树：
1、B(a)
2、B(S, b)
3、A(b, B(a))
4、S(A(b, B(a)), B(S, b))
因此，短语共有四个：a、Sb、ba、baSb
而因为前两棵子树只有父子两代，所以直接短语有两个：a、Sb
句柄是最左直接短语（位于最左端的简单子树），而两棵子树中，B(a)在B(S, b)的左边，所以句柄应该为a
在理解定义之后，就开始看LR方法的思想了
LR分析法和LR分析程序
此类分析法命名为LR，是用于表达“从左至右”的含义
现在，自上而下语法分析面临的问题，主要就在于这两点：
1、如何找出当前句型中的句柄
2、应该将句柄归约到哪一个非终结符号
在进行详细讨论之前，首先大致浏览程序的总体结构，以展现出LR分析法相对于LL(1)分析法的简洁之处
LR分析程序的逻辑结构
LR分析程序主要有总控程序和分析表这两个部分
相比于LL(1)，LR多出了一个状态栈，用于存储符号栈中各个符号所对应的状态，而新进栈的符号的状态则是根据栈顶的状态和输入的符号进行查表（分析表）而决定
分析表主要包含：动作部分（ACTION）和状态转换部分（GOTO）。表中使用S表示移进、r表示规约、acc（accept）表示接受、（ACTION部分的）空白表示错处理（而GOTO部分的空白则不是出错处理）
尽管LR分析器有好几种类型（常见的有LR(0)、SLR、LR(1)、LALR），但所有LR分析器的总控程序一致，只是分析表不同而已。由此可知，LR分析法的程序是可以通用的，这再次体现出了LR分析法的一个优越之处
LR分析过程简要描述
LR分析过程主要包括移进、规约、接受和出错四种操作。对过程的简要描述如下：
1、总控程序在分析的每一步，按照状态栈顶状态q和当前输入符号a，查阅LR分析表，并执行其中ACTION[q，a]和GOTO部分规定的操作。
2、若ACTION [ q i q_i qi， a k a_k ak]= S j S_j Sj，则：
3、若ACTION [ q i q_i qi， a k a_k ak]=rj，且第j条产生式为U → \rightarrow →x，|x|=m，LR分析表中有GOTO[ q i − m q_{i-m} qi−m，U]= q t q_t qt，则：
4、若ACTION[ q i q_i qi， a k a_k ak]=acc，表示接受，不发生变化，分析成功：
5、若ACTION[ q i q_i qi， a k a_k ak]=ERROR，表示出错，中止变化
LR分析过程非常地简单，没有左递归、提取公因子的问题，因此关键在于：如何构造分析表
LR(0)分析表的构造
LR分析法的基本原理
对于由n个符号构成的句柄，如果每识别一个句柄的符号就对应着一个状态，则加上开始状态后，共有n+1个状态
可以利用打点的方式记录状态，例如，现在有句柄XYZ，则.XYZ表示即将开始得到X，X.YZ表示已经得到X，即将得到YZ，XY.Z表示已经得到XY，即将得到Z，XYZ.表示已经得到XYZ，即将归约
用LR(0)项目来表示一个句柄的所有识别状态：
移进项目：
U
→
x
.
a
y
U\rightarrow x.ay
U→x.ay。点后为终结符号，需要移入栈中
待约项目：
U
→
x
.
V
y
U\rightarrow x.Vy
U→x.Vy。点后为非终结符号
规约项目：
U
→
x
.
U\rightarrow x.
U→x.。点已经到句柄的最后了，已完整地完成
接受项目：
S
′
→
S
.
S'\rightarrow S.
S′→S.。其中，S为开始符号。这里使用了拓广文法，引入了一个新的开始符号S’，和产生式
S
′
→
S
S'\rightarrow S
S′→S
即便是在得到完整的产生式右部时，也无法知道能不能规约（信息还是不够），说明不能离开句型谈句柄，即需要句型中的信息，利用历史来帮助判断
由此引入活前缀：包含了句柄识别到当前时刻的历史，并逐步向后传递，最长活的前缀(可归约前缀)包含了句柄完全被识别的整个历史。这样一来，符号栈中存放的就是活前缀，而符号串和输入串连起来就是句型：
对句柄的识别过程就是对规范句型的活前缀的识别过程，对于这样的识别，可以用确定的有穷自动机来进行
构造识别规范句型活前缀的DFA
在此处，使用拓广文法：引入一个新的开始符号S’，及对应的产生式 S ′ → S S'\rightarrow S S′→S
将所有的产生式的所有状态全部列出，然后根据状态间的转换关系进行相应的连线：
上述方式构造出的是NFA，如果要转换为DFA，则需要进行状态的合并
首先对空弧的闭包进行状态合并：
合并后，被并入的状态所对应的产生式称作派生项目，反之称为核心项目。例如，在上图的开始状态集中， S ′ → . S S'\rightarrow .S S′→.S为核心项目，而 S → . a A c B e S\rightarrow .aAcBe S→.aAcBe则为派生项目
随后，再对相同输入所到达的多个状态进行合并：
这样便转换为了DFA