第06章、自底向上优先分析法

1、126.1 自底向上语法分析概述6.2 简单优先分析6.3 算符优先分析 346.1 自底向上语法分析概述p自底向上分析也称移进归约分析，实现思想是对输入符号串自左至右进行扫描，并将输入符逐个移入栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串（该句柄或可归约串对应某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就是确认输入串是文法的句子。p自底向上分析的关键问题是如何确定可归约串以进行归约。p自底向上语法分析比自上而下语法分析更有效率，对语法的限制更少。51. 归约和语法分析树

2、显然，abbcde是该文法的一个句子，于是可如右图构造其语法分析树。 该语法树的构造的确是一个“自左而右、自下而上”的过程，把这一类分析方法统称为“自下而上”的。GE: S aAcBe A b|Ab B dabbcdeAABS6自底向上语法分析的策略：移进-归约分析；移进就是将一个终结符推进栈归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈接受指宣布最终分析成功，可以把它看成是归约的一种特殊形式；出错处理指发现栈顶的内容与输入串相悖，分析工作无法正常进行。此时需调用出错处理程序进行诊察和校正，并调整栈顶的内容。2. 移进归约7 在计算机上模拟以上的语法分析树的构造过程，可借助

3、于一个符号栈来实现：输入串：abbcde#步骤：动作：符号栈：12345678910移进a移进b 归约b 移进b 归约Ab移进c 移进d归约d归约aAcBe移进e归约产生式：#a#ab#aA#aAb#aA#aAc#aAcd#aAcB#aAcBe#S(2)(3)(4)(1)8上述自下而上分析法就是对栈的“移进归约”法，更进一步的，也就是对句子的一个规范归约过程何为规范归约呢？（回顾短语、句柄、推导、归约）9短语、句柄的定义 10推导、规约的定义 是文法G的产生式，若有v, w满足：v=, w=, 其中V*,V* 则称v直接推导到w，记作 v w，也称w直接归约到v，就是说归约是推导的逆过程。 自

4、左向右的规约过程也称规范归约，是最右推导的逆过程，因此规范归约也称最左归约；最右推导常被称为规范推导，由规范推导得到的句型称为规范句型。 再来看上述的例子，每一步归约都是替换句柄：11算法应考虑的问题 何时移进？ 在每一步中如何选择子串进行归约？ 算法是否能够终止？ 算法是否快速？ 算法是否能够处理所有的情况？12归约归约T iT + i | 移进移进T + | i移进移进i | * i + i移进移进i * | i + i移进移进|i * i + iE |归约归约E T + ET + E |归约归约E TT + T |移进移进T | + i归约归约T i * Ti * T | + i归约归约

5、 T ii * i | + i文法文法GE：E T + E | TT i * T | i | (E)ETE+i*iTiT13 我们如何决定什么时候移进，什么时候归约？ 考虑 i | * i + i 我们可以用 T i 进行归约，而得到 T| * i + i 致命错误: 无法归约到开始符号 E 直觉: 归约时应想办法归约到文法的开始符号 一般的移进-归约策略： 若句柄在栈顶出现，则归约 否则移进14自底向上的分析算法 优先分析法 -简单优先分析法 -算符优先分析法 LR分析 -LR(0) -SLR(1) -LR(1)156.2 简单优先分析法 对一个文法按一定原则求出该文法所有符号（终结符和非终

6、结符）之间的优先关系，按照这种关系确定归约过程中的句柄。 它的归约实际上是一种规范归约。16一、简单优先分析基本思想 1、对句型中相邻的文法符号规定优先关系，以寻找句型中的句柄； 2、规定句柄内各相邻符号之间具有相同的优先级； 3、规定句柄两端符号优先级要比位于句柄之外而又和句柄相邻的符号的优先级高，以先归约句柄； 4、对于文法中所有符号，只要它们可能在某个句型中相邻，就要为它们规定相应的优先关系，若某两个符号永远不可能相邻，则它们之间就无关系。17 优先关系 X =Y 文法G中存在产生式A.XY. X Y 文法G中存在产生式A.XB.，且B Y. X Y 文法G中存在产生式A.BD.，且B

7、.X,D Y. 对任何X， - 若文法开始符号S = X，则# X，则X#。* *18优先关系举例 GS: S bAb (1) A (B|a (2) B Aa) (3)19 根据优先关系的定义，将简单优先文法中各文法符号之间的这种关系用一个矩阵表示，称作简单优先矩阵。 简单优先矩阵的构造可通过定义求出，也可通过Warshall算法实现。 具体方法我们不作讨论。 20简单优先关系矩阵 S b A ( B a ) # S b A ( B a ) # GS: S bAb (1) A (B|a (2) B Aa) (3) 空白处表示这两个终结符不能相邻，故没优先关系 对于与#相邻的符号，所有符号 #，

