移入-归约语法分析
使用一个栈来保存归约/扫描移入的文法符号，栈中符号（从底向上）和待扫描的符号组成了一个最右句型。
四个操作
移入：将下一个输入符号移入到栈顶
归约：将句柄规约为相应的非终结符号
句柄总是在栈顶，具体操作时弹出句柄，压入被规约到的非终结符号。
接受：宣布分析过程成功完成
报错：发现语法错误，调用错误恢复子程序
移入-归约分析中的冲突
对于有些不能使用移入-规约分析的文法，不管用什么样的移入-归约分析器都会达到同样的结果
即使知道栈中所有内容，以及后续k个输入符号，仍然：
无法知道是否该进行归约（移入-归约冲突）
无法知道按照什么产生式进行归约（归约-归约冲突）
LR语法分析器
LR（k）的语法分析概念：
L表示最左扫描，R表示反向构造出最右推导
k表示最多向前看k个符号
当k增大时，相应的语法分析器的规模急剧增大
k=2时，程序语言的语法分析器的规模通常非常庞大
当k=0或1时，已经可以解决很多语法分析问题，因此具有实践意义
LR语法分析器的优点
由表格驱动，虽然手工构造表格工作量很大，但是表格可以自动生成
对于几乎所有的程序设计语言，只要写出上下文无关文法，就能够构造出识别该语言的LR语法分析器
最通用的无回溯移入-归约分析技术
能分析的文法比LL（k）文法更多
LR语法分析思路
核心任务：识别句柄，规约句柄
句柄：栈中内容（已扫描/规约的串）的最右可规约子串
关键问题：如何知道栈中内容可以归约了？
维护一个状态，记录当前句柄识别的进度
项（term）：一个文法产生式加上在其中某处的一个点
Last updated