第4章 语法分析.ppt

1、第4章 语法分析,本章讨论程序语言的语法分析方法，以及语法分析程序的设计原理和实现技术。,第4章 语法分析,语法分析程序的功能和语法分析方法,自顶向下语法分析法,自底向上算符优先分析法,LR分析法,4.1 语法分析程序的功能,语法分析程序的功能,或错误表,4.1 语法分析程序的功能,语法分析的方法,自顶向下语法分析法,(自上而下语法分析法),自底向上语法分析法,(自下而上语法分析法),4.1 语法分析程序的功能,1. 自上而下的分析法,从文法的开始符号出发，根据文法规则正向推导出给定句子的一种方法；或者说，从树根开始，往下构造语法树，直到建立每个叶的分析方法。,4.1 语法分析程序的功能,2.

2、 自下而上的分析法,从给定的输入串开始，根据文法规则逐步进行归约，直至归约到文法开始符号的一种方法；或者说，从语法树的未端开始，步步向上归约，直至根结点的分析方法。,4.2 自上而下语法分析法,非确定的自上而下分析法的基本思想是：,对任何输入串W试图用一切可能的办法，从文法的开始符号出发，自上而下地为它建立一棵语法树。或者说，为输入串寻找一个最左推导。如果试探成功，则W为相应文法的一个句子，否则W就不是文法句子。,4.2.1 非确定的自上而下分析法的思想,也就是说，这种分析过程本质上是一种穷举试探过程，是反复使用不同规则，谋求匹配输入串的过程。,试探发生回溯。,4.2.1 非确定的自上而下分析

3、法的思想,例 设有文法GS：,S aAb A de | d,输入串 W=adb,匹配失败、这时应回溯,选择A的其它可能的规则重新匹配。,4.2.1 非确定的自上而下分析法的思想,匹配成功,S aAb A de | d,输入串 W=adb,4.2.1 非确定的自上而下分析法的思想,上述自上而下为输入串W建立语法树的过程，实际也是设法为输入串建立一个最左推导序列：SaAbadb。,由于对输入串从左向右进行扫描，使用最左推导，才能保证按从左到右扫描顺序匹配输入串。,4.2.1 非确定的自上而下分析法的思想,根据以上分析，不难看出，非确定的自上而下分析法即是带回溯的自上而下分析法, 实际上是一种穷举的

4、试探方法，其分析效率极低，代价很高，在实用的编译程序中是不常用的。我们通常使用确定的自上而下分析法进行语法分析。,4.2.1 非确定的自上而下分析法的思想,但确定的自上而下分析法对语言的文法有一定的限制条件，那就是要求描述语言的文法是无左递归的和无回溯的。,4.2.2 文法的左递归性和回溯的消除,文法左递归的消除,当一个文法是左递归文法时，采用自上而下分析法会使分析过程进入无穷循环之中。,文法左递归是指文法中的某个非终结符A存在推导,4.2.2 文法的左递归性和回溯的消除,用非终结符A去匹配输入串时,使当前句型的最左非终结符仍然为A。,也就是说，在没有读进任何输入符号的情况下，又重新要求A去进

5、行新的匹配。 于是，造成无穷循环。,4.2.2 文法的左递归性和回溯的消除,对含直接左递归的规则进行等价变换，消除左递归,引进一个新的非终结符，把含左递归的规则改写成右递归。,设关于非终结符A的直接左递归的规则为,4.2.2 文法的左递归性和回溯的消除,对A的规则可改写成如下右递归形式：,A A | ,A A,A A | ,其中 、是任意的符号串, 不等于 , 不以A开头,4.2.2 文法的左递归性和回溯的消除,改写以后的形式和原来形式是等价的。也就是说，从A推出的符号串的集合是相同的。,4.2.2 文法的左递归性和回溯的消除,一般情况下，设文法中关于A的规则为,A A1| A2| | Am|

