编译原理5.2.1—12—3—算符优先文法.pptVIP

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