第四章语法分析——自顶向下

1、u语法分析概述语法分析概述u不确定的自上而下语法分析不确定的自上而下语法分析uLL(1)LL(1)分析法与分析法与LL(1)LL(1)分析器分析器u递归下降分析法与递归下降分析器递归下降分析法与递归下降分析器2基本思想：从文法的开始符号出发，推导出句子 回溯避免条件 First(x), Follow(u) 基本问题 无限循环消除左递归 LL(1)分析法 分析方法 递归子程序法 自上而下语法分析语法分析程序要解决的问题语法分析程序要解决的问题n语法分析程序的构造要素语法分析程序的构造要素n源程序串n源语言的文法Gn识别出的语法范畴的表示CompilerPrinciples3设给定文法G和字符串(

2、句子) ( VT*)，检查、判定L(G)？即检查、判定是否是文法G所能产生的合法的句子，同时检查和处理语法错误。处理对象处理对象分析依据分析依据分析结果分析结果二、分析方法二、分析方法分析方法：分析方法：n自上而下分析法：自上而下分析法：给定文法G和源程序串$。从G的开始符号S出发，通过反复使用产生式对句型中的非终结符进行替换(推导)，逐步推导出$ 。n是一种产生的方法，面向目标的方法。n分析的主旨是选择产生式的合适的侯选式进行推导，逐步使推导结果与$匹配。CompilerPrinciples45自上而下分析算法自上而下分析算法要点：.由根向下构造语法树.构造最左推导.推导出的终结符是否与当前

3、输入符匹配 S A B a A a A a A S ABA aA | B b | bB分析w=aaab的构造过程S AB S AB aAB A aA aaAB A aA aaaAB A aA aaa B A aaab B bb4.2不确定的自上而下语法分析例：GS: S cAd A ab A a 识别输入串w=cad是否是该文法的句子产生回溯回溯的原因：同一个非终结符有多个候选式的首符号相同6分析的本质是逐一试探推导的过程，即反复使用不分析的本质是逐一试探推导的过程，即反复使用不同的产生式去谋求匹配输入串的过程。算法效率低同的产生式去谋求匹配输入串的过程。算法效率低开销大。开销大。一、回溯问题

4、一、回溯问题4.2不确定的自上而下语法分析例：GS: S Sa S a w=aaaaCompilerPrinciples7按照自上而下分析法对输入串w产生分析树，则对非终结符的最左推导会使分析树无休止的延伸，使自上而下分析陷入死循环。二、左递归问题二、左递归问题8不确定性的原因：不确定性的原因：l回溯问题回溯问题l不停的试探，走回头路。l左递归问题左递归问题l左递归文法会造成死循环。l左递归分类：左递归分类：l关于非终结符P的规则：l直接左递归：P-P|l一般左递归：P P 、 V*提取左公因子提取左公因子消除文法的左递归消除文法的左递归l例：一般左递归例：一般左递归S-S-AaAaA-A-S

5、bSbA-bA-b4.2不确定的自上而下语法分析(1) 直接左递归的消除：l假定关于非终结符的规则为CompilerPrinciples9PP| 、(VTVN)*l其中，不以P开头。则可以把P的规则改写成如下等价的非直接左递归形式P PP P|(1) 直接左递归的消除：分析分析 ：PP| CompilerPrinciples10不变不变个数可以无穷多个，只能用递归表示且不能用左递归。PPP P P P PP P |P |P = P = * *n例例: : 设有简单表达式文法设有简单表达式文法G G（E E）: : nEE+E | E*E |（E）| in对G(E)消除二义性后，得到文法G(E)

6、：n继续消除文法G(E)的左递归，得到文法G(E)11nEE+T | T nTT*F | FnF(E) | i* *nE TEnE +TE|nT FTnT *FT|nF （E）| i(1) 直接左递归的消除：n假定关于非终结符的规则为P P1| P2 | | Pn | 1 | 2 | | nn其中，每个 i不等于，1 , 2 , n 不以P开头。则可以把P的规则改写成如下等价的非直接左递归形式CompilerPrinciples12P 1P|2P|nPP 1P| 2P|nP|(1) 直接左递归的消除：n例：n 设有文法G：II0 | Ia | Ib | a | bn对左递归文法G改写后的文法G

