第6篇 自下而上语法分析6.pdf

第6章 自下而上语法分析 ● 学习思路 ● ● 第6章 自下而上语法分析 ● 基本思想 ● ● 存在的问题 Bottom-up Parsing ● ● 解决方法 ● ● 主要分析方法 伍 春 香 武汉大学计算机学院 学习目标 掌握 自下而上语法分析的基本思想 短语、简单短语/直接短语、句柄 自下而上语法分析简介 素短语、最左素短语 基本思想 移进-归约技术 实现技术——移进-归约 算符优先分析方法 存在的问题 了解 解决方法分析 简单优先分析方法 6.1 自下而上语法分析 6.1 自下而上语法分析 1．自下而上语法分析的基本思想 ——如何表示分析过程? 2．基本实现技术——移进-归约法 ◆ 推导——从输入的符号串开始逐步向上归约，试图归 ◆ 引进一个后进先出的栈来存放符号，按照扫描顺序把 约到文法的开始/识别符号。 当前输入符号下推入栈中(移进) ，然后查看栈顶的符号串是 ◆ 语法树—— 以输入符号串作为末端结点符号串，向根 否可以被归约。 ◆ 结点方向构造语法树，使识别符号正好是语法树的根 栈 # X X X …X X …X a a ……a # 输入串 结点。 1 2 3 i i+1 j k k+1 m ◆ 程序的编译——从该高级语言文法的源程序或与其等 ◆ x 价的单词串 出发，试图归约到该文法的开始符号—— 当前句型 程序。 6.1 自下而上语法分析 6.1 自下而上语法分析 3.自下而上语法分析遇到的基本问题 栈 # X X X …X X …X a a ……a # 输入串 1 2 3 i i+1 j k k+1 m