编译原理 第4章-自顶向下语法分析方法.

1、Compiler Construction Principles 本本章讨论程序语言的语法分析方章讨论程序语言的语法分析方法，以及语法分析程序的设计原理法，以及语法分析程序的设计原理和实现技术。和实现技术。Compiler Construction Principlesu语法分析程序的功能和语法分析方法u 自顶向下语法分析法u 自底向上算符优先分析法u LR分析法 Compiler Construction Principles语法分析程序的功能语法分析程序的功能 语法分析器语法分析器词法分析后词法分析后的单词串的单词串语法成分构语法成分构成的语法树成的语法树或错误表或错误表Compiler

2、Construction Principles语法分析的方法自顶向下语法分析法(自上而下语法分析法)自底向上语法分析法(自下而上语法分析法)Compiler Construction Principles1. 1. 自上而下的分析法自上而下的分析法 从文法的开始符号出发，根据文法规从文法的开始符号出发，根据文法规则正向推导出给定句子的一种方法；或者则正向推导出给定句子的一种方法；或者说，从树根开始，往下构造语法树，直到说，从树根开始，往下构造语法树，直到建立每个叶的分析方法。建立每个叶的分析方法。 Compiler Construction Principles2. 2. 自下而上的分析法自下

3、而上的分析法 从给定的输入串开始，根据文法规从给定的输入串开始，根据文法规则逐步进行归约，直至归约到文法开始则逐步进行归约，直至归约到文法开始符号的一种方法；或者说，从语法树的符号的一种方法；或者说，从语法树的未端开始，步步向上归约，直至根结点未端开始，步步向上归约，直至根结点的分析方法。的分析方法。 Compiler Construction Principles4.2 4.2 自上而下自上而下语法语法分析法分析法 非确定的自上而下分析法的基本思想是非确定的自上而下分析法的基本思想是： 对任何输入串对任何输入串W试图用一切可能的试图用一切可能的办法，从文法的开始符号出发，自上而办法，从文法的

4、开始符号出发，自上而下地为它建立一棵语法树。或者说，为下地为它建立一棵语法树。或者说，为输入串寻找一个最左推导。如果试探成输入串寻找一个最左推导。如果试探成功，则功，则W为相应文法的一个句子，否则为相应文法的一个句子，否则W就不是文法句子。就不是文法句子。Compiler Construction Principles4.2.1 4.2.1 非确定的自上而下分析法的非确定的自上而下分析法的思想思想 也就是说，这种分析过程本质上是也就是说，这种分析过程本质上是一种穷举试探过程，是反复使用不同规一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。则，谋求匹配输入串的过程。试探发生回溯。试探

5、发生回溯。 Compiler Construction Principles4.2.1 4.2.1 非确定的自上而下分析法的非确定的自上而下分析法的思想思想例例 设有文法设有文法GS：S aAbA de | d输入串输入串 W=adbS a A bd e匹配失败、这时应回匹配失败、这时应回溯溯, ,选择选择A A的其它可能的其它可能的规则重新匹配。的规则重新匹配。Compiler Construction Principles4.2.1 4.2.1 非确定的自上而下分析法的非确定的自上而下分析法的思想思想d匹配成功匹配成功 S aAbA de | dS a A b输入串输入串 W=adbCom

6、piler Construction Principles4.2.1 4.2.1 非确定的自上而下分析法的非确定的自上而下分析法的思想思想 上述自上而下为输入串上述自上而下为输入串W建立语法建立语法树的过程，实际也是设法为输入串建树的过程，实际也是设法为输入串建立一个最左推导序列：立一个最左推导序列：SaAbadb。 由于对输入串从左向右进行扫描，由于对输入串从左向右进行扫描，使用最左推导，才能保证按从左到右使用最左推导，才能保证按从左到右扫描顺序匹配输入串扫描顺序匹配输入串。Compiler Construction Principles4.2.1 4.2.1 非确定的自上而下分析法的非确定

7、的自上而下分析法的思想思想 根据以上分析，不难看出，非确定根据以上分析，不难看出，非确定的自上而下分析法即是带回溯的自上而的自上而下分析法即是带回溯的自上而下分析法下分析法, , 实际上是一种穷举的试探方实际上是一种穷举的试探方法，其分析效率极低，代价很高，在实法，其分析效率极低，代价很高，在实用的编译程序中是不常用的。我们通常用的编译程序中是不常用的。我们通常使用确定的自上而下分析法进行语法分使用确定的自上而下分析法进行语法分析。析。 Compiler Construction Principles4.2.1 4.2.1 非确定的自上而下分析法非确定的自上而下分析法的思想的思想 但确定的自上

