编译原理 语法分析—自底向上分析技术课件.pptVIP

编译原理;第五章 语法分析——自底向上分析技术 5.1 引言 5.1.1 自底向上分析技术及识别算法 1. 基本思想 句型分析，识别一个符号串是否是某文法的句型，是某个推导或语法分析树的构造过程。 从语法分析树的角度，自底向上分析过程将以输入符号串为语法分析树的末端结点符号串，试图向着根结点方向往上构造语法分析树，使识别符号正是根结点。 按自底向上分析技术，句型分析的过程是一个不断从语法分析树中剪去分支的过程。;2.识别算法 基于自底向上分析技术对输入符号串进行句型分析的算法称为自底向上识别算法。 实现识别算法的程序称为识别程序。识别程序功能：进行句型分析(识别) 。 3. 要解决的基本问题 自底向上分析技术要解决的基本问题： 在每一分析步的当前句型中， · 找出要被(直接)归约的（简单）短语u · 把所找出的（简单）短语u（直接）归约到哪一个非终结符号U? 为什么自底向上分析技术可行？ 凡是句子都存在规范分析。;5.1.2 讨论的前提 ? 语法分析程序的输入是中间表示形式的符号串 ? 讨论是以压缩了的上下文无关文法为基础 ? 分析过程是从左到右逐个符号地进行规范分析 语法分析的基础文法是上下文无关文法 输入和输出 输入：词法分析程序的输出(属性字序列) 输出：识别出是句子时， 输出语法分析树或 其他内部中间表示； 出错时报错。;5.1.3 基本实现方法: 移入-归约法 1. 基本思想 分析栈顶形成要归约的短语时进行归约，当还未形成时便移入(输入符号)。 分析动作：移入 归约 成功 报错 2. 基本实现工具：栈 3. 例 G[E]：E∷=E+E | E*E | (E) | i 输入符号串：i*i+i E=E+E=E+i=E*E+i=E*i+i=i*i+i 应用移入-归约法的分析过程如下。; 移入-归约法分析过程： 步骤 栈 输入其余部分 动作 规则 （1） # i*i+i# 移入 （2） #i *i+i# 归约 E::=i （3） #E *i+i# 移入 （4） #E* i+i# 移入 （5） #E*i +i# 归约 E::=i （6） #E*E +i# 归约 E::=E*E （7） #E +i# 移入 （8） #E+ i# 移入 （9） #E+i # 归约 E::=i （10） #E+E # 归约 E::=E+E （11） #E # 成功 所以，输入符号串i*i+i是该文法的句子。; 4. 是规范分析吗？为什么？ 移入-归约法解决了自底向上分析技术的2个基本问题？ · 找出要被归约的短语u · 确定归约到哪个非终结符号U 答案：？ ;下例的语法分析如何？;5.2 算符优先分析技术 自底向上分析技术的两个基本问题： · 找出被归约的短语 · 把被归约的短语归约为哪个非终结符号 5.2.1 算符优先分析技术的引进 寻找被归约短语的基本思想 · 仅由终结符号决定归约顺序 · 每次只查看两个相邻的终结符号： 先找出被归约短语的尾终结符号 然后再找出被归约短语的头终结符号 再确定归约的规则(左部非终结符号);5.2.2 算符文法（OG） 算符文法: 没有形如U∷=…V W…的规则的文法，其中U、V、W∈VN。 即，任意两个非终结符号之