7、为CompilerPrinciples13I aI | bII 0I| aI| bI|CompilerPrinciples14n(2)间接左递归的问题n例:如设有文法G(A)：nA Ba | aA Ba | anB Cb | bB Cb | bnC Ac | cC Ac | cn经若干步推导代换，有：nA = Ba = Cba = AcbaA = Ba = Cba = AcbanB = Cb = Acb = BacbB = Cb = Acb = BacbnC = Ac = Bac = CbacC = Ac = Bac = Cbac(2)间接左递归的问题n消除间接左递归的方法：n(1) 把间接左

8、递归文法改写为直接左递归文法；n(2) 用消除直接左递归的方法改写文法。CompilerPrinciples15+16n例如：文法GP：n PQc c QRb b RPa an .排序：R,Q,Pn . R代入Q得QPab ab bn Q代入P得PPabc abc bc cn 消除P的直接左递归得nPabcP bcP cP, PabcP n 如此可得文法为： PabcP bcP cP, n P abcP ，QPab ab b, RPa an. Q,R去掉。最终文法是：n PabcP bcP cP, P abcP n排序不同，最终的产生式集可能不尽相同，但文法是等价的。 解决回溯问题的方法：Co

9、mpilerPrinciples17l二. 消除回溯lP 1 | 2 | n 当前$：ail在一般自上而下分析中，对于一个VN 进行推导并试图去匹配句子剩余符号时，若VN含有两个或两个以上的候选式，是依次一个一个地去试探，试图找出一个合乎要求的i。先选1，与当前输入ai匹配成功则替换，否则选2，依此类推。 产生回溯回溯的原因：同一个非终结符有多个候选式的首符号相同解决回溯问题的方法：定义定义n设G是二型文法且文法不含左递归，则中的非终结符的每个候选式的终结首符集FIRST()为FIRST ( ) = a | a ，aVT n若 =, 则FIRST() CompilerPrinciples18*

10、解决回溯问题的方法：CompilerPrinciples19l解决办法：解决办法：提取公共左因子提取公共左因子l引入新的非终结符，改写产生式，直到其所有候选的终结首符集两两不相交。n不带回溯的条件：l如果对文法G的一个产生式A，设A为A 1 | 2 | nl它的每个候选式i均不存在i =的情况，而且FIRST(i)两两彼此互不相交。即： FIRST (i)FIRST (j)= ，（对任意，（对任意ij）l则不存在回溯问题 *20n 若关于A的产生式为：n A1 2 n n提取左因子：提取左因子：n A(1 2 n) n引入非终结符引入非终结符An AA,n A1 2 n l总结：总结：l判断回

11、溯的方法：l求每个候选的First集使其两两不相交；l消除回溯的办法：l提取左因子 解决回溯问题的方法：CompilerPrinciples21lFirst集的构造：l对每一个文法符号XVTVN,可连续使用如下规则，直到每个First集不再增大为止：la.若XVT则First(X)=X;lb.若XVN，且有产生式Xa,则aFirst(X),特别若 l X，则First(X)；lc.若XY且有YVN，则把First(Y)中的所有非元素加到First(X)中；若XY1Y2Yk是一个产生式，Y1Yi-1都是非终结符，而且，对于任何j (1 j i-1),都有First(Yj)，则把First(Yi)

