编译原理5.2.1-1_2-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 的产生式,图示 算符优先关系 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