8、而下分析法对语言但确定的自上而下分析法对语言的文法有一定的限制条件，那就是要的文法有一定的限制条件，那就是要求描述语言的文法是无左递归的和无求描述语言的文法是无左递归的和无回溯的。回溯的。 Compiler Construction Principles4.2.2 文法的左递归性和回溯的消除 文法左递归的消除 当一个文法是左递归文法时，采用自上而下分析法会使分析过程进入无穷循环之中。 文法左递归是指文法中的某个非终结符A存在推导A A+Compiler Construction Principles4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除 用非终结符用非终结

9、符A去匹配输入串时去匹配输入串时,使当前句使当前句型的最左非终结符仍然为型的最左非终结符仍然为A。 也就是说，在没有读进任何输入符号的也就是说，在没有读进任何输入符号的情况下，又重新要求情况下，又重新要求A去进行新的匹配。去进行新的匹配。于是，造成无穷循环。于是，造成无穷循环。 Compiler Construction Principles4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除 对含直接左递归的规则进行等价变换，对含直接左递归的规则进行等价变换，消除左递归消除左递归(1) 引进一个新的非终结符，把含左递归引进一个新的非终结符，把含左递归 的规则改写成右递

10、归。的规则改写成右递归。 设关于非终结符设关于非终结符A的直接左递归的的直接左递归的规则为规则为Compiler Construction Principles4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除对对A的规则可改写成如下右递归形式：的规则可改写成如下右递归形式： A A | A AA A | 其中其中 、是任意的符号串是任意的符号串, 不等于不等于 , 不以不以A开头开头Compiler Construction Principles4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除 改写以后的形式和原来形式是等价改写以后的形式

11、和原来形式是等价的。也就是说，从的。也就是说，从A推出的符号串的集推出的符号串的集合是相同的。合是相同的。 Compiler Construction Principles4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除一般情况下，设文法中关于一般情况下，设文法中关于A的规则为的规则为A A1| A2| | Am| 1| 2| | n 其中每个其中每个都不等于都不等于，而每个，而每个 都不都不以以A开头，消除直接左递归后改写为开头，消除直接左递归后改写为:A 1A | 2A | mA | A 1A | 2A | nACompiler Construction Pri

12、nciples4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除例例1 设有文法设有文法GE： E E+T | ET | TT T* *F | T/F | FF (E) | id消去非终结符消去非终结符E, T的直接左递归后，的直接左递归后，文法文法GE改写为：改写为：F (E) | idETEE +TE | TE | T FTT * *FT | /FT | Compiler Construction Principles4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除例例2 设有文法设有文法GA: A Ac | Aad | bd | e消

13、去直接左接左递归后文法消去直接左接左递归后文法GA改写为改写为 A cA | adA | A bdA | eACompiler Construction Principles4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除2. 2. 回溯的消除回溯的消除 在自上而下分析过程中，由于回在自上而下分析过程中，由于回溯，需要推翻前面的分析，包括已做溯，需要推翻前面的分析，包括已做的一大堆语义工作，重新去进行试探，的一大堆语义工作，重新去进行试探，这样大大降低了语法分析器的工作效这样大大降低了语法分析器的工作效率，因此，需要消除回溯。率，因此，需要消除回溯。 Compile

14、r Construction Principles4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除 我们分析发现引起回溯的原因是我们分析发现引起回溯的原因是: 在在文法中文法中,当某个非终结符当某个非终结符A有多个候选式时有多个候选式时:遇到用遇到用A去匹配当前输入符号去匹配当前输入符号a时，时，无法确定选用唯一的一个候选式，而只无法确定选用唯一的一个候选式，而只能逐一进行试探，从而引起回溯。具体能逐一进行试探，从而引起回溯。具体表现在下面两种情况。表现在下面两种情况。A 1 | 2 | 3 | nCompiler Construction Principles4.

15、2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除 第一种情况第一种情况: : 文法中相同左部的文法中相同左部的规则，其右部左端第一个符号相同而规则，其右部左端第一个符号相同而引起回溯。引起回溯。S aAbA de | d例例 设有文法设有文法GS： Compiler Construction Principles4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除 第二种情况第二种情况: 文法中相同左部的规文法中相同左部的规则，其中某一右部能推出则，其中某一右部能推出串，例如串，例如, 文法文法G： A BxB x | 其非终结符其非终结符B有两

