自底向上分析概述
- 从分析树的底部 (叶节点) 向顶部 (根节点) 方向构造分析树
- 可以看成是将输入串 w 归约为文法的开始符号 S 的过程
- 自顶向下的语法分析采用最左推导方式
- 自底向上的语法分析采用最左归约方式 (反向构造最右推导)
- 自底向上语法分析的通用框架：移入 - 归约分析 (Shift-Reduce Parsing)
【例】移入 - 归约分析
- $表示栈底和栈顶
- 开始时栈中没有任何符号
- 第一步，将id入栈
- 第二步，因为id是第四个产生式的右部，所以将id归约为E，id出栈，E入栈
- ……
- 每次归约的符号串称为 “句柄”，一旦句柄在栈顶出现，我们就立即将其归约，从而保证我们的每一次归约都是最左归约
-
移入 - 归约分析的工作过程
在对输入串的一次从左到右扫描过程中，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串β进行归约为止
- 然后，它将β归约为某个产生式的左部
- 语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空 (当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析) 为止
移入 - 归约分析器可采取的 4 种动作：
- 移入：将下一个输入符号移到栈的顶端
- 归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
- 接收：宣布语法分析过程成功完成
- 报错：发现一个语法错误，并调用错误恢复子例程
【例】移入 - 归约分析中存在的问题
句柄var
，i既可以使用产生式 2 归约，又可以使用产生式 3 归约，由于句柄是句型的最左直接短语，所以选用产生式 3 进行归约 LR 分析法概述
LR 文法 (Knuth, 1963) 是最大的、可以构造出相应移入 - 归约语法分析器的文法类
- L: 对输入进行从左到右的扫描
- R: 反向构造出一个最右推导序列
LR(k) 分析
自底向上分析的关键问题是什么？
- 如何正确地识别句柄
- 句柄是逐步形成的，用 “状态” 表示句柄识别的进展程度
【例】状态
- 文法开始符号 S 定义为 bBB，因为产生式右部由 3 个符号构成，所以将句柄识别划分为 4 个状态
- S→·bBB 移进状态：期待出现一个终结符 b，当终结符 b 出现，将其移入分析栈中，进入下一状态
- S→b·BB 待约状态：期待归约出一个非终结符 B，当归约出非终结符 B，进入下一状态
- S→bB·B 待约状态：期待归约出一个非终结符 B，当归约出非终结符 B，进入下一状态
- S→bBB· 归约状态：此时构成句柄的三个符号都已识别，将其归约成文法开始符号 S
-
LR 分析器 (自动机) 的工作过程
LR 分析器 (自动机) 由输入带、读头、带有分析表的主控程序和状态、符号栈构成
【例】LR 分析表的结构
- 状态有 7 个0-6、ACTION 表中有 2 个终结符a、b和一个结束符号$、GOTO 表中有两个非终结符S、B
- Sn：将符号 a/b 压入符号栈，状态 n 压入状态栈
- rn：用第 n 个产生式进行归约，对应终结符和状态出栈，非终结符入栈
- GOTO 表中的每一项表示在某一状态遇到某一非终结符时，进入的后继状态
【例】LR 分析器的工作过程。若输入串 bab，则 LR 分析器的工作过程如下：
- 初始时，将待分析的输入串放入输入缓冲区中，后面连接结束符$。状态栈中只有状态0，符号栈中只有栈底标记$：
- 初始状态 0 遇到终结符 b，查 ACTION 表，采取 S4，将符号 b 压入符号栈，状态 4 压入状态栈：
- 状态 4 遇到终结符 a，查 ACTION 表，采取 r3，用第 3 个产生式进行归约，对应终结符 b 和状态 4 出栈，非终结符 B 入栈；
- 状态 0 遇到非终结符 B，查 GOTO 表，状态 2 入栈
- 状态 2 遇到终结符 a，查 ACTION 表，采取 S3，将符号 a 压入符号栈，状态 3 压入状态栈：
- ……
- 状态 6 遇到结束符$，查 ACTION 表，采取 r2，用第 2 个产生式进行归约，对应终结符 aB 和状态 36 出栈，非终结符 B 入栈：
- 状态 2 遇到非终结符 B，查 GOTO 表，状态 5 入栈：
- 状态 5 遇到结束符$，查 ACTION 表，采取 r1，用第 1 个产生式进行归约，对应非终结符 BB 和状态 25 出栈，非终结符 S 入栈：
- 状态 0 遇到非终结符 S，查 GOTO 表，状态 1 入栈：
状态 1 遇到结束符$，查 ACTION 表，acc 表示 accept，成功将该输入串归约为文法的开始符号 S
LR 分析算法
CLOSURE 函数
GOTO 函数
如何构造给定文法的 LR 分析表？不同的 LR 分析法有不同的 LR 分析表构造方法
-
增广文法
文法中的项目
这 15 个项目中有某些项目是等价的
- 可以把等价的项目组成一个项目集 (I) ，称为项目集闭包 (Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态
- 项目 0 表示，等待非终结符 S；由产生式 2 可知，等待非终结符 S 相当于等待终结符 v，也就是项目 2；所以项目 0 和项目 2 等价
- 同理，项目 3、项目 7 和项目 11 等价；项目 5 和项目 13 等价
- 综上，当圆点后面是一个非终结符时，说明存在等价项目
【例】根据文法构造 LR(0) 分析的分析表
- 文法→分析图→分析表
- 将初始项目 S’→·S 放到初始状态 I0 中，初始项目在等待非终结符 S，由产生式 2 可知，等待非终结符 S 就相当于在等待非终结符 B，因此，将初始项目的等价项目 S→·BB 加入状态 I0，同理，加入其他等价项目
- 根据状态 I0 中的第一个项目：当归约出非终结符 S 时，状态 I0 进展到状态 I1，将项目 S’→·S 的后继项目 S’→S· 加入状态 I1，
- 由于项目 S’→S· 是归约项目，且文法开始符号出现在产生式右部，所以状态 I1 是接收状态，遇到结束符$时，acc
- 根据状态 I0 中的第二个项目：当归约出非终结符 B 时，状态 I0 进展到状态 I2，将项目 S→·BB 的后继项目 S→B·B 加入状态 I2，由于圆点后面是一个非终结符，所以要加入其他等价项目
- 根据状态 I0 中的第三个项目：当归约出终结符 a 时，状态 I0 进展到状态 I3，将项目 B→·aB 的后继项目 B→a·B 加入状态 I3，由于圆点后面是一个非终结符，所以要加入其他等价项目
- 根据状态 I0 中的第四个项目：当归约出终结符 b 时，状态 I0 进展到状态 I4，将项目 B→·b 的后继项目 B→b· 加入状态 I4
- 由于项目 B→b· 是归约项目，所以状态 I4 是遇到任何符号都使用产生式 3 进行归约
- 状态 I1 中的唯一一个项目是归约项目，因为圆点后不再有符号，所以不再有后继状态
- 根据状态 I2 中的第一个项目：当归约出非终结符 B 时，状态 I2 进展到状态 I5，将项目 S→B·B 的后继项目 S→BB· 加入状态 I5
- 由于项目 S→BB· 是归约项目，所以状态 I5 遇到任何符号都使用产生式 1 进行归约
- 根据状态 I2 中的第二个项目：当归约出终结符 a 时，状态 I2 进展到状态 I3
- 根据状态 I2 中的第三个项目：当归约出终结符 b 时，状态 I2 进展到状态 I4
- 根据状态 I3 中的第一个项目：当归约出非终结符 B 时，状态 I3 进展到状态 I6，将项目 B→a·B 的后继项目 B→aB· 加入状态 I6
- 由于项目 B→aB· 是归约项目，所以状态 I6 遇到任何符号都使用产生式 2 进行归约
- 根据状态 I3 中的第二个项目：当归约出终结符 a 时，状态 I3 仍是状态 I3
- 根据状态 I3 中的第三个项目：当归约出终结符 b 时，状态 I3 进展到状态 I4
- 状态 I5 中的唯一一个项目是归约项目，因为圆点后不再有符号，所以不再有后继状态
状态 I6 中的唯一一个项目是归约项目，因为圆点后不再有符号，所以不再有后继状态
LR(0) 分析中的冲突
移进 / 归约冲突
移进 / 归约冲突和归约 / 归约冲突
如果 LR(0) 分析表中没有语法分析动作冲突，那么给定的文法就称为 LR(0) 文法
- 不是所有 CFG(上下文无关文法) 都能用 LR(0) 方法进行分析，也就是说，CFG 不总是 LR(0) 文法
如何消解冲突将在后面的 SLR 分析法和 LR(1) 分析法中介绍
SLR 分析
【例 1】用 SLR 分析法的基本思想解决 LR(0) 分析过程中的移进 / 归约冲突
在状态 2，当下一个输入符号是*时，既可以采取归约，也可以采取移入，产生冲突
- 该问题本质是如何识别句柄，如果栈顶符号 T 是一个句柄，就应该归约，否则就不应该归约，可见 LR(0) 本身的信息已经不能帮助我们确定是否进行归约
- 事实上，LR(0) 分析在构造项目的时候，没有向前查看符号，也就是没有考虑文法符号的上下文环境
- 在状态 2，当下一个输入符号是时，如果把栈顶的 T 归约成 E，根据 FOLLOW(E) 可知，E 后面不可能连接，所以这里不应该归约，T 不是句柄
- 由此可见，FOLLOW 集可以帮助判断是否进行归约
- 用 SLR 分析法的基本思想解决 LR(0) 分析过程中的冲突后得到上面的分析表
- 与 LR(0) 分析法得到的分析表相比，SLR 分析法得到的分析表中的归约状态只在遇到 FOLLOW 集中的元素才采取归约；而 LR(0) 分析法得到的分析表中的归约状态在遇到任何元素都采取归约
【例 2】用 SLR 分析法的基本思想解决 LR(0) 分析过程中的移进 / 归约冲突和归约 / 归约冲突
- 在状态 2，既可以将栈底的空串归约为 B，也可以归约为 T，产生冲突；此外，还有一个移入项目，也与两个归约项目产生冲突
- 对于状态 2 中的归约归约冲突，查看 FOLLOW 集可知，FOLLOW(B) 中只有 d，因此，状态 2 遇到 d 时采用第四个产生式；FOLLOW(T) 中有 b 和$，因此，状态 2 遇到 b 和$时采用第二个产生式；此外，状态 2 遇到 a 时采用移入动作，将 a 入栈，进入状态 2
如果给定文法的 SLR 分析表中不存在有冲突的动作，那么该文法称为 SLR 文法
SLR 分析中的冲突
- 状态 2 中，第一个项目表示，当下一个输入符号是=时，采用移入动作，将=入栈，进入状态 6；第二个项目表示，当遇到 FOLLOW(R) 集中的元素=和$时，将栈顶元素归约为 R。因此，当遇到=时，产生移入 / 归约冲突。
-
LR(1) 分析
SLR 分析存在的问题：
SLR 只是简单地考察下一个输入符号 b 是否属于与归约项目 A→α相关联的 FOLLOW(A)，但 b∈FOLLOW(A) 只是归约α的一个必要条件，而非充分条件
LR(1) 项目
,后面的叫展望符
【例】LR(1) 项目的表示
- LR(1) 文法在构造项目的时候，将特定位置的后继符信息考虑了进去
在 R 位置，R 的后继符号是$，采用R→L·,S来表示项目：R 产生式的归约项目，这个项目表示：当下一个符号是$时，可以将栈顶的 L 归约为 R
等价 LR(1) 项目
展望符是 FIRST(β) 集中元素
【例】构造 LR(1) 分析表
- I0 中第一个项目，因为 S’后面只能跟结束符$，所以该项目的展望符是$
- I0 中第二三个项目，是第一个项目的等价项目，因为第一个项目的 S 后面是一个空串，所以它的两个等价项目继承展望符$
- I0 中第四五个项目，是第二个项目的等价项目，因为第二个项目的 L 后面是一个 =，所以它的两个等价项目继承展望符 =
- ……
- 与 SLR 分析法和 LR(0) 分析法得到的分析表相比，LR(1) 分析法得到的分析表中的归约状态只在遇到展望符时才采取归约；而 SLR 分析法得到的分析表中的归约状态在遇到 FOLLOW 集中的元素采取归约；LR(0) 分析法得到的分析表中的归约状态在遇到任何元素都采取归约
- 如果除展望符外，两个 LR(1) 项目集是相同的，则称这两个 LR(1) 项目集是同心的
若有收获，就点个赞吧
0 人点赞
