编译器笔记12-语法分析-自底向上分析概述编译器笔记12-语法分析-自底向

自底向上的语法分析

从分析树的底部(叶节点)向顶部(根节点)方向构造分析树
【编译器笔记12-语法分析-自底向上分析概述】可以看成是将输入串w归约为文法开始符号S的过程
自顶向下的语法分析采用最左推导方式，自底向上的语法分析采用最左归约方式（反向构造最右推导）。
自底向上语法分析的通用框架移入-归约分析 (Shift-Reduce Parsing)

文章图片
例：移入-归约分析.png 分析过程中一旦句柄在栈顶形成就马上进行归约操作，保证了每一步的归约都是最左归约。关于什么是句柄可以查看文章句柄与移入-归约分析的关系。
最左归约是最右推导的逆过程，最右推导的每一步得到的符号串都是一个句型我们称之为最右句型或者是规范句型，因此最左归约得到符号串也是规范句型。
因此栈内符号串+剩余输入=“规范句型”，在自底向上的分析过程中每次归约的符号串是当前句型的直接短语。

文章图片
例：移入-归约分析.png 移入-归约分析的工作过程

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

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