编译复习:自底向上语法分析
本学期做编译助教，需要复习一下。LR文法分析之前的内容都跳过了，对于自底向上的语法分析内容需要详细复习一下，在此记录
- 资料：龙书第2版4.5节， 4.6节
一、初步知识
- 自底向上语法分析本质上是为输入串构造语法分析树的过程
- LR文法类是最大的、可以构造相应的移入-归约语法分析器的文法类
- 当今构造LR语法分析器可以借助自动生成工具
- LR(k)文法中的L是自左向右扫描，R是用最右推导，k是指向前看k个字符，k=1时省略标出。
二、正文
1. 归约
- 归约就是将串恢复成文法开始符号的过程，方法为将串中与某产生式体相匹配的子串替换为该生成式的头部。
- 将归约过程反过来对应着一个最右推导。
- 最右推导是每次替换掉最右边的非终结符号的推导过程。
2. 句柄
- 句柄是进行一步最右推导后，生成的串中与刚刚使用的生成式体相匹配的那个子串。但要注意这不等价于串中左边与某生成式体匹配的字串。
例子： $T$ * $id_2$ 这个串的句柄是$id_2$而不是$T$，因为将$T$归约后得到$E$ * $id_2$将无法继续归约。事实上，正常的最右推导过程是$E \rightarrow T \rightarrow T * F \rightarrow T * id_2$, 正确的句柄是$id_2$，对应的生成式是$F \rightarrow id_2$。
- 句柄是一个生成式，但为了简便，常用生成式体代替。
- 无二义的文法，那么其每个最右句型都有唯一的句柄。
- 归约的关键就在于找到句柄然后替换。
3. 移入-归约语法分析技术
采用四个动作：移入，归约，接受，报错
- 用两个栈结构完成算法，过程中将w串的字符移入左侧栈，当达到可规约条件时，在左侧栈中完成规约，当右侧已空且左侧只剩下文法开始符号，则为接受，否则报错。
栈1 栈2
$__ _w$ - 性质：句柄总是会出现在左侧栈的栈顶
- 两种冲突：移入归约冲突和归约归约冲突。
4. 项和LR(0)自动机
- 项： 生成式的右侧中含有一个点，如$A \rightarrow .XYZ$。
- LR(0)自动机，每个状态代表规范LR(0)项集族的一个项集。
(1) 构造规范LR(0)项集族：
定义增广文法和两个函数：CLOSURE, GOTO
- 增广文法： 为开始符号S增加$S’ \rightarrow S$。这个增加的生成式是用来确定何时采取接受动作的。
- CLOSURE(I)：最开始I的项都在其中，如果$A \rightarrow \alpha . B \beta$在其中且项$B \rightarrow .\gamma$不在其中，那么将其加入闭包。这样直到闭包不再变大为止。
- 内核项：这些项定义了整个项集的结构，它们是那些点不在生成式体最左边的项，以及$S’ \rightarrow S$。
- 非内核项：除了$S’ \rightarrow S$以外的所有点在生成式体最左边的项。
- GOTO(I, X)，对项集I遇到文法符号X时应到达的项集的闭包
(2) LR语法分析算法：
- 有两个表：ACTION和GOTO
(3) SLR语法分析：
- SLR语法分析是用LR(0)自动机进行的语法分析
- 构造ACTION表和GOTO表：移入看GOTO函数，归约看FOLLOW集，有$S’ \rightarrow S.$时对符号$接受，这些构成ACTION表，对于GOTO表则是对应非终结符号的GOTO函数结果。
(4) 可行前缀：
最右推导的某个句型中不越过句柄的前缀。
