编译原理 - 陈火旺版 - 第四章

1编译方法中国人民大学信息学院陈文萍2第四章语法分析——自上而下分析•4.1语法分析器的功能•4.2自上而下分析面临的问题•4.3LL(1)分析法•4.4递归下降分析程序构造•4.5预测分析程序•4.6LL(1)分析中的错误处理34.1语法分析器的功能•语法分析器的地位•分类–自上而下分析–自下而上分析词法分析器语法分析器编译程序后续部分符号表源程序单词符号取下一个单词符号语法分析树44.2自上而下分析•定义：也称面向目标的分析方法，从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子。•主旨：对任何输入串，试图用一切可能的办法，从文法开始符号着手，自上而下地为输入串构造一棵语法树。本质上是一个试探过程，反复使用不同的产生式谋求匹配输入串的过程。5自上而下分析的问题（1）•左递归例：例文法G0[S]:(1)S→Sa(2)S→b分析baa是不是文法的句子按照自上而下的分析思想，选用产生式(1)来推导SSa，语法树末端结点最左符号为非终结符，所以选用（1）继续推导SSaSaa此时语法树末端结点最左符号为非终结符，选用（1）继续推导SSaSaaSaaa试图用S匹配输入串时，出现：在没有识别任何输入符号的情况下，又得重新要求S去进行新的匹配，分析过程陷入无限循环6自上而下分析的问题（2）•回溯例：G[S]:S→xAy，A→ab｜a若当前输入串为xay，首先构造的推导SxAy匹配进一步推导对A可选择A→ab替换，得SxAyxabyxayxaby匹配xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式A→a进行试探，SxAyxay输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。由于相同左部的产生式的右部开始符号相同而引起回溯。7自上而下分析的问题（3）•分析过程中，匹配成功可能是暂时的。•最终分析不成功，很难知道输入串中出错的确切位置。•带回溯，效率低，代价高84.3LL(1)分析法•左递归的消除•消除回溯•LL(1)分析条件9直接左递归的消除•左递归：一个文法是含有左递归的，如果存在非终结符P，P=＋Pα•形如：P→Pα|β，其中α不为，β不以P打头消除直接左递归改写为：P→βP’，P’→αP’|•一般来说，若P→Pα1|Pα2|…|Pαm|β1|β2|…|βn，αi不为，βi不以P打头，消除直接左递归就把规则改写为：P→β1P’|β2P’|…|βnP’P‘→α1P’|α2P’|…|αmP’|•例：E→E+T|T，T→T*F|F，F→(E)|i消除直接左递归后变为：E→TE’E’→+TE’|T→FT’T’→*FT’|F→(E)|i10文法左递归的消除•消除一个文法左递归：对文法的要求–无回路()–不含以为右部的产生式•消除左递归算法：（1）以某种顺序将文法非终结符排列P1,P2……Pn（2）fori:=1tondobeginforj:=1toi-1do用Pi--1r|2r…|kr替代形如Pi--Pjr的规则其中Pj--1|2…|k是关于Pj的全部产生式;消除Pi规则的直接左递归;end（3）化简由2得到的文法PP11左递归的消除•例，文法S→Qc|c,Q→Rb|b,R→Sa|a–1,非终结符排序为：S,Q,R–2,替换规则•对于S，无需替换，S→Qc|c•对于Q，无需替换，Q→Rb|b•关于R，替换为，R→Rbca|bca|ca|a,消除直接左递归为R→bcaR’|caR’|aR’，R’→bcaR’|•非终结符的顺序不同，文法的形式可能不同，但都是等价的12消除回溯•不回溯，对文法的要求–设G是一个不含左递归的文法，对G的所有非终结符的每个候选，它的终结首符集FIRST()为FIRST()={a|=*a…,a∈VT}，若=*ε则规定ε∈FIRST（）–若非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选α和β，FIRST（α）∩FIRST(β)=，则可消除回溯•改造文法的方法：提左公因子将产生式Ａβ1|…|βn|1|…|m变换为：ＡB|1|…|mBβ1|…|βn13LL(1)分析条件•例如：文法：E→TE’，E’→+TE’|，T→FT’，T’→*FT’|，F→(E)|i输入串i+i，语法分析树FIRST(TE’)=｛（，i｝FIRST(+TE’)=｛+｝FIRST(FT’)=｛（，i｝FIRST(*FT’)=｛*｝FIRST((E))=｛(｝FIRST(i)=｛i｝ETE’iTE’+T’FFT’εiεε14LL(1)分析条件•S是文法G的开始符号，对G的任何非终结，定义FOLLOW（A）={aS=*…Aa…且a∈VT},若S=*…A,则#∈FOLLOW(A)•一个文法G是LL（1）的，当且仅当对于G的每一个非终结符Ａ的任何两个不同产生式Ａαβ，下面的条件成立：1.文法不含左递归。2.FIRST（α）∩FIRST(β)=,也就是α和β推导不出以同一个终结符a为首的符号串；它们不应该都能推出空字。3.假若β=*，那么，FIRST（α)∩FOLLOW（A）＝.也就是，若β=*.则α所能推出的串的首符号不应在FOLLOW(A）中。15LL(1)分析条件•文法是LL(1)的第一个L从左到右扫描输入串第二个L生成的是最左推导1向前看一个输入符号164.4递归下降分析程序构造•递归分析器：不带回溯的自上而下的分析程序•例：文法：E→TE’，E’→+TE’|，T→FT’，T’→*FT’|，F→(E)|i递归子程序为：PROCEDUREE;BEGINT;E’END;PROCEDUREE’;IFSYM=‘+’THENBEGINADVANCE;T;E‘END;174.4递归下降分析程序构造PROCEDURET;BEGINF;T’END;PROCEDURET’;IFSYM=‘*’THENBEGINADVANCE;F;T’END;PROCEDUREF;IFSYM=‘i’THENADVANCEELSEIFSYM=‘(‘THENBEGINADVANCE;E;IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR;184.4递归下降分析程序构造•扩充的巴科斯范式–用{a}表示闭包运算a*–用表示a可任意重复0次到n次，–用[a]表示，即a的出现可有可无•例如，文法E→T|E+T，T→F|T*F，F→(E)|I可以表示成E→T{+T}，T→F{*F}，F→(E)|IPROCEDUREE;BEGINT;WHILESYM=‘+’DOBEGINADVANCE;TENDEND;000}{aa0}{na01}{a194.4递归下降分析程序构造PROCEDUREF;IFSYM=‘*’THENADVANCEELSEIFSYM=‘(‘THENBEGINADVANCE;E;IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR;PROCEDURET;BEGINF;WHILESYM=‘*’DOBEGINADVANCE;F;ENDEND;204.4LL(1)分析器•LL(1)分析器的模型…a+b…#XYZ..#LL(1)分析算法LL(1)分析表M输入缓冲区分析栈输出21LL(1)分析器•分析要件–输入缓冲区：存放要分析的符号串，在串的末尾加符号#表示输入结束。–预测分析表：看作矩阵，存放文法中非终结符A和终结符a的关系。矩阵元素M[A,a]表示A对于输入符号a所采用的候选。结束标记符#作为一个终结符号。–栈：分析过程中，存放当前句型中尚待分析的文法符号，包括终结符号和非终结符号。栈底用#标记结束。初始化时，把#和文法的开始符号放在栈顶。22LL(1)预测分析表i+*()#E(1)(1)E’(2)(3)(3)T(4)(4)T’(6)(5)(6)(6)F(8)(7)例：G[E]:(1)E–TE’(2)E’–+TE’(3)E’–(4)T–FT’(5)T’–*FT’(6)T’–(7)F–(E)(8)F–i23预测分析表的构造•计算FIRST集合的方法1.若XV,则FIRST(X)={X}2.若XVN,且有产生式Xa…，则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中.3.若XY…是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若XY1Y2…YK是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj)都含有(即Y1..Y(i-1)=*),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj,j=1,2,…,K)均含有,则把加到FRIST(X)中.24预测分析表的构造•计算FOLLOW集1.对于文法的开始符号S,置#于FOLLOW(S)中;2.若ＡαBβ是一个产生式,则把FIRST(β)\{}加至FOLLOW(B)中;3.若ＡαB是一个产生式,或ＡαBβ是一个产生式而β=*(即FIRST(β)），则把FOLLOW（A）加至FOLLOW（B）中．25预测分析表的构造•例：文法G[E]:(1)E–TE’(2)E’–+TE’(3)E’–(4)T–FT’(5)T’–*FT’(6)T’–(7)F–(E)(8)F–a非终结符的FIRST集合：FIRST(E)=｛(,a｝FIRST(E′)=｛+,ε｝FIRST(T)=｛(,a｝FIRST(T′)=｛*,ε｝FIRST(F)=｛(,a｝·非终结符的FOLLOW集合：FOLLOW(E)=｛),＃｝FOLLOW(E′)=｛)，＃｝FOLLOW(T)=｛＋，)，＃｝FOLLOW(T′)=｛＋,)，#}FOLLOW(F)=｛*,＋，),#}26预测分析表构造算法1.对文法G的每个产生式Ａ执行第二步和第三步；2.对每个终结符aFIRST()，把Ａ加至[A,a]中，3.若FIRST()，则对任何bFOLLOW(A)把Ａ加至[A,b]中，4.把所有无定义的[A,a]标上“出错标志”。可以证明，一个文法G的预测分析表不含多重入口，当且仅当该文法是LL(1)的27预测分析程序•预测分析程序算法：首先把’#‘然后把文法开始符号推入栈；把第一个输入符号读进a;FLAG：=TRUE；WHILEFLAGDOBEGIN把栈顶符号上托出去并放在Ｘ中；IFXVtTHENIFX=aTHEN把下一个输入符号读进aELSEERRORELSEIFX=‘#’THENIFX=aTHENFLAG:=FALSEELSEERRORELSEIF[X,a]={X–X1X2..XK}THEN把XK，XK-1,..,X1一一推进栈ELSEERRORENDOFWHILE;STOP/*分析成功，过程完毕*／28预测分析程序•分析步骤栈内容栈顶符号当前输入余留串M[X,a]1#EEi+i#E–TE’2#E’TTi+i#T–FT’3#E’T’FFi+i#F–i4#E’T’iii+i#5#E’T’T’+i#T’–6#E’E’+i#E’–+TE’7#E’T+++i#8#E’TTi#T–FT’9#E’T’FFi#F–i10#E’T’iii#11#E’T’T’#T’–12#E’E’#E’–13###294.6LL(1)分析中的错误处理•发现错误–栈顶的终结符与当前输入符不匹配–非终结符A于栈顶，面临的输入符为a，但分析表M的M[A,a]为空•应急恢复策略–跳过输入串中的一些符号直至遇到“同步符号”为止。304.6LL(1)分析中的错误处理•同步符号集的选择–把FOLLOW(A)中的所有符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续•错误处理–若M[A,a]为空，跳过输入符号a–