语法分析自底向上分析.pptVIP

第五章 语法分析——自底向上分析 5.1 基本问题 方法 从句子出发，反复利用产生式做归约 （用产生式的左部替代右部），逐步构造语法分析树，最后得到文法的开始符号 核心 寻找句型与句柄的匹配 分析方法 例 5-1： S → a A c B e A → A b｜b B → d 分析过程: abbcde → aAbcde → aAcde → aAcBe → S 语法分析树的生成 a b b c d e 句柄：最左直接短语 短语： 设文法Ｇ＝｛ＶT，ＶN，Ｐ，Ｓ｝ 若 Ｓ =* αＡδ 且 Ａ =+ β， 则称β是句型αβδ相对于非终结符Ａ的短语 若Ｓ=*αＡδ 且Ａ=β，则称β是直接短语。 规范归约的定义 设 α为文法 G 的句子，称序列 αn，...，α1，α0 为 α的规范归约，其中 1) αn 　= α 2) α0 　= Ｓ （开始符号） 3) 对每个 i (1 = i = n)，αi-1 是将αi 中的句柄归约后得到的 规范归约 规范归约是规范推导(最右推导)的逆过程 中心问题是如何寻找和确定一个句型中的句柄 各种自底向上分析采用不同的方法确定句柄 移进归约分析器 分析器的四种动作 1) 移进：将下一输入符号移入栈 2) 归约：用产生式左侧的非终结符替换栈顶的句柄 3) 接受：分析成功 4) 出错：出错处理 各种自底向上分析方法的控制方法不同 例5-2：id+id*id 的分析 动作 栈 输入缓冲区 1) # id1+id2*id3# 2) 移进 #id1 +id2*id3# 3) 归约 E→id #E +id2*id3# 4) 移进 #E+ id2*id3# 5) 移进 #E+id2 *id3# 6) 归约 E→id #E+E *id3# 7) 移进 #E+E* id3# 8) 移进 #E+E*id3 # 9) 归约 E→id #E+E*E # 10) 归约 E→E*E #E+E # 11) 归约 E→E+E #E # 12) 接受 产生式序列表示语法分析树 E → id E → id E → id E → E * E E → E + E 移进归约分析中的冲突 文法复杂时出现: 1) 移进归约冲突 例中的 6) 可以移进 id 或 归约 E→E+E 2) 归约归约冲突 存在两个可用的产生式 各种分析方法处理冲突的方法不同 5.2 算符优先分析 方法： 利用终结符之间的优先关系确定句柄。 算符优先关系的定义 (终结符之间) a ≮ b a 的优先级低于 b a ≡ b a 的优先级等于 b a ≯ b a 的优先级高于 b 算符优先文法 如果文法 Ｇ 中不存在具有相邻非终结符的产生式，则称为算符文法。 如果无ε产生式的算符文法 Ｇ中，且任意两个终结符之间至多有一种优先关系，则称为算符优先文法。 算符优先分析仅适用于算符优先文法。 例5-3：表达式文法的算符优先关系 E → E + E ｜ E - E ｜ E * E ｜ E / E ｜ E ^ E ｜ ( E ) ｜ id 存在优先级 + ≮ * * ≯ + id ≯ + id ≯ * + ≮ id * ≮ id id ≯ # # ≮ id 算符优先关系的使用 分析例：id + id * id 在输入符号串中插入优先符，形成一组以 ≮为左端，以≡为中缀，以≯为右端的短语。 ? # ≮ id ≯ + ≮ id ≯ * ≮ id ≯ # 对短语进行归约后再次插入优先符 ? # ≮ E + ≮ E * E ≯ # ? # ≮ E + E ≯ # ? # E # 算符优先分析的实现 组成结构 移进归约分析器 + 优先关系表 工作框架 输入、输出、初态、终态不变 分析算法 P93 参照输入串、优先关系表，完成一组产生式归约，产生语法分析树。 id+id*id 的分析过程 算符优先关系表的构造 对于任何符号 X 和 Y： 若 X 的运算优先级高于 Y， 则设 X ≯ Y 和 Y ≮ X 若 X 和 Y 运算优先级相同， 且具有左结合性，则设 X ≯ Y 和 Y ≯ X; 否则设 X ≮ Y 和 Y ≮ X 设 X ≮ id， id ≯ X， X ≮ (， ( ≮ X， ) ≯ X，