6、 1| 2| | n,其中每个都不等于，而每个都不以A开头，消除直接左递归后改写为:,A 1A | 2A | mA | ,A 1A | 2A | nA,4.2.2 文法的左递归性和回溯的消除,例1 设有文法GE：,E E+T | ET | T T T*F | T/F | F F (E) | id,消去非终结符E, T 的直接左递归后，文法GE改写为：,F (E) | id,ETE,E +TE | TE | ,T FT,T *FT | /FT | ,4.2.2 文法的左递归性和回溯的消除,例2 设有文法GA:,A Ac | Aad | bd | e,消去直接左接左递归后文法GA改写为,A cA

7、| adA | ,A bdA | eA,4.2.2 文法的左递归性和回溯的消除,(2) 采用扩充BNF表示法改写含直接左递归的规则：,在扩充的BNF表示中,使用花括号 表示符号串的出现可0次或多次，即表示 *,4.2.2 文法的左递归性和回溯的消除,例如 定义标识符的文法,(b) 使用方括号 表示 的出现可有可无，它用来表示可供选择的符号串。,lld,使用扩充BNF表示可改写成, l l | d ,4.2.2 文法的左递归性和回溯的消除,例如，定义C语言中条件语句的文法是,if if ; else ,用扩充BNF表示可改写成如下形式,if ;else,4.2.2 文法的左递归性和回溯的消除,(

8、c) 使用圆括号可在规则中提因子。,例如,A x1 | x2 | xm,可写为,A x ( 1 | 2 | m),4.2.2 文法的左递归性和回溯的消除,例3 对下列文法用扩充BNF表示法对其进行改写。,E E+T | ET | T T T*F | T/F | F F (E) | id,分析 规则 EE+T | ET | T表示了E所生成的符号串是T开头的后面跟0个或多个+T或T组成, 对T规则类似。,4.2.2 文法的左递归性和回溯的消除,文法GE可以改写为：,ET +T | T ,TF *F | / F ,F(E) | id,4.2.2 文法的左递归性和回溯的消除,例4 对下列文法用扩充B

9、NF表示法对其 进行改写。,A Ac | Aad | bd | e,分析,4.2.2 文法的左递归性和回溯的消除,所以原文法可以改写成如下形式,A ( bd | e) c | ad ,4.2.2 文法的左递归性和回溯的消除,2. 回溯的消除,在自上而下分析过程中，由于回溯，需要推翻前面的分析，包括已做的一大堆语义工作，重新去进行试探，这样大大降低了语法分析器的工作效率，因此，需要消除回溯。,4.2.2 文法的左递归性和回溯的消除,我们分析发现引起回溯的原因是: 在文法中,当某个非终结符A有多个候选式时:,遇到用A去匹配当前输入符号a时，无法确定选用唯一的一个候选式，而只能逐一进行试探，从而引起

10、回溯。具体表现在下面两种情况。,A 1 | 2 | 3 | n,4.2.2 文法的左递归性和回溯的消除,第一种情况: 文法中相同左部的规则，其右部左端第一个符号相同而引起回溯。,S aAb A de | d,例 设有文法GS：,4.2.2 文法的左递归性和回溯的消除,第二种情况: 文法中相同左部的规则，其中某一右部能推出串，例如, 文法G：,A Bx B x |,其非终结符B有两个右部，第二个右部能推导出串且两个右部左端第一个符号不相同，但在分析符号串 Wx 时出现回溯。,4.2.2 文法的左递归性和回溯的消除,试探分析过程如下图所示：,A Bx B x |,Wx,匹配失败,匹配成功,4.2.

11、2 文法的左递归性和回溯的消除,综上所述，在自上而下分析过程中，为了避免回溯， 对描述语言的文法有一定的要求:,对文法的某个非终结符A,当它有多个侯选式时:,若用A匹配输入串时,能根据当前读到的输入符号a唯一地选择一条规则去匹备输入串。或者说，能唯一地选择一条规则进行推导。,4.2.2 文法的左递归性和回溯的消除,A 1 | 2 | 3 | n,这也就是说，在自上而下分析过程中，为了避免回溯，要求描述语言的文法是LL(1)文法。,4.2.2 文法的左递归性和回溯的消除,LL(1)文法的判断条件,为了建立LL(1)文法的判断条件，需引进三个相关的集合：,FIRST集,FOLLOW集,SELECT