16、个右部，第二个右有两个右部，第二个右部能推导出部能推导出串且两个右部左端第一串且两个右部左端第一个符号不相同，但在分析符号串个符号不相同，但在分析符号串Wx 时出现回溯。时出现回溯。 Compiler Construction Principles4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除试探分析过程如下图所示：试探分析过程如下图所示： A B xxA B xA BxB x | Wx匹配失败匹配失败匹配成功匹配成功 Compiler Construction Principles4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除消除 综上

17、所述，在自上而下分析过程综上所述，在自上而下分析过程中，为了避免回溯，中，为了避免回溯， 对描述语言的对描述语言的文法有一定的要求文法有一定的要求: :Compiler Construction Principles 对文法的某个非终结符对文法的某个非终结符A,当它有多当它有多个侯选式时个侯选式时: 若用若用A匹配输入串时匹配输入串时,能根据当前读到能根据当前读到的输入符号的输入符号a唯一地选择一条规则去匹唯一地选择一条规则去匹备输入串。或者说，能唯一地选择一条备输入串。或者说，能唯一地选择一条规则进行推导。规则进行推导。4.2.2 4.2.2 文法文法的左递归性和回溯的的左递归性和回溯的消除

18、消除A 1 | 2 | 3 | nCompiler Construction Principles 这也就是说，在自上而下分析过程中，为了避免回溯，要求描述语言的文法是LL(1)文法。4.2.2 文法的左递归性和回溯的消除Compiler Construction PrinciplesLL(1)文法的判断条件文法的判断条件 为了建立为了建立LL(1)文法的判断条件，需引文法的判断条件，需引进三个相关集：进三个相关集： FIRST集集 FOLLOW集集SELECT集集 Compiler Construction PrinciplesLL(1)文法的判断条件文法的判断条件(1) 设设是文法是文法G

19、的任一符号串，定义文的任一符号串，定义文 法符号串法符号串的首符号集合。的首符号集合。FIRST() = a | a且且 aVT *,则规定则规定 FIRST()若若 *Compiler Construction PrinciplesLL(1)文法的判断条件文法的判断条件例例 设有文法设有文法GS: S Ap | BqA cA | aB dB | bFIRST(Ap) = c, a AP cAp AP ap FIRST(Bq) =Bq bq b, d Bq dBq Compiler Construction Principles LL(1)文法的判断条件文法的判断条件(2) 设文法设文法G的开

20、始符号为的开始符号为S，对于，对于G的的任任 何非终结符何非终结符A，定义非终结符，定义非终结符A的后的后 继符号的集合继符号的集合 FOLLOW(A) = a | S Aa 且且aVT *若有若有S A ,*则规定则规定 # FOLLOW(A)。 Compiler Construction PrinciplesLL(1)文法的判断条件文法的判断条件 换句话说换句话说FOLLOW(A)是是G的所有句的所有句型中紧接在型中紧接在A之后出现的终结符或之后出现的终结符或#。 这里我们用这里我们用#作为输入串的结束符，作为输入串的结束符，例如，例如， # 输入串输入串 # 。 Compiler Con

21、struction PrinciplesLL(1)文法的判断条件文法的判断条件例例 设有文法设有文法GA: FOLLOW(B) =A aB A aB abBA abBd A aB abBA abBaB # , d, a AaB | dBbBA | Compiler Construction PrinciplesLL(1)文法的判断条件文法的判断条件(3) 定义规则的选择集合定义规则的选择集合SELECT，设，设 A 是文法是文法G的任一条规则，其中的任一条规则，其中 AVN , (VNVT)* ，定义，定义 SELECT(A ) =FIRST() FIRST()FOLLOW (A) */若若

22、*若若 Compiler Construction PrinciplesLL(1)文法的判断条件文法的判断条件例例 设有文法设有文法GA: AaB | dBbBA | SELECT(AaB ) =FIRST(aB) = a SELECT(Ad ) = FIRST(d) = d Compiler Construction PrinciplesLL(1)文法的判断条件文法的判断条件 b SELECT(BbBA ) =FIRST(bBA) = = , #, d, a FOLLOW(B)SELECT(B) =FIRST() FOLLOW(B) = #, d, a AaB | dBbBA | Compi

23、ler Construction PrinciplesLL(1)文法的判断条件文法的判断条件LL(1)文法定义文法定义一个上下文无关文法一个上下文无关文法 G是是LL(1)文法文法, 当当且仅当对且仅当对 G 中每个非终结符中每个非终结符A的任何两的任何两个不同的规则个不同的规则 A | ，满足，满足 SELECT(A )SELECT(A) = 其中其中 、中至多只有一个能推出中至多只有一个能推出串。串。 Compiler Construction PrinciplesLL(1)文法的判断条件文法的判断条件 LL(1)中的第一个中的第一个L表明自上而下的表明自上而下的分析是从左到右扫描输入串，

