编译原理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,|,E,E,|,E*E,|,E/E,|,EE,|,(E),|,i,二义性文法,不能构造确定的分析过程,例如：对输入串,i,1,+i,2,*i,3,进行自下而上分析,可构造两棵不同的语法树,算符优先概念的引入,表达式运算的次序只与运算符有关,而与运算对象无关,我们称这类文法具有算符特性,-,优先性,结合性,广义讲：终结符为算符,对表达式的文法按公认的计算顺序规定优先级和结合性,优先级最高。服从右结合,*,/,优先级其次。服从左结合,+,-,优先级最低。服从左结合,(,),括号的优先性大于括号外的运算符,小于括号内的运算符,内括号的优先性大于外括号。,#,与它相邻的任何运算符的优先性都比它大。,i,优先级最高,算符优先关系表,分析步骤详见黑板,G:E,E+E,|,E,E,|,E*E,|,E/E,|,EE,|,(E),|,i,利用算符优先关系对输入串,i,1,+i,2,*i,3,进行移进,-,归约分析,结论,:,对于二义性的表达式文法，我们可以直观地给出运算符之间的优先关系，使得输入串,i,1,+i,2,*i,3,的归约过程可以唯一确定,.,对任意给定的一个文法,如何计算算符之间的优先关系,?,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,中含有形如,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,R,b,A,a,3,、算符优先文法,OPG,文法,Operator Precedence Grammar,一个算符文法,G,中的任意两个终结符对,(a,b),至多只满足下述三种关系之一,:,a b,a b,a b,则称,G,是一个算符优先文法,.,补充例：,表达式文法,G:E,E+E,|,E*E,|,(E),|,i,该文法不是,算符优先文法,