12、加入First(X)中；特别是，若所有的First(Yj) 均含有 (j=1,2,k),则把加入First(X)中。解决回溯问题的方法：FIRSTFIRST集集例 E TE E + TE | T FT T FT | F (E) | il各个非终结符FIRST集：lFIRST(E) = FIRST(T) = FIRST(F) = ( , ilFIRST(E ) = +, lFRIST(T ) = , l各个候选式的FIRST集：lFRIST(T E ) = FIRST(T) - = ( , ilFRIST(+T E ) = + lFRIST ) = lFRIST(FT ) = + = FIRST

13、(F) - = ( , ilFRIST(*FT ) = *lFRIST(E) = ( lFRIST(i) = i First集例设有文法G：lS Ap | BqlA a | cAlB b | dB对S: lFIRST(Ap)=a,c FIRST(Bq)=b,dl且 FIRST(Ap) FIRST(Bq)=对A:l FIRST(a)=a FIRST(cA)=cl且 FIRST(a) FIRST(cA)=对B: lFIRST(b)=b FIRST(dB)=dl且 FIRST(b) FIRST(dB)= CompilerPrinciples23First集若给出$=cap ,则有：CompilerP

14、rinciples24$: c cap$: c capl对S: FIRST(Ap)=a,c FIRST(Bq)=b,dl对A: FIRST(a)=a FIRST(cA)=cl对B: FIRST(b)=b FIRST(dB)=d$: c cap例设有文法G：lS Ap | BqlA a | cAlB b | dB例：例设有文法G：lS aA|blA cASlA CompilerPrinciples25若给出$=aca,则有：推导过程推导过程产生式号产生式号输入串输入串Saca#=aA( 1)aca#=acAS( 3)aca#=acS( 4)aca#=acaA( 1)aca#=aca(4 )aca

15、#4.3 FOLLOW4.3 FOLLOW、SELECTSELECT集的构造集的构造定义定义l设上下文无关文法G，S是文法的开始符号，对于文法G的任何非终结符AFOLLOW(A)a|S=Aa，aVTl若S=A，则令FOLLOW(A)。CompilerPrinciples26* nFOLLOW(A)的含义是指，在文法G的一切句型中，能够紧跟着A之后的一切终结符或“”。l问题：如何构造问题：如何构造FollowFollow集？集？*CompilerPrinciples27nFollowFollow集的构造：集的构造：n对于文法G的每个非终结符A连续使用如下规则，直至每个Follow不在增大为止：n

16、a.若开始符号为A,则置#于Follow(A)中；nb.若BA, 则把First()/加入Follow(A)中；nc.若BA或BA且* ,则Follow(B) Follow(A)；4.3 FOLLOW4.3 FOLLOW、SELECTSELECT集的构造集的构造FollowFollow集的构造：集的构造：例例 E TE E + TE | T FT T FT | F (E) | in各个非终结符的各个非终结符的FOLLOWFOLLOW集：集：lFOLLOW(E) = FOLLOW(E ) l = ), #lFOLLOW(T) = FOLLOW (T ) = l +, ), #lFOLLOW(F)

17、 =l +, , ), # 4.3 FOLLOW4.3 FOLLOW、SELECTSELECT集的构造集的构造4.3 FOLLOW4.3 FOLLOW、SELECTSELECT集的构造集的构造例： 设有文法GS为：lSAB | bC A| blB| aD CAD| blDaS | c计算文法GS FOLLOW集为：lFOLLOW(S)=#lFOLLOW(A)=a,c,#lFOLLOW(B)=# lFOLLOW(C)=# lFOLLOW(D)=#CompilerPrinciples29练习：设有文法G：lS eT|RTlT DR| lR dR|lD a|bdl计算文法GS 的各个非终结符的FIR

18、ST集和FOLLOW集CompilerPrinciples30SELECT集给定文法G,对于产生式A, V*，如果它的编号为i，则它的可选集SELECT( A)定义如下：(1)若, 且*，则SELECT(A)=FIRST()(2)若, 且=*，则SELECT(A)=FIRST()UFOLLOW(A)(3)若=，则SELECT(A)=FOLLOW(A)例：给定文法GS:lS aA|clA bASlA 求各个产生式的SELECT集合CompilerPrinciples31练习：文法GE: nETEnEATE|nTFTnTMFT|nF(E)|inA+|-nM*|/n求各个产生式的FIRST 、SEL

19、ECT集合和各个非终结符的FOLLOW集CompilerPrinciples324.3 FOLLOW4.3 FOLLOW、SELECTSELECT集的构造集的构造结论：一个上下无关文法称为LL(1)文法，当且仅当同一非终结符的各个产生式的可选集互不相交。CompilerPrinciples3334基本思想：从文法的开始符号出发，推导出句子 回溯避免条件 First(x), Follow(u) 基本问题 无限循环消除左递归 LL(1)分析法 分析方法 递归子程序法 自上而下语法分析4.4 LL(1)分析法与LL(1)分析器L L (1)CompilerPrinciples35l分析模式：最左推导

20、分析模式：最左推导l在分析中最多向前看在分析中最多向前看1 1个输入字符个输入字符l扫描模式：自左向右扫描模式：自左向右36LL(1)预测分析程序模型预测分析程序模型 a a #stackE#输出LL(1)LL(1)预测分析表预测分析表总控程序总控程序输入字符串$总控程序总控程序总控程序利用分析表和分析栈对输入符号进行预测分析分析栈分析栈用于存放分析过程中的文法符号分析表分析表事先根据文法构造的一个MA,a形式的矩阵组成组成4.4 LL(1)4.4 LL(1)分析器的结构分析器的结构LL(1)LL(1)分析器的逻辑结构和工作过程分析器的逻辑结构和工作过程n关键问题关键问题: :n是对于某个非终

21、结符A和当前输入符号a，如何去选择A的候选式。n方法方法: :n根据其产生式把所有的对偶(A,a)构造出来，这些对偶构成一张分析表。374.4 LL(1)分析器的结构(1) (1) 分析栈分析栈存放分析过程中的文法符号（待匹配和已经推导的串）。初始状态为：CompilerPrinciples384.4 LL(1)分析器的结构(2) (2) 分析表分析表CompilerPrinciples39 a a1 1 a a2 2 a an nA A1 1 M(AM(A1 1,a,a1 1) M(A) M(A1 1,a,a2 2) M(A) M(A1 1,a,an n) )A A2 2 A An n文法的

22、文法的V VT T文文法法的的V VN N 文法的一条产生式规则(含义) M(Ai i,ai i) 出错（空白）4.4 LL(1)4.4 LL(1)分析器的结构分析器的结构例:对文法GE: ETE E+TE TF T T*FT F(E) i 有如下预测分析表：40i+*()#EE TEE TEEE+TEEETTFTTFTTTT*FTTTFFiF(E)源程序结束标志源程序结束标志例: (E,i ) E TE (E,( ) E TE (E ,+ ) E +TE 4.4 LL(1)分析器的结构 算法算法l(1)初始化工作：l(2)若当前分析栈顶符号和a 都是文法的终结符号，则对于：l Xa “”，表

23、示分析成功，停止分析过程；l Xa “”，则将从分析栈顶退掉，p指向下一个输入字符；l Xa ，表示不匹配的出错情况。CompilerPrinciples41# #S Slp4.4 LL(1)分析器的结构l若(, a )中为一个产生式规则，则将X从栈中弹出并将此规则右部的符号序列按倒序推进栈(若产生式规则为，则仅将从栈中弹出) 。l若(, a )中为空白，表示出错，可调用语法出错处理子程序。CompilerPrinciples4243i+-*/()#EETEETEEEATE EATEE ETTFTT FTTTT TMFTTMFTT TFF iF (E)AA +A -MM *M /文法GE: n

24、ETEnEATE|nTFTnTMFT|nF(E)|i; A+|-nM*|/; 其对应的预测分析表如下：其对应的预测分析表如下：对对i+ii+i* *i i进行预测分析的过程进行预测分析的过程44总控程序工作原理45“#”，“S”进栈，当前输入符号送入a弹出栈顶符号X X V VT T? ?X=“#”X=“#”? ?X=aX=a? ?结束X=aX=a?读入下一符号给a出错MMX,aX,a 是是产生式产生式?出错若产生式为XX1X2Xn则按逆序入栈YYYYYNNNNNi i+ +* *( () )# #E EE TEE TEE TEE TEE EE E+TE+TEE EE ET TTFTTFTTF

25、TTFTT TT TT T* *FTFTT TT TF FFiFiF(E)F(E)CompilerPrinciples46练习 文法 GE: nETE nE +TE |nT FT nT *FT | nF (E)| i n输输入串入串i+i#i+i#的分析的分析过过程程步骤步骤符号栈符号栈输入串输入串M X,aM X,a1 1#E#E i+i# i+i#E TEE TE2 2#E#ET Ti+i#i+i#TFTTFT3 3#E#ET TF Fi+i#i+i#FiFi4 4#E#ET Ti ii+i#i+i#5 5#E#ET T+i#+i#T T 6 6#E#E+i#+i#E E +TE +TE7

26、 7#E#ET+T+i#+i#8 8#E#ET Ti# i#T FTT FT9 9#E#ET TF Fi# i#FiFi1010#E#ET Ti ii# i#1111#E#ET T# #T T1212#E#E# #E E1313# # #4.4 LL(1)分析器的结构注意：注意：l(1) 整个分析过程是分析栈和$构成的二元式不断变化的过程。l(2) 分析器结构、总控程序不变，不同的源语言仅是LL(1)分析表不同。CompilerPrinciples474.4 LL(1)分析器的构造LL(1)分析器构造关键分析表的构造关键CompilerPrinciples48分析表的构造分析表的构造预测函数预

27、测函数l对文法对文法G G，若，若G G中产生式形如中产生式形如AA，若，若a a SELECT(A)，则把当当 AA置于矩阵中，置于矩阵中， 即：即：( (A,aA,a) = A) = A 其中其中a a为终结符或为终结符或# #l凡未定义的表元素凡未定义的表元素( (A,aA,a) ) 均标上出错标志。均标上出错标志。4.4 LL(1)分析器的构造设有文法G：lS Ap | BqlA a | cAlB b | dB对S: lSELECT(S Ap)=a,c SELECT(S Bq)=b,dl且且 SELECT ( (S Ap) Ap) SELECT ( (S Bq)=Bq)=对A:l SE

28、LECT (A a)=a SELECT(A cA)=cl且且 SELECT (A a) SELECT (A cA)=SELECT (A a) SELECT (A cA)=对B: lSELECT(b)=B b SELECT(B dB)=dl且且 SELECT (B b) SELECT (B dB)= SELECT (B b) SELECT (B dB)= CompilerPrinciples494.4 LL(1)分析器的构造文法G的LL(1)分析表CompilerPrinciples50 a b c d p qS SAp SBq SAp SBq A Aa AcAB Bb BdB51例 文法 GE

29、: nETE nE +TE |nT FT nT *FT | nF (E)| i n构造每个非终结符的FIRST和FOLLOW集n构造分析表:FIRST(E) = (, i FOLLOW(E) = ), # FIRST(E) = +, FOLLOW(E) = ), # FIRST(T) = (, i FOLLOW(T) = +, ), # FIRST(T) = *, FOLLOW(T) = + , ), # FIRST(F) = (, i FOLLOW(F) = *, +, ) , # i i+ +* *( () )# #E EE TEE TEE TEE TEE EE E+TE+TEE EE E

30、T TTFTTFTTFTTFTT TT TT T* *FTFTT TT TF FFiFiF(E)F(E)LL(1)LL(1)分析表的构造：分析表的构造：52【练习练习】文法文法G GE: E: nETEnEATE|nTFTnTMFT|nF(E)|i; A+|-nM*|/; n构造如下的分析表:LL(1)LL(1)分析表的构造：分析表的构造：产生式产生式FIRSTFIRSTFOLLOWFOLLOW1.1. E E TETE(, i(, i ), # ), #2.2. EE ATE|ATE|+, -; +, -; ), # ), #3.3.T T FTFT(, i(, i+, - , ), #+,

31、 - , ), #4.4.TT MFT |MFT | * *, /; , /; +, -, ), #+, -, ), #5.5.F F (E) | i(E) | i ( ; i ( ; i +, -, +, -, * *, /, ),#, /, ),#6.6.A A +|-+|- + ; - + ; - (, i(, i7.7.M M * *|/|/ * * ; / ; / (, i(, i其对应的预测分析表如下：其对应的预测分析表如下：i+-*/()#E ETEETEEEATE EATEE ET TFTT FTTTTTMFTTMFTT TF F iF (E)AA +A -MM *M /4.4

32、 LL(1)分析器的构造例设有文法G(S)lS iCtSSalSeSl bCompilerPrinciples53对S：lSELECTSELECT( iCtSS )= i lSELECTSELECT(a)= a 对S: lSELECTSELECT(eS )= e lSELECTSELECT()=FOLLOW(S)=#,eSELECTSELECT(eS ) SELECT(SSELECT(S) 4.4 LL(1)分析器的构造文法G(S)的分析表54 a b e a b e i i t # t #S Sa SiCtSSS S S SeSC Cb多重定义CompilerPrinciples55n可以证

33、明，一个文法可以证明，一个文法G G的预测分析表不含多重入口，当的预测分析表不含多重入口，当且仅当该文法是且仅当该文法是LL(1)LL(1)的。的。n 定义定义n一部文法一部文法G G，若它的，若它的LL(1)LL(1)分析表不含多重定义入口，分析表不含多重定义入口，则称它是一个则称它是一个LL(1)LL(1)文法。由文法。由LL(1)LL(1)文法产生的语言称为文法产生的语言称为LL(1)LL(1)语言。语言。结论：LL(1)LL(1)文法的判别条件文法的判别条件LL(1)LL(1)文法文法任何两个产生式任何两个产生式A A | | 都满足下列条件：都满足下列条件： SELECT( SELE

34、CT(A A ) ) SELECT ( SELECT (A A ) = ) = LL(1)LL(1)文法有一些明显的性质文法有一些明显的性质没有公共左因子没有公共左因子不是二义的不是二义的不含左递归不含左递归某些非LL(1)文法到LL(1)文法的等价转换n方法：通过消除左递归和反复提取公共左因子进行等价转换方法：通过消除左递归和反复提取公共左因子进行等价转换n例题：例题：nGS:S aSb|An A bAc| bBcn B Ba| a n判断该文法是不是判断该文法是不是LL（1）文法）文法574.5 递归下降分析法和递归下降分析器递归下降分析器递归下降分析器( Recursive-Descen

35、t Parser )( Recursive-Descent Parser )l由一组递归过程组成，且每个过程对应文法的一个VN 的分析程序。 递归下降分析器的基本构造方法递归下降分析器的基本构造方法l对文法的每个非终结符号，都根据其产生式的各个候选式的结构，为其编写一个对应的子程序（或函数），该子程序完成相应的非终结符对应的语法成份的识别和分析任务CompilerPrinciples58递归递归下降下降分析分析法分析分析法59递归下降分析法条件递归下降分析法条件不带回溯地进行分析文法不含左递归每个非终结符的所有候选式集SELECT两两不相交60n例：文法GE:nE E+TTnT T*F|FnF

36、 (E)|in消除左递归后的文法G(E)：nE TEnE+TE|nT FTnT*FT|nF (E)|in文法G(E)的递归下降语法分析程序如下递归递归下降下降分析分析法分析分析法4.5 递归下降分析法和递归下降分析器E ( ) T( ); E( );CompilerPrinciples61E( )if (c=+) c=get char(); T( ); E( ); T ( ) F( ); T( );F ( ) if ( c=i ) c=get char();else if ( c=( )c=get char(); E( );if (c=) ) c=get char(); else error; error;T( ) if (c=*) c=get char(); F( ); T( )4.5 递归下降分析法和递归下降分析器设有 $