24、第二个分析是从左到右扫描输入串，第二个L表明分析过程中使用最左推导，表明分析过程中使用最左推导，1表示表示分析时每一步只需向前看一个符号即可分析时每一步只需向前看一个符号即可决定所选用的规则，而且这种选择是准决定所选用的规则，而且这种选择是准确无误的。确无误的。 Compiler Construction Principles 确定的自上而下分析法要求描述确定的自上而下分析法要求描述 语言的文法是语言的文法是 LL(1)LL(1)文法。文法。 (1) (1) 求文法每个产生式右部符号串的求文法每个产生式右部符号串的 FIRSTFIRST集。集。(2)(2)求文法各个非终结符的求文法各个非终结符

25、的FOLLOWFOLLOW集。集。LL(1)文法的判断条件文法的判断条件Compiler Construction Principles(3)(3)求文法每个产生式的求文法每个产生式的SELECTSELECT集。集。(4)(4)求相同左部产生式的求相同左部产生式的SELECTSELECT交集。交集。对对文法文法GG的每一个的每一个非终结符非终结符A A的的产生式产生式SELECT(A i)SELECT(A j)= (ij)则文法则文法G G是一个是一个LL(1)LL(1)文法文法A 1 | 2 | n下面条件成立下面条件成立: :LL(1)文法的判断条件文法的判断条件Compiler Cons

26、truction Principles例例 设有文法设有文法GSSaAbDe | dABSD | eBSAc | cD | DSe | 1. 计算文法计算文法GS每个非终结符的每个非终结符的FIRST集集 和和FOLLOW集集 。2. 判断文法判断文法GS 是否是否LL(1)文法。文法。 Compiler Construction Principles对每一文法符号对每一文法符号XV, 求求FIRST(X)的规则的规则: FIRST() = a | a且且 aVT *,则规定则规定 FIRST()若若 *1. 若若 XVT , 则则FIRST(X) =X2. 若若 XVN 且有且有 X a,

27、则把则把 a 加入加入 FIRST(X)中中 ,若若 X , 则把则把 加入加入FIRST(X)中中 3. 若若 XY1Y2Yn, YiVN ,则把则把 FIRST(Y1)中所有非中所有非 元素加入元素加入FIRST(X)中中 ,若若Y1 ,则把则把 FIRST(Y1)中所有非中所有非 元素加入元素加入FIRST(X)中中 , Y1 y2Yn ,则把则把 加入加入FIRST(X)中中 Compiler Construction Principles FIRST(S)=FIRST(aAbDe)FIRST(d)= a,d FIRST(A)=FIRST(B)FIRST(e) FIRST(S)e= a

28、,d,c,e SaAbDe | dABSD | eBSAc | cD | DSe | 问问: 能否能否 因为从因为从 A */ , 所以所以 FIRST(A) FIRST(B)=FIRST(S)FIRST(cD)= a,d,c, FIRST(D)=FIRST(Se)= a, d, Compiler Construction PrinciplesFOLLOW(A) = a | S Aa 且且aVT *若有若有S A ,*则规定则规定 #FOLLOW(A)。 求求FOLLOW(A)的规则的规则:1. 对文法的开始符号对文法的开始符号S , 令令#FOLLOW(S)2.若若 AB是一条规则是一条规则

29、, 则把则把FOLLOW(A)加到加到FOLLOW(B)中中3.若若 AB是一条规则是一条规则, 则将则将FIRST() 加到加到FOLLOW(B)中中,若若 , 则把则把FOLLOW(A)加到加到FOLLOW(B)中中*Compiler Construction Principles FOLLOW(S)=#,a,b,c,d,eFOLLOW(A)=b,cFOLLOW(B)=a,dFOLLOW(D)=a,b,c,d,eSaAbDe | dABSD | eBSAc | cD | DSe | FIRST(D)= a, d, FIRST(S)= a,d FIRST(A)= a,d,c,e Compil

