自底向上优先分析法ppt课件

1、第第6 6章章 自底向上优先分析法自底向上优先分析法6.1 概 述讨论前提根本方法参看课本参看课本P102例例6.1根本方法续例 子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:=E+E|E*E|(E)输入符号串：输入符号串：i*i+i已处置已处置 未处置未处置 句型句型 句柄句柄 规那么规那么不用此页例子的解释 当栈中的符号的栈顶部分还不能构成句柄时，当栈中的符号的栈顶部分还不能构成句

2、柄时，进展移入操作。进展移入操作。 一旦发现栈顶部分构成了句柄的时候，对该一旦发现栈顶部分构成了句柄的时候，对该句柄进展归约。将句柄出栈，然后将归约得句柄进展归约。将句柄出栈，然后将归约得到的非终结符号压栈。到的非终结符号压栈。 假设输入是句子，那么栈中的符号从底到假设输入是句子，那么栈中的符号从底到上和未处置的符号组成句型。上和未处置的符号组成句型。 在例子中，发现句柄和归约是人为干涉的结在例子中，发现句柄和归约是人为干涉的结果。所以移入果。所以移入-归约不是实践可运转的技术，归约不是实践可运转的技术，而是技术的模板。而是技术的模板。不用此页根本问题 如何找出进展直接归约的简单短语？即如何如

