自顶向下（向上）的语法分析对比.ppt

语法分析技术概况,不确定的 自顶向下分析法 递归下降分析法 确定的 预测分析法LL(1) 语法分析方法 简单优先分析法 优先分析法 算符优先分析法 自底向上分析法 LR(0)分析法 LR分析法 SLR(1)分析法 LR(1)分析法 LALR(1)分析法,第五章 自顶向下语法分析方法,5.1 自顶向下分析法的相关问题 5.2 LL(1)文法的定义和判别 5.3 文法等价变换 5.4 确定的自顶向下分析法 （递归下降程序法和预测分析法）,5.1 相关问题,1、什么是语法分析？ 2、什么是自顶向下分析法？ 3、在自顶向下的分析过程中，存在的问题 是什么？ 4、什么是确定的自顶向下分析法？,文法G1S: S pA 1 S qB 2 A cAd 3 A a 4 输入串W= pccadd。自顶向下的推导过程为: S pA pcAd pccAdd pccadd 相应的语法树为：,p,A,c,A,d,c,A,d,a,S,5.1 相关问题,文法G1S: S pA 1 S qB 2 A cAd 3 A a 4 自顶向下的语法分析过程【Sf,Rest,Action(D/M/S/E)】 S # pccadd # Derivation pA # pccadd # Match A # ccadd # Derivation cAd # ccadd # Match Ad # cadd # Derivation cAdd # cadd # Match Add # add # Derivation add # add # Match dd # dd # Match d # d # Match # # Success,5.1 相关问题,问：,当一个非终结符号对应若干个规则时，选择哪个 规则的右部对该非终结符号进行展开呢？ 例如：如果要被代换的最左非终结符号是U，且 有n条规则：U:=A1|A2|An，那么如何确定用 哪个规则的右部去替代U？,5.1 相关问题,确定的自顶向下分析法： 对每一个非终结符，都能够确定地选择规则来展开它。LL(1)文法,文法G2S: S Ap 1 S Bq 2 A a 3 A cA 4 B b 5 B dB 6 输入串W=ccap。自顶向下的推导过程为: S Ap cAp ccAp ccap 相应的语法树为：,S,A,p,c,A,c,A,a,5.1 相关问题,First集的定义,设G=(VT，VN，S，P)是上下文无关文法, 其中：(VT VN )*，则： First()= aVT | a.(if then ) 可以根据当前的输入符号是属于哪个产生式右部的首符集而决定选择相应产生式进行推导。,*,*,5.2 LL(1)文法的定义和判别,文法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. (if SA then # ) 当文法中存在推导形如：A 时，如果 当前的字符属于Follow(A)，则用空字符 串取代A的出现。,*,+,+,5.2 LL(1)文法的定义和判别,Select集的定义,Select(A) = First() ， 当First() = First() Follow(A), 当First() 定义：文法G是LL(1)文法的充要条件是,对 于U的任意两个不同的规则有: Select(U) Select(U)=,5.2 LL(1)文法的定义和判别,LL(1)文法的判别,判别算法： 1、计算能推出的非终结符 2、构造First集 3、构造Follow集 4、构造Select集并作判别,5.2 LL(1)文法的定义和判别,文法GE：E T E E + T E | T F T T * F T | F i | ( E ),N,Y,Y,N,N,计算First(X)集,对每一文法符号X计算First(X) 若XVT,First(X)=X 若XVN则 First(X)= a | XaP,a VT 若XVN,且有产生式X,则 First(X) 若XVN,有产生式XY1Y2Yn，且Y1,Y2,Yi VN 当Y1,Y2,Yi-1，则 First(Y1)-,First(Y2)-, First(Yi-1)-, First(Yi)都包含在First(X)中。 当Yi (i=1,2,n), 将并入First(X)中。,*,*,文法GE：E T E E + T E | T F T T * F T | F i | ( E ),First(E),First(T),First(E),First(T),First(F),*,+,i,(,计算First()集,若符号串=X1X2Xn， 当X1,X2,Xi-1，Xi不能，则 First()=(First(Xj)-) First(Xi) 若所有Xi都能，则 First()= First(Xj),i=1,j,j-1,i=1,*,*,*,计算Follow(X)集,1:对所有XVN，令Follow(X):=；对开始符S, 令Follow(S)= # ； 2:若有产生式AxBy， 如果First(y) 则： Follow(B)= First(y) 否则 Follow(B)=(First(y) Follow(A) 3:重复2和3，直至对所有XVN，Follow(X)收 敛为止。,文法GE：E T E E + T E | T F T T * F T | F i | ( E ),Follow(E),Follow(T),Follow(E),Follow(T),Follow(F),#,First(E),),+,First(T),*,计算Select集,Select(A) = First() ，当First()不含 = First()- Follow(A) ， 当First()含 结论：如果相同左部产生式的Select交集都 是空集，则该文法是LL(1)文法。,文法GE：E T E E + T E | T F T T * F T | F i | ( E ) Select( ETE ) = first(TE) = i , ( Select( E +TE ) = first(+TE) = + Select( E ) = follow(E) = ) , # Select( T FT ) = first(FT) = i , ( Select( T *FT ) = first(*FT) = * Select( T ) = follow(T) = + , ) , # Select( F i ) = first(i) = i Select( F (E) ) = first(E) = ( ,文法GE：E T E E + T E | T F T T * F T | F i | ( E ) Select( E +TE ) Select( E ) = Select( T *FT ) Select( T ) = Select( F i ) Select( F (E)= 因此，该文法是LL(1)文法。,5.3 文法等价变换,LL(1)文法不含公共左因子 某个非终极符A有如下的两个产生式： A ，A (即有左公共前缀) LL(1)文法不含左递归 某个非终极符A有直接左递归产生式： A A | ,消除左公共因子,变换步骤： 1:产生式形如：A1|2|n| 表示不以开头的字符串。 2:引进非终极符A，使产生式替换为： A A | A 1|2 | n,Stm id := Exp Stm id (ExpL) ExpL Exp ExpL Exp,ExpL,Stm id Stm Stm := Exp Stm ( ExpL ) ExpL Exp ExpL ExpL , Exp ExpL ExpL ,消除左公共因子的例子1,消除左公共因子(简接)的例子2,A ad A Bc B aA B bB,A ad A aAc A bBc B aA B bB,Aa(d|Ac) A bBc B aA B bB,消除左递归,一个文法含有下列形式的产生式时 （1）AA AVN, V* （2）AB BA A,BVN, , V* 其中（1）为直接左递归，（2）为间接左递归，因此文法中只要有AA，则称文法为左递归的。,+,对直接左递归形如： A A | 消除直接左递归为： A A A A | ,消除间接左递归：在没有形如A=A的推导和没有 空规则的条件下，算法如下： 1: 将所有非终结符排列为A1,A2, ,An; 2: for (i=1; i=n; i+) for （j=1； j=i-1; j+） 将规则AiAjy改写； / 若Ajx1|x2|xk， / 则Aix1y|x2y|xky 消除规则中的直接左递归; 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 C(b13|a3|c)C 5 C213C|,2 把2代入3得： 3 CC213|b13|a3|c,3 1 把1代入3得：3 C(B1|a)3|c,2 1 无须替换，没有直接左递归，无需改写,5.4 自顶向下分析递归下降法,递归下降法(Recursive-Descent Parsing) 对每个非终结符按其产生式右部设计相应的 语法分析子程序。 终结符产生匹配命令 match() 非终结符则产生调用命令 文法递归则相应的子程序也递归， 所以称为递归子程序方法或递归下降法。,对应每个非终结符，编一个独立的子程序。 对应每个非终结符语法分析从读入第一个单词开始，沿语法描述图箭头所指出的方向进行分析： 当遇到非终结符时，则调用相应的子程序。 当遇到描述图中是终结符时，则判断当前读入的单词是否与图中的终结符相匹配，若匹配，再读取下一个单词继续分析。 遇到分支点时，将当前的单词与分支点上多个终结符逐个相比较，若都不匹配时可能是进入下一个非终结符语法单位或是出错。,（） 选择形式 根据规则Ux1|x2|xn，有: P(U)P(x1|x2|xn) switch (SYM) case SELECT(Ux1): P(x1); break; case SELECT(Ux2): P(x2); break; case SELECT(Uxn): P(xn); break; default: ERROR();,()序列形式。根据y=y1y2ym，有: P(y)P(y1y2ym) P(y1); P(y2); ; P(ym); ()若每个终结符yi，有 P(yi)match(yi) CHECK(yi); GetSym(); 而CHECK(yi)if (SYM!=yi) ERROR(); ()对每个非终结符U，P(U)是调用语句U(),例5 构造文法GE的递归子程序 GE:EeBaA P(E) match(e); Aa|bAcB B(); BdEd|aC match(a); Ce|dC A(); ,P(A)if (SYM=a) P(a); else if (SYM=b) P(bAcB); else ERROR(); if (SYM=b) P(bAcB); else match(a); if (SYM=b) /*match(b)*/ GetSym() ;A(); match(c); B(); else match(a);,P(B)switch (SYM) case d: GetSym(); E(); match(d); break; case a: GetSym(); C(); break; default: ERROR(); P(C)if (SYM=d) GetSym(); C(); else match(e);,(5)重复形式。 P(E)while (SYM IN FIRST(E) P(E); P(EE)do P(E); while(SYM IN FIRST(E); (6)取舍形式。 P(E)if (SYM IN FIRST(E) P(E);,例6 PL0语言的表达式的语法分析程序 E+|-T(+|-)T TF(*|/)F Fi|d|(E),P(E)P(+|-T(+|-)T) if (SYM