第4章-自顶向下语法分析方法.ppt

第4章自顶向下语法分析方法确定的自顶向下分析思想这个文法的特点：
每个产生式的右部都由终结符号开始。
如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。文法G2[S]:S→ApS→BqA→aA→cAB→bB→dB
这个文法的特点：
每个产生式的右部不全是由终结符号开始。
如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。
文法中无空产生式。定义：设G=(VT,VN,S,P)是上下文无关文法，FIRST(α)={a|αaβ,a∈VT,α,β∈V*}若αε，则规定ε∈FIRST(α)FIRST(Ap)={a,c}
FIRST(Bq)={b,d}文法G3[S]:S→aAS→dA→bASA→ε定义：设G=(VT,VN,S,P)是上下文无关文法，A∈VN,S是开始符号。FOLLOW(A)={a|SA且a∈FRIST(), ∈VT*,∈V+}若SA,且ε，则规定#∈FOLLOW(A)
即：FOLLOW(A)={a|S…Aa…,a∈VT}若S…A，则规定#∈FOLLOW(A)
#作为输入串的结束符，或称为句子括号，如：#输入串#
对A→αA→β其中A∈VN,α,β∈VN*
当α和β不同时推导出空时（设α不推导出空，β推导出空），则当FIRST(α)∩(FIRST(β)∪FOLLOW(A))=Φ时，对于非终结符A的替换仍可唯一地确定候选。定义：给定上下文无关文法的产生式A→α，A∈VN,α∈V*，若αε，则SELECT(A→α)=FIRST(α)如果αε，则SELECT(A→α)=FIRST(α)∪FOLLOW(A)定义：一个上下文无关文法是LL(1)文法的充要条件是：对每个非终结符A的两个不同产生式A→α和A→β，满足SELECT(A→α)∩SELECT(A→β)=Φ其中α,β不同时能εLL(1)文法的含义：文法G[S]是否是LL(1)文法:S→aAS→dA→bASA→ε设文法G[S]为:S→aASS→bA→bAA→εG[S]:S→aASS→bA→bAA→εLL(1)文法的判别例：设文法G[S]为:S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c判断它是否是LL(1)文法。1.求出能推出ε的非终结符2.计算FIRST集S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c3.计算FOLLOW集S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c4.计算SELECT集某些非LL(1)文法到LL(1)文法的等价变换提取左公共因子例：文法G1[S]为:S→aSbS→aSS→ε例：文法G2为:A→adA→BcB→aAB→bB例：文法G3[S]为:S→aSdS→AcA→aSA→b例：文法G4[S]为:S→Ap|BqA→aAp|dB→aBq|e结论消除左递归文法G5含有直接左递归：S→SaS→b所能产生的语言L={ban|n≥0}输入串baaaa#是该语言的句子，但如何用自顶向下分析呢？文法G6含有间接左递归：A→aBA→BbB→AcB→d输入串adbcbcbc#A→aB→adA→aB→aAc→aBbc→aAcbc…消除直接左递归消除直接左递归的一般方法：
A→Aα1|Aα2|…|Aαm|β1|β2|…|βn其中：αi不等于ε，βj不以A开头。改为：
A→β1A'|β2A'|…|βnA'A'→α1A'|α2A'|…|αmA'|ε消除间接左递归消除文法中一切左递归的算法例：不确定的自顶向下分析思想2.由于相同左部非终结符的右部能ε且该非终结符FOLLOW集中含有其右部FIRST集的元素。
设文法G[S]为:S→aASS→bA→bASA→ε3.由于文法含有左递归而引起回溯。
设文法G[S]为:S→SaS→b确定的自顶向下分析方法2.预测分析法预测分析表的构造构造过程可推出ε的非终结符表：各非终结符的FIRST集和FOLLOW集：各产生式的SELECT集：2.构造预测分析表运行：