《编译原理5.2.1-12-3-算符优先文法.ppt》由会员分享，可在线阅读，更多相关《编译原理5.2.1-12-3-算符优先文法.ppt（17页珍藏版）》请在三一办公上搜索。
1、第五章 语法分析,5.1 自下而上分析基本问题5.2 算符优先分析 5.3 LR分析5.4 YACC,根据某种优先关系确定“可归约串”.简单优先分析法*求出该文法所有符号之间的优先关系可归约串:句柄是一种规范归约算符优先分析法 只规定算符(广义讲为终结符)之间的优先关系可归约串:最左素短语不是规范归约,优先分析法,1.算符间的优先关系表示,a b 表示a的优先性低于ba b 表示a的优先性等于ba b 表示a的优先性高于b,2.直观算符优先分析法,G:EE+E|EE|E*E|E/E|EE|(E)|i,二义性文法不能构造确定的分析过程,例如：对输入串 i1+i2*i3进行自下而上分析,可构造两棵
2、不同的语法树,算符优先概念的引入,表达式运算的次序只与运算符有关,而与运算对象无关我们称这类文法具有算符特性-优先性,结合性广义讲：终结符为算符,对表达式的文法按公认的计算顺序规定优先级和结合性,优先级最高。服从右结合*,/优先级其次。服从左结合+,-优先级最低。服从左结合(,)括号的优先性大于括号外的运算符,小于括号内的运算符,内括号的优先性大于外括号。#与它相邻的任何运算符的优先性都比它大。i 优先级最高,算符优先关系表,分析步骤详见黑板,G:EE+E|EE|E*E|E/E|EE|(E)|i 利用算符优先关系对输入串 i1+i2*i3 进行移进-归约分析,结论:对于二义性的表达式文法，我们
3、可以直观地给出运算符之间的优先关系，使得输入串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
4、的产生式2.a b,当且仅当 G中含有形如 P aR 的产生式，且 R b 或 R Qb3.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 b,a b 则称G是一个算符优先文法.,补充例：表达式文法,G:EE+E|E*E|(E)|i 该文法不是 算符优先文法,
