资源描述：
《编译原理算符优先分析法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、4.3自下而上分析法的一般原理1自下而上语法分析概述基本思想：用一个寄存文法符号的栈，将一个输入串反向归约至文法的开始符号。特点：效率高、文法限制少。1自下而上语法分析概述移进－归约过程实例。例4.11设有文法G[A]：(1)AaBcDe(2)Bb(3)BBb(4)Dd对输入串abbcde$的移进－归约分析过程对输入串abbcde$移进－归约分析过程：步骤符号栈输入串动作012345678910$$a$ab$aB$aBb$aB$aBc$aBcd$aBcD$aBcDe$Aabbcde$bbcde$bcde$bcde$cde$cde$de
2、$e$e$$$a进栈b进栈用Bb归约b进栈用BBb归约c进栈d进栈用Dd归约e进栈用AaBcDe归约分析成功2移进－归约的基本思想(1)用一个栈寄存文法符号，移进将一个终结符推进栈;(2)归约是将0个或多个符号从栈中弹出，用相应产生式的左部一个非终结符压入栈;把栈顶被归约的一串符号称为可归约串;(3)重复这一过程直至整个输入串分析完毕;(4)最终栈中只剩下左界符$和开始符号S，则所分析的输入串是文法的正确句子;否则，出错。可归约串3分类◆算符优先分析法◆规范归约分析法简单优先分析法LR分析法用句柄刻画可归约串用最左素短语刻画可归约串4
3、.4算符优先分析法4.4.1方法概述1特点适合分析各类表达式;宜于手工实现;规定运算符之间的优先顺序(优先关系，结合性质)。通过比较算符之间的优先关系确定可归约串。4.4.1方法概述2优先关系例文法G[E]：EE+E
4、E*E
5、(E)
6、id对输入串id+id*id的规范归约过程。(1)id+id*id(2)E+id*id(3)E+E*id(4)E+E*E(5)E+E(6)E(1)id+id*id(2)E+id*id(3)E+E*id(4)E*id(5)E*E(6)E*优先于＋：＋优先于*：4.4.1方法概述3优先关系种类任何两个相邻的终
7、结符a和b可能的优先关系有3种：ab:a的优先级低于bab:a的优先级等于bab:a的优先级高于b注：优先关系与出现的左右次序有关，不同于数学符号<,=,>。4.4.1方法概述4优先关系矩阵(表)矩阵的行和列都是文法的终结符;矩阵元素是两终结符间的优先关系。算符优先分析法借助优先关系表寻找句型的可归约串。算符优先关系表实例+*id()$+*id()$栈顶第一个终结符当前输入串首字符4.4.2算符优先文法的定义1算符文法的定义设有文法G，若G中没有形如U…VW…的规则，其中V和W为非终结符，则G称为算符文法，也称OG文法。性质：1.在算
8、符文法中任何句型都不包含两个相邻的非终结符。2.如Ab或bA出现在算符文法的句型中，则中任何含b的短语必含有A。4.4.2算符优先文法的定义2算符优先关系的定义在OG中定义算符优先关系：(1)ab:含有P…ab…，或P…aQb…的规则。(2)ab:含有P…aR…的规则，且Rb…或RQb…(3)ab:含有P…Rb…的规则，且R…a或R…aQ。4.4.2算符优先文法的定义2算符优先关系的定义规定：若Sa…或SCa…，则$a若S…a或S…aC，则a$4.4.2算符优先文法的定义3算符优先文法的定义设有一个不含规则的OG文法G，如果任意两个终
9、结符间至多有一种算符关系存在，则称G是算符优先文法，也称OPG文法。结论：算符优先文法是无二义的。4.4.3算符优先关系表的构造1FIRSTVT集、LASTVT集FIRSTVT(A)={b
10、Ab…或ABb…,bVT,BVN}即：非终结符Ａ往下推导所有可能出现的首个算符的集合．LASTVT(A)={a
11、A…aA…aB,aVT,BVN}即：非终结符Ａ往下推导所有可能出现的最后一个算符的集合．4.4.3算符优先关系表的构造2算符优先关系表的构造方法(1)为每个非终结符Ａ计算FIRSTVT(A),LASTVT(A)(2)计算算符之间的优先关系
12、，并填表。计算方法：★关系:若A…ab…或A…aBb,则ab★关系:若A…aB…,则bFIRSTVT(B),ab★关系:若A…Bb…,则aLASTVT(B),ab(3)最后，在表中填入界符的优先关系：对FIRSTVT(S)中所有b,置$b;对LASTVT(S)中所有a,置a$.置$$。例4.12文法G[E]:EE+T
13、TTT*F
14、FF(E)
15、id构造该文法的算符优先关系表。FIRSTVTLASTVTETF{+,*,(,id}{*,(,id}{(,id}{+,*,),id}{*,),id}{),id}Homework:(P105)-4.
16、5(2)4.4.4算符优先分析算法的设计0算符优先分析法与规范归约的区别算符优先分析法:只考虑终结符之间的优先关系来确定可归约串，而与非终结符无关。规范归约:自上而下最右推导的逆过程。例4.12文法G[E]:EE+T
17、T