30、er Construction Principles根据LL(1)文法的定义有:SELECT(SaAbDe)SELECT(Sd)=FIRST(aAbDe)FIRST(d)=SELECT(ABSD)SELECT(Ae)=FIRST(BSD)FIRST(e)=SaAbDe | dABSD | eBSAc | cD | DSe | SELECT(BSAc)SELECT(BcD)=FIRST(SAc)FIRST(cD)=SELECT(BSAc)SELECT(B)=FIRST(SAc) a, d FOLLOW(B)=a,d所以该文法不是LL(1)文法Compiler Construction Princ

31、iplesE TEE +TE | T FTT *FT | F (E) | id练习练习 设有文法设有文法GE：1. 计算文法计算文法GS每个非终结符的每个非终结符的FIRST集和集和FOLLOW集集 。2. 判断文法判断文法GS 是否是否LL(1)文法。文法。 Compiler Construction Principles例例1 设有文法设有文法GS:S aAbA de | dSELECT(Ade)= FIRST(de)=dSELECT(Ad)= FIRST(d)=dSELECT(Ade)SELECT(Ad) 由由LL(1)文法定义可知，该文法不是文法定义可知，该文法不是LL(1)文法，因此

32、对输入串不能进行确文法，因此对输入串不能进行确定的自上而下分析。定的自上而下分析。 Compiler Construction Principles例例2 设有文法设有文法GA A aB | dB bBA | 则则 SELECT(AaB)=FIRST(aB)=a SELECT(Ad)=FIRST(d)=d SELECT(BbBA)=FIRST(bBA)=b SELECT(B) =(FIRST()- )FOLLOW(B)=a, d, #Compiler Construction Principles所以所以 SELECT(AaB)SELECT(Ad)=SELECT(BbBA)SELECT(B)=

33、由定义可知，由定义可知，GA是是LL(1)文法，对任文法，对任何输入串何输入串W可进行确定的分析。可进行确定的分析。 Compiler Construction Principles例例3 设有文法设有文法GS:S aABA bB | dA | B a | e SELECT(AbB)=FIRST(bB)= b SELECT(AdA)=FIRST(dA)= d SELECT(A) =(FIRST()- ) FOLLOW(A) = a, e 试判断该文法是否试判断该文法是否LL(1)文法。文法。Compiler Construction Principles SELECT(Ba)=FIRST(a)

34、= a SELECT(Be)=FIRST(e)= e SELECT(AbB)SELECT(AdA)=SELECT(AbB)SELECT(A)=SELECT(AdA)SELECT(A)=SELECT(Ba)SELECT(Be)=S aABA bB | dA | B a | e 该文法为该文法为LL(1)文法文法Compiler Construction Principles例例4 设有文法设有文法GS:S AB | bCA b | B aD | C AD | D aS | c 试判断该文法是否试判断该文法是否LL(1)文法文法 分析分析 对文法某个非终结符对文法某个非终结符,当有多个候当有多个候

35、选式时选式时, 求规则的求规则的SELECT集合集合Compiler Construction PrinciplesSELECT(SAB) =FIRST(AB)FOLLOW(S) = a, b, # SELECT(SbC)=FIRST(bC)= b SELECT(SAB)SELECT(S bC) S AB | bCA b | B aD | C AD | D aS | cFIRST(AB)=FIRST(A)FIRST(B)=a, b, FOLLOW(S)=# 该文法不为该文法不为LL(1)文法文法Compiler Construction PrinciplesLL(1)LL(1)文法文法的判断条

36、件的判断条件 由定义可知由定义可知, 文法文法GS是是LL(1)文法，文法，对任何的输入串可进行确定的自上而下对任何的输入串可进行确定的自上而下分析。分析。Compiler Construction PrinciplesLL(1)文法的判断条件文法的判断条件综合上面的讨论，我们可知对综合上面的讨论，我们可知对LL(1)文法，若当前非终结符文法，若当前非终结符A面临输入符号面临输入符号a时，可根据时，可根据a属于哪一个属于哪一个SELECT集，唯集，唯一地选择一条相应规则去准确地匹配输一地选择一条相应规则去准确地匹配输入符号入符号a。也就是说，当描述语言的文法。也就是说，当描述语言的文法是是LL

37、(1)文法时，可对其进行确定的自上文法时，可对其进行确定的自上而下的分析。而下的分析。 Compiler Construction Principles4.2.3 某些非某些非LL(1)文法到文法到LL(1)文法的改文法的改写写 前面已经指出，构造确定的自上前面已经指出，构造确定的自上而下分析程序要求对给定语言的文法而下分析程序要求对给定语言的文法必须是必须是LL(1)文法，但是，并不是每文法，但是，并不是每个语言都有个语言都有LL(1)文法。文法。 Compiler Construction Principles 由由 LL(1)文法定义可知文法定义可知, 若文法中含若文法中含有左递归或含有