12、集,LL(1)文法的判断条件,设是文法G的任一符号串，定义文 法符号串的首符号集合。,LL(1)文法的判断条件,例 设有文法GS:,S Ap | Bq,A cA | a,B dB | b,FIRST(Ap) =, c, a ,AP cAp,AP ap,FIRST(Bq) =,Bq bq, b, d ,Bq dBq,LL(1)文法的判断条件,(2) 设文法G的开始符号为S，对于G的任何非终结符A，定义非终结符A的后继符号的集合,则规定 $FOLLOW(A)。,LL(1)文法的判断条件,换句话说FOLLOW(A)是G的所有句型中紧接在A之后出现的终结符或 $。,这里我们用$作为输入串的结束符，例如

13、，$ 输入串 $。,也可以用#作为输入串的结束符，例如，# 输入串 #。,LL(1)文法的判断条件,例 设有文法GA:,FOLLOW(B) =,A aB,A aB abBA abBd,A aB abBA abBaB, $, d, a ,AaB | d,BbBA | ,LL(1)文法的判断条件,(3) 定义规则的选择集合SELECT，设 A 是文法G的任一条规则，其中AVN , (VNVT)* ，定义,SELECT(A ) =,FIRST(),FIRST()FOLLOW (A),*,若 ,LL(1)文法的判断条件,例 设有文法GA:,AaB | d,BbBA | ,SELECT(AaB ) =,

14、FIRST(aB) =, a ,SELECT(Ad ) =,FIRST(d) =, d ,LL(1)文法的判断条件, b ,SELECT(BbBA ) =,FIRST(bBA) =,= $, d, a ,FOLLOW(B),SELECT(B) =,FIRST() ,AaB | d,BbBA | ,LL(1)文法的判断条件,LL(1)文法定义,一个上下文无关文法 G是LL(1)文法, 当且仅当对 G 中每个非终结符A的任何两个不同的规则 A | ，满足,SELECT(A )SELECT(A) = ,其中 、中至多只有一个能推出串。,LL(1)文法的判断条件,LL(1)中的第一个L表明自上而下的分

15、析是从左到右扫描输入串，第二个L表明分析过程中使用最左推导，1表示分析时每一步只需向前看一个符号即可决定所选用的规则，而且这种选择是准确无误的。,LL(1)文法的判断条件,例1 设有文法GS:,S aAb A de | d,SELECT(Ade)= FIRST(de)=d,SELECT(Ad)= FIRST(d)=d,SELECT(Ade)SELECT(Ad),由LL(1)文法定义可知，该文法不是LL(1)文法，因此对输入串不能进行确 定的自上而下分析。,LL(1)文法的判断条件,例2 设有文法GA,A aB | d B bBA | ,则 SELECT(AaB)=FIRST(aB)=a,SEL

16、ECT(Ad)=FIRST(d)=d,SELECT(BbBA)=FIRST(bBA)=b,SELECT(B)= FIRST() FOLLOW(B),=a, d, $,LL(1)文法的判断条件,所以 SELECT(AaB)SELECT(Ad)=,SELECT(BbBA)SELECT(B)=,由定义可知，GA是LL(1)文法，对任何输入串W可进行确定的分析。,LL(1)文法的判断条件,例3 设有文法GS:,S aAB A bB | dA | B a | e, SELECT(AbB)=FIRST(bB)= b,SELECT(AdA)=FIRST(dA)= d,SELECT(A)=FIRST()FOL

17、LOW(A),= a, e,试判断该文法是否LL(1)文法。,LL(1)文法的判断条件,SELECT(Ba)=FIRST(a)= a,SELECT(Be)=FIRST(e)= e,SELECT(AbB)SELECT(AdA)=,SELECT(AbB)SELECT(A)=,SELECT(AdA)SELECT(A)=,SELECT(Ba)SELECT(Be)=,S aAB A bB | dA | B a | e, 该文法为LL(1)文法,LL(1)文法的判断条件,例4 设有文法GS:,S AB | bC A b | B aD | C AD | D aS | c,试判断该文法是否LL(1)文法,分析