8、# 所有符号21 满足以下条件的文法是简单优先文法（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。（2）在文法中任意两个产生式没有相同的右部。 22 读入一个单词后，比较栈顶符号和该单词的优先级，若栈顶符号优先级低于或等于该单词，继续读入；若栈顶符号优先级高于读入符号，则找句柄进行归约，然后继续读入。直到最后栈内只剩下开始符号，输入串读到“”为止。此时识别正确。23文法文法GS：(1) S bAb(2) A (B|a(3) B Aa)步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # b(aa)b# #b,移进移进 2） #b (aa)b# b(,移进移进 3） #b

9、( aa)b# (a,归约归约Aa 5） #b(A a)b# A=a,移进移进 6） #b(Aa )b# a=),移进移进 7） #b(Aa) b# )b,归约归约BAa) 8） #b(B b# Bb,归约归约A(B 9） #bA b# A=b,移进移进10） #bAb # b#,归约归约SbAb11） #S # 接受接受对输入串对输入串b(aa)b#的简单优先分析过程的简单优先分析过程简单优先关系矩阵 S b A ( B a ) # S b A ( B a ) # 24 优点：技术简单，准确，规范 缺点：适用范围小，分析表尺寸太大，分析效率低。 256.3 算符优先分析 某些文法具有“算符”

10、特性表达式运算符（优先级、结合性）人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性 只规定算符（终结符）之间的优先关系。只考虑算符之间的优先关系来确定句柄，找到句柄就归约，不是规范归约。26 1、自底向上归约 2、规定算符(更一般地说，指终结符)的优先级及结合规则，以使得分析过程唯一 3、比较相邻两个算符而决定动作 注：1)这里的关键是对所有算符定义某种优先关系 2)直观算符优先分析法是仿效四则运算的计算过程而构造的一种语法分析方法 27如何确定算符优先关系？（1）i 的优先级最高（2） 优先级次于i，右结合（3）*和/优先级次之，左结合（4）+和-优先级最低，左结合（5）括号(,

11、)的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先级大于外括号（6）#的优先级低于与其相邻的算符实例：文法GE：EE+EE*EEE(E)i算符优先关系表28文法GE：EE+EE*EEE(E)i步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # i+i*i# #i,移进移进 2） #i +i*i# #+,归约归约 3） #E +i*i# #+,移进移进 4） #E+ i*i# +i,移进移进 5） #E+i *i# +*,归约归约 6） #E+E *i# +*,移进移进 7） #E+E* i# *i,移进移进 8） #E+E*i # *#,归约归约 9） #E+E*E # +

12、#,归约归约10） #E+E # #,归约归约11） #E # 接受接受对输入串i+i*i的算符优先分析过程算符优先关系表29 定义: 设有一文法G，如果G中没有形如 ABC的产生式，其中B和C为非终结符，则称G 为算符文法（也称OGOperator Grammar）。 性质1：在算符文法中任何句型都不包含两个相邻的非终结符. 性质2：若 Va 或 aV 出现在算符文法的句型 中，其中VVN,aVT, 则 中任何含 a 的短语必含有V.（既包含该算符左右两边的非终结符）30 设G是一个不包含空串产生式的算符文法，并设a,b VT; P,Q,R VN ，定义关系：1)a b 当且仅当G中含有形如

13、P ab产生式，或者P aRb产生式；2)a b 当且仅当G中含有形如P aR的产生式，且R=b, 或R = Qb;3)a b 当且仅当G中有形如P Rb产生式，且R =a，或R =aQ.规定 若 S x或 S Vx 则 # x若S x 或 S xV 则 x #+31 设有一不含产生式的算符文法G，若任意两个终结符间至多存在一种算符优先关系，则称G 为算符优先文法(OPGOperation Priority Grammar)。结论 算符优先文法是无二义的。32 首先引入两个概念 FIRSTVT(B)=b|B b或B Cb. 对于非终结符B，其往下推导所可能出现的首个算符 LASTVT(B)=a

14、|B a或B .aC 对于非终结符B，其往下推导所可能出现的最后一个算符 由定义直接构造 由关系图法构造算符优先关系表(不讲)33构造集合FIRSTVT(P)的算法 根据FIRSTVT(P)的定义，按下面的规则来构造： (1) 若有产生式P a或P Qa ，则 a FIRSTVT(P) (2) 若a FIRSTVT(Q)，且有产生式 P Q，则 a FIRSTVT(P) 例 GS: S aAcBe A Ab|b B dFIRSTVT(S)=a FIRSTVT(A)=bFIRSTVT(B)=d34构造集合LASTVT(P)的算法 根据LASTVT(P)的定义，按下面的规则来构造： (1) 若有产

15、生式P a或P aQ ，则 a LASTVT(P) (2) 若a LASTVT(Q)，且有产生式P Q ，则 a LASTVT(P)例GS: S aAcBe A Ab|b B dLASTVT(S)=e LASTVT(A)=bLASTVT(B)=d35如何计算算符优先关系1) 关系 直接看产生式的右部，若出现了A ab或A aBb,则a b2) 关系 求出每个非终结符B的FIRSTVT(B) 若AaB,则 bFIRSTVT(B),a b3) 关系 求出每个非终结符B的LASTVT(B) 若ABb,则 aLASTVT(B),a b36acebd#acebd#GS: S aAcBe A Ab|b B