38、公共左因子，则该文有左递归或含有公共左因子，则该文法不是法不是 LL(1) 文法，因此，对某些非文法，因此，对某些非LL(1)文法而言文法而言, 可通过消除左递归和可通过消除左递归和反复提取公共左因子对文法进行等价反复提取公共左因子对文法进行等价变换，可能将其改造为变换，可能将其改造为 LL(1)文法。文法。消除文法左递归的方法见消除文法左递归的方法见4.2.2。 Compiler Construction Principles提取公共左因子提取公共左因子当文法中含有形如当文法中含有形如A 1 | 2 | | n 的规则的规则 不满足不满足LL(1)文法条件。文法条件。则其右部的则其右部的FI

39、RST集交不空，即集交不空，即 SELECT(A i)SELECT(A j)Compiler Construction Principles提取公共左因子将文法改写成提取公共左因子将文法改写成: : A A 若在若在 1 1, , 2 23 3中仍含有公共左因子，中仍含有公共左因子，这时可再次提取这时可再次提取, , 这样反复进行提取，直这样反复进行提取，直到引进新非终结符的有关规则再无公共左到引进新非终结符的有关规则再无公共左因子为止。因子为止。 A 1 | 2 | | n 的规则的规则 A 1| 2| | nCompiler Construction Principles例例1 设有文法设

40、有文法GS: 该文法是非该文法是非LL(1)文法，该文法有公共文法，该文法有公共左因子，利用提取公共左因子的方法对左因子，利用提取公共左因子的方法对其进行改写，我们得到其进行改写，我们得到 S aAbA de | dCompiler Construction Principles不难验证改写后的文法为不难验证改写后的文法为LL(1)文法。文法。 因为因为 SELECT(A e)SELECT(A ) =e, b= S aAbA dAA e | Compiler Construction Principles例例2 2 设有文法设有文法GS:GS:S ad | AeA aS | bA将将A的两条规

41、则代入非终结符的两条规则代入非终结符S的规则中的规则中A aS | bAS ad | aSe | bAeCompiler Construction Principles对对S提取公共左因子得提取公共左因子得 S bAe | aS改写后的文法是改写后的文法是LL(1)文法。文法。S d | SeA aS | bAA aS | bAS ad | aSe | bAeCompiler Construction Principles应当指出的是并非一切非应当指出的是并非一切非LL(1)文法文法都能改写为都能改写为LL(1)文法。文法。例如，对于文法例如，对于文法 S Ae | BdA aAe | bB

42、aBd | b 该文法不为该文法不为LL(1)文法文法 SELECT(SAe)SELECT(SBd) = a, b a, b Compiler Construction Principles对对S提取公共左因子后，得提取公共左因子后，得对于对于S的两条规则的两条规则, 可先将非终结可先将非终结符符A、B用相应规则右部进行替换，我用相应规则右部进行替换，我们得到们得到S aAee | be | aBdd | bdA aAe | bB aBd | bCompiler Construction Principles显然，它仍不是一个显然，它仍不是一个LL(1)文法，且文法，且不难看出无论将上述步骤重

43、复多少次不难看出无论将上述步骤重复多少次, 都都无法将它改写为无法将它改写为LL(1)文法。文法。S aS | bSS Aee | BddA aAe | bS e | dB aBd | bCompiler Construction Principles4.2.4 递归下降分析法递归下降分析法 递归下降分析法是确定的自递归下降分析法是确定的自上而下分析法，这种分析法要上而下分析法，这种分析法要求文法是求文法是LL(1)文法。文法。 Compiler Construction Principles基本思想基本思想 对文法中的每个非终结符编写一个函对文法中的每个非终结符编写一个函数数 ( (或子程序

44、或子程序), ), 每个函数（或子程序）的每个函数（或子程序）的功能是识别由该非终结符所表示的语法成功能是识别由该非终结符所表示的语法成分。由于描述语言的文法常常是递归定义分。由于描述语言的文法常常是递归定义的，因此相应的这组函数（或子程序）必的，因此相应的这组函数（或子程序）必然以相互递归的方式进行调用，所以将此然以相互递归的方式进行调用，所以将此种分析法称为递归下降分析法。种分析法称为递归下降分析法。 Compiler Construction Principles构造递归下降分析程序的方法构造递归下降分析程序的方法: : 为每个非终结符编制一个递归下降为每个非终结符编制一个递归下降分析函