18、 对文法某个非终结符,当有多个候选式时, 求规则的SELECT集合,LL(1)文法的判断条件,SELECT(SAB)=FIRST(AB)FOLLOW(S)= a, b, , $ ,SELECT(SbC)=FIRST(bC)= b,SELECT(SAB)SELECT(S bC) ,S AB | bC A b | B aD | C AD | D aS | c,FIRST(AB)=FIRST(A)FIRST(B)=a, b, ,FOLLOW(S)=$, 该文法不为LL(1)文法,LL(1)文法的判断条件,由定义可知, 文法GS是LL(1)文法，对任何的输入串可进行确定的自上而下分析。,LL(1)文法

19、的判断条件,综合上面的讨论，我们可知对LL(1)文法，若当前非终结符A面临输入符号a时，可根据a属于哪一个SELECT集，唯一地选择一条相应规则去准确地匹配输入符号a。也就是说，当描述语言的文法是LL(1)文法时，可对其进行确定的自上而下的分析。,4.2.3 某些非LL(1)文法到LL(1)文法的改写方法,某些非LL(1)文法到LL(1)文法的改写,前面已经指出，构造确定的自上而下分析程序要求对给定语言的文法必须是LL(1)文法，但是，并不是每个语言都有LL(1)文法。,由 LL(1)文法定义可知, 若文法中含有左递归或含有公共左因子，则该文法不是 LL(1) 文法，因此，对某些非LL(1)文

20、法而言, 可通过消除左递归和反复提取公共左因子对文法进行等价变换，可能将其改造为 LL(1)文法。 消除文法左递归的方法见4.2.2。,4.2.3 某些非LL(1)文法到LL(1)文法的改写方法,提取公共左因子,当文法中含有形如,A 1 | 2 | | n 的规则,不满足LL(1)文法条件。,则其右部的FIRST集交不空，即,SELECT(A i)SELECT(A j),4.2.3 某些非LL(1)文法到LL(1)文法的改写方法,提取公共左因子将文法改写成:,A A,若在 1, 23中仍含有公共左因子，这时可再次提取, 这样反复进行提取，直到引进新非终结符的有关规则再无公共左因子为止。,A 1

21、 | 2 | | n 的规则,A 1| 2| | n,4.2.3 某些非LL(1)文法到LL(1)文法的改写方法,例1 设有文法GS:,该文法是非LL(1)文法，该文法有公共左因子，利用提取公共左因子的方法对其进行改写，我们得到,S aAb A de | d,4.2.3 某些非LL(1)文法到LL(1)文法的改写方法,不难验证改写后的文法为LL(1)文法。,因为 SELECT(A e)SELECT(A )=e, b= ,S aAb A dA A e | ,4.2.3 某些非LL(1)文法到LL(1)文法的改写方法,例2 设有文法GS:,S ad | Ae A aS | bA,将A的两条规则代入

22、非终结符S的规则中,A aS | bA,S ad | aSe | bAe,4.2.3 某些非LL(1)文法到LL(1)文法的改写方法,对S提取公共左因子得,S bAe | aS,改写后的文法是LL(1)文法。,S d | Se,A aS | bA,4.2.3 某些非LL(1)文法到LL(1)文法的改写方法,应当指出的是并非一切非LL(1)文法都能改写为LL(1)文法。,例如，对于文法,S Ae | Bd,A aAe | b,B aBd | b, 该文法不为LL(1)文法, SELECT(SAe)SELECT(SBd)= a, b a, b ,4.2.3 某些非LL(1)文法到LL(1)文法的改写方法,对S提取公共左因子后，得,对于S的两条规则, 可先将非终结符A、B用相应规则右部进行替换，我们得到,S aAee | be | aBdd | bd,A aAe | b,B aBd | b,4.2.3 某些非LL(1)文法到LL(1)文法的改写方法,显然，它仍不是一个LL(1)文法，且不难看出无论将上述步骤重复多少次, 都无法将它改写为LL(1)文法。,S aS | bS“,S Aee | Bdd,A aAe | b,S“ e | d,B aBd | b,4.2.3 某些非LL(1)文法到LL(1)文法的改写方法,