自顶向下语法分析方法市公开课金奖市赛课一等奖课件

第五章

自顶向下语法分析方法学习目标:掌握：LL(1)文法判别，预测分析法，递归子程序结构方法了解：LL（1）文法了解：不确定自顶向下分析第1页语法分析作用是识别由词法分析给出单词序列是否是给定文法正确句子分类:语法分析自顶向下分析自底向上分析确定不确定算法优先分析（第六章）LR分析（第七章）自顶向下基本思想: 从文法开始符出发企图推导出与输入单词串完全相匹配句子.第2页5.1 确定自顶向下分析思想5.2 LL(1)文法判别5.3 一些非LL(1)文法到LL(1)文法等价变换5.4 不确定自顶向下分析思想5.5 确定自顶向下分析方法第3页5.1确定自顶向下分析思想1确定分析条件2开始符号集FIRST(α)定义3后跟符号集FOLLOW(A)定义4选择集合SELECT(A→α)定义5LL(1)文法定义第4页1确定分析条件 从文法开始符出发，如能依据当前输入符号（单词符号）唯一地确定选取哪个产生式进行推导，则分析是确定。第5页例1设有文法G1[S]: S→pA|qB A→cAd|a B→dB|b 若输入串W=pccadd。自顶向下推导过程为:SSApcAdcAda=>pA=>pcAd=>pccAdd=>pccaddG1[S]有以下特点：(1)每个产生式右部由终止符开头;(2)同一非终止符不一样产生式右部由不一样终止符开头。对于这种文法，在推导过程能够依据当前输入符号唯一确定选哪个产生式往下推导，即分析过程是确定。第6页例2：设有文法G2[S]为:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS=>cAp=>ccAp=>Ap该例说明，当(1)产生式右部以终止符或非终止符开头（无空产生式）；(2)同一非终止符不一样产生式右部由不一样符号开头。对于这种文法，在推导过程选取哪个产生式不直观，关键是判断产生式右部推出开始符号（集），分析过程可能是确定若输入串W=ccap,自顶向下推导过程为：第7页例3：设有文法G3[S]S→aA|dA→bAS|ε若输入串W=abd，自顶向下推导过程为：AaSbSAεd=>abd

S=>abAS=>abS文法特点是:包含空产生式对于空产生式左部非终止符，关键是判断该非终止符后跟符号（集），分析过程可能是确定。=>aA第8页要进行确定自顶向下分析，文法要满足一定限制——即文法是LL(1)文法。先研究三个定义

开始符号集FIRST 后跟符号集FOLLOW 选择集合SELECT第9页2开始符号集FIRST(α)定义定义:设G=(VN,VT,P,S)是上下文无关文法，

(VNVT)*

FIRST()={aVT|*a......} 若*ε

则要求ε∈FIRST()

直观上说文法符号串

开始符号集是由推导出开头终止符（包含ε）组成。第10页例文法G2[S]:S→ApS→BqA→aA→cAB→bB→dBFIRST(Ap)={a,c}FIRST(Bq)={b,d}FIRST(a)={a}FIRST(cA)={c}FIRST(b)={b}FIRST(dB)={d}因为同一非终止符两个产生式右部推导出来开始符号集不相交，所以可依据当前输入符属于哪个产生式右部开始符号集而决定选哪个产生式进行推导，能够进行确定自顶向下分析第11页3后跟符号集FOLLOW(A)定义定义 设G=(VT,VN,P,S)是上下文无关文法，A∈VN， FOLLOW(A)={a|S=>*…Aa…，a∈VT}， 若有S=>*…A，则要求#∈FOLLOW(A) （注：#输入串#，‘#’做为输入串结束符）

直观上说,非终止符A后跟符号集是由句型中紧跟A后那些终止符（包含#）组成。第12页例文法G3[S]: S→aA|d A→bAS|ε由S=>*S

得#∈FOLLOW(S)由S=>aA=>abAS=>abbASS=>abbASaA…=>abbASd

