自底向上的语法分析
- 从分析树的底部（叶节点）向顶部（根结点）方向构造分析树
- 可以看成是将输入串$w$规约为文法开始符号$S$的过程
- 自顶向下的语法分析采用最左推导的方式
- 自底向上的语法分析采用最左归约的方式（方向构造最右推导）
- 自底向上语法分析的通用框架——移入-归约分析（Shift-Reduce Parsing）
例：移入-归约分析
栈内符号串+剩余输入=“规范句型”
移入-归约分析的工作过程
在对输入串的一次从左到右扫描过程中，语法分析将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串$\beta$进行归约为止
然后，它将$\beta$归约为某个产生式的左部
语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析)为止
移入-归约分析其可采取的4种动作
- 移入：将下一个输入符号移到栈的顶端
- 归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
- 接收：宣布语法分析过程成功完成
- 报错：发现一个语法错误，并调用错误恢复子例程
LR(0)分析法
LR文法(Knuth, 1963)是最大的、可以构造出相应移入-归约语法分析器的文法类
- L：对输入进行从左到右的扫描
- R: 反向构造出一个最右推导序列
LR(k)分析：需要向前查看k个输入符号的LR分析。k=0和k=1这两种情况具有实践意义当省略(k)时，表示k=1
LR(0)项目
右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）$A \to a_1·a_2$。项目描述了句柄的识别状态
例：$S \to bBB$
- $S \to ·bBB$ 移进项目
- $S \to b·BB$ 待约项目
- $S \to bB·B$ 待约项目
- $S \to bBB·$ 规约项目
产生式$A \to \epsilon$只生成一个项目$A \to ·$
增广文法（Augmented Grammar）
如果G 是一个以S为开始符号的文法，则G的增广文法G' 就是在G中加上新开始符号S' 和产生式$S' \to S$而得到的文法
引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态
文法中的项目
- 后继项目（Successive Item）：同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目。例如$A \to a·X\beta$的后继项目是$A \to aX·\beta$
可以把等价的项目组成一个项目集(I)，称为项目集闭包(Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态
CLOSURE()函数
计算给定项目集I的闭包
$$ CLOSURE(I) = I \cup \{B \to ·\gamma | A \to \alpha·|B\beta \in CLOSURE(I),B \to \gamma \in P\} $$
SetOfltems CLOSURE (I) {
J = I;
repeat
for ( J中的每个项A → α·Bβ )
for ( G的每个产生式B → γ )
if ( 项B → ·γ不在J中)
将B → ·γ加入J中;
until 在某一轮中没有新的项被加入到J中；
return J;
}GOTO()函数
返回项目集I对应于文法符号X的后继项目集闭包
$$ GOTO(I,X) = CLOSURE(\{A \to \alpha X·\beta | A \to \alpha·X\beta \in I\}) $$
SetOfltems GOTO (I,X) {
将J 初始化为空集;
for ( I 中的每个项A → α·Xβ )
将项A → αX·β 加入到集合J 中;
return CLOSURE ( J );
}规范LR(0)项集族
$$ C = \{I_0\} \cup \{I | \exists J \in C, X \in V_N \cup V_T,I = GOTO(J,X)\} $$
void items( G' ) {
C＝{ CLOSURE ({[ S'→ ·S ] } ) };
repeat
for (C中的每个项集I )
for(每个文法符号X )
if ( GOTO ( I，X )非空且不在C中)
将GOTO ( I，X )加入C中;
until在某一轮中没有新的项集被加入到C中;
}LR(0)分析表构造算法
SLR分析法
由于LR分析中可能存在冲突（移进-归约冲突、归约-归约冲突），因此引入分析能力更强的SLR(1)分析法
SLR分析法的基本思想
- 构造G'的规范LR(0)项集族$C = \{I_0,I_1,…,I_n\}$
根据$I_i$构造得到状态i。状态i的语法分析动作按照下面的方法决定：
- if $A \to \alpha·a\beta \in I_i$ and $GOTO(I_i,a) = I_j$ then $ACTION[i,a] = s_j$
- if $A \to \alpha·B\beta \in I_i$ and $GOTO(I_i,B) = I_j$ then $GOTO[i,B] = j$
- if $A\to \alpha·\in I_i$且$A ≠ S'$ then for $\forall a \in FOLLOW(A)$ do $ACTION[i,a] = r_j$（$j$是产生式$A \to \alpha $的编号）
- if $S'\to S·\in I_i$ then ACTION[i,$] = acc
- 没有定义的所有条目都设置为"error"
如果给定文法的SLR分析表中不存在有冲突的动作，那么该文法称为SLR文法
用一句话概括SLR分析表的构造算法：移进策略与LR(0)分析法相同，只有归约时不同，仅对当前产生式左部字母的Follow集进行归约
LR(1)分析
SLR分析存在的问题：SLR只是简单地考察下一个输入符号b是否属于与归约项目$A\to α$相关联的FOLLOW(A)，但$b \in FOLLOW(A)$只是归约$alpha$的一个必要条件，而非充分条件
对于产生式$A\to α$的归约，在不同的使用位置，A会要求不同的后继符号
在特定位置，A的后继符集合是FOLLOW(A)的子集
规范LR(1)项目
将一般形式为$[A\to \alpha·\beta,a]$的项称为LR(1)项，其中$A\to \alpha \beta$是一个产生式，$a$是一个终结符(这里将$视为一个特殊的终结符)它表示在当前状态下，A后面必须紧跟的终结符，称为该项的展望符(lookahead)
- LR(1)中的1指的是项的第二个分量的长度
- 在形如$[A\to \alpha·\beta,a]$且$\beta ≠ \epsilon$的项中，展望符a没有任何作用
- 但是一个形如$[A\to \alpha·,a]$的项在只有在下一个输入符号等于a时才可以按照$A\to \alpha·$进行归约
- 这样的a的集合总是FOLLOW(A)的子集，而且它通常是一个真子集
如果除展望符外，两个LR(1)项目集是相同的，则称这两个LR(1)项目集是同心的。例如，再上图的LR(1)自动机中，$I_4$和$I_{11}$是同心集，$I_5$和$I_{12}$是同心集，$I_1$和$I_{13}$是同心集，$I_8$和$I_{10}$是同心集
LR(1)项目集闭包
$CLOSURE(I) = I\cup \{[B\to·\gamma,b] | [A\to \alpha·B\beta,a] \in CLOSURE(I), B\to \gamma \in P, b\in FIRST(\beta a)\}$
SetOfltems CLOSURE ( I ) {
repeat
for ( I中的每个项[A → α·Bβ，a ])
for (G'的每个产生式B → γ)
for ( FIRST (βa)中的每个符号b )
将[ B → · γ ，b]加入到集合I中;
until 不能向I中加入更多的项;
until I;
}GOTO函数
$GOTO(I,X) = CLOSURE(\{[A\to \alpha X·β,a]|[A\to \alpha·X\beta,a]\in I\})$
SetOfltems GOTO ( I，X ) {
将J 初始化为空集;
for ( I 中的每个项[A → α·Xβ，a ])
将项[ A → αX·β，a]加入到集合J 中;
return CLOSURE ( J );
}构造文法G'的LR(1)项目集族
void items (G' ) {
将C初始化为{CLOSURE ({[ S' → · S, $]} )};
repeat
for ( C中的每个项集I )
for ( 每个文法符号X )
if (GOTO(I，X )非空且不在C中)
将GOTO(I，X )加入C中;
until 不再有新的项集加入到C中;
}LR分析表构造算法
- 构造G'的规范LR(1)项集族$C = \{I_0,I_1,…,I_n\}$
根据$I_i$构造得到状态i。状态i的语法分析动作按照下面的方法决定：
- if $[A\to \alpha·a\beta,b] \in I_i$ and $GOTO(I_i,a) = I_j$ then $ACTION[i,a]=sj$
- if $[A\to \alpha·B\beta,b] \in I_i$ and $GOTO(I_i,B) = I_j$ then $GOTO[i,B]=j$
- if $[A\to \alpha·,a] \in I_i$ 且 $A ≠ S'$ then $ACTION[i,a]=rj$（$j$是产生式$A\to \alpha$的编号）
- if $S' \to S \cdot \in I_i$ then ACTION [i,$] = acc
- 没有定义的所有条目都设置为"error"
如果LR(1)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(1)文法
LALR分析法
LALR(lookahead-LR)分析的基本思想如下：
- 寻找具有相同核心的LR(1)项集，并将这些项集合并为一个项集。所谓项集的核心就是其第一分量的集合
- 然后根据合并后得到的项集族构造语法分析表
- 如果分析表中没有语法分析动作冲突，给定的文法就称为LALR(1)文法，就可以根据该分析表进行语法分析
合并同心项集不会产生移进-归约冲突，但是有可能产生归约归约冲突。因为合并的时候合并的是同心项的展望符，而展望符只在规约的时候起作用，在移入的时候是不起作用的，只要合并前各个同心项目集本身是没有冲突的，就不会有冲突
LALR的特点
- 形式上与LR(1)相同
- 大小上与LR(0)和SLR相当
- 分析能力介于SLR和LR(1)二者之间
- 合并后的展望符集仍为FOLLOW集的子集
