第5章-自顶向下语法分析方法

武汉理工大学计算机科学系陈天煌第5章自顶向下语法分析(Top-downSyntaxAnalysis)语法分析的主要工作：是识别由词法分析给出的单词序列是否是给定的正确句子（程序）。语法分析常用的方法：自顶向下的语法分析和自底向上的语法分析两大类。武汉理工大学计算机科学系陈天煌自顶向下分析思想自顶向下的方法：从文法的开始符号（设为〈程序〉）开始进行分析，逐渐推导的往下构造语法树，使其树叶正好构造出所给定的源程序串。自顶向下的主要思想：从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。自顶向下方法的关键：是确定在推导过程中选择候选式的问题。当进行推导时，一个非终结符可能对应多个产生式，这样我们就无法事先知道应该用哪个产生式，因此实用都作了一些限制。以便在任何情况下都能确定应该用的产生式。武汉理工大学计算机科学系陈天煌自顶向下的缺点:在推导过程中，如果对文法不做限制。那么产生式的选择成为无根据的，只好一一去试所有可能的产生式，直至成功为止。这种方法的致命弱点是不断地回溯，大大影响速度。所以自顶向下分析法又分为确定的和不确定的两种：确定的分析方法需对文法有一定的限制，但由于实现方法简单，直观，便于手工构造或自动生成语法分析器，因此仍是目前常有的方法之一。不确定的方法即回溯的分析方法。这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因此极少使用。武汉理工大学计算机科学系陈天煌5.1确定的自顶向下分析思想例5.1若有文法G[S]：S→pAS→qBA→cAdA→a若有输入串w=pccadd.解：推导过程为：其相应的语法树见右图：SS这个文法的特点：[1]每个产生式的右部都由终结符号开始。[2]如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。显然对于这样的推导中完全可以根据当前的输入符号决定选择哪个产生式往下推导。因此分析过程是唯一的。pcAdcAdpccAddcAdpccaddapApA考察自顶向下的推导过程。武汉理工大学计算机科学系陈天煌例5.2：若有文法G2[S]：SApSBqAaAcABbBdB若有输入串w=ccap。考察自顶向下的推导过程。解：自顶向下的推导过程为：其相应的语法树见右图：SS这个文法的特点：[1]产生式的右部不全是由终结符号开始。[2]如果两个产生式有相同的左部，它们的右部由不同的终结符或非终结符开始。[3]文法中无空产生式。ccApcAAppAAcApcccapa武汉理工大学计算机科学系陈天煌小结：在上述推导过程中，对于产生式中相同左部含有非终结符打头的右部时，在推导中选用哪个产生式是不能直接知道的。对输入串W=ccap为输入串时，其第一个符号为c，这时从S出发选择S→Ap，还是选择S→Bq。其根据是要知道A或B它们是否能推导以c打头的符号串，即它们的首符集是什么。若c是Ap的首符集的元素，且不在Bq的首符集中，则选择S→Ap往下推导。反之，若c在Bq的首符集中，不在Ap的首符集中，则选择S→Bq往下推导。其它情况为不确定推导或出错。因此，在推导前有必要求出每个文法符号的首符集。武汉理工大学计算机科学系陈天煌一.首符集，后继符集与选择集的定义：定义4-1（首符集定义）：设G=(VN，VT，P，S）是上下文无关文法，α是G的任一符号串，则有：FIRST（α）={a|α*aβ,a∈VT，α、β∈V*}特别地，若α*ε，则规定ε∈FIRST(α)即：FIRST(α)是从α出发推导出的所有符号串首终结符或可能的ε构成的集合。武汉理工大学计算机科学系陈天煌这样在文法G2中，关于S的两个产生式虽然都以非终结符开始，但它们右部符号串可以推导出首符集合互不相交，因此可根据当前的输入符号是属于哪个产生式右部的首符号集合而决定选择相应产生式进行推导。因此是确定的自顶向下分析。有文法G2[S]：SApSBqAaAcABbBdB武汉理工大学计算机科学系陈天煌例5.3:若有文法G3[S]:S→aAS→dA→bASA→ε若有输入串W=abd。考察自顶向下的推导过程。解：相应语法树为右图：SSaAaAabASbASabSεabdd当文法中有空产生式时,如例：武汉理工大学计算机科学系陈天煌小结：由此可以看出，当某一非终结符的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推导过程中紧跟该非终结符右边可能出现的终结符集也不相交，则仍可构造确定的自顶向下分析。为此可定义一个文法符号的后继符集合为：（定义5.2）从上述推导过程中我们可以在第二步到第三步的推导中，即abASabS时，因当前面临输入符号为d，而最左非终结符A的产生式右部的开始集合都不包括d，但有ε，因此对于d的匹配自然认为只能依赖于在可能的推导过程中A的后面的符号。所以这时选用产生式A→ε往下推导，而当前A后面的符号为S，S产生式右部的开始符号包括了d，所以匹配。武汉理工大学计算机科学系陈天煌FOLLOW(A)={a|S*μAβ且a∈VT,a∈FIRST(β),μ∈VT*,β∈V*}或FOLLOW(A)={a|S*…Aa…,a∈VT}定义5.2:特别地，若S*…A,则#∈FOLLOW(A)(这里#不是文法中的符号，而一个特别的表示输入串的结束符或称句子括号如#输入串#）表示：所有在句型中紧挨着A出现的终结符或#均是FOLLOW(A)的元素。因此当文法中含有形如：A→α和A→β的产生式时，其中A∈VN,α,β∈V*,当α和β不同时推导出空串时，设α*ε，β*ε，则当FIRST(α)∩(FIRST(β)∪FOLLOW(A))=φ时，对于非终结符A的替代仍可唯一地确定候选。\设G=(VN,VT,P,S)是上下文无关文法，A∈VN的后继符集合为：武汉理工大学计算机科学系陈天煌定义5.3：定义选择符集合SELECT如下：对于给出上下文无关文法的产生式A→α,A∈VN,α∈V*，则SELECT(A→α)=FIRST(α)，当αε时FIRST(α)-{ε}∪FOLLOW(A)，否则﹨*武汉理工大学计算机科学系陈天煌（一）求FIRST(X)的算法对每一文法符号X∈(VN∪VT），求FIRST(X).(a)若X∈VT,则令FIRST(X)={X};(b)若X∈VN,且有产生式X→a….,(a∈VT)，则令a∈FIRST(X);(c)若X∈VN,有X→ε，则令ε∈FIRST(X);(d)若X∈VN,y1,y2,…..yi都∈VN,且有产生式X→y1y2…..yn,三种集合的构造算法：注：三种集合均为终结符集当y1,y2,…..yi-1都*ε时，（其中1≤i≤n),则FIRST(y1)-ε,FIRST(y2)-ε,….,FIRST(yi-1)-ε,FIRST(yi)都包含在FIRST(X)中。(e)当(d)中所有yi*ε(i=1,2,….,n),则FIRST(X)=FIRST(y1)∪FIRST(y2)∪….∪FIRST(yn)∪{ε}反复使用上述（b)～(d)步直到每个符号的FIRST集合不再增加为止。武汉理工大学计算机科学系陈天煌（二）求FIRST(α)的算法（α=x1x2….xn):1.若n=0,即α=ε,则令FIRST(α)={ε};2.否则，对1≤i≤n,求FIRST(xi)3.若n=1,则令FIRST(α)=FIRST(x1);4.若n≥2且对一切j=1,2,….,i-1都有ε∈FIRST(xj).则令FIRST(xi)-{ε}FIRST(α),其中2≤i≤n;若对一切j=1,2,…,n都有ε∈FIRST(xj),则令ε∈FIRST(α)或：1.把FIRST(x1)中所有非ε元素加入到FIRST(α)中，即FIRST(α)=FIRST(x1)-{ε};若FIRST(x1)包含有ε，则把FIRST(x2)的所有非ε元素加入到FIRST(α)中，即FIRST(α)=FIRST(α)∪(FIRST(x2)-{ε});若FIRST(x1)和FIRST(x2)都包含有ε，则把FIRST(x3)的所有非ε元素加到FIRST(α)中；……照此方法继续，一直到考察到xn。2.若FIRST(xi),i=1,2,…,n;即每个FIRST(xi)中都有ε。则将ε加到FIRST(α)中。特别地，若α=ε，则FIRST(α)={ε}.武汉理工大学计算机科学系陈天煌(三)求FOLLOW(A)的算法(A∈VN):(a)对文法开始符号S，令#∈FOLLOW(S).(b)若B→αAβ是一个产生式，则令FIRST(β)-{ε}属于FOLLOW(A);(c)若B→αA是一个产生式，或B→αAβ是一个产生式且有ε∈FIRST(β)，则令FOLLOW(B)是FOLLOW(A)的子集。即把FOLLOW(B)的所有元素加入到FOLLOW(A)中。(d)反复使用(b)直到每个非终结符的FOLLOW集合不再增加为止。武汉理工大学计算机科学系陈天煌(四)求SELECT(A→α)的算法：(a)求FIRST(α)；(b)若ε∈FIRST(α),则令SELECT(A→α)=FIRST(α)否则求FOLLOW(A),并令SELECT(A→α)=FIRST(α)∪FOLLOW(A).例：有文法：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→i|(E)求其三种集合。武汉理工大学计算机科学系陈天煌解：FIRST(E)=FIRST(T)=FIRST(F)={i,(}FIRST(E')={+,ε}FIRST(T')={*,ε}FOLLOW(E)=FOLLOW(E')={),#}FOLLOW(T)=FOLLOW(T')={+,),#}FOLLOW(F)={*,+,),#}SELECT(E→TE')=FIRST(T)={i,(}SELECT(E'→+TE')=FIRST(+TE')={+}SELECT(E'→ε)=FIRST(ε)∪FOLLOW(E')={),#}SELECT(T→FT')=FIRST(F)={i,(}SELECT(T'→*FT')=FIRST(*FT')={*}SELECT(T'→ε)=FIRST(ε)∪FOLLOW(T')={+,),#}SELECT(F→i)=FIRST(i)={i}SELECT(F→（E))=FIRST(i)={(}例：有文法：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→i|(E)求其三种集合。武汉理工大学计算机科学系陈天煌例：设有文法G[S]：S→aAS，S→b，A→bA，A→ε5.2LL(1)文法的判别定义5.4：一个上下文无关文法是LL(1)文法的充分必要条件是每个非终结符A的两个不同产生式，A→α,A→β；满足SELECT(A→α)∩SELECT(A→β)=Ф。其中，α、β不能同时*ε。SELECT(S→aAS)=FIRST(aAS)={a}SELECT(S→b)={b}SELECT(A→bA)={b}SELECT(A→ε)=FIRST(ε)-{ε}∪FOLLOW(A)={a,b}∵SELECT(S→aAS)∩SELECT(S→b)={a}∩{b}=φSELECT(A→bA)∩SELECT(A→ε)={b}∩{a,b}≠φ故文法G[S]不是LL(1)文法。当一个文法是LL(1)文法时，则该文法一定能够采用确定的自顶向下的分析方法进行分析。武汉理工大学计算机科学系陈天煌5.3文法的等价变换确定的自顶向下分析要求给定语言的文法必须是LL(1)形式，然而，不一定每个语言都是LL(1)文法，对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是我们讨论的主要问题。由LL(1)文法的定义可知若文法中含有左递归或含有左公共因子，则该文法肯定不是LL(1)文法，因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换。(1).提取左公共因子若文法中含有形如：αβ|αγ的产生式，这导致了对相同的产生式右部的FIRST集相交。即有SELECT(A→αβ)SELECT(A