编译原理5.2.1-12-3-算符优先文法.ppt

第五章 语法分析 5.1 自下而上分析基本问题 5.2 算符优先分析 5.3 LR分析 5.4 YACC 根据某种优先关系确定 “可归约串” . 简单优先分析法 * 求出该文法所有符号之间的优先关 系 可归约串: 句柄 是一种规范归约 算符优先分析法 只规定算符(广义讲为终结符)之间的 优先关系 可归约串: 最左素短语 不是规范归约 优先分析法 1. 算符间的优先关系表示 a b 表示a的优先性低于b a b 表示a的优先性等于b a b 表示a的优先性高于b 2. 直观算符优先分析法 G:E E+E | EE| E*E | E/E | EE | (E) | i 二义性文法 不能构造确定的分析过程 例如：对输入串 i1+i2*i3进行自下而上分析, 可构造两棵不同的语法树 算符优先概念的引入 表达式运算的次序只与运算符有关,而 与运算对象无关 我们称这类文法具有算符特性 -优先性, 结合性 广义讲：终结符为算符 对表达式的文法按公认的 计算顺序规定优先级和结合性 优先级最高。服从右结合 * , / 优先级其次。服从左结合 + , - 优先级最低。服从左结合 ( , )括号的优先性大于括号外的运算符, 小于括号内的运算符, 内括号的优先性大于 外括号。 # 与它相邻的任何运算符的优先性都 比它大。 i 优先级最高 算 符 优 先 关 系 表 分析步骤详见黑板 G:E E+E | EE| E*E | E/E | EE | (E) | i 利用算符优先关系对输入串 i1+i2*i3 进行移进-归约分析 结论: 对于二义性的表达式文法，我们可以直 观地给出运算符之间的优先关系，使得输入串 i1+i2*i3的归约过程可以唯一确定. 对任意给定的一个文法, 如何计算算符之间的优先关系? 5.2.1 算符优先文法及优先表构造 1、算符文法 2、算符优先关系的定义 3、算符优先文法 4、优先关系表的构造 1、算符文法 OG文法 Operator Grammar 任一产生式都不含形如以下形式的右部: QR 产生式的右部不含有两个相邻(相继/并列) 的非终结符 算符文法的两个限制 上下文无关文法 不含空产生式 补充例：表达式文法 G: EE+E | E*E | (E) | i 该文法是算符文法 2、算符优先关系的定义 1. a b , 当且仅当 G中含有形如 Pab 或 PaQb 的产生式 2. a b , 当且仅当 G中含有形如 P aR 的产生式，且 R b 或 R Qb 3. a b , 当且仅当 G中含有形如 P Rb 的产生式，且 R a 或 R aQ 图示 算符优先关系 1 1. a b , 当且仅当 G中含有形如 Pab 或 PaQb 的产生式 P a b 图示 算符优先关系 2 2. a b , 当且仅当 G中含有形如 P aR 的产生式，且 R b 或 R Qb P a R A b 图示 算符优先关系 3 3. a b , 当且仅当 G中含有形如 P Rb 的产生式，且 R a 或 R aQ P Rb A a 3、算符优先文法 OPG文法 Operator Precedence Grammar 一个算符文法G中的任意两个终结符对 (a, b)至多只满足下述三种关系之一: a b ,