《编译第010章》由会员分享，可在线阅读，更多相关《编译第010章（132页珍藏版）》请在金锄头文库上搜索。
1、第十章 自下而上语法分析,概述 算符优先分析法 LR分析法,语法分析内容回顾,什么是语法分析？ 自上而下分析方法：前提条件：提取公共左因子、消除左递归 缺陷只适合部分文法、效率较低,第十章 自下而上语法分析,第一节 概述 自下而上分析： 从输入串出发，寻找归约序列，逐步进行归约，直至开始符号S 方法：采用栈， 移进-归约,基本方法:移进-归约,基于下推自动机1)采用栈，将输入符号移进栈中2)如果栈顶（一个或多个符号）形成某个非终结符号的候选式3)则进行归约, 将归约后的非终结符号移进栈,4)重复进行上述过程，直到输入串扫描结束。 5)如果栈内只剩下开始符号S，则输入串是文法合法的句子。,例10
2、-1文法G：,SSASSbAccAAa 输入串bccab的归约过程为：,b,S,c S,c c S,a c c S,A c c S,A S,b A S,S A S,S,G(S)：SSASSbAccAAa,输入串bccab,符号栈,b,S,c,c,a,A,A,b,S,S,历史记录,语法分析过程可以用分析树的形成过程来表示,串bccab分析树的形成,语法分析过程也可以用语法树的修剪过程来表示,语法树的剪枝过程：,S,S,S,A,b,c,c,A,b,a,冲突归约与归约的冲突移进与归约的冲突,自下而上分析可能遇到的问题,如何判断栈顶符号串已经形成可归约串 如何进行归约,自下而上分析的关键问题,对归约串
3、的不同的定义,形成不同的语法分析方法：算符优先分析法：最左素短语LR分析法：句柄,1.短语:是无关文法G的一个句型, 如果有S*A并且A+则称是句型的一个短语(关于非终结符A的短语),短语、句柄和规范归约,2.直接短语（简单短语）A =表示只有一层子树，且可以是非终结符 3.句柄：一个句型的最左直接短语。,4.素短语:是短语，至少包含一个终结符,且不再含更小的素短语 5.最左素短语:句型中最左的素短语。,例: G(E) EE+T|TTT*F|FF(E)|I 求T*F+i的短语、直接短语、句柄,EE+TT+TT*F+TT*F+FT*F+iT*F+i是关于E的短语T*F是关于E的短语,句型：推导树
4、的叶结点(拐点)自左至右连接 短语：子树的边缘是相对于根的短语 直接短语：有且仅有两层的子树的边缘是相对于根的直接短语 句柄：位于最左的有且仅有两层的子树的边缘,推导树确定短语,E,E,T,+,T,T,F,F,i,*,例: G(E) EE+T|TTT*F|FF(E)|I 求T*F+i的短语、直接短语、句柄,是文法的句子, 序列n,n-1,0 满足下述条件时的归约称为规范归约 (1)n= (2)0为文法的开始符, 即0=S (3) 对i, 0in,将i的句柄归约得i-1,规范归约（最左归约）,EE+TTTT*FFF(E) i i+i*i的LR分析过程(按句柄归约),例: G(E),i+i*i F
5、+i*i T+i*i E+i*i E+F*i E+T*i E+T*F E+T E,E,E,T,+,F,T,i,i,*,F,T,i,F,例 : G(E) EE+TTTT*FFF(E) i i+i*i的算符优先分析过程（按照最左素短语进行归约）,E,E,T,+,F,T,i,i,*,F,T,i,F,i+i*i F+i*i F+F*i F+F*F F+T E,注意：,按最左素短语归约是结构归约：处于栈顶待归约的最左素短语与对应的产生式在结构上一致即长度一致, 对应的终结符一致 而非终结符可以不一致。不懂，为什么按句柄规约不是“结构规约”？,优点,按照最左素短语进行的归约省略了A 的产生式的使用。 其中
6、： VN+ (非终结符号串),缺点,并不是任何文法都可以按照最左素短语进行归约。例如： S ABA aB b,总结,部分文法可以进行算符优先分析; 所有文法可以进行LR分析。,SaAcBeAAb|bBd abbcde的LR和算符优先分析过程,例: LR和算符优先分析一致,S,abbcde aAbcde aAcde aAcBe S,a,SaAcBe AAb|b Bd,A,c,B,e,A,b,d,b,思考,算符优先分析的条件?,第二节 算符优先分析法,使用终结符号之间的 归约顺序进行语法分析。,在算术表达式中，有运算符号的优先级和结合性的规定。算符优先分析法的实质就是仿效表达式的计算过程而设计的。
7、,一、算符优先文法,1. 算符文法上下文无关文法G 如果没有形如P 或 P. . .QR. . .（两个连续的非终结符） 的产生式，则称G为算符文法。,对算符文法G, a,bVT 定义 (1)a=bG有P. . .ab. . . 或 P. . .aQb. . . (2)abG有P. . .Qb. . . 且Q+. . .a 或Q+aR,2. 相邻的2个终结符之间的优先关系,(1)a=b P.ab.或P.aQb.,P,b,a,Q,(2)ab G中有P.Qb. 且Q+.a或Q+aR,P,a,b,Q,LASTVT集合,LASTVT(Q)=a|Q+.a 或 Q+aRaVT,R VN,a是最后一个终结符
8、，a的后面可以有若干非终结符。 算符优先分析法中的FIRSTVT、LASTVT与FIRST、FOLLOW的区别：FIRSTVT（A）、LASTVT（A）都是规约的目标A出现在产生是左边；而FIRST（A）、FOLLOW（A）中，FOLLOW（A）中，须寻找A在产生是右边的情况。,3. 算符优先文法,若算符文法G的任何终结符a、b之间的优先关系至多只有=、,=,=,算符优先关系表,思考,特殊符号#的优先关系如何确定?,对文法进行改造，得： G（S）:S #E#EE+T|TTT*F|FF(E)|i,(1)相同终结符的优先关系未必是= (2)有aa (3)a、b之间未必一定有优先关系,注意,思考,两
9、个终结符之间若没有优先关系则表示?我也不知道啊？,二. 算符优先分析算法设a为栈顶终结符,初始化: #栈,a=b=#,ab,归约最左素短语:最左素短语出栈, 左部符号入栈,b入栈,结束,出错,Y,N,Y,Y,N,N,读一符号b,k:=1; Sk:=#; repeata:=下一输入符号；if SkVT then j:=k else j:=k-1;while Sja dobeginrepeatQ:=Sj;if Sj-1VT then j:=j-1 else j:=j-2until SjQ;把Sj+1Sk归约为某个N;k:=j+1;Sk:=Nend of while;if Sja or Sj=ath
10、en begin k:=k+1; Sk:=a endelse error until a=#;,k指向栈顶符号 a指向下一输入符号 j指向栈顶终结符,EE+TTTT*FFF(E) i i+i*i的分析过程,例 G(E),步骤,1,2,3,4,5,6,7,8,9,10,11,下推栈,输入串,动作,#,i+i*i#,#+, 用Fi归约,#F,+i*i#,#+, 移进+,#F+,i*i#,+*, 用Fi归约,#F+F,*i#,+*, 移进*,#F+F*,i#,*#, 用Fi归约,*#, 用TT*F归约,+#, 用EE+T归约,结束,#F+F*F,#F+T,#E,当栈中当前符号“大于”输入串当前符号，
11、则-规约,E,E,T,+,F,T,i,i,*,F,T,i,F,i+i*i F+i*i F+F*i F+F*F F+T E,(1)FIRSTVT集 FIRSTVT(P)=a|P+a 或 P+Qa,三、优先关系表的构造,若Pa或PQa 则aFIRSTVT(P) 若PQ 则FIRSTVT(Q)FIRSTVT(P) 直至FIRSTVT(P)不再增大。,(2)LASTVT集 LASTVT(P)=a|P+.a 或 P+aQ,若P.a或PaQ 则aLASTVT(P) 若P.Q 则LASTVT(Q)LASTVT(P) 直至LASTVT(P)不再增大。,例 G(E) EE+TTTT*FFF(E) i,E,T,F
12、,FIRSTVT,LASTVT,( i + *,( i,) i + *,) i *,) i,( i *,（3）求FIRSTVT集的矩阵规则 若Pa 或 PQa则MP,a:=1 若PQ 则对所有的MQ,a=1置MP,a:=1 重复上述两步，直到矩阵不再变化,(4)求LASTVT集的矩阵规则 若Pa 或 PaQ则MP,a:=1; 若PQ则对所有的MQ,a=1置MP,a:=1 重复上述两步，直到矩阵不再变化,例 G(E) EE+TTTT*FFF(E) i,FIRSTVT,LASTVT,ETF,ETF, * i （ ）, * i （ ）, * i （ ）,1,1,1,1,1 1,1 1 1,1,1,1,1,1 1,1 1 1,FOR 每条产生式PX1X2Xn DOFOR i:=1 TO n-1 DOBEGINIF Xi和Xi+1均为终结符 THEN Xi= Xi+1; /abIF i=n-2 且 Xi和Xi+2均为终结符 但 Xi+1VNTHEN Xi=Xi+2; /aQb,
