《哈工大编译原理4-2》由会员分享，可在线阅读，更多相关《哈工大编译原理4-2（51页珍藏版）》请在金锄头文库上搜索。
1、1,第四章 语法分析,计算机学院,辛明影,2,4.3 自底向上,4.3.1自底向上分析中的问题研究,一、方法描述,自左向右逐个扫描输入串，,一边把输入符号移入分析栈 ，,一边检查位于栈顶的一串符号是否与某个产生式的右部相同，,如果相同，就把栈顶的这串符号归约为左部的非终结符；,不同，则继续移入输入符号，进行判断。,上述过程一直重复到输入串结束，栈内恰好为S。,计算机学院,辛明影,3,移入归约分析法为输入串构造分析树时从叶节占点（底端）开始，向根节点（顶端）前进。,该过程可看成是把输入串w“归约”成文法开始符号的过程,如果每一步都能恰当地选择子串，我们就可以得到最右推导的逆过程-最左归约,文法4
2、.1：SaABeAAb|bBd,规范归约：最左归约规范推导：最右推导,计算机学院,辛明影,4,句子abbde的归约过程(最左归约）,a b b d e,A,A,B,S,对应的最右推导:S=aABe=aAde=aAbde=abbde,计算机学院,辛明影,5,存在的问题：在第 步归约时，,有两种可能： AAb 和Ab,分析栈的情况如图：,b A a,计算机学院,辛明影,6,a b b d e,A,A,B,正确地选择归约的符号串很重要,现在看看用Ab归约的情况,计算机学院,辛明影,7,二、句柄,定义4.1短语 * +如果S= Aw=w，则称为相对于A的、句型w 的短语。,S A w,裁剪句柄,Aw
3、和 w为最右推导所得的右句型；,w只包含终结符,计算机学院,辛明影,8,S,A,A,B,b,d,e,a,短语：Ab, d, aAbde,计算机学院,辛明影,9,定义4.2 直接短语 若A 为一产生式，则称为相对于A的、句型w 的直接短语,句型aAbde所包含的直接短语： Ab、d、,定义4.3 最左直接短语是句柄,句型aAbde所包含的句柄:Ab,计算机学院,辛明影,10,在第步归约中，相对于句型aAbde来说，Ab是句柄，其上一级句型为aAde；而b根本就不是短语，因为不存在上一级句型aAAde,计算机学院,辛明影,11,例：证明T/（E-T）*F+i是句型，并指出其所包含的短语、直接短语和
4、句柄,E=E+T,=E+i,=E+F,=T+i,=T*F+i,=T/F*F+i,=T/(E)*F+i,=T/(E-T)*F+i,E,+,T,F,i,T,T,*,F,T,/,F,（,E,）,E,-,T,（E-T），,T/（E-T），,T/（E-T）*F，,i,T/（E-T）*F+i,短语：E-T，,E,直接短语:,E-T, i,句柄：,E-T,计算机学院,辛明影,12,考虑文法4.1：SaABeAAbA bBdabbde的最右推导和最左归约如左,右句型,句柄,归约产生式,abbde,aAbde,aAde,aABe,S,b,Ab,d,aABe,A b,AAb,Bd,AaABe,S=aABe,=aA
5、de,=abbde,= aAbde,E,E,+,T,*,F,T,F,id3,id2,T,F,句子 F+id*id 对应的语法树,短语：FId2Id3id2*id3id1+id2*id3,直接短语：FId2Id3,句柄：F,计算机学院,辛明影,14,三、用栈实现移进归约分析,移入归约分析器使用了一个栈来保存文法符号，,初始时，栈和输入串的情形为： 栈 输入串 w ,终止时，形成如下格局： 栈 输入串 S ,用输入缓冲区来存放待分析的串w,为栈底符号和输入结束标记。,计算机学院,辛明影,15,考虑文法4.2： EE+T|T TT*F|F F(E)|idid1*id2+id3的分析过程如下：,计算机
6、学院,辛明影,16,步骤,符号栈,输入串,动作,0,id1*id2+id3 ,prepare,1,id1,*id2+id3 ,移入,2,F,*id2+id3 ,归约Fid,3,T,*id2+id3 ,归约TF,4,T*,id2+id3 ,移进,5,T* id2,+id3 ,移进,6,T*F,+id3 ,归约Fid,7,T,+id3 ,归约TT*F,8,E,+id3 ,归约ET,9,E+,id3 ,移入,10,E+id3,移入,11,E+F,归约Fid,12,E+T,归约TF,13,E,归约EE+T,14,E,access,计算机学院,辛明影,17,移进：把下一个输入符号移进栈,移进归约的基本动
7、作：,归约：栈顶已形成句柄右端，需向栈 内搜索确定句柄的左端，并选 择正确的非终结符进行替换,接受：分析成功,出错：调用错误处理程序,计算机学院,辛明影,18,四、句柄的识别,解决两个问题：,栈顶形成的一定是最左直接短语,2、判断句柄的左、右端：,优先法状态法,1、最左性：,计算机学院,辛明影,19,4.3.1 算符优先分析,一、算符优先文法,定义4. 4 算符文法,定义4.5 相邻,一个文法，如果它的任一产生式的右部都不含两个相邻的非终结符，即不含有形如 AQR的产生式，则该文法是算符文法,若S= ab 或S= aQb ,称a,b相邻,计算机学院,辛明影,20, a b:当且仅当存在产生式A
8、aT， 且T=b，或T=Rb，称a后 于b归约,定义4.6 关系, a b:当且仅当存在产生式Aab 或AaTb，称a、b同等归约, a b:当且仅当存在产生式ATb, 且T=a，或T=aR，称a先 于b归约,ab无关系：当且仅当a与b在任何句型 都不相邻,计算机学院,辛明影,21,注意： 1. 算术关系“”与优先关系具有十分不同的性质。例如，ab并不一定意味着ba，,例如：+ +不一定存在。,具体如：2+(3+5),计算机学院,辛明影,22,4、算符优先文法,如果一个算符文法G中的任意两个终结符之间仅满足上述关系之一,文法4.2： EE+T|E-T|T TT*F|T/F|F FP F |P
9、P (E)|id是算符优先文法,由P(E)，得( ),由EE+T 和T=T*F, 得+ *,由EE+1T 和E=E+2T, 得+2 +1,优先级3+4*2,结合率2+3+4,计算机学院,辛明影,23,二、算符优先关系（矩阵）,栈内符号,剩余输入符号,计算机学院,辛明影,24,定义4. 6 FIRSTVT和LASTVT集,+ +FIRSTVT(P)=a|P=a或P=Qa, 其中， aVT, QVN,+ +LASTVT(P)=a|P= a或P=aQ, 其中， aVT, QVN,对于前面文法，有：FIRSTVT(E)=+，-，*，/，（，i , FIRSTVT(T)=*，/，（，i ,FIRSTVT
10、(F)=（，i , FIRSTVT(P)=（，i , ,计算机学院,辛明影,25,LASTVT(E)=+，-，*，/，)，I, LASTVT(T)=*，/，)，i , LASTVT(F)=)，i , LASTVT(P)=)，i ,由产生式 EE+T ，知：,若aLASTVT（E），则a +;,固：+ +, - +, * +, / +, ) + , i +, +,若bFIRSTVT（T），则+ b;,固：+ *, + /, + i , + (, + ,计算机学院,辛明影,26,求FIRSTVT和LASTVT集的算法,若有产生式，Pa 或PQa，则 aFIRSTVT（P）,若aFIRSTVT（Q）
11、，且有产生式 PQ，则aFIRSTVT（P）,求FIRSTVT规则,同理，可构造LASTVT的算法,计算机学院,辛明影,27,求FIRSTVT算法,布尔数组FP,a,若aFIRSTVT（P） 则FP，a=1初始时，按规则为F置初值,+ - * / ( ) i E 1 1 0 0 0 0 0 0 T 0 0 1 1 0 0 0 0 F 0 0 0 0 1 0 0 0 P 0 0 0 0 0 1 0 1,如何把上面的算法程序化？,计算机学院,辛明影,28,PROCEDURE INSERT（P，a) IF FP,a=0 THEN BEGIN FP,a=1; PUSH(P,a); END,算法4.1 设置F某一元素为真的过程：,计算机学院,辛明影,29,For 每个aVT, PVN do FP,a=0For 每个Pa.或PQa的产生式 do INSERT P,a;WHILE 栈不为空 DO POP （Q，a）； FOR 每个PQ产生式 DO INSERT(P,a);END WHILE,算法4.2 求F数组的主程序：,计算机学院,辛明影,30,上述算法的运行结果为数组F，从它可以得到任何非终结符P的FIRSTVT,