45、数，每个函数名是相应的非终结分析函数，每个函数名是相应的非终结符，函数体则是根据规则右部符号串的符，函数体则是根据规则右部符号串的结构和顺序编写。结构和顺序编写。A12niVTiVN 12n=Compiler Construction Principles(1) 当遇到终结符当遇到终结符a时，则编写语句时，则编写语句 if (当前读来的输入符号当前读来的输入符号=a) 读下一个输入符号；读下一个输入符号； (2) 当遇到非终结符当遇到非终结符A时，则编写语句调时，则编写语句调 用用 A( )； Compiler Construction Principles(4) 当某个非终结符的规则有多个候

46、选式当某个非终结符的规则有多个候选式 时，按时，按LL(1)文法的条件能唯一地选文法的条件能唯一地选 择一个候选式进行推导。择一个候选式进行推导。 (3) 当遇到规则当遇到规则A 时，则编写语句时，则编写语句 if (当前读来的输入符号当前读来的输入符号 FOLLOW(A) error( )；Compiler Construction PrinciplesE E + T | TT T * * F | FF (E) | id 例例 设有文法设有文法GE：试构造一个识别该文法句子的递归下试构造一个识别该文法句子的递归下降分析程序。降分析程序。 Compiler Construction Princ

47、iples分析分析 首先消去文法左递归，得到文法首先消去文法左递归，得到文法 GEE TEE +TE | T FTT * *FT | F (E) | idEE + T |TTT * * F |FF(E) | id Compiler Construction Principles 无左递归的文法不一定是无左递归的文法不一定是LL(1)文法，文法，根据根据LL(1)文法的判断条件，对非终结符文法的判断条件，对非终结符 E, T, F有：有： E TEE +TE | T FTT * *FT | F (E) | idCompiler Construction Principles SELECT(E +

48、TE)SELECT(E ) =FIRST(+TE)FOLLOW(E) = + ), # = SELECT(T * *FT)SELECT(T ) =FIRST(* *FT)FOLLOW(T) = * * ), #, + = Compiler Construction Principles SELECT(Fid )SELECT(F(E) = FIRST(id)FIRST(E)=id(=所以文法所以文法GE是是LL(1)文法。文法。 Compiler Construction Principles分析程序中定义两个函数：分析程序中定义两个函数：(1) 函数函数 Scaner( ) 功能功能: 读进源

