编译原理(清华)第五章自顶向下语法分析方法

第五章自顶向下语法分析方法学习目标:掌握：LL(1)文法的判别，预测分析法，递归子程序的构造方法理解：LL（1）文法了解：不确定的自顶向下分析语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子分类:语法分析自顶向下分析自底向上分析确定的不确定的算法优先分析（第六章）LR分析（第七章）自顶向下的基本思想:从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子.5.1确定的自顶向下分析思想5.2LL(1)文法的判别5.3某些非LL(1)文法到LL(1)文法的等价变换5.4不确定的自顶向下分析思想5.5确定的自顶向下分析方法5.1确定的自顶向下分析思想1确定分析的条件2开始符号集FIRST(α)的定义3后跟符号集FOLLOW(A)的定义4选择集合SELECT(A→α)的定义5LL(1)文法的定义1确定分析的条件从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。例1设有文法G1[S]:S→pA|qBA→cAd|aB→dB|b若输入串W=pccadd。自顶向下的推导过程为:SSApcAdcAda=pA=pcAd=pccAdd=pccaddG1[S]有如下特点：(1)每个产生式的右部由终结符开头;(2)同一非终结符的不同产生式的右部由不同的终结符开头。对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。例2：设有文法G2[S]为:S→Ap|BqA→a|cAB→b|dBpAScAcAa=ccapS=cAp=ccAp=Ap该例说明，当(1)产生式右部以终结符或非终结符开头（无空产生式）；(2)同一非终结符的不同产生式的右部由不同的符号开头。对于这种文法，在推导过程选用哪个产生式不直观，关键是判断产生式右部推出的开始符号（集），分析过程可能是确定若输入串W=ccap,自顶向下的推导过程为：例3：设有文法G3[S]S→aA|dA→bAS|ε若输入串W=abd，自顶向下的推导过程为：AaSbSAεd=abdS=abAS=abS文法的特点是:包含空产生式对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集），分析过程可能是确定的。=aA要进行确定的自顶向下的分析，文法要满足一定的限制——即文法是LL(1)文法。先研究三个定义开始符号集FIRST后跟符号集FOLLOW选择集合SELECT2开始符号集FIRST(α)的定义定义:设G=(VN,VT,P,S)是上下文无关文法，(VNVT)*FIRST()={aVT|*a......}若*ε则规定ε∈FIRST()直观上说文法符号串的开始符号集是由推导出的开头的终结符（包括ε）组成。例文法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}由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符属于哪个产生式右部的开始符号集而决定选哪个产生式进行推导，可以进行确定的自顶向下分析3后跟符号集FOLLOW(A)的定义定义设G=(VT,VN,P,S)是上下文无关文法，A∈VN，FOLLOW(A)={a|S=*…Aa…，a∈VT}，若有S=*…A，则规定#∈FOLLOW(A)（注：#输入串#，‘#’做为输入串的结束符）直观上说,非终结符A的后跟符号集是由句型中紧跟A后的那些终结符（包括#）组成。例文法G3[S]:S→aA|dA→bAS|ε由S=*S得#∈FOLLOW(S)由S=aA=abAS=abbASS=abbASaA…=abbASdFOLLOW(S)={#,a,d}由S=*aA得#∈FOLLOW(A)由S=*abAS=*abAaA得a∈FOLLOW(A)…=*abAd得d∈FOLLOW(A)FOLLOW(A)={#,a,d}说明：对于非终结符A的两个产生式A→bAS和A→ε，当输入符号∈FIRST(bAS)={b}时，选A→bAS推导，当输入符号∈FOLLOW(A)={#,a,d}时，选A→ε推导。由于FIRST(bAS)∩FOLLOW(A)=ф，所以可进行确定的自顶向下分析。4选择集合SELECT(A→α)的定义定义对给定的上下文无关文法的产生式A→α，A∈VN，α∈V*，若α≠*ε,则SELECT(A→α)=FIRST(α)若α=*ε,则SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)解释当A面对应输入符a，在自顶向下的分析中应选择这样的产生式A→进行推导：First()中包含a；此外若可能导出空串，A自动获得匹配，输入符a有可能与A后的一个符号匹配，所以当a应属于Follow(A)时，选择产生式A→也是可以的。直观上说某产生式A→α的选择集合是指遇到哪些输入符号（包括#）时选用该产生式向下推导。例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)说明：同一非终结符的不同产生式A→α与A→β，若SELECT(A→α)∩SELECT(A→β)=Φ，则一定可以进行确定的自顶向下分析α、β不能同时=*ε5LL(1)文法的定义定义:一个上下文无关文法是LL(1)文法的充分必要条件是，对每个非终结符A的两个不同产生式A→α与A→β，满足SELECT(A→α)∩SELECT(A→β)=Φ。LL(1)文法的含义是：第一个L表示从左到右扫描输入串第二个L表示分析过程用最左推导1表明只需向前看一个符号便可以决定选哪个产生式进行推导，类似地LL(k)文法需要向前看K个符号才可以确定选用哪个产生式。例有文法G[S]为：S→aASS→bA→bAA→ε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→ε去推导。5.2LL(1)文法的判别要判别一个上下文无关文法是否是LL(1)文法分为五步：1.求能推出ε的非终结符集2.计算每个产生式右部α的FIRST(α)集3.计算每个非终结符A的FOLLOW(A)集4.计算每个产生式A→α的SELECT(A→α)集5.按LL(1)文法的定义判别1.求出能推出ε的非终结符集算法:用S表示能推出ε的非终结符集第一步令S={Aj|Aj→ε产生式集}对每个产生式p:Ap→X1....Xn，若X1....XnS，则S:=S{Ap}重复第二步的循环，直至S收敛（不再变化）为止。例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c{A,B,S}第一次{A,B}初值{A,B,S}收敛第二次非终结符集S能推出ε的非终结符集为{A,B,S}2.计算每个产生式右部α的FIRST(α)集首先对每一文法符号X(XVTVN)，求FIRST(X)的算法:1.对每个aVT：First(a)={a}2.对每个AVN：若A*ε则First(A):={ε}否则First(A):={}3.对每个产生式A→X1…Xj…Xn做：First(A)=First(A)SectionFirst(X1…Xj…Xn)其中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)4.重复3直到每个符号的FIRST集合都不再增大为止。例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|cbaacbacεaεbεbaFirst集(3)baacbεaεbεbFirst集(2)baεεεFirst集(1)ABCDabSabεεεFirst集(0)已求出能推出ε的非终结符集为{A,B,S}bbabacaac利用求出每个文法符号的FIRST集求符号串的FIRST集设α=X1X2…Xn1.当X1不能=*ε，则FIRST(α)=FIRST(X1)2.若对任何j(1≤j＜n）都有ε∈FIRST(Xj),则FIRST(α)=(FIRST(X1)-{ε})∪…∪(FIRST(Xj)-{ε})∪FIRST(Xj+1)3.若对所有i(1≤i≤n)，都有ε∈FIRST(Xi)，则FIRST(α)=FIRST(X1)∪…∪FIRST(Xn)例G[S]S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c已求出非终结符的First集合如下:First(S)={a,b,ε}First(A)={b,ε}First(B)={a,ε}First(C)={a,b,c}First(D)={a,c}产生式右部符号串的开始符集合为:S→ABFIRST(AB)=FIRST(A)∪FIRST(B)∪{ε}={a,b,ε}S→bCFIRST(bC)={b}A→εFIRST(ε)={ε}A→bFIRST(b)={b}C→ADFIRST(AD)=(FIRST(A)-{ε})∪FIRST(D)={b,a,c}D→aSFIRST(aS)={a}3．计算每个非终结符A的FOLLOW(A)集1.对所有AVN令Follow(A)={};对开始符S，令Follow(S)={#}因为S=*S，显然#∈FOLLOW(S)2.对每条产生式A→αBγ，考察产生式右部的每一非终结符B，α,γ∈V*，如果γ不能推出εFollow(B)=Follow(B)First(γ)否则Follow(B)=Follow(B)(First(γ)-{ε})Follow(A)3.重复2，直至对所有AVN，Follow(A)收敛为止。若a∈FOLLOW(A),则表明S=*…Aa…，由于A→αBγ，且γ=*ε,则有S=*…Aa…=…αBγa=…xBa…，即S=*…αBa…,所以a∈FOLLOW(B)例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)c4．计算每个产生式A→α的SELECT(A→α)集按定义计算SELECT(A→α)：若α≠*ε，则SELECT(A→α)=FIRST(α)若α=*ε，则SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)例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,#}S