《自底向上优先分析法课件》由会员分享，可在线阅读，更多相关《自底向上优先分析法课件（59页珍藏版）》请在金锄头文库上搜索。
1、第第6 6章章 自底向上优先分析法自底向上优先分析法1自底向上优先分析法6.1 概 述对待分析的符号串，自左向右对待分析的符号串，自左向右对待分析的符号串，自左向右对待分析的符号串，自左向右逐个逐个逐个逐个扫描，输入符扫描，输入符扫描，输入符扫描，输入符号栈，一旦栈顶符号串形成某个句型的号栈，一旦栈顶符号串形成某个句型的号栈，一旦栈顶符号串形成某个句型的号栈，一旦栈顶符号串形成某个句型的句柄句柄句柄句柄或或或或可可可可归约串归约串归约串归约串（对应于某产生式的右部），就用该产生（对应于某产生式的右部），就用该产生（对应于某产生式的右部），就用该产生（对应于某产生式的右部），就用该产生式的左部非
2、终结符代替相应右部的文法符号，即式的左部非终结符代替相应右部的文法符号，即式的左部非终结符代替相应右部的文法符号，即式的左部非终结符代替相应右部的文法符号，即归约归约归约归约成识别符号。成识别符号。成识别符号。成识别符号。在分析过程中，每次归约的都是最左边的简单短在分析过程中，每次归约的都是最左边的简单短在分析过程中，每次归约的都是最左边的简单短在分析过程中，每次归约的都是最左边的简单短语（或其它短语）。语（或其它短语）。语（或其它短语）。语（或其它短语）。从语法树的角度，以输入符号为树的末端结点，从语法树的角度，以输入符号为树的末端结点，从语法树的角度，以输入符号为树的末端结点，从语法树的角
3、度，以输入符号为树的末端结点，试图向根结点方向往上构造语法树。试图向根结点方向往上构造语法树。试图向根结点方向往上构造语法树。试图向根结点方向往上构造语法树。2自底向上优先分析法讨论前提和和自自顶顶向向下下技技术术同同样样，不不考考虑虑符符号号的的具具体构成方式。体构成方式。识识别别过过程程是是从从左左到到右右，自自底底向向上上进进行行的的。一一般般都都采采用用规规范范归归约约：每每一一步步都都是是对对句句柄进行归约（特例除外）。柄进行归约（特例除外）。3自底向上优先分析法基本方法采用采用移入移入- -归约归约方法。方法。使用一个栈来存放归约得到的符号。使用一个栈来存放归约得到的符号。在在分分
4、析析的的过过程程中中，识识别别程程序序不不断断地地移移入入符符号号。移移入入的的符符号号暂暂时时存存放放在在一一个个栈栈中中。一一旦旦在在已已经经移移入入的的（和和归归约约得得到到的的）符符号号串串中中包包含含了了一一个个句句柄柄时时，将将这这个个句句柄柄归约归约成为相应的非终结符号。成为相应的非终结符号。参看课本参看课本P102例例6.14自底向上优先分析法基本方法（续）归约中的动作有归约中的动作有4 4类类移入移入：读入一个符号并把它归约入栈。：读入一个符号并把它归约入栈。归归约约：当当栈栈中中的的部部分分形形成成一一个个句句柄柄（栈栈顶顶的符号序列）时，对句柄进行归约。的符号序列）时，对
5、句柄进行归约。接接受受：当当栈栈中中的的符符号号仅仅有有# #和和识识别别符符号号的的时时候候，输输入入符符号号也也到到达达结结尾尾的的时时候候，执执行行接接受动作。受动作。错错误误处处理理：当当识识别别程程序序发发现现输输入入符符号号串串不不是句子时，即出错，调用错误处理模块。是句子时，即出错，调用错误处理模块。5自底向上优先分析法例 子i *i+i i*i+i i E:=iE *i+iE*i+iE* i+iE*i+iE*i +iE*i+i i E:=iE*E +iE*E+i E*E E:=E*EE +iE+iE+iE+i i E:=iE+EE+EE+E E:=E+EE文法文法GEE: E:
6、=E+E|E*E|(E)输入符号串：输入符号串：i*i+i已处理已处理 未处理未处理 句型句型 句柄句柄 规则规则不用此页6自底向上优先分析法例子的解释当当栈栈中中的的符符号号的的栈栈顶顶部部分分还还不不能能形形成成句句柄柄时时，进行移入操作。进行移入操作。一一旦旦发发现现栈栈顶顶部部分分形形成成了了句句柄柄的的时时候候，对对该该句句柄柄进进行行归归约约。将将句句柄柄出出栈栈，然然后后将将归归约约得得到的非终结符号压栈。到的非终结符号压栈。如如果果输输入入是是句句子子，则则栈栈中中的的符符号号（从从底底到到上上）和未处理的符号组成句型。和未处理的符号组成句型。在在例例子子中中，发发现现句句柄柄
7、和和归归约约是是人人为为干干预预的的结结果果。所所以以移移入入-归归约约不不是是实实际际可可运运行行的的技技术术，而是技术的模板。而是技术的模板。不用此页7自底向上优先分析法基本问题如何找出进行直接归约的简单短语？即如何如何找出进行直接归约的简单短语？即如何知道栈顶符号串已形成了句柄？知道栈顶符号串已形成了句柄？将找到的简单短语归约到哪个非终结符号？将找到的简单短语归约到哪个非终结符号？即如何选取适当的产生式进行归约即如何选取适当的产生式进行归约?8自底向上优先分析法6.2 两种优先分析法两种优先分析法简单优先分析法简单优先分析法：求出该文法所有符号（终结符和非终结符）之间求出该文法所有符号（
8、终结符和非终结符）之间求出该文法所有符号（终结符和非终结符）之间求出该文法所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句的优先关系，按照这种关系确定归约过程中的句的优先关系，按照这种关系确定归约过程中的句的优先关系，按照这种关系确定归约过程中的句柄。柄。柄。柄。规范归约。规范归约。规范归约。规范归约。分析准确规范，但效率低，不实用。分析准确规范，但效率低，不实用。分析准确规范，但效率低，不实用。分析准确规范，但效率低，不实用。算符优先分析法算符优先分析法：规定算符之间的优先关系，即只考虑终结符之间规定算符之间的优先关系，即只考虑终结符之间规定算符之间的优先关系，即只
9、考虑终结符之间规定算符之间的优先关系，即只考虑终结符之间的优先关系，而不考虑非终结符的优先关系。的优先关系，而不考虑非终结符的优先关系。的优先关系，而不考虑非终结符的优先关系。的优先关系，而不考虑非终结符的优先关系。不是规范归约。不是规范归约。不是规范归约。不是规范归约。分析速度快，适用于表达式的分析。分析速度快，适用于表达式的分析。分析速度快，适用于表达式的分析。分析速度快，适用于表达式的分析。基本思想基本思想9自底向上优先分析法简单优先分析法简单优先分析法思路思路： 每次察看句型中相邻的两个符号。通过两每次察看句型中相邻的两个符号。通过两个符号的关系判定出前一个符号是句柄的个符号的关系判定
10、出前一个符号是句柄的尾。然后，反向找出句柄的头。这样我们尾。然后，反向找出句柄的头。这样我们就找到了一个句柄。就找到了一个句柄。S0 Sj-1SjSj+1Sj+2 Si-1SiSi+1 SnU10自底向上优先分析法优先关系优先关系和书上的写法不一样。和书上的写法不一样。等同：等同：Si Sj先于：先于：Si Sj后于：后于：SiSj注意：，注意：，和和不同于不同于=，和和 Si；Sj Si：当且仅当：当且仅当 U VW， 其中其中V和和W分别满足分别满足 + V = Sj * W = Si 且且 Si为终结符号。为终结符号。13自底向上优先分析法优先关系的例子优先关系的例子文法：文法：SbAb
11、A(B | a BAa)语言：语言：bab, b(aa)b, b(aa)a)b, 可以从语法树里面导出可以从语法树里面导出部分部分优先关系。优先关系。bAbaSba abb A bS( Bb ( BBb14自底向上优先分析法优先矩阵可以将优先可以将优先关系填写到关系填写到一个矩阵，一个矩阵，得到优先矩得到优先矩阵。阵。(将矩阵将矩阵作为关系的作为关系的表示形式）表示形式）SA Bab()SA=B a ( = b=) =15自底向上优先分析法# b ( ( a a ) a ) b # 句柄句柄: a 归约为归约为A# b ( ( A a ) a ) b # = = 句柄句柄: A a) 归约为归
12、约为B# b ( ( B a ) b # = 句柄句柄: (B 归约为归约为A16自底向上优先分析法识别过程(例子续)# b ( B b # = 句柄句柄: (B 归约为归约为A# b ( A a ) b # = = 句柄句柄: Aa) 归约为归约为B# b ( A a ) b # = = 句柄句柄: Aa) 归约为归约为B# b A b # = = 句柄句柄: bAb 归约为归约为S# b ( B b # = 句柄句柄: (B 归约为归约为A17自底向上优先分析法优先关系的构造根据优先关系的构造性的定义（定义根据优先关系的构造性的定义（定义6.1），），我们立刻可以得到构造算法。我们立刻可以
13、得到构造算法。(1) =的构造：直接对每个规则右部处理，对所的构造：直接对每个规则右部处理，对所有右部有右部X1X2Xn，都有，都有Xi = Xi+1。SjSi=当且仅当当且仅当G中有规则中有规则 U SjSi18自底向上优先分析法（2）的构造：由定义，的构造：由定义，Sj Si 可以得到可以得到存在规则存在规则U SjV，也就是，也就是Sj = V, + HEAD(V)Sk | V = Sk Si1, Si2, , Sin 。SjSi1 Si2 Sin 19自底向上优先分析法（3） 关系的构造：由定义，关系的构造：由定义，Sj Si 表示表示:存在规则存在规则 U VW 其中其中V = W
14、+ TAIL (V)Sl | V = Sl Sj1, Sj2, , Sjm 。 + HEAD(W)Sk | W = Sk Si1, Si2, , Sin 。Sj1Si1 Si2 Sin Sj2 Sjm 20自底向上优先分析法=简单优先关系矩阵（表）文法：文法：SbAbA(B | aBAa)HEAD(A)= ( a HEAD(B)= ( a A TAIL(A)= a ) B SA Bab()SA=B a ( = b=) 21自底向上优先分析法优先关系的冲突当优先矩阵中出现值不唯一的元素当优先矩阵中出现值不唯一的元素时，文法不适合使用优先识别技术时，文法不适合使用优先识别技术来识别句型。来识别句型
15、。22自底向上优先分析法简单优先文法定义定义6.26.2 如果某个文法满足：如果某个文法满足：字字汇汇表表中中的的任任意意两两个个符符号号之之间间至至多多有有一一种种优优先关系成立。先关系成立。任何两个规则式的右部不相同。任何两个规则式的右部不相同。则称该文法为则称该文法为简单优先文法简单优先文法。第一点保证可以识别出句柄第一点保证可以识别出句柄.第二点保证可以确定归约到哪个非终结符号。第二点保证可以确定归约到哪个非终结符号。23自底向上优先分析法定理6.4一个简单优先文法是无二义性的，且其一个简单优先文法是无二义性的，且其任何一个句型任何一个句型SmSn的唯一句柄是满足的唯一句柄是满足条件：
16、条件：Sj-1 Sj = Sj+1 = Sj+2 = = Si-1 = Si Si+1的最左子符号串的最左子符号串SjSj+1Sj+2 Si-1Si。24自底向上优先分析法定理6.4的证明首先用反证法证明任何句型的句柄是唯一的。首先用反证法证明任何句型的句柄是唯一的。句型必然有句柄，且这个句柄必然满足句型必然有句柄，且这个句柄必然满足Sj-1 Sj = Sj+1 = Sj+2 = = Si-1 = Si Si+1 (句句柄柄1)如如果果还还有有另另外外一一个个语语法法树树，那那么么它它对对应应的的归归约约（称称为为归归约约过过程程2）必必然然不不是是把把上上面面的的句句柄柄作为一个整体归约的。
17、作为一个整体归约的。在在归归约约过过程程2中中，当当首首次次有有句句柄柄1(包包括括Sj-1和和Si+1)中中间间的的某某个个符符号号St作作为为句句柄柄（句句柄柄2）的的一一部部分分被被归归约约的的时时候候，我我们们可可以以考考虑虑以以下下的的情况：（下一页）情况：（下一页）25自底向上优先分析法定理6.4的证明(续)如果如果t=j-1，那么，那么, 由句柄由句柄1，Sj-1 Sj； 由句柄由句柄2， Sj-1 = Sj 或者或者Sj-1 Sj；矛盾！；矛盾！如果如果t=i+1，由句柄，由句柄1，Si Si+1； 由句柄由句柄2，Si Si+1 或者或者 Si = Si+1。如果如果i= t
18、 y，那么，那么y也不包含相邻的非终结符。也不包含相邻的非终结符。假设假设x=wUv，而，而y=wuv。由由于于x不不包包含含两两个个相相邻邻的的非非终终结结符符，那那么么w和和v中中没没有有不不相邻的非终结符。相邻的非终结符。根据算符文法的定义，根据算符文法的定义，u中也不包含相邻的非终结符。中也不包含相邻的非终结符。根根据据假假设设，w的的结结尾尾不不是是非非终终结结符符（否否则则，x中中包包含含有有相邻的非终结符）。相邻的非终结符）。同样，同样，v的开始符也不是非终结符。的开始符也不是非终结符。综上所述：综上所述：y中不存在相邻的非终结符。中不存在相邻的非终结符。38自底向上优先分析法定
19、理6.6 和 6.7 的证明假假设设w=xvy是是文文法法的的句句型型，而而v是是相相对对于于V的的短语。短语。 那么那么xVy也是句型。也是句型。 如如果果w中中有有两两个个相相邻邻的的符符号号TU，且且T在在v中中，而而U不在不在v中。显然中。显然U是是y的头符号。的头符号。 因此因此xVy中存在两个相邻的非终结符中存在两个相邻的非终结符VU。 和定理和定理6.5矛盾。矛盾。定理定理6.7的证明和定理的证明和定理6.6类似。类似。39自底向上优先分析法算符优先关系定定义义6.5 设设文文法法G是是一一个个算算符符文文法法，Tj和和Ti是是两两个个任任意意的的终终结结符符，而而U,V,WVN
20、，定定义义算算符符优优先先关关系系如如下：下：当且仅当文法：当且仅当文法G中存在以下形式中存在以下形式的规则的规则： U:= TjTi 或者或者 U:= TjVTi ：当且仅当文法：当且仅当文法G中存在形如中存在形如 U:= TjV 的规则，且的规则，且V= Ti 或者或者 V=WTi ：当且仅当文法：当且仅当文法G中存在形如中存在形如 U:= VTi 的规则，且的规则，且V= Tj 或者或者 V= TjW。+40自底向上优先分析法算符优先关系的直观意义算符优先分析技术的基本思想是通过终结符之算符优先分析技术的基本思想是通过终结符之间的优先关系，确定句型的间的优先关系，确定句型的句柄句柄。对于
21、句型对于句型 N1T1Ni-1Ti-1NiTiNjTjNj+1Tj+1NkTkNk+1满足关系满足关系Ti-1 Ti Ti+1 Tj Tj+1的最左子符号串就是要被归约的的最左子符号串就是要被归约的短语短语。41自底向上优先分析法优先关系例子文法：文法：Z:=EE:=T|E+TT:=F|T*FF:=(E)|i等同关系等同关系：（：（） 只有左、右括号只有左、右括号1对对由推导由推导ZEE+TE+FE+iZEE+TE+T*FE+T*(E)E+T*(E+T)ZEE+TE+T+TE+T+FE+T+(E)得到以下关系：得到以下关系： + i，+ *，* (，( +，+ )，+ +，+ ( 等等42自底
22、向上优先分析法优先关系的构造优先关系的构造优先关系优先关系的构造，只需要按照定义，枚举各的构造，只需要按照定义，枚举各个规则的右部就可以得到。个规则的右部就可以得到。对于关系对于关系 和和 的构造，我们需要引入两个辅的构造，我们需要引入两个辅助的关系：助的关系：FIRSTTERM和和LASTTERM。U FIRSTTERM T 当且仅当存在规则当且仅当存在规则U:=T 或者或者 U:=VTU LASTTERM T 当且仅当存在规则当且仅当存在规则U:=T 或者或者 U:=TV43自底向上优先分析法FIRSTTERM+关系的构造FIRSTTERM+ 并不是并不是FIRSTTERM的传递闭包。的传
23、递闭包。U FIRSTTERM+ T 表示表示T是是U经过若干步推导得经过若干步推导得到的字的首终结符。构造算法如下：到的字的首终结符。构造算法如下：步骤步骤1：如果：如果 U FIRSTTERM T， 那么那么 U FIRSTTERM+ T.步骤步骤2：如果：如果U:=V，且，且V FIRSTTERM+ T， 那么那么U FIRSTTERM+ T。步骤步骤3：重复步骤：重复步骤2，直到过程收敛。，直到过程收敛。44自底向上优先分析法LASTTERM+的构造算法LASTTERM+ 不是不是LASTTERM的传递闭包。的传递闭包。 U LASTTERM+ S 表示表示U经过若干步推导得到的经过若
24、干步推导得到的字的尾终结符为字的尾终结符为S。构造算法为：。构造算法为：步骤步骤1：如果：如果 U LASTTERM T， 那么那么 U LASTTERM+ T。步骤步骤2：如果：如果 U:= V，且，且 V LASTTERM+ T， 那么那么 U LASTTERM+ T。步骤步骤3：重复步骤：重复步骤2，直到收敛。，直到收敛。45自底向上优先分析法关系和的构造关系关系 的构造：的构造： = ()(HEAD*)(FIRSTTERM)= ()(FIRSTTERM+) = (TAIL*)(LASTTERM)T()= (LASTTERM+)T()46自底向上优先分析法算符优先文法定定义义6.6：设设
25、有有算算符符文文法法G，如如果果在在其其任任意意两两个个终终结结符符之之间间，算算符符优优先先关关系系最最多多只只有有一一种种关关系系成成立立，那那么么该该文文法法G称称为为算算符优先文法。符优先文法。47自底向上优先分析法算符优先文法句型的识别由由于于算算符符优优先先分分析析技技术术在在分分析析的的过过程程中中，非非终终结结符符是是“不不可可见见”的的。因因此此，对对于于单单规则，算符优先技术无法处理。规则，算符优先技术无法处理。定义定义6.7 素短语素短语是满足下面条件的短语：是满足下面条件的短语：（1）至少包含一个终结符号。）至少包含一个终结符号。（2）该短语不再包含满足第一个条件的）该
26、短语不再包含满足第一个条件的 更小的短语。更小的短语。48自底向上优先分析法素短语的例子短语有短语有T+T*F+i，T+T*F，T*F，最左边的，最左边的T，i。 其中，其中，素短语素短语为为T*F，i。T+T*F+i，T+T*F不是不是素短素短语语，因为其中包含了，因为其中包含了T*F。T不是不是素短语素短语，因为其中不，因为其中不含终结符。含终结符。EE+TEZT+FiT*FT49自底向上优先分析法定理6.8定理定理6.8：句型句型 N1T1Ni-1Ti-1NiTiNjTjNj+1Tj+1NkTkNk+1中满足关系中满足关系Ti-1 Ti Ti+1 Tj Tj+1的最左子符号串的最左子符号
27、串NiTi NjTjNj+1就是句型的就是句型的最左素短语最左素短语。50自底向上优先分析法句型识别过程关关 系系最左素短语最左素短语符号符号句句 型型1# i +iFi+(i+i)*i2# + ( I +iFF+(i+i)*i3# + ( + i )iFF+(F+i)*i4# + ( + )F+FEF+(F+F)*i5# + () *(E)FF+(E)*i6# + * i #iFF+F*i7# + * #F*FTF+F*F8# + #F+TZF+T51自底向上优先分析法识别得到的语法树FZ+T*EFiF)(+FFiiiEE+T*ETTF)(+EFFiiFiFTTZi52自底向上优先分析法算符
28、优先技术的说明在在算算符符优优先先技技术术的的应应用用中中，分分析析过过程程并并不不考考虑虑非非终终结结符符。可可以以认认为为：编编译译程程序序不不考考虑虑具具体体符符号号的的名名字字，只只考考虑虑它它的的意意义。义。需要有处理素短语的语义处理子程序。需要有处理素短语的语义处理子程序。在在使使用用算算符符优优先先技技术术的的过过程程中中，我我们们可可以以使使用用同同一一个个符符号号N来来表表示示归归约约得得到到的的非非终结符，分析过程照样可以进行。终结符，分析过程照样可以进行。53自底向上优先分析法识别算法流程图开始开始i=1; Si=#R=Next SymbolSi VT或或Si=#j=i-
29、1j=iSjR否否i=i+1; Si=RANYY54自底向上优先分析法识别算法流程图(续)AQ=Sj; j=j-1Sj VTj=i-1Sju w且且在在u到到w的的推推导导过过程程中中，只只用用到到了了形形如如U:=W的单规则。的单规则。U，W为非终结符。为非终结符。+56自底向上优先分析法实际应用的算符优先分析技术可以使用优先函数来替代优先矩阵。优可以使用优先函数来替代优先矩阵。优先函数的求解方法等同于简单优先矩阵先函数的求解方法等同于简单优先矩阵的算法。（前面的算法不考虑优先关系的算法。（前面的算法不考虑优先关系的种类）的种类）可以使用两个栈：运算符栈，运算分量可以使用两个栈：运算符栈，运
30、算分量栈。运算分量（非终结符号）和运算符栈。运算分量（非终结符号）和运算符（终结符号）将分别存放在两个栈中。（终结符号）将分别存放在两个栈中。57自底向上优先分析法算符优先文法的范围可以被用来处理各种表达式。可以被用来处理各种表达式。如果把各个关键字看作算符，这个技术也如果把各个关键字看作算符，这个技术也可以被使用来处理程序设计语言。可以被使用来处理程序设计语言。对于实际使用的程序设计语言，只需要对对于实际使用的程序设计语言，只需要对文法稍微修改就可以应用算符优先分析技文法稍微修改就可以应用算符优先分析技术。术。对于有些情况，比如表达式，我们可以使对于有些情况，比如表达式，我们可以使用单优先函
31、数来解决。实际上即用单优先函数来解决。实际上即f(S)=g(S)58自底向上优先分析法两种优先技术的比较使用范围使用范围简单优先文法简单优先文法算符优先文法算符优先文法关系定义集关系定义集字汇表字汇表终结符号集终结符号集项 目简单优先技术算符优先技术归约方式归约方式规范归约规范归约规范规范归约归约被归约者被归约者句柄句柄质短语质短语语义子程序语义子程序要求少要求少要处理的多要处理的多功能功能低低较高较高存储需求存储需求比较大比较大比较小比较小归约条件归约条件控制方式控制方式优先矩阵或优先函数优先矩阵或优先函数优先矩阵或优先函数优先矩阵或优先函数实现工具实现工具栈栈栈栈优先关系优先关系简单优先关系简单优先关系算符优先关系算符优先关系59自底向上优先分析法
