编译原理课件Chapter5.ppt

1、语法分析技术概况,不确定的 自顶向下分析法 递归下降分析法 确定的 预测分析法LL(1) 语法分析方法 简单优先分析法 优先分析法 算符优先分析法 自底向上分析法 LR(0)分析法 LR分析法 SLR(1)分析法 LR(1)分析法 LALR(1)分析法,第五章 自顶向下语法分析方法,自顶向下分析法的相关问题 LL(1)文法的定义和判别 文法等价变换 确定的自顶向下分析法（递归下降程序法和 预测分析法）,5.1 相关问题,1、什么是语法分析？ 2、什么是自顶向下分析法？ 3、在自顶向下的分析过程中，存在的问题 是什么？ 4、什么是确定的自顶向下分析法？,文法G1S: S pA 1 S qA 2

2、A cAd 3 A a 4 输入串W= pccadd。自顶向下的推导过程为: S pA pcAd pccAdd pccadd 相应的语法树为：,p,A,c,A,d,c,A,d,a,S,存在的问题,当一个非终结符号对应若干个规则时，选择哪个 规则的右部对该非终结符号进行展开呢？ 例如：如果要被代换的最左非终结符号是U，且 有n条规则：U:=A1|A2|An，那么如何确定用 哪个规则的右部去替代U？,文法G1S: S pA 1 S qA 2 A cAd 3 A a 4 输入串W= pccadd。自顶向下的推导过程为: S pA pcAd pccAdd pccadd 相应的语法树为：,p,A,c,A