3、何找出进展直接归约的简单短语？即如何知道栈顶符号串已构成了句柄？知道栈顶符号串已构成了句柄？ 将找到的简单短语归约到哪个非终结符号？将找到的简单短语归约到哪个非终结符号？即如何选取适当的产生式进展归约即如何选取适当的产生式进展归约?S0 Sj-1SjSj+1Sj+2 Si-1SiSi+1 SnU优先关系的定义 V = Sj* W = Si 且且 Si为终结符号。为终结符号。bAbaSba abb A bS( Bb ( BBb优先矩阵SA Bab()SA=B a ( = b=) =# b ( ( a a ) a ) b # 句柄句柄: a 归约为归约为A# b ( ( A a ) a ) b #

4、 = = 句柄句柄: A a) 归约为归约为B# b ( ( B a ) b # = 句柄句柄: (B 归约为归约为A识别过程(例子续)# 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 归约为归约为A优先关系的构造 根据优先关系的构造性的定义定义根据优先关系的构造性的定义定义6.1，我们立刻可以得到构造算法。我们立刻可以得到构造算法

5、。 (1) =的构造：直接对每个规那么右部处置，的构造：直接对每个规那么右部处置，对一切右部对一切右部X1X2Xn，都有，都有Xi = Xi+1。SjSi=当且仅当当且仅当G中有规那么中有规那么 U SjSi 2的构造：由定义，的构造：由定义，Sj Si 可以得可以得到到存在规那么存在规那么U SjV ，也就是，也就是Sj = V, + HEAD(V)Sk | V = Sk Si1, Si2, , Sin 。SjSi1 Si2 Sin 3 关系的构造：由定义，关系的构造：由定义，Sj Si 表示表示:存在规那么存在规那么 U VW 其中其中V = W + TAIL (V)Sl | V = Sl

6、 Sj1, Sj2, , Sjm 。 + HEAD(W)Sk | W = Sk Si1, Si2, , Sin 。Sj1Si1 Si2 Sin Sj2 Sjm =简单优先关系矩阵表文法：文法：SbAbA(B | aBAa)HEAD(A)= ( a HEAD(B)= ( a A TAIL(A)= a ) B SA Bab()SA=B a ( = b=) 优先关系的冲突 当优先矩阵中出现值不独一的元素当优先矩阵中出现值不独一的元素时，文法不适宜运用优先识别技术时，文法不适宜运用优先识别技术来识别句型。来识别句型。简单优先文法 定义定义6.26.2 假设某个文法满足：假设某个文法满足： 字汇表中的恣

7、意两个符号之间至多有一种优先字汇表中的恣意两个符号之间至多有一种优先关系成立。关系成立。 任何两个规那么式的右部不一样。任何两个规那么式的右部不一样。 那么称该文法为简单优先文法。那么称该文法为简单优先文法。 第一点保证可以识别出句柄第一点保证可以识别出句柄. . 第二点保证可以确定归约到哪个非终结符号。第二点保证可以确定归约到哪个非终结符号。定理6.4 一个简单优先文法是无二义性的，且其一个简单优先文法是无二义性的，且其任何一个句型任何一个句型SmSn的独一句柄是满足的独一句柄是满足条件：条件： Sj-1 Sj = Sj+1 = Sj+2 = = Si-1 = Si Si+1的最左子符号串的

8、最左子符号串SjSj+1Sj+2 Si-1Si。定理6.4的证明 首先用反证法证明任何句型的句柄是独一的。首先用反证法证明任何句型的句柄是独一的。 句型必然有句柄，且这个句柄必然满足句型必然有句柄，且这个句柄必然满足 Sj-1 Sj = Sj+1 = Sj+2 = = Si-1 = Si Si+1 (句柄句柄1) 假设还有另外一个语法树，那么它对应的归约假设还有另外一个语法树，那么它对应的归约称为归约过程称为归约过程2必然不是把上面的句柄作为必然不是把上面的句柄作为一个整体归约的。一个整体归约的。 在归约过程在归约过程2中，当初次有句柄中，当初次有句柄1(包括包括Sj-1和和Si+1)中间的某

9、个符号中间的某个符号St作为句柄句柄作为句柄句柄2的一的一部分被归约的时候，我们可以思索以下的情况：部分被归约的时候，我们可以思索以下的情况：下一页下一页定理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 y，那么，那么y也不包含相邻的非终结符。也不包含相邻的非终结符。 假设假设x=wUv，而，而y=wuv。 由于由于x不包含两个相邻的非终结符

10、，那么不包含两个相邻的非终结符，那么w和和v中没有中没有不相邻的非终结符。不相邻的非终结符。 根据算符文法的定义，根据算符文法的定义，u中也不包含相邻的非终结符。中也不包含相邻的非终结符。 根据假设，根据假设，w的结尾不是非终结符否那么，的结尾不是非终结符否那么，x中包中包含有相邻的非终结符。含有相邻的非终结符。 同样，同样，v的开场符也不是非终结符。的开场符也不是非终结符。 综上所述：综上所述：y中不存在相邻的非终结符。中不存在相邻的非终结符。定理6.6 和 6.7 的证明 假设假设w=xvy是文法的句型，而是文法的句型，而v是相对于是相对于V的的短语。短语。 那么那么xVy也是句型。也是句

11、型。 假设假设w中有两个相邻的符号中有两个相邻的符号TU，且，且T在在v中，中，而而U不在不在v中。显然中。显然U是是y的头符号。的头符号。 因此因此xVy中存在两个相邻的非终结符中存在两个相邻的非终结符VU。 和定理和定理6.5矛盾。矛盾。 定理定理6.7的证明和定理的证明和定理6.6类似。类似。算符优先关系定义定义6.5 设文法设文法G是一个算符文法，是一个算符文法，Tj和和Ti是两个恣是两个恣意的终结符，而意的终结符，而U,V,WVN，定义算符优先关系，定义算符优先关系如下：如下：当且仅当文法：当且仅当文法G中存在以下方式的规那么：中存在以下方式的规那么： U:= TjTi 或者或者 U

12、:= TjVTi ：当且仅当文法：当且仅当文法G中存在形如中存在形如 U:= TjV 的规那么，且的规那么，且V= Ti 或者或者 V=WTi ：当且仅当文法：当且仅当文法G中存在形如中存在形如 U:= VTi 的规那么，且的规那么，且V= Tj 或者或者 V= TjW。+算符优先关系的直观意义 算符优先分析技术的根本思想是经过终结符算符优先分析技术的根本思想是经过终结符之间的优先关系，确定句型的句柄。之间的优先关系，确定句型的句柄。 对于句型对于句型 N1T1Ni-1Ti-1NiTiNjTjNj+1Tj+1NkTkNk+1 满足关系满足关系 Ti-1 Ti Ti+1 Tj Tj+1 的最左子

13、符号串就是要被归约的短语。的最左子符号串就是要被归约的短语。优先关系例子 文法：文法：Z:=EE:=T|E+TT:=F|T*FF:=(E)|i 等同关系：等同关系： 只需左、右括号只需左、右括号1对对 由推导由推导 ZEE+TE+FE+i ZEE+TE+T*FE+T*(E)E+T*(E+T) ZEE+TE+T+TE+T+FE+T+(E) 得到以下关系：得到以下关系： + i，+ *，* (，( +，+ )，+ +，+ ( 等等优先关系的构造优先关系的构造 优先关系优先关系的构造，只需求按照定义，枚举各的构造，只需求按照定义，枚举各个规那么的右部就可以得到。个规那么的右部就可以得到。 对于关系对

14、于关系 和和 的构造，我们需求引入两个的构造，我们需求引入两个辅助的关系：辅助的关系：FIRSTTERM和和LASTTERM。 U FIRSTTERM T 当且仅当存在规那么当且仅当存在规那么 U:=T 或者或者 U:=VT U LASTTERM T 当且仅当存在规那么当且仅当存在规那么 U:=T 或者或者 U:=TVFIRSTTERM+关系的构造 FIRSTTERM+ 并不是并不是FIRSTTERM的传送闭包。的传送闭包。U FIRSTTERM+ T 表示表示T是是U经过假设干步推导经过假设干步推导得到的字的首终结符。构造算法如下：得到的字的首终结符。构造算法如下： 步骤步骤1：假设：假设

15、U FIRSTTERM T， 那么那么 U FIRSTTERM+ T. 步骤步骤2：假设：假设U:=V，且，且V FIRSTTERM+ T， 那么那么U FIRSTTERM+ T。 步骤步骤3：反复步骤：反复步骤2，直到过程收敛。，直到过程收敛。LASTTERM+的构造算法 LASTTERM+ 不是不是LASTTERM的传送闭包。的传送闭包。 U LASTTERM+ S 表示表示U经过假设干步推导经过假设干步推导得到的字的尾终结符为得到的字的尾终结符为S。构造算法为：。构造算法为： 步骤步骤1：假设：假设 U LASTTERM T， 那么那么 U LASTTERM+ T。 步骤步骤2：假设：假

16、设 U:= V，且，且 V LASTTERM+ T， 那么那么 U LASTTERM+ T。 步骤步骤3：反复步骤：反复步骤2，直到收敛。，直到收敛。关系 和 的构造 关系关系 的构造：的构造： = ()(HEAD*)(FIRSTTERM)= ()(FIRSTTERM+) = (TAIL*)(LASTTERM)T()= (LASTTERM+)T()算符优先文法 定义定义6.6：设有算符文法：设有算符文法G，假设在其恣，假设在其恣意两个终结符之间，算符优先关系最多意两个终结符之间，算符优先关系最多只需一种关系成立，那么该文法只需一种关系成立，那么该文法G称为称为算符优先文法。算符优先文法。算符优

17、先文法句型的识别 由于算符优先分析技术在分析的过程中，由于算符优先分析技术在分析的过程中，非终结符是非终结符是“不可见的。因此，对于单不可见的。因此，对于单规那么，算符优先技术无法处置。规那么，算符优先技术无法处置。 定义定义6.7 素短语是满足下面条件的短语：素短语是满足下面条件的短语： 1至少包含一个终结符号。至少包含一个终结符号。 2该短语不再包含满足第一个条件的该短语不再包含满足第一个条件的 更小的短语。更小的短语。素短语的例子 短语有短语有T+T*F+i，T+T*F，T*F，最左边的，最左边的T，i。 其中，素短语为其中，素短语为T*F，i。 T+T*F+i，T+T*F不是素短不是素

18、短语，由于其中包含了语，由于其中包含了T*F。 T不是素短语，由于其中不不是素短语，由于其中不含终结符。含终结符。EE+TEZT+FiT*FT定理6.8 定理定理6.8：句型：句型 N1T1Ni-1Ti-1NiTiNjTjNj+1Tj+1NkTkNk+1 中满足关系中满足关系 Ti-1 Ti Ti+1 Tj Tj+1 的最左子符号串的最左子符号串 NiTi NjTjNj+1 就是句型的最左素短语。就是句型的最左素短语。句型识别过程关关 系系最左素短语最左素短语符号符号句句 型型1# i +iFi+(i+i)*i2# + ( I +iFF+(i+i)*i3# + ( + i )iFF+(F+i)

19、*i4# + ( + )F+FEF+(F+F)*i5# + () *(E)FF+(E)*i6# + * i #iFF+F*i7# + * #F*FTF+F*F8# + #F+TZF+T识别得到的语法树FZ+T*EFiF)(+FFiiiEE+T*ETTF)(+EFFiiFiFTTZi算符优先技术的阐明 在算符优先技术的运用中，分析过程并在算符优先技术的运用中，分析过程并不思索非终结符。可以以为：编译程序不思索非终结符。可以以为：编译程序不思索详细符号的名字，只思索它的意不思索详细符号的名字，只思索它的意义。义。 需求有处置素短语的语义处置子程序。需求有处置素短语的语义处置子程序。 在运用算符优先

20、技术的过程中，我们可在运用算符优先技术的过程中，我们可以运用同一个符号以运用同一个符号N来表示归约得到的非来表示归约得到的非终结符，分析过程照样可以进展。终结符，分析过程照样可以进展。识别算法流程图开场开场i=1; Si=#R=Next SymbolSiVT或或Si=#j=i-1j=iSjR否否i=i+1; Si=RANYY识别算法流程图(续)AQ=Sj; j=j-1SjVTj=i-1Sju w 且在且在u到到w的推导过程中，只用到了形如的推导过程中，只用到了形如U:=W的单规那么。的单规那么。U，W为非终结符。为非终结符。+实践运用的算符优先分析技术 可以运用优先函数来替代优先矩阵。优可以运用优先函数来替代优先矩阵。优先函数的求解方法等同于简单优先矩阵先函数的求解方法等