移入-归约语法分析

使用一个栈来保存归约/扫描移入的文法符号，栈中符号（从底向上）和待扫描的符号组成了一个最右句型。

四个操作

• 移入：将下一个输入符号移入到栈顶

• 归约：将句柄规约为相应的非终结符号

  句柄总是在栈顶，具体操作时弹出句柄，压入被规约到的非终结符号。

• 接受：宣布分析过程成功完成

• 报错：发现语法错误，调用错误恢复子程序

移入-归约分析中的冲突

对于有些不能使用移入-规约分析的文法，不管用什么样的移入-归约分析器都会达到同样的结果

即使知道栈中所有内容，以及后续k个输入符号，仍然：

• 无法知道是否该进行归约（移入-归约冲突）

• 无法知道按照什么产生式进行归约（归约-归约冲突）

LR语法分析器

LR（k）的语法分析概念：

• L表示最左扫描，R表示反向构造出最右推导

• k表示最多向前看k个符号

当k增大时，相应的语法分析器的规模急剧增大

• k=2时，程序语言的语法分析器的规模通常非常庞大

• 当k=0或1时，已经可以解决很多语法分析问题，因此具有实践意义

LR语法分析器的优点

1. 由表格驱动，虽然手工构造表格工作量很大，但是表格可以自动生成

2. 对于几乎所有的程序设计语言，只要写出上下文无关文法，就能够构造出识别该语言的LR语法分析器

3. 最通用的无回溯移入-归约分析技术

4. 能分析的文法比LL（k）文法更多

LR语法分析思路

核心任务：识别句柄，规约句柄

句柄：栈中内容（已扫描/规约的串）的最右可规约子串

关键问题：如何知道栈中内容可以归约了？

• 维护一个状态，记录当前句柄识别的进度

项（term）：一个文法产生式加上在其中某处的一个点