第09章自上而下的语法分析

1第9章自上而下的语法分析9.1引言9.1.1语法分析的任务语法分析对源程序经过词法分析后转换成的符号串（即单词符号的序列），按文法规则进行判断，对能构成正确句子的符号串，给出相应的语法树；对不能构成正确句子的符号串，判定其出现了语法错误，并作出适当的处理。2语法分析程序的功能语法分析程序符号串（单词符号序列）正确句子的语法树报告语法错误39.1.2语法分析的分类(1)自上而下的语法分析对给定的上下文无关文法G(Vt,Vn,S,P)及符号串ω（ω∈Vt*），按照以下方法判断ω是否是文法G的一个合法句子：从根结点S开始，根据最左推导，看能否向下构造一棵语法树，使得该语法树的边缘正好是ω。4(2)自下而上的语法分析对给定的上下文无关文法G(Vt,Vn,S,P)及符号串ω（ω∈Vt*），按照以下方法判断ω是否是文法G的一个合法句子：从语法树边缘ω开始，根据最左规约，看能否向上构造一棵语法树，使得该语法树的根结点正好是S。59.1.3语法分析的方法自上而下的语法分析方法回溯分析法递归下降分析法预测分析法自下而上的语法分析方法算符优先分析法LR分析法69.2.1回溯分析实例实例1.文法G(S)：S→xAyA→ab│a对输入串xay的分析过程为9.2回溯分析法7SxAySxAyabSxAyaSxAy8实例2.文法G(S)：S→SaS→b对输入串baa的分析过程为9SbSS1aSS1abSS1aS2aSS1aS2abSS1a109.2.2引起回溯的原因(1)存在公共左因子A→1|2(2)存在左递归直接左递归：A→Aα间接左递归：A→Bα和B→A11当选用一个候选式来试探与输入串的匹配可能时，很可能会遇到匹配失败的情况，这时需回溯到这一次试探前的现状，包括注销已生长的子树，输入串的待匹配指针指针回退到失败前的位置，以便选取其它的候选式。12回溯分析法实际上是一种试探的方法，其分析效率是非常低的。特别是当匹配失败发生在多级试探后，逐级回溯的开销是令人难以忍受的。为避免回溯，可对文法进行等价改造，消除公共左因子和左递归。139.2.3公共左因子的消除将A→1|2|δ改写为A→B|δB→1|2一般形式：将A→1|2|...|m|δ1|δ2|...|δn改写为A→B|δ1|δ2|...|δnB→1|2|...|m14例如文法S→xAyA→ab│a可改写为S→xAyA→aBB→b│159.2.4左递归的消除(1)直接左递归的消除将P→Pα|β改写为P→P’P’→αP’│ε一般形式：将A→A1|A2|…|Am|1|2|…|n（Iε，j不以A开头）改写为A→1P’│2P’│...│nP’P’→1P’│2P’│...│mP’│ε16(2)间接左递归的消除对存在间接左递归的文法G：Ax→Ay……Ay→Az……Az→Ax…按以下算法消除间接左递归：17消除间接左递归算法1)将文法G的所有非终结符按任一给定的顺序排列，设为A1，A2，…，An2)改造产生式，消除左递归fori:=2tondoforj:=1toi-1do消除形如AiAj的产生式；3)去掉无效的符号和产生式18消除形如AiAj的产生式的方法1)将AiAj改写为Ai1|2|…|k（Aj1|2|…|k是Aj的所有产生式）2)消除新引入的直接左递归。19例子：消除间接左递归S→Qc│cQ→Rb│bR→Sa│a文法产生的语言：{c,bc,abc,cabc,bcabc,abcabc,cabcabc,bcabcabc,abcabcabc,…}20按R、Q、S排列，改造文法R→Sa│aQ→Sab│ab│bS→Sabc│abc│bc│c消除S中的直接左递归S→abcS’│bcS’│cS’S’→abcS’│文法产生的语言：{c,bc,abc,cabc,…}R→Sa│aQ→Rb│bS→Qc│c21按S、Q、R排列，改造文法S→Qc│cQ→Rb│bR→Rbca│bca│ca│a消除R中的直接左递归R→bcaR’│caR’│aR’R’→bcaR’│文法产生的语言：{c,bc,abc,cabc,…}S→Qc│cQ→Rb│bR→Sa│a22递归下降分析器的构造方法：对一个没有公共左因子和左递归的文法G，为每个非终结符构造一个函数（子程序），该函数的任务是对相应非终结符的产生式的右端进行分析和识别。9.3递归下降分析法23例如，对文法G1：E→E+T│TT→T*F│FF→(E)│i消除左递归后的等价文法G1’：E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│i24对文法G1’，构造递归下降分析器如下：变量sym表示当前符号，即输入指针ip指向的符号。函数advance()表示成功识别当前符号sym，输入指针ip后移一位。函数error()为出错处理程序。25voidE(){T()；E'()；}voidE'(){if(sym=='+'){advance()；T()；E'()；}}26voidT'(){if(sym=='*'){advance()；F()；T'()；}}voidT(){F()；T'()；}27voidF(){if(sym=='('){advance()；E()；if(sym==')')advance()；elseerror()；}elseif(sym=='i')advance()；elseerror()；}28i+i*i#的递归下降分析过程E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iETFii识别(i)E’TFii识别(i)+++识别(+)*#*T’识别(*)iF###T’E’####识别(i)T’++i+i*i#ip29预测分析程序的结构预测分析过程文法的FIRST集和FOLLOW集预测分析表的构造LL(1)文法非LL(1)文法9.4预测分析法309.4.1预测分析程序的结构下推栈、输入串、预测分析表、控制程序控制程序预测分析表下推栈输入串输出a1…ai…＃SmSm-1...S031预测分析表是一个M[A,a]形式的二维表格。其中A为Vn；a为Vt或#（结束符）。表项内容为一个产生式（表示下一步的动作）或空白（表示出错）。例如文法G1’：E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│i32EE’TT’Fi+*()#E→TE’E→TE’E’→+TE’T→FT’T→FT’T’→*FT’F→iF→(E)E’→εE’→εT’→εT’→εT’→ε文法G1’的预测分析表33初始时，#（输入串结束符）和文法开始符相继入栈，输入指针ip指向第一个符号。然后根据栈顶符号X和当前符号a（输入指针ip指向的符号）进行以下动作：①如X=a=#，输入串合法，分析成功②如X=a#，匹配，X出栈，输入指针右移③如XVN，查分析表的M[X，a]表项：1)如为“X→α”，X出栈，α反向入栈2)如为“空白”，输入串非法，出错处理9.4.2预测分析过程34下推栈输入串查分析表i+i*i##E#E’T#E’T’F#E’T’#E’T’i#E’#E’T#E’T+i+i*i#+i*i#i+i*i#i+i*i#+i*i#+i*i#i*i#E→TE’T→FT’T→FT’F→iT’→εE’→+TE’例：文法G(E)，输入串i+i*i#的分析过程35#E’T’Fi*i##E’T’i#E’T’#E’T’F*#E’T’i#E’T’F#E’T’##E’*i#i#*i#i####T’→*FT’成功F→iT’→εi*i#F→iE’→ε361)FIRST集定义：对α(VTVN)*，FIRST(α)={a|α∗a...,aVT}，特别地，若有α∗ε,则εFIRST(α)。（即：FIRST(α)是所有能由α推导出的第1个终结符或ε构成的集合。）9.4.3文法的FIRST集和FOLLOW集37FIRST集求法当α=X时，且XVT，则FIRST(X)={X}当α=X时，且XVN，分三种情形1.如有Xa…，则aFIRST(X)；（特别地，如有Xε，则εFIRST(X)）2.如有XY…，则FIRST(Y)-{}⊆FIRST(X)；3.如有XY1Y2…Yk，且εFIRST(Y1Y2…Yi-1)，则FIRST(Yi)-{}⊆FIRST(X)。注意:求FIRST(X)实际上是考察X在产生式左端的每一次出现。当α=X1X2…Xn时，参考上述第三种情形。38例如文法：XY1Y2AY1y1│Y2y2│AaFIRSTXY1Y2Ay1y2ay1y2a392)FOLLOW集定义：对AVN,有FOLLOW(A)={a│S∗...Aa...，aVT}，特别地，若有S∗…A，则#FOLLOW(A)，其中S为开始符号。（即：FOLLOW(A)是在文法的所有合法句型中，出现在A后面的终结符或结束符#构成的集合。）40FOLLOW集求法：#FOLLOW(S)如有A→αBβ，则FIRST()-{}⊆FOLLOW(B)如有A→αB，则FOLLOW(A)⊆FOLLOW(B)如有A→αBβ且β∗ε，则FOLLOW(A)⊆FOLLOW(B)注意：求FOLLOW(B)实际上是考察B在产生式右端的每一次出现。41例如文法G1’：E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│i42EE’TT’FFIRSTFOLLOW(i(i(i+*#++#)*#)#)+#))文法G1’的FIRST集和FOLLOW集439.4.4预测分析表的构造构造算法：对文法的每个产生式A→α执行以下操作：(1)对aFIRST(α)，将A→α记入M[A,a];(2)若εFIRST(α)，则对bFOLLOW(A)，将A→α记入M[A,b]；(3)其它表项为空白，表示出错。44EE’TT’Fi+*()#E→TE’E→TE’E’→+TE’T→FT’T→FT’T’→*FT’F→iF→(E)E’→εE’→εT’→εT’→εT’→εE→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│iEE’TT’FFIRSTFOLLOW(i(i(i+*#)+#)#)+#)*+#)459.4.5LL(1)文法设上下文无关文法G的产生式形如A→1|2|…|n,当G满足下述条件时则称为LL(1)文法：(1)FIRST(i)FIRST(j)=Φ；(2)若i∗,则FIRST(j)FOLLOW(A)=Φ。对于LL(1)文法，在子上而下语法分析时，可根据当前输入符号a选择唯一的候选。46并非任何文法G都是LL(1)文法。对非LL(1)文法可以根据语义进行处理。例：下述文法具有二义性SiCtS│iCtSeS│aCb提取公共左因子后：SiCtSS’│aS’eS│Cb9.4.6非LL(1)文法47FIRSTFOLLOWSS’CSiCtSS’|aS’eS|CbFIRST(eS)FOLLOW(S’)={e}iaeb#e#et48SS’Cabeit#S→aS→iCtSS’S’→eSS’→εC→b存在多重入口（例如句子ibtibtaea存在二义性）。解决方法：强制M[S’,e]仅含一个产生式S’→eS（即if-else结构中常用的最近匹配原则）。S’→εSiCtSS’|aS’eS|Cb预测分析表