第四章第1节 自底向上的语法分析

自底向上的语法分析

从分析树的底部（叶节点）向顶部（根节点）方向构造分析树
可以看成是将输入串w归约为文法开始符号S的过程
自顶向下的语法分析采用最左推导方式
自底向上的语法分析采用最左归约方式（反向构造最右推导）
自底向上语法分析的通用框架
移入-归约分析（Shift_Reduce Parsing）

image.png image.png

移入-归约分析的工作过程

在对输入串的一次从左到右扫描过程中，语法分析器将零个或者多个输入符号移入到栈顶，直到它可以对栈顶的一个文法符号串β进行归约为止
然后，它将β归约为某个产生式的左部
语法分析器不断重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空（当进入这样的格局时，语法分析器停止运行，并宣称完成了语法分析）为止

移入-归约分析器可采取的4中动作

1. 移入：将下一个输入符号移动到栈的顶端
   2.归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这>个串的左端，并决定用哪个非终结符来替换这个串
   3.接收：宣布语法分析过程成功完成
   4.报错：发现一个语法错误，并调用错误恢复子例程

移入-归约分析中存在问题

image.png image.png

如何自动的识别句柄 需要用到 LR 分析法