FOLLOW(S)={#,a,d}由S=>*aA得#∈FOLLOW(A)

由S=>*abAS=>*abAaA得a∈FOLLOW(A) …=>*abAd

得d∈FOLLOW(A)

FOLLOW(A)={#,a,d}第13页说明：对于非终止符A两个产生式A→bAS和A→ε，当输入符号∈FIRST(bAS)={b}时，选A→bAS推导，当输入符号∈FOLLOW(A)={#,a,d}时，选A→ε推导。因为FIRST(bAS)∩FOLLOW(A)=ф，所以可进行确定自顶向下分析。第14页4选择集合SELECT(A→α)定义定义 对给定上下文无关文法产生式A→α，A∈VN，α∈V*，若α≠>*ε,则SELECT(A→α)=FIRST(α)若α=>*ε,则SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)

第15页解释 当A面对应输入符a，在自顶向下分析中应选择这么产生式A→进行推导：First()中包含a； 另外若可能导出空串，A自动取得匹配，输入符a有可能与A后一个符号匹配，所以当a应属于Follow(A)时，选择产生式A→也是能够。

直观上说某产生式A→α选择集合是指碰到哪些输入符号（包含#）时选取该产生式向下推导。第16页例G3[S]:S→aAS→dA→bASA→εSELECT(S→aA)=FIRST(aA)={a}SELECT(S→d)=FIRST(d)={d}SELECT(A→bAS)=FIRST(bAS)={b}SELECT(A→ε)=FOLLOW(A)={#,a,d}若α≠>*ε,则SELECT(A→α)=FIRST(α)若α=>*ε,则SELECT(A→α) =(FIRST(α)-{ε})∪FOLLOW(A)第17页说明： 同一非终止符不一样产生式A→α与A→β，若SELECT(A→α)∩SELECT(A→β)=Φ，则一定能够进行确定自顶向下分析第18页5LL(1)文法定义定义: 一个上下文无关文法是LL(1)文法充分必要条件是，对每个非终止符A两个不一样产生式A→α与A→β，满足SELECT(A→α)∩SELECT(A→β)=Φ。

LL(1)文法含义是：第一个L表示从左到右扫描输入串第二个L表示分析过程用最左推导1表明只需向前看一个符号便能够决定选哪个产生式进行推导，类似地LL(k)文法需要向前看K个符号才能够确定选取哪个产生式。第19页例有文法G[S]为： S→aAS S→b A→bA A→εSELECT(S→aAS)={a}SELECT(S→b)={b}SELECT(A→bA)={b}SELECT(A→ε)=Follow(A)={a,b}因为SELECT(A→bA)∩SELECT(A→ε)={b}≠Φ，所以文法G[S]不是LL(1)文法，当A遇输入符b时，不能确定选A→bA还是A→ε去推导。第20页5.2LL(1)文法判别要判别一个上下文无关文法是否是LL(1)文法分为五步：1.

求能推出ε非终止符集2.

计算每个产生式右部αFIRST(α)集3.

计算每个非终止符AFOLLOW(A)集4.

计算每个产生式A→αSELECT(A→α)集5.

按LL(1)文法定义判别第21页1.

求出能推出ε非终止符集算法: 用S表示能推出ε非终止符集第一步令S={Aj|Aj→ε

产生式集}对每个产生式p:Ap→X1....Xn，若X1....XnS，则

S:=S{Ap}重复第二步循环，直至S收敛（不再改变）为止。第22页例G[S]： S→AB|bC A→b|ε B→aD|ε C→AD|b D→aS|c{A,B,S}第一次{A,B}初值{A,B,S}收敛第二次非终止符集S能推出ε非终止符集为{A,B,S}第23页2.

计算每个产生式右部αFIRST(α)集首先对每一文法符号X(XVTVN)，求FIRST(X)算法:对每个aVT

：First(a)={a}对每个AVN

：若

A*ε

则

First(A):={ε} 不然

First(A):={}对每个产生式

A→X1…Xj…Xn

做： First(A)=First(A)SectionFirst(X1…Xj…Xn)第24页其中SectionFirst(X1…Xj…Xn) =(First(X1)-{ε})(First(X2)-{ε})…(First(Xj)-{ε})First(Xj+1)

Xj+1是产生式右部中第一个不能推出ε符号若X1≠>*ε

则SectionFirst(X1…Xj…Xn)=First(X1)若X1…Xn全可推出ε 则SectionFirst(X1…Xn)=FIRST(X1)∪…∪FIRST(Xn)重复3直到每个符号FIRST集合都不再增大为止。第25页例G[S]：S→AB|bC A→b|ε B→aD|ε C→AD|b D→aS|cbaacbac

εaεbεbaFirst集(3)baacbεaεbεbFirst集(2)ba

εεεFirst集(1)ABCDabSabεεεFirst集(0)已求出能推出ε非终止符集为{A,B,S}bbabacaac第26页利用求出每个文法符号FIRST集求符号串FIRST集设α=X1X2…Xn当X1不能=>*ε

，则FIRST(α)=FIRST(X1)若对任何j(1≤j＜n）都有ε∈FIRST(Xj),

则FIRST(α) =(FIRST(X1)-{ε})∪…∪(FIRST(Xj)-{ε}) ∪FIRST(Xj+1)若对全部i(1≤i≤n)，都有ε∈FIRST(Xi)，

则

FIRST(α)=FIRST(X1)∪…∪FIRST(Xn)第27页例G[S] S→AB|bC A→b|ε B→aD|ε C→AD|b D→aS|c已求出非终止符First集合以下:First(S)={a,b,ε}First(A)={b,ε}First(B)={a,ε}First(C)={a,b,c}First(D)={a,c}产生式右部符号串开始符集合为:S→AB FIRST(AB)=FIRST(A)∪FIRST(B)∪{ε}={a,b,ε}S→bC FIRST(bC)={b}A→ε FIRST(ε)={ε}A→b FIRST(b)={b}C→AD FIRST(AD)=(FIRST(A)-{ε})∪FIRST(D)={b,a,c}D→aS FIRST(aS)={a}第28页3．计算每个非终止符AFOLLOW(A)集1.对全部AVN令Follow(A)={};对开始符S，令Follow(S)={#}因为S=>*S，显然#∈FOLLOW(S)2.对每条产生式A→xBy，考查产生式右部每一非终止符B，x,y∈V*，假如y不能推出ε Follow(B)=Follow(B)First(y)不然

Follow(B)=Follow(B)(First(y)-{ε})Follow(A)3.重复2，直至对全部AVN，Follow(A)收敛为止。若a∈FOLLOW(A),则表明S=>*…Aa…，因为A→xBy，且y=>*ε,则有S=>*…Aa…=>…xBya=>…xBa…，即S=>*…xBa…,所以a∈FOLLOW(B)第29页例G[S]：[1]S→AB[2]S→bC[3]A→b[4]A→ε[5]B→aD[6]B→ε[7]C→AD[8]C→b[9]D→aS[10]D→c已求出非终止符First集合以下:First(S)={a,b,ε} First(A)={b,ε}First(B)={a,ε} First(C)={a,b,c}First(D)={a,c}#D#C#Ba#A###a#c＃＃＃SFollow集(2)Follow集(1)Follow集(0)c第30页4．计算每个产生式A→αSELECT(A→α)集按定义计算SELECT(A→α)：若α≠>*ε，则 SELECT(A→α)=FIRST(α)若α=>*ε，则 SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)第31页例G[S]： S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c是否=>*

εFirst集Follow集S是{a,b,ε}{#}A是{b,ε}{a,c,#}B是{a,ε}{#}C否{a,b,c}{#}D否{a,c}{#}部分产生式select集合SELECT(S→AB)=(FIRST(AB)-{ε})∪FOLLOW(S)={b,a,#}SELECT(S→bC)=FIRST(bC)={b}SELECT(A→ε)=(FIRST(ε)-{ε}）∪FOLLOW(A)={a,c,#}SELECT(A→b)=FIRST(b)={b}SELECT(B→aD)=FIRST(aD)={a}SELECT(C→AD)=FIRST(AD)={b,a,c}第32页5.

按LL(1)文法定义判别产生式select集以下:SELECT(S→AB)={b,a,#} SELECT(S→bC)=={b}SELECT(A→ε)={a,c,#} SELECT(A→b)={b}SELECT(B→ε)={#} SELECT(B→aD)={a}SELECT(C→AD)={b,a,c} SELECT(C→b)={b}SELECT(D→aS)={a} SELECT(D→c)={c}因为 SELECT(S→AB)∩SELECT(S→bC)={b}≠ф SELECT(C→AD)∩SELECT(C→b)={b}≠ф所以文法G[S]不是LL(1)文法第33页5.3一些非LL(1)文法到LL(1)文法等价变换非LL(1)文法含有左公共因子文法 若文法中含有形如：A→αβ|αr产生式，称文法含有左公共因子。 显然, SELECT(A→αβ)∩SELECT(A→αr)≠ф,文法不是LL(1)文法第34页含有左递归文法 文法中只要含有以下形式产生式（含有a或含有b或二者皆有）则称文法含有左递归：A→AβA→Bβ B→Aα 在a)中含有左递归产生式，称为直接左递归； 在b)中即使没有含左递归产生式， 但A=>Bβ=>Aαβ即A=>+A…,称为间接左递归第35页以直接左递归为例，若有以下产生式

A→A

|

A→其中和为任意语法符号串。不难证实有下面关系式：

Select(A→A))First(A)First() Select(A→

))First()故A→A和A→

Select集相交，不是LL(1)文法。第36页对非LL(1)文法进行等价变换提取左公共因子消除左递归

注意：变换后文法不一定是LL(1)文法，文法不含左递归和左公共因子只是LL(1)文法必要条件。第37页1提取左公共因子将产生式A→αβ|αr等价变换为: A→α(β|r)， 将括号内用一新引入非终止符A’表示,得A→αA’，A’→β|r普通形式：若A→αβ1|αβ2|…|αβn, 提取左公共因子后变为A→αA’， A’→β1|β2|…|βn

若在βi中仍含有左公共因子,可再次提取.第38页例 文法G1： S→aSb|aS|ε

提左因子得:S→aS(b|ε)|ε

引进新非终止符得:

S→aSS’|ε S’→b|ε第39页2.

消除左递归消除直接左递归文法G:S→Sa|b 可改写成 S→bS’ S’→aS’|ε普通情形: 含直接左递归文法G： A→Aα1|Aα2|…|Aαm|β1|β2|…|βn 消除左递归后改写成：

A→β1A’|β2A’|…|βnA’

A’→α1A’|α2A’|…|αmA’|ε

第40页消除间接左递归将间接左递归变成直接左递归，再消除算法步骤：把文法全部非终止符按任一次序排列， 如：A1，A2，…，An从A1开始，按以下次序处理Ai。首先，消除左部为Ai产生式直接左递归然后，若左部为Ai产生式右部为非终止符Aj(j<i)开头，即Ai→Aj…，则用左部为Aj全部产生式右部分别代替Ai→Aj…中Aj最终，得到左部为Ai产生式若有直接左递归，则消除之

去掉无用产生式。第41页例文法G：(1)S→Qc|c (2)Q→Rb|b(3)R→Sa|a将非终止符排序：R，Q，S对R：产生式(3)不含直接左递归，所以保持不变

对Q：把(3)代入(2)得(2’)Q→Sab|ab|b，无直接左递归

对S：把(2’)代入(1)得(1’)S→Sabc|abc|bc|c，有直接左递归，消除直接左递归得

S→abcS’|bcS’|cS’ S’→abcS’|ε 处理结果为：R→Sa|a Q→Sab|ab|b S→abcS’|bcS’|cS’ S’→abcS’|ε因为Q，R是不可抵达非终止符，其产生式应删除。最终得文法G’：S→abcS’|bcS’|cS’S’→abcS’|ε第42页示例说明：当非终止符次序为R，Q，S，消除左递归最终止果为：

S→abcS’|bcS’|cS’S’→abcS’|ε若非终止符次序为S，Q，R，则消除左递归最终止果为：

S→Qc|cQ→Rb|bR→bcaR’|caR’|aR’R’→bcaR’|ε结论：当非终止符排序不一样时，结果产生式形式不一样，但它们是等价。第43页5.4不确定自顶向下分析思想不确定自顶向下分析也称带回溯自顶向下分析定义： 不确定是指某个非终止符有多条产生式，而面临当前输入符无法唯一确定选取哪条产生式进行推导，只好逐一试探。当分析不成功时，则推翻分析退回到适当位置重新试探其余候选可能推导，直到把全部可能推导序列都试完仍不成功，才能确认输入串不是该文法句子。第44页例1 设有文法S→xAyA→ab|a，对输入串w=xay，推导树为SxAySxAybaSxAy回溯aSxAy因为A两条产生式：A→ab和A→a右部First集交集不为空，从而引发回溯第45页例2 文法G：S→aAS S→b A→bAS A→ε 输入串w=ab，推导树为:SaAS回溯S

aASSaASSbASaASεb因为A产生式A→ε右部能=>*ε，且Follow(A)∩First(bAS)={b}≠ф

，从而引发回溯第46页例3 文法G：S→Sa S→b输入串w=baa，推导树为:SSabSbSSa回溯回溯SSaSaSSaSab因为文法含有左递归而引发回溯第47页5.5确定自顶向下分析方法确定自顶向下分析方法有：递归子程序法(recursive-descentparser)预测分析法(predictiveparser)两种方法都要求文法是LL(1)文法。第48页5.5.1递归子程序法实现思想： 对文法中每个非终止符编写一个递归过程，识别由该非终止符推出串。当非终止符有多条产生式时，按当前输入符属于哪条产生式SELECT集可唯一确定选择哪个产生式进行匹配。当识别到终止符时，与当前输入符号匹配，并读取下一输入符；当识别到非终止符时，则调用该非终止符对应过程。第49页例算术表示式文法G

E→E+T│T T→T*F│F F→(E)│i1）消除左递归得G':E→TE' E'→+TE'│εT→FT' T'→*FT'│εF→(E)│i 2）求出G’选择集合SELECT(E→TE')={(,i}SELECT(E'→+TE')={+}SELECT(E'→ε)={),#}SELECT(T→FT')={(,i}SELECT(T'→*FT')={*}SELECT(T'→ε)={+,),#}SELECT(F→(E))={(}SELECT(F→i)={i}G’是LL(1)文法1

判断是否能够应用递归子程序法第50页表示式正规式E=T(+T)*转换成正则文法E→TB，B→(+T)*，即B→(+T)*εB→(+T)B，B→ε，即B→(+T)B│ε

与E→E+T│T消除左递归所得E→TE‘ E’→+TE‘│ε一致表示式项＋－项＋－原产生式变换后产生式规则1A→xyA→xBB→y规则2A→x*yA→xAA→y规则3A→x|yA→xA→y第51页2

结构文法G'递归下降分析器定义： 当一个文法满足LL(1)条件时，就为它结构一个不带回溯自顶向下分析程序，这个分析程序由一组递归过程组成，每个过程对应文法一个非终止符。这么一个分析程序称为递归下降分析器。第52页组成： 递归下降分析器由一个主程序MAIN和每个非终止符对应一个递归过程组成。 用到一些子过程：过程GETNEXT负责读入下一个TOKEN字过程ERROR负责汇报语法错误 约定：变量TOKEN存放已读入TOKEN字过程进入时变量TOKEN存放了一个待匹配TOKEN字退出过程时，变量TOKEN中仍存放着一个待匹配TOKEN字。第53页非终止符对应分析子程序结构方法对于每个非终止符U，编写一个对应子程序P(U);对于产生式U→x1|x2|…|xn，x1,...xn都≠ε关于U子程序P(U)按以下方法结构：

ifTOKENinfirst(x1)thenp(x1)elseifTOKENinfirst(x2)thenp(x2)else…….ifTOKENinfirst(xn)thenp(xn)elseERROR第54页假如U还有空产生式U→ε,则算法中语句：

ifTOKENinfirst(xn)thenp(xn)elseERROR改写为

ifTOKENinfirst(xn)thenp(xn)elseifTOKENnotinfollow(U)thenERROR对于符号串x=y1y2…yn；p(x)含义为：

beginp(y1);p(y2);…;p(yn)end 假如yi∈VN，则P(yi)就代表调用yi子程序；yi∈VT，则P(yi)为形以下述语句一段程序

ifTOKEN=yithenGETNEXT(TOKEN)elseERROR第55页(1)programMAIN;/*主程序,匹配E→E#*/

beginGETNEXT(TOKEN);E(TOKEN);/*转匹配E→TE'*/ifTOKEN≠'#'thenERRORend.结构文法G’： E→TE' E'→+TE'│εT→FT' T'→*FT'│ε F→(E)│i 递归下降分析器(2)procedureE(TOKEN); /*匹配E→TE'*/beginT(TOKEN); /*转匹配T→FT'*/E’(TOKEN)/*转匹配E'→+TE'│ε*/end;

第56页(3)procedureE’(TOKEN);/*匹配E'→+TE'│ε*/beginifTOKEN=’+’then/*选择产生式E'→+TE'*/beginGETNEXT(TOKEN);

/*匹配’+’,读下一个TOKEN字*/

T(TOKEN);/*转匹配T→FT'*/E’(TOKEN)/*转匹配E'→+TE'│ε*/end else/*E→ε对应语句*/ ifTOKEN≠’)’andTOKEN≠’#’thenERROR

/*结构方法3，求follow(E’)=follow(E)={’)’,’#’}*/

end;第57页(5)procedureT'(TOKEN);/*匹配T'→*FT'│ε*/beginifTOKEN='*'then/*选择产生式T'→*FT'*/beginGETNEXT(TOKEN);/*匹配'*'，读下一TOKEN字*/

F(TOKEN);/*转匹配F→(E)│i*/T'(TOKEN)/*转匹配T'→*FT'│ε*/end else/*T‘→ε对应语句*/ifTOKEN≠'+'andTOKEN≠')'andTOKEN≠'#'thenERRORend;/*follow(T’)=follow(T)=first(E’)+follow(E’)={’+’,’)’,’#’}*/

(4)procedureT(TOKEN);/*匹配T→FT'*/beginF(TOKEN);/*转匹配F→(E)│i*/T’(TOKEN)/*转匹配T'→*FT'│ε*/end;第58页(6)procedureF(TOKEN);/*匹配F→(E)│i*/beginifTOKEN='('then/*选择产生式F→(E)*/beginGETNEXT(TOKEN);/*匹配'('，读下一TOKEN字*/

E(TOKEN);/*转匹配E→TE'*/

ifTOKEN=')'thenGETNEXT(TOKEN)

/*匹配')',读下一TOKEN字*/

elseERRORendelse /*选择产生式F→i

*/ ifTOKEN=‘i’thenGETNEXT(TOKEN) elseERRORend;第59页特点：优点：简单直观、易于结构缺点： 对文法要求高，必须满足LL(1)文法； 递归调用多，速度慢，占用空间多实用性：许多高级语言，如Pascal、c等编译系统经常采取此方法。第60页5.5.2预测分析方法一个预测分析器由三个部分组成：预测分析程序：控制分析过程进行。分析栈：存放从文法开始符号出发自顶向下推导过程中等候匹配文法符号。开始时放入‘#’和文法开始符，结束时栈应是空。预测分析表：是一张二维表，元素M[A,a]内容是当非终止符A面临输入符号a（终止符或句子括号＃）