自顶向下语法分析.pptx

第五章第五章 自顶向下语法分析方法自顶向下语法分析方法5.1 5.1 自顶向下分析法的相关问题自顶向下分析法的相关问题自顶向下分析法的相关问题自顶向下分析法的相关问题5.2 LL(1)5.2 LL(1)文法的定义和判别文法的定义和判别文法的定义和判别文法的定义和判别5.3 5.3 文法等价变换文法等价变换文法等价变换文法等价变换5.4 5.4 确定的自顶向下分析法确定的自顶向下分析法确定的自顶向下分析法确定的自顶向下分析法 （递归下降程序法递归下降程序法递归下降程序法递归下降程序法和和和和预测分析法预测分析法预测分析法预测分析法）第1页/共38页5.1 5.1 5.1 5.1 相关问题相关问题相关问题相关问题1 1 1 1、什么是语法分析？、什么是语法分析？、什么是语法分析？、什么是语法分析？2 2 2 2、什么是自顶向下分析法？、什么是自顶向下分析法？、什么是自顶向下分析法？、什么是自顶向下分析法？3 3 3 3、在自顶向下的分析过程中，存在的问题、在自顶向下的分析过程中，存在的问题、在自顶向下的分析过程中，存在的问题、在自顶向下的分析过程中，存在的问题 是什么？是什么？是什么？是什么？4 4 4 4、什么是确定的自顶向下分析法？、什么是确定的自顶向下分析法？、什么是确定的自顶向下分析法？、什么是确定的自顶向下分析法？第2页/共38页文法文法G1S:S G1S:S pA 1 S pA 1 S qB 2 qB 2 A A cAd 3 A cAd 3 A a 4 a 4输入串输入串W=W=pccaddpccadd。自顶向下的推导过程为。自顶向下的推导过程为:S S pA pA pcAd pcAd pccAdd pccAdd pccadd pccadd相应的语法树为：相应的语法树为：pAcAdcAdaS5.1 5.1 相关问题相关问题第3页/共38页文法文法G1S:S G1S:S pA 1 S pA 1 S qB 2 qB 2 A A cAd 3 A cAd 3 A a 4 a 4自顶向下的语法分析过程自顶向下的语法分析过程【Sf,Rest,Action(D/M/S/E)Sf,Rest,Action(D/M/S/E)】S#pccadd#S#pccadd#DerivationDerivation pA#pccadd#Match pA#pccadd#Match A#ccadd#A#ccadd#DerivationDerivation cAd#ccadd#Match cAd#ccadd#Match Ad#cadd#Ad#cadd#DerivationDerivation cAdd#cadd#Match cAdd#cadd#Match Add#add#Add#add#DerivationDerivation add#add#Match add#add#Match dd#dd#Match dd#dd#Match d#d#Match d#d#Match#Success#Success5.1 5.1 相关问题相关问题第4页/共38页问：问：问：问：当一个非终结符号对应若干个规则时，选择哪个规则的右部对该非终结符号进行展开呢？例如：如果要被代换的最左非终结符号是U，且有n条规则：U:=:=A1|A2|An，那么如何确定用哪个规则的右部去替代U？5.1 5.1 相关问题相关问题确定的自顶向下分析法：确定的自顶向下分析法：对每一个非终结符，都能够确定地选择规则来展开它。对每一个非终结符，都能够确定地选择规则来展开它。LL(1)LL(1)文法文法第5页/共38页文法文法G2S:S G2S:S Ap 1 S Ap 1 S Bq 2 Bq 2 A A a 3 A a 3 A cA 4 cA 4 B B b 5 B b 5 B dB 6 dB 6 输入串输入串W=W=ccapccap。自顶向下的推导过程为。自顶向下的推导过程为:S S Ap Ap cAp cAp ccAp ccAp ccap ccap 相应的语法树为：相应的语法树为：SApcAcAa5.1 5.1 相关问题相关问题第6页/共38页First集的定义集的定义设设设设G=(VG=(VT T，V VN N，S S，P)P)是上下文无关文法是上下文无关文法是上下文无关文法是上下文无关文法,其中：其中：其中：其中：(V VT T V VN N)*)*，则：，则：，则：，则：First(First()=a)=a V VT T|a.a.(if (if then then )可以根据当前的输入符号是属于哪个产生式右部的首符集而决定选择相应产生式进行推导。可以根据当前的输入符号是属于哪个产生式右部的首符集而决定选择相应产生式进行推导。可以根据当前的输入符号是属于哪个产生式右部的首符集而决定选择相应产生式进行推导。可以根据当前的输入符号是属于哪个产生式右部的首符集而决定选择相应产生式进行推导。*5.2 LL(1)文法的定义和判别第7页/共38页文法文法G3S:S G3S:S aA 1 S aA 1 S d 2 d 2 A A bAS 3 A bAS 3 A 4 4 输入串输入串W=W=abdabd。自顶向下的推导过程为。自顶向下的推导过程为:S S aA aA abAS abAS abS abS abd abd相应的语法树为：相应的语法树为：SaAbASd第8页/共38页Follow集的定义集的定义设设设设G=(VG=(VT T，V VN N，S S，P)P)是上下文无关文法，是上下文无关文法，是上下文无关文法，是上下文无关文法，A A V VN N，S S是开始符号是开始符号是开始符号是开始符号 Follow(A)Follow(A)=a=a V VT T|S|S.Aa.Aa.(if S(if S.A then#).A then#)当文法中存在当文法中存在当文法中存在当文法中存在推导推导推导推导形如：形如：形如：形如：A A 时，如果时，如果时，如果时，如果当前的字符属于当前的字符属于当前的字符属于当前的字符属于Follow(A)Follow(A)，则用空字符，则用空字符，则用空字符，则用空字符串取代串取代串取代串取代A A的出现。的出现。的出现。的出现。*+5.2 LL(1)5.2 LL(1)文法的定义和判别文法的定义和判别第9页/共38页SelectSelect集的定义集的定义集的定义集的定义 Select(ASelect(A )=First(=First()，当当当当 First(First()=First(=First()Follow(A),Follow(A),当当当当 First(First()定义：定义：定义：定义：文法文法文法文法GG是是是是LL(1)LL(1)文法的充要条件是文法的充要条件是文法的充要条件是文法的充要条件是,对对对对于于于于U U的任意两个不同的规则有的任意两个不同的规则有的任意两个不同的规则有的任意两个不同的规则有:Select(USelect(U)Select(U)Select(U )=)=5.2 LL(1)5.2 LL(1)文法的定义和判别文法的定义和判别第10页/共38页LL(1)LL(1)文法的判别文法的判别文法的判别文法的判别判别算法：判别算法：判别算法：判别算法：1 1、计算能推出、计算能推出、计算能推出、计算能推出 的非终结符的非终结符2 2、构造、构造、构造、构造FirstFirst集集集集3 3、构造、构造、构造、构造FollowFollow集集集集4 4、构造、构造、构造、构造SelectSelect集并作判别集并作判别集并作判别集并作判别5.2 LL(1)5.2 LL(1)文法的定义和判别文法的定义和判别第11页/共38页文法GE：E E T E T E E E +T E+T E|T T F T F T T T *F T*F T|F F i|(E)i|(E)EETTFNYYNN第12页/共38页计算计算First(X)First(X)集集对每一文法符号对每一文法符号X X计算计算First(X)First(X)若若X X V VT T,First(X)=XFirst(X)=X若若X X V VN N则则 First(X)=a|XFirst(X)=a|Xa a P,a P,a V VT T 若若X X V VN N,且有产生式且有产生式X X,则则 First(X)First(X)若若X X V VN N,有产生式有产生式X XY Y1 1Y Y2 2Y Yn n，且，且Y Y1 1,Y,Y2 2,Y,Yi i V VN N 当当Y Y1 1,Y,Y2 2,Y,Yi-1i-1，则，则 First(YFirst(Y1 1)-)-,First(Y,First(Y2 2)-)-,First(Y First(Yi-1i-1)-)-,First(Y,First(Yi i)都包含在都包含在First(X)First(X)中。中。当当Y Yi i(i=1,2,(i=1,2,n),n),将将 并入并入First(X)First(X)中。中。*第13页/共38页文法GE：E E T E T E E E +T E+T E|T T F T F T T T *F T*F T|F F i|(E)i|(E)First(E)First(T)First(E)First(T)First(F)*+i(第14页/共38页计算计算First(First()集集若符号串若符号串=X=X1 1X X2 2X Xn n，当当X X1 1,X,X2 2,X Xi-1i-1，X Xi i不能不能，则，则 First(First()=)=(First(X(First(Xj j)-)-)First(X First(Xi i)若所有若所有X Xi i都能都能，则，则 First(First()=)=First(X First(Xj j)i=1jj-1i=1*第15页/共38页计算计算Follow(X)Follow(X)集集1:1:对所有对所有X X V VN N，令，令Follow(X):=Follow(X):=；对开始符；对开始符S,S,令令Follow(S)=#Follow(S)=#；2:2:若有产生式若有产生式AxByAxBy，如果如果First(y)First(y)则：则：Follow(B)=First(y)Follow(B)=First(y)否则否则 Follow(B)=(First(y)Follow(B)=(First(y)Follow(A)Follow(A)3:3:重复重复2 2和和3 3，直至对所有，直至对所有X X V VN N，Follow(X)Follow(X)收收 敛为止。敛为止。第16页/共38页文法GE：E E T E T E E E +T E+T E|T T F T F T T T *F T*F T|F F i|(E)i|(E)Follow(E)Follow(T)Follow(E)Follow(T)Follow(F)#First(E)+First(T)*第17页/共38页计算计算SelectSelect集集Select(ASelect(A)=First(=First()，当，当First(First()不含不含 =First(=First()-)-Follow(A)Follow(A)，当当First(First()含含结论：结论：如果相同左部产生式的如果相同左部产生式的SelectSelect交集都交集都是空集，则该文法是是空集，则该文法是LL(1)LL(1)文法。文法。第18页/共38页文法GE：E E T E T E E E +T E+T E|T T F T F T T T *F T*F T|F F i|(E)i|(E)Select(ESelect(ETETE)=)=first(TEfirst(TE)=i,(i,(SelectSelect(E(E +TE+TE)=)=first(+TEfirst(+TE)=+SelectSelect(E(E )=)=follow(Efollow(E)=),#),#SelectSelect(T(T FT FT)=)=first(FTfirst(FT)=i,(i,(SelectSelect(T(T *FT*FT)=)=first(*FTfirst(*FT)=*SelectSelect(T(T )=)=follow(Tfollow(T)=+,),+,),#SelectSelect(F(F i)=i)=first(i)first(i)=i i SelectSelect(F(F(E)=(E)=first(E)first(E)=(第19页/共38页文法GE：E E T E T E E E +T E+T E|T T F T F T T T *F T*F T|F F i|(E)i|(E)SelectSelect(E(E +TE+TE)SelectSelect(E(E )=)=SelectSelect(T(T *FT*FT)SelectSelect(T(T )=)=SelectSelect(F(F i)i)SelectSelect(F(F(E)=(E)=因此，该文法是因此，该文法是LL(1)LL(1)文法。文法。第20页/共38页5.3 5.3 5.3 5.3 文法等价变换文法等价变换文法等价变换文法等价变换 LL(1)LL(1)LL(1)LL(1)文法不含公共左因子文法不含公共左因子文法不含公共左因子文法不含公共左因子 某个非终极符某个非终极符某个非终极符某个非终极符A A A A有如下的两个产生式：有如下的两个产生式：有如下的两个产生式：有如下的两个产生式：A A A A ，A A A A (即有左公共前缀即有左公共前缀即有左公共前缀即有左公共前缀)LL(1)LL(1)LL(1)LL(1)文法不含左递归文法不含左递归文法不含左递归文法不含左递归 某个非终极符某个非终极符某个非终极符某个非终极符A A A A有直接左递归产生式：有直接左递归产生式：有直接左递归产生式：有直接左递归产生式：A A A A A A A A|.|.|.|.第21页/共38页消除左公共因子消除左公共因子消除左公共因子消除左公共因子变换步骤：变换步骤：变换步骤：变换步骤：1:1:1:1:产生式形如：产生式形如：产生式形如：产生式形如：A A A A1 1 1 1|2 2 2 2|n n n n|表示不以表示不以表示不以表示不以 开头的字符串。开头的字符串。开头的字符串。开头的字符串。2:2:2:2:引进非终极符引进非终极符引进非终极符引进非终极符A A A A，使产生式替换为：，使产生式替换为：，使产生式替换为：，使产生式替换为：A A A A A A A A|A A A A 1 1 1 1|2 2 2 2|n n n n第22页/共38页Stm Stm id id:=Exp:=ExpStm Stm idid(ExpL)(ExpL)ExpL Exp ExpL Exp ExpL Exp,ExpLExpL Exp,ExpLStm Stm idid Stm Stm StmStm :=:=Exp ExpStmStm (ExpL)(ExpL)ExpL Exp ExpLExpL Exp ExpL ExpLExpL ,Exp ExpL,Exp ExpL ExpLExpL 消除左公共因子的例子消除左公共因子的例子1 1第23页/共38页消除左公共因子消除左公共因子(简接简接)的例子的例子2nA adnA BcnB aAnB bBnA adnA aAcnA bBcnB aAnB bBnAa(d|Ac)nA bBcnB aAnB bBnA aAnA dnA Ac A bBc B aA B bB替换提因子引进A第24页/共38页消除左递归消除左递归一个文法含有下列形式的产生式时一个文法含有下列形式的产生式时（1 1）A AA A A A V VN N,V V*（2 2）A AB B B BA A A,B A,B V VN N,V V*其中（其中（1 1）为）为直接左递归直接左递归，（，（2 2）为）为间接左递归间接左递归，因此文法中只要有，因此文法中只要有A AA A，则称文法为左递归的。，则称文法为左递归的。+第25页/共38页对直接左递归形如：对直接左递归形如：A A A A|消除直接左递归为：消除直接左递归为：A A A A A A A A|第26页/共38页消除间接左递归：消除间接左递归：在没有形如在没有形如A=AA=A的推导和没的推导和没有有空规则的条件下，算法如下：空规则的条件下，算法如下：1:1:将所有非终结符排列为将所有非终结符排列为A A1 1,A,A2 2,A,An n;2:for(i=1;i=n;i+)2:for(i=1;i=n;i+)for for（j=1j=1；j=i-1;j+j=i-1;j+）将规则将规则A Ai iAAj jy y改写；改写；/若若A Aj jxx1 1|x|x2 2|x|xk k，/则则A Ai ixx1 1y|xy|x2 2y|y|x|xk ky y 消除规则中的直接左递归消除规则中的直接左递归;3:3:化简文法（消除无用规则）。化简文法（消除无用规则）。第27页/共38页例：例：例：例：1 A B 1 A B 1 1|a|a 2 B C 2 B C 2 2|b|b 3 C A 3 C A 3 3|c|cA A B B 1 1 C C 2 2 1 1 A A 3 3 2 2 1 1 2:2:i ji j 1 1 没有直接左递归，无须改写没有直接左递归，无须改写1:1:非终结符排序：非终结符排序：A,B,CA,B,C 3:消除无用规则。新文法中的产生式是1245 消除消除33 中的直接左递归，引入新非终结符中的直接左递归，引入新非终结符C C：4 C(b4 C(b 1 1 3 3|a|a 3 3|c)C|c)C 5 C 5 C 2 2 1 1 3 3C C|2 把2代入3得：3 CC213|b13|a3|c 3 13 1 把把11代入代入33得：得：33 C(B C(B 1 1|a)|a)3 3|c|c 2 12 1 无须替换，没有直接左递归，无需改写无须替换，没有直接左递归，无需改写第28页/共38页5.4 5.4 5.4 5.4 自顶向下分析自顶向下分析自顶向下分析自顶向下分析递归下降法递归下降法递归下降法递归下降法递归下降法递归下降法递归下降法递归下降法(Recursive-Descent Parsing)(Recursive-Descent Parsing)(Recursive-Descent Parsing)(Recursive-Descent Parsing)对每个非终结符按其产生式右部设计相应的对每个非终结符按其产生式右部设计相应的对每个非终结符按其产生式右部设计相应的对每个非终结符按其产生式右部设计相应的语法分析子程序。语法分析子程序。语法分析子程序。语法分析子程序。终结符终结符终结符终结符产生匹配命令产生匹配命令产生匹配命令产生匹配命令 match(match(match(match()非终结符非终结符非终结符非终结符则产生调用命令则产生调用命令则产生调用命令则产生调用命令文法递归则相应的子程序也递归，文法递归则相应的子程序也递归，文法递归则相应的子程序也递归，文法递归则相应的子程序也递归，所以称为所以称为所以称为所以称为递归子程序方法递归子程序方法递归子程序方法递归子程序方法或或或或递归下降法递归下降法递归下降法递归下降法。第29页/共38页对应对应对应对应每个非终结符每个非终结符每个非终结符每个非终结符，编一个独立的子程序。，编一个独立的子程序。，编一个独立的子程序。，编一个独立的子程序。对应每个非终结符语法分析从读入第一个单词开始，沿语法描述图对应每个非终结符语法分析从读入第一个单词开始，沿语法描述图对应每个非终结符语法分析从读入第一个单词开始，沿语法描述图对应每个非终结符语法分析从读入第一个单词开始，沿语法描述图箭头箭头箭头箭头所指出的方向进行所指出的方向进行所指出的方向进行所指出的方向进行分析：分析：分析：分析：当遇到非终结符时，则当遇到非终结符时，则当遇到非终结符时，则当遇到非终结符时，则调用调用调用调用相应的相应的相应的相应的子程序子程序子程序子程序。当遇到描述图中是当遇到描述图中是当遇到描述图中是当遇到描述图中是终结符终结符终结符终结符时，则判断当前读入的单词是否与图中的终结符时，则判断当前读入的单词是否与图中的终结符时，则判断当前读入的单词是否与图中的终结符时，则判断当前读入的单词是否与图中的终结符相匹配相匹配相匹配相匹配，若匹，若匹，若匹，若匹配，再读取下一个单词继续分析。配，再读取下一个单词继续分析。配，再读取下一个单词继续分析。配，再读取下一个单词继续分析。遇到遇到遇到遇到分支点分支点分支点分支点时，将当前的单词与分支点上多个终结符时，将当前的单词与分支点上多个终结符时，将当前的单词与分支点上多个终结符时，将当前的单词与分支点上多个终结符逐个相比较逐个相比较逐个相比较逐个相比较，若都不匹配时可能是，若都不匹配时可能是，若都不匹配时可能是，若都不匹配时可能是进入下一个非终结符语法单位或是出错。进入下一个非终结符语法单位或是出错。进入下一个非终结符语法单位或是出错。进入下一个非终结符语法单位或是出错。第30页/共38页（）（）选择形式选择形式选择形式选择形式根据规则根据规则U Ux x1 1|x|x2 2|x|xn n，有，有:P(U)P(U)P(xP(x1 1|x|x2 2|x|xn n)switch(SYM)switch(SYM)case SELECT(Ucase SELECT(Ux x1 1):P(x):P(x1 1);break;);break;case SELECT(Ucase SELECT(Ux x2 2):P(x):P(x2 2);break;);break;case SELECT(Ucase SELECT(Ux xn n):P(x):P(xn n);break;);break;default:ERROR();default:ERROR();第31页/共38页()序列形式序列形式。根据。根据y=yy=y1 1y y2 2yymm，有，有:P(y)P(y P(y)P(y1 1y y2 2yymm)P(y P(y1 1);P(y);P(y2 2);P(y);P(ymm););()若每个若每个终结符终结符y yi i，有，有 P(yP(yi i)match(y)match(yi i)CHECK(y CHECK(yi i);GetSym(););GetSym();而而CHECK(yCHECK(yi i)if(SYM!=y)if(SYM!=yi i)ERROR();)ERROR();()对每个对每个非终结符非终结符U U，P(U)P(U)是调用语句是调用语句U()U()第32页/共38页例例5 5构造文法构造文法GEGE的递归子程序的递归子程序GE:EGE:EeBaA P(E)eBaA P(E)match(e);match(e);A Aa|bAcB B();a|bAcB B();B BdEd|aC match(a);dEd|aC match(a);C Ce|dC A();e|dC A();P(A)if(SYM=a)P(a);P(A)if(SYM=a)P(a);else if(SYM=b)P(bAcB);else if(SYM=b)P(bAcB);else ERROR();else ERROR();if(SYM=b)P(bAcB);if(SYM=b)P(bAcB);else match(a);else match(a);if(SYM=b)/*match(b)*/if(SYM=b)/*match(b)*/GetSym();A();match(c);B();GetSym();A();match(c);B();else match(a);else match(a);第33页/共38页P(B)switch(SYM)P(B)switch(SYM)case d:case d:GetSym();E();match(d);break;GetSym();E();match(d);break;case a:case a:GetSym();C();break;GetSym();C();break;default:ERROR();default:ERROR();P(C)if(SYM=d)GetSym();C();P(C)if(SYM=d)GetSym();C();else match(e);else match(e);第34页/共38页(5)(5)重复形式重复形式。P(E)while(SYM IN FIRST(E)P(E);P(E)while(SYM IN FIRST(E)P(E);P(EE)do P(EE)do P(E);P(E);while(SYM IN FIRST(E);while(SYM IN FIRST(E);(6)(6)取舍形式取舍形式。P(E)if(SYM IN FIRST(E)P(E);P(E)if(SYM IN FIRST(E)P(E);第35页/共38页例例6 6 PL0 PL0语言的表达式的语法分析程序语言的表达式的语法分析程序 E+|-T(+|-)TE+|-T(+|-)T TF(*|/)F TF(*|/)F Fi|d|(E)Fi|d|(E)P(E)P(+|-T(+|-)T)P(E)P(+|-T(+|-)T)if(SYM=PLUS|SYM=MINUS)if(SYM=PLUS|SYM=MINUS)GetSym();GetSym();T();T();while(SYM=PLUS|SYM=MINUS)while(SYM=PLUS|SYM=MINUS)GetSym();T();GetSym();T();第36页/共38页P(T)P(F(*|/)F)P(T)P(F(*|/)F)F();F();while(SYM=TIMES|SYM=SLASH)while(SYM=TIMES|SYM=SLASH)GetSym();F();GetSym();F();P(F)P(i|d|(E)P(F)P(i|d|(E)if(SYM=IDENT)GetSym();if(SYM=IDENT)GetSym();else if(SYM=NUMBER)GetSym();else if(SYM=NUMBER)GetSym();else if(SYM=LPAREN)else if(SYM=LPAREN)GetSym();E();CHEGET(RPAREN);GetSym();E();CHEGET(RPAREN);TEST();TEST();第37页/共38页感谢您的观看！第38页/共38页