3、,d,c,A,d,a,S,First集的定义,设G=(VT，VN，S，P)是上下文无关文法,其 中(VT VN )* First()= aVT | a. (if then ) 可以根据当前的输入符号是属于哪个产生 式右部的首符集而决定选择相应产生式进 行推导。,*,*,文法G3S: S aA 1 S d 2 A bAS 3 A 4 输入串W=abd。自顶向下的推导过程为: S aA abAS abS abd 相应的语法树为：,S,a,A,b,A,S,d,Follow集的定义,设G=(VT，VN，S，P)是上下文无关文法， AVN，S是开始符号 Follow(A)= aVT | S.Aa. (i

4、f S.A then # ) 当文法中存在推导形如：A 时，如果 当前的字符属于Follow(A)，则用空字符 串取代A的出现。,*,+,+,Select集的定义,Select(A) = First() ， 当First() =(First()-) Follow(A), 当First() 结论:文法G是LL(1)文法的充要条件是,对 于每个非终结符U有多个不同的产生式，比 如为U和U，满足: Select(U) Select(U)=,5.2 LL(1)文法的判别,判别算法： 1、计算非终结符是否能推出 2、构造First集 3、构造Follow集 4、构造Select集并作判别,文法GE： E

5、 T E1 E + T E2 | 3 T F T4 T * F T5 | 6 F i7 | ( E )8,N,Y,Y,N,N,计算First(X)集,对每一文法符号X计算First(X) 若XVT,First(X)=X 若XVN ,且有产生式XaP,aVT ,则aFirst(X) 若XVN,且有产生式X,则 First(X) 若XVN,有产生式XY1Y2Yn，且Y1,Y2,Yi任意一 个文法符号，当Y1,Y2,Yi-1，则 First(Y1)-,First(Y2)-, First(Yi-1)-, First(Yi)都包含在First(X)中。 当Yi (i=1,2,n), 将并入First(X

6、)中。 反复使用上述步骤，直到每个符号的First不再增大。,*,*,文法GE： E T E1 E + T E2 | 3 T F T4 T * F T5 | 6 F i7 | ( E )8,First(E),First(T),First(E),First(T),First(F),*,+,i,(,计算First()集,若符号串=X1X2Xn，Xi为任意一文法符号 当X1,X2,Xi-1，Xi不能，则 First()=(First(Xj)-) First(Xi) 若所有Xi都能，则 First()= First(Xj),j=1,i,i-1,j=1,*,*,*,文法GE： E T E1 E + T

7、E2 | 3 T F T4 T * F T5 | 6 F i7 | ( E )8 First(TE)= First(+TE)= First()= First(FT)= First(*FT)= First(i)= First(E)=,First(T)=( ,i , + , ,First(F) = ( ,i , * , i , ( ,计算Follow(X)集,1:对所有XVN，令Follow(X)=；对开始符S, 令Follow(S)= # ； 2:若有产生式YX， 如果First() 则： Follow(X)= First() 否则 Follow(X)=(First() Follow(Y) 3:

8、重复2和3，直至对所有XVN，Follow(X)收 敛为止。,文法GE： E T E1 E + T E2 | 3 T F T4 T * F T5 | 6 F i7 | ( E )8,Follow(E),Follow(T),Follow(E),Follow(T),Follow(F),#,First(E),),+,First(T),*,计算Select集,Select(A) = First() ，当First()不含 = (First()-) Follow(A) ， 当First()含,文法GE： E T E1 E + T E2 | 3 T F T4 T * F T5 | 6 F i7 | ( E

9、 )8,Select( ETE ) = first(TE) = i , ( Select( E +TE ) = first(+TE) = + Select( E )=(first()-)follow(E) = ),# Select( T FT ) = first(FT) = i , ( Select( T *FT ) = first(*FT) = * Select( T )=(first()-)follow(T) = +,),# Select( F i ) = first(i) = i Select( F (E) ) = first(E) = ( ,文法GE： E T E1 E + T E2

10、| 3 T F T4 T * F T5 | 6 F i7 | ( E )8 Select( E +TE ) Select( E ) = Select( T *FT ) Select( T ) = Select( F i ) Select( F (E)= 结论：如果相同左部产生式的Select交集都是空集， 则该文法是LL(1)文法。因此，该文法是LL(1)文法。,5.3 文法等价变换,LL(1)文法不含左公共因子 某个非终极符A有如下的两个产生式： A ，A (即有左公共因子) LL(1)文法不含左递归 某个非终极符A有直接左递归产生式： A A | .,消除左公共因子,变换步骤： 1:产生式

11、形如：A1|2|n| 表示不以开头的字符串。 2:提取左公共因子： A(1|2|n)| 3:引进非终极符A，使产生式替换为： A A | A 1|2 | n,消除左公共因子的例子1 Stm id := Exp Stm id (ExpL) ExpL Exp ExpL Exp,ExpL Exp id,Stm id Stm Stm := Exp Stm ( ExpL ) ExpL Exp ExpL ExpL , ExpL ExpL Exp id,消除左公共因子的例子2,A ad1 A Bc2 B aA3 B bB4,A ad A aAc A bBc B aA B bB,Aa(d|Ac) A bBc

12、B aA B bB,消除左递归,一个文法含有下列形式的产生式时 （1）AA AVN, V* （2）AB BA A,BVN, , V* 其中（1）为直接左递归，（2）为间接左递归，因此文法中只要有AA，则称文法为左递归的。,+,对直接左递归形如： A A1|A2|Am|1|2|n 消除直接左递归,引入新的非终结符A： A 1A|2A|nA A 1A|2A|mA| 例 GS:S Sa S b,改写后的文法为: GS: S bS S aS | ,消除间接左递归：在没有形如A-A的有害规则和 没有空规则的条件下，算法如下： 1: 将所有非终结符排列为A1,A2, ,An; 2: for (i=1; i

13、=n; i+) for （j=1； j=i-1; j+） 将规则AiAjy改写； / 若Ajx1|x2|xk， / 则Aix1y|x2y|xky 消除规则Ai中的直接左递归 3: 化简文法（消除无用规则）。,例：1 A B 1 | a 2 B C 2 | b 3 C A 3 | c,A B1 C21 A321,2:i j 1 没有直接左递归，无须改写,1:非终结符排序：A,B,C,3:消除无用规则。新文法中的产生式是1245,消除3中的直接左递归，引入新非终结符C： 4 Cb13C|a3C|cC(C(b13|a3|c)C) 5 C213C|,2 把2代入3得： 3 CC213|b13|a3|c

14、,3 1 把1代入3得：3 CB13 |a3|c,2 1 无须替换，没有直接左递归，无需改写,5.4 预测分析法(LL(1)分析法),LL(1)是LL(k)的特例,其中，第一个L表示从左到右扫描输入串, k表示向前看k个符号，第二个L表示分析的过程是最左推导。 LL(1)方法和递归下降法属于同一级别的自顶向下分析法，但有一些区别. 递归下降法对每个非终极符产生子程序，而LL(1)方法则产生LL分析表； 递归下降法能判断每个产生式的结束，而LL(1)方法则不能； 递归下降法分析法不用符号栈，而LL(1)方法则用符号栈。,构造预测分析表,T：VN(VT # ) P Error T(A,t)= A

15、若tSelect( A ) T(A,t)= Error 否则 其中P表示所有产生式的集合,1初始化： Stack :=empty；Push(#S)； 2读下一个输入符： Read(a)； 3若当前格局是( #, # )，则成功结束； 否则转下； 4设当前格局为（. X, a.)，则 若 XVT P(X2);P(Xn); 1. 如果XiVN，P(Xi)就是Xi的子程序 2. 如果XiVT，P(Xi) Match(Xi) Match(Xi) if (SYM!=Xi) ERROR() ; GetSym();,假设有文法 S a B a B b B | c 则相应的递归子程序可如下：,B( ) if(SYM =b) getSym(); B(); else if (SYM = c) getSym(); else ERROR(); ,S( ) if(SYM =a) getSym()； B()； if(SYM=a) getSym(); else ERROR(); else ER