16、 dFIRSTVTLASTVTS a e A b b B d d 相当于：相当于：#S# FIRSTVT(S)LASTVT(S) # #37例例2:文法文法GE：EE+T|E-T|T TT*F|T/F|F FP F|P P(E)|iFIRSTVT(E)=#FIRSTVT(E)=+,-,*,/, ,(,iFIRSTVT(T)=*,/, ,(,iFIRSTVT(F)= ,(,iFIRSTVT(P)=(,iLASTVT(E)=#LASTVT(E)=+,-,*,/, ,),iLASTVT(T)=*,/, ,),iLASTVT(F)= ,),iLASTVT(P)=),i1) 关系关系由产生式由产生式(0

17、)和和(6),得得# #，（，（ ）2） 关系关系找形如：找形如：AaB的产生式的产生式3) 关系关系找形如：找形如：ABb的产生式的产生式LASTVT(E) #+-*/ ()i#+-*/ ()i# 38 归约过程中，只考虑终结符之间的优先关系来确定句柄，而与非终结符无关。这样去掉了单非终结符的归约，所以用算符优先分析法的归约过程与规范归约是不同的； 为解决在算符优先分析过程中如何寻找可归约串，引进最左素短语的概念。39 素短语定义 上下文无关文法 G 的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。 处于句型最左边的素短语为最左素短语 算符文法的任一句型有如下形

18、式：#N1a1N2a2.NnanNn+1#, 若 ai-1 ai ai+1 . aj-1 aj ai+1，则有Niai.NjajNj+1为句柄40文法文法GE：(1) EE+T(2) ET(3) TT*F(4) TF(5) FP F|P(6) P(E)(7) Pi句型句型T+T*F+i其短语有：其短语有：T；T*F； i；T+T*F+i；T+T*FEET+ETF* FTTi素短语有：素短语有：T*F, i最左素短语为：最左素短语为：T*F句型句型N+N*N+i的归约过程的归约过程NN+NNi* NNN41最左素短语的判断假定文法的句型的一般形式为: N1a1 N2a2 Nnan Nn+1# 其

19、中ai是终结符，Ni是可有可无的非终结符,设最左素短语为Niai Njaj Nj1 , 必有： ai-1 ai ai+1 aj aj+1 则 Niai Njaj Nj1一定能归约为某非终结符。42算符优先分析算法k=1,sk=#;/s为符号栈，#压入栈，sk为栈顶项do a=getsym( );/读入下一个符号给a if(skVT) j=k; else j=k-1; while(sj a) do/在栈中寻找满足的sj sj+1 sk a的sj+1，即最左素短语的头 Q= sj ; if(sj-1VT) j=j-1; else j=j-2; while(sj Q) sj+1 sk归约为N; /归

20、约最左素短语 k=j+1; sk=N;/end of while if(sj a| sj a)k=k+1;sk=a; /移进 else error while(a!=# /符号栈中不是#S)43算符优先分析算法-说明 (1) 算法结束时，若栈内只有“”和某非终结符，读头下为“”，则表示分析成功，否则输入串有错。 (2) 在进行最左素短语归约时，只要能找出产生式，其右部的终结符与栈顶的若干终结符有一一对应的关系，当名称相同，位置也相同时即可进行归约，由于最左素短语不考虑非终结符，所以归约成什么符号无关紧要。 (3) 通用算符优先分析不考虑非终结符，终结符和非终结符放在同一个栈中。44文法文法GE

21、： EE+T|E-T|T TT*F|T/F|F FP F|P P(E)|i步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # i+i*i# #i,移进移进 2） #i +i*i# #+,规约规约 3） #N +i*i# #+,移进移进 4） #N+ i*i# +i,移进移进 5） #N+i *i# +*,规约规约 6） #N+N *i# +*,移进移进 7） #N+N* i# *i,移进移进 8） #N+N*i # *#,规约规约 9） #N+N*N # +#,规约规约10） #N+N # #,规约规约11） #N # 接受接受 因此符号串因此符号串i+i*i是文法是文法GE的句子的句

22、子 对输入串对输入串i+i*i的算符优先分析过程的算符优先分析过程算符优先分析算法-例算符优先关系表+ - * / ()i #+-*/ ()i#451.作用 减小优先表的空间占有量。2. 基本思想 将每个终结符与一对整数f(),g()联系在一起。其中， f()是在栈内时的优先数， g()是还未进栈时的优先数，叫比较优先数。且有如下关系：若 1 2 则f(1)g(2) 这样就可将优先表转换为优先函数表，所需存储空间也由n*n个单元减少到2*n个单元。同时把比较运算转化成数学的比较大小，方便了语法分析过程。463、优先表向优先函数的转化 -逐次加1法1）对所有终结符a（包括#），令f(a)g(a)=c，c为一任意常数。2）对所有终结符：若a b 而f(a)=g(b),则取g(b) = f(a)+1；若a b 而f(a)g(b),则取f(