49、程序的下一个单词符号读进源程序的下一个单词符号 并将它放在全程变量并将它放在全程变量sym。(2) 函数函数 error( ) 功能功能: 出错处理程序。出错处理程序。 Compiler Construction Principles 对文法对文法GE可写出相应的递归下降分可写出相应的递归下降分析程序如下：析程序如下： E TEE +TE | T FTT * *FT | F (E) | idmain( ) Scaner ( ); E ( ); if (sym= =#) printf (“success”); else printf (“fail”); Compiler Construction

50、 PrinciplesE ( ) T( ); E( ); E( ) if (sym = =+) Scaner( ); T ( ) ; E ( ); else if (sym!=)&(sym!=#) error( ); E TEE +TE | T FT T * *FT | F (E) | idCompiler Construction PrinciplesT ( ) F ( ) ; T ( ); E TEE +TE | T FT T * *FT | F (E) | idT ( ) if (sym = =* *) Scaner( ); F ( ) ; T ( ); else if (sym

51、 follow(T) error( ); Compiler Construction PrinciplesF ( ) if (sym= = id) Scaner ( ); else if (sym= = () Scaner( ) ; E ( ); if (sym = = ) ) Scaner ( ); else error ( ); else error ( ); E TE E +TE | T FT T * *FT | F (E) | idCompiler Construction Principlesmain( ) Scaner ( ); E ( ); if (sym= =#) printf

52、 (“success”); else printf (“fail”); id + id #E ( ) T( ); E ( ); T ( ) F ( ) ; T ( ); 见见F见见E见见T返回下一页返回下一页Compiler Construction PrinciplesF ( ) if (sym= = id) Scaner ( ); else if (sym= = () Scaner( ) ; E ( ); if (sym = = ) ) Scaner ( ); else error ( ); else error ( ); 返回返回TCompiler Construction Princi

53、plesT ( ) if (sym = =* *) Scaner( ); F ( ) ; T ( ); else if (sym follow(T) error( ); follow(T)=+, ), # 返回返回TCompiler Construction PrinciplesE ( ) if (sym = =+) Scaner( ); T ( ) ; E ( ); else if (sym!=)&(sym!=#) error( ); 返回返回E见见T返回返回ECompiler Construction Principles 对这个例子，若采用扩充的对这个例子，若采用扩充的BNF表示

54、表示法改写文法，得到法改写文法，得到GE：E T +T T F * *F F (E) | idEE + T |TTT * * F |FF(E) | id Compiler Construction Principles 该文法是该文法是LL(1)文法，其递归下降分文法，其递归下降分析程序中主函数和函数析程序中主函数和函数F( )同上，对函同上，对函数数E( )和函数和函数T( )用用while语句描述如下：语句描述如下： Compiler Construction PrinciplesE ( ) T ( ); while ( sym = =+) Scanner ( ); T ( ); T (

55、) F ( ); while ( sym = =*) Scanner ( ); F ( ); E T +T T F * *F F (E) | idCompiler Construction Principles缺点缺点: : 对文法要求高，必须是对文法要求高，必须是LL(1)LL(1)文文 法，同时由于递归调用较多，影法，同时由于递归调用较多，影 响分析器的效率。响分析器的效率。 优点优点: : 递归下降分析法简单、直观，易递归下降分析法简单、直观，易 于构造分析程序。于构造分析程序。 Compiler Construction Principles 预测分析法预测分析法(LL(1)分析法分析

56、法)是确是确定的自上而下分析的另一种方法，定的自上而下分析的另一种方法，采用这种方法进行语法分析要求采用这种方法进行语法分析要求描述语言的文法是描述语言的文法是LL(1)文法。文法。 Compiler Construction Principles预测分析器的逻辑结构预测分析器的逻辑结构预测分析表预测分析表总控程序总控程序 a1 a2 ai an #T j 输入串输入串 X #输出输出分分析析栈栈Compiler Construction Principles 输入缓冲区输入缓冲区Tj中存放待分析的输入符中存放待分析的输入符号串，它以右界符号串，它以右界符 # 或或#作为结束。作为结束。 分析

57、栈分析栈SK中存放替换当前非终结符的中存放替换当前非终结符的某规则右部符号串，句子左界符某规则右部符号串，句子左界符#或或#存入栈底。存入栈底。 预测分析表是一个二维形式的矩阵，预测分析表是一个二维形式的矩阵，其中矩阵的行为文法非终结符，矩阵的其中矩阵的行为文法非终结符，矩阵的列为文法终结符或列为文法终结符或#或或# 。见表见表Compiler Construction Principles id + * * ( ) # E E T T FETEETEE +TEEETFTTFTTT TT* *FTFidF(E) 预测分析器的总控程序在任何时候都是根据栈预测分析器的总控程序在任何时候都是根据栈顶

58、符号和当前输入符号顶符号和当前输入符号a来决定分析器的动作。来决定分析器的动作。Compiler Construction Principles#和文法开始符号进和文法开始符号进S栈栈第一个输入符号读进第一个输入符号读进aS栈顶符号上托出去放栈顶符号上托出去放 X中中 XVT?X=a ?Y将下一个输将下一个输入符号读入入符号读入aY出错出错NNX=# ?X=a ?YSTOPYN查查MX,a=Xy1y2yn ?N将将y1y2yn逆序放逆序放入入S栈中，若右部栈中，若右部符号串为符号串为，则，则不进不进S栈栈Y出错出错NCompiler Construction Principles 预测分析器的

59、总控程序对于不同的预测分析器的总控程序对于不同的LL(1)文法都是相同的，而预测分析表对文法都是相同的，而预测分析表对于不同的于不同的LL(1)文法是不相同的。文法是不相同的。 构造预测分析表的方法：构造预测分析表的方法：输入输入: 文法文法G输出输出: 预测分析表预测分析表M Compiler Construction Principles方法：方法： 1 1. .计算文法计算文法GG的每一非终结符的的每一非终结符的FIRSTFIRST集集 和和FOLLOWFOLLOW集。集。 2.对文法的每个规则对文法的每个规则A, 若若aFIRST() , 则置则置MA, a= A 。 3.若若FIRS

60、T(), 则对则对 任任bFOLLOW(A), 则置则置MA, b= A Compiler Construction Principles 4. 4.把分析表中每个未定义的元素标上出把分析表中每个未定义的元素标上出 错标志错标志errorerror（表中用空白格表示）（表中用空白格表示）例例 设有文法设有文法GEGE： 试构造该文法的预测分析表。试构造该文法的预测分析表。 E TEE +TE | T FTT * *FT | F (E) | idCompiler Construction Principles E E T T F (, id ), # (, id + +, ), # (, id +, ), #,