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

第4章自顶向下语法分析方法确定的自顶向下分析思想LL(1)文法的判别某些非LL(1)文法到LL(1)文法的等价变换不确定的自顶向下分析思想确定的自顶向下分析方法确定的自顶向下分析思想文法G1[S]:

S→pA

S→qB

A→cAd

A→a

B→dB

B→bW=pccadd自顶向下的推导过程：SpApcAdpccAddpccadd语法树：SpASpAcAdSpAcAdcAdSpAcAdcAda这个文法的特点：每个产生式的右部都由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。文法G1[S]:

S→pA

S→qB

A→cAd

A→a

B→dB

B→b文法G2[S]:

S→Ap

S→Bq

A→a

A→cA

B→b

B→dBW=ccap自顶向下的推导过程：SApcApccApccap语法树：SApSApcASApcAcASApcAcAa这个文法的特点：每个产生式的右部不全是由终结符号开始。如果两个产生式有相同的左部，那么它们的右部由不同的终结符或非终结符开始。文法中无空产生式。文法G1[S]:

S→Ap

S→Bq

A→a

A→cA

B→b

B→dB定义：设G=(VT,VN,S,P)是上下文无关文法，

FIRST(α)={a|αaβ,a∈VT,α,β∈V*}

若αε，则规定ε∈FIRST(α)**调用返回FIRST(Ap)={a,c}FIRST(Bq)={b,d}文法G2[S]:

S→Ap

S→Bq

A→a

A→cA

B→b

B→dB文法G3[S]:

S→aA

S→d

A→bAS

A→εW=abd试图推导的过程：SaAabASabSabd定义：设G=(VT,VN,S,P)是上下文无关文法，A∈VN,S是开始符号。

FOLLOW(A)={a|SA且a∈FRIST(), ∈VT*,∈V+}

若SA,且

ε，则规定#∈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)文法的含义：第一个L表示：自顶向下分析是从左向右扫描输入串。第二个L表示：分析过程中将用最左推导。

1表示：只需向右看一个符号便可决定如何推导（即选择哪个产生式进行推导）。类似也可以有LL(K)文法：需向前查看K个符号才可确定选用哪个产生式。文法G[S]是否是LL(1)文法:

S→aA

S→d

A→bAS

A→εSELECT(S→aA) ={a}

SELECT(S→d) ={d}

SELECT(A→bAS) ={b}

SELECT(A→ε) ={a,d,#,ε}SELECT(S→aA)∩SELECT(S→d)={a}∩{d}=Φ

SELECT(A→bAS)∩SELECT(A→ε)={b}∩{a,d,#,ε}=Φ所以该文法是LL(1)文法。设文法G[S]为:

S→aAS

S→b

A→bA

A→εSELECT(S→aAS) ={a}

SELECT(S→b) ={b}

SELECT(A→bA) ={b}

SELECT(A→ε) ={a,b,ε}SELECT(S→aAS)∩SELECT(S→b)={a}∩{b}=Φ

SELECT(A→bA)∩SELECT(A→ε)={b}∩{a,b,ε}≠Φ所以该文法不是LL(1)文法。G[S]:

S→aAS

S→b

A→bA

A→ε对输入串W=ab进行推导：SaASabASabS出错SaASaSabLL(1)文法的判别求出能推出ε的非终结符计算FIRST集计算FOLLOW集计算SELECT集判别是否是LL(1)文法例：设文法G[S]为:

S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c

判断它是否是LL(1)文法。1.求出能推出ε的非终结符S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→c非终结符SABCD初值未定未定未定未定未定第一次扫描是是否第二次扫描是否2.计算FIRST集1.若XV,则FIRST(X)={X}2.若XVN,且有产生式Xa…，则a∈FIRST(X);

若X也是一条产生式,则∈FIRST(X).3.若XY…是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若XY1Y2…YK

是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj)都含有(即Y1..Y(i-1)

),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj,

j=1,2,…,K)均含有,则把加到FRIST(X)中.*S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→cFIRST(S)=(FIRST(A)-{ε})∪FIRST(B)-{ε})∪{ε}∪{b}={a,b,ε}FIRST(A)={b,ε}FIRST(B)={a,ε}FIRST(C)={a,b,c}FIRST(D)={a,c}FIRST(AB)={a,b,ε}FIRST(AD)={a,b,c}3.计算FOLLOW集1.对于文法的开始符号S,置#于FOLLOW(S)中;2.若Ａ→αBβ是一个产生式,则把FIRST(β)\{}加至FOLLOW(B)中;3.若Ａ→αB是一个产生式,或Ａ→αBβ是一个产生式而β

(即FIRST(β)），则把FOLLOW（A），加至FOLLOW（B）中．*S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→cFOLLOW(S)={#}∪FOLLOW(D)FOLLOW(A)={a}∪{a,c}∪FOLLOW(S)FOLLOW(B)=FOLLOW(S)FOLLOW(C)=FOLLOW(S)FOLLOW(D)=FOLLOW(B)∪FOLLOW(C)FOLLOW(S)={#}FOLLOW(A)={a,c,#}FOLLOW(B)={#}FOLLOW(C)={#}FOLLOW(D)={#}4.计算SELECT集S→AB

S→bC

A→ε

A→b

B→ε

B→aD

C→AD

C→b

D→aS

D→cFIRST(S)={a,b,ε}FIRST(A)={b,ε}FIRST(B)={a,ε}FIRST(C)={a,b,c}FIRST(D)={a,c}FIRST(AB)={a,b,ε}FIRST(AD)={a,b,c}SELECT(S→AB)={a,b,ε,#}SELECT(S→bC)={b}SELECT(A→ε)={a,c,#,ε}SELECT(A→b)={b}SELECT(B→ε)={#,ε}SELECT(B→aD)={a}SELECT(C→AD)={a,b,c}SELECT(C→b)={b}SELECT(D→aS)={a}SELECT(D→c)={c}FOLLOW(S)={#}FOLLOW(A)={a,c,#}FOLLOW(B)={#}FOLLOW(C)={#}FOLLOW(D)={#}该文法不是LL(1)文法。某些非LL(1)文法到LL(1)文法的等价变换提取左公共因子消除左递归提取左公共因子A→αβ|αγ导致SELECT(A→αβ)∩SELECT(A→αγ)≠Φ，因此非LL(1)文法。等价变换为A→α(β|γ)，然后：

A→αA'

A'→β|γA→αβ1|αβ2|…|αβn变换为A→α(β1|β2|…|βn)

，然后：

A→αA'

A'→β1|β2|…|βn例：文法G1[S]为:

S→aSb

S→aS

S→ε化为：

S→aS(b|ε)

S→ε进一步化为：

S→aSAA→bA→εS→ε结果仍然不是LL(1)文法。

因此，文法中不含左公共因子只是LL(1)文法的必要条件。w=aabbS=>aSA

=>aaSAA

=>aaAA

=>aabA(aaA)例：文法G2为:

A→ad

A→Bc

B→aA

B→bB1.化为：

A→adA→aAcA→bBcB→aA

B→bB2.化为：A→a(d|Ac)A→bBcB→aA

B→bB3.化为：A→aA'A→bBcA'→dA'→AcB→aA

B→bB结果是LL(1)文法。例：文法G3[S]为:

S→aSd

S→Ac

A→aS

A→b1.化为：

S→aSd

S→aScS→bc

A→aS

A→b2.化为：S→aS(d|c)

S→bcA→aS

A→b3.化为：S→aSA'

S→bcA'→dA'→cA→aS

A→b结果中A是不可达到的符号。例：文法G4[S]为:

S→Ap|Bq

A→aAp|d

B→aBq|e1.化为：

S→aApp|aBqq|dq|eq

A→aAp|d

B→aBq|e2.化为：S→a(App|Bqq)

S→dq|eqA→aAp|d

B→aBq|e3.化为：S→aS'S→dq|eqS'→App|Bqq

A→aAp|d

B→aBq|e4.化为：S→aS'S→dq|eqS'→aAppp|aBqqq|dpp|eqq

A→aAp|d

B→aBq|e利用提取左公共因子无法在有限步骤内替换成无左公共因子的文法结论不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法。一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。消除左递归直接左递归：

A→Aβ AVN,βV*间接左递归：

A→Bβ

B→Aα A,BVN,α,βV*文法G5含有直接左递归：

S→Sa

S→b

所能产生的语言L={ban|n≥0}

输入串baaaa#是该语言的句子，但如何用自顶向下分析呢？文法G6含有间接左递归：

A→aB

A→Bb

B→Ac

B→d

输入串adbcbcbc#

A→aB→ad

A→aB→aAc→aBbc→aAcbc…消除直接左递归把直接左递归改写为右递归。如G5:

S→Sa

S→b

(L={ban|n≥0})改为：

S→bS'

S'→aS'|ε消除直接左递归的一般方法：A→Aα1|Aα2|…|Aαm|β1|β2|…|βn

其中：αi不等于ε，βj不以A开头。

改为：A→β1A'|β2A'|…|βnA'

A'→α1A'|α2A'|…|αmA'|ε消除间接左递归将间接左递归变为直接左递归，然后消除直接左递归。如文法G6含有间接左递归：

A→aB

A→Bb

B→Ac

B→d

B→aBc

B→Bbc

B→dB→aBcB'|dB'

B'→bcB'|ε消除文法中一切左递归的算法1.无回路(A(A(A)2.无空产生式（1）以某种顺序将文法非终结符排列A1,A2…An（2）fori:=1tondobegin

forj:=1toi-1do用Ai-->1|2r…|kr替代形如Ai-->Ajr的规则,其中Aj-->1|2…|k是关于Aj的全部产生式;消除Ai规则的直接左递归;

end;（3）化简由2得到的文法+例：文法G:

S→Qc|c

Q→Rb|b

R→Sa|aR→Qca|ca|aR→Rbca|bca|ca|aR→(bca|ca|a)R'R'→bcaR'|ε参考P.84不确定的自顶向下分析思想1.由于相同左部的产生式的右部FIRST集交集不为空引起回溯。 S→xAy A→ab|aw=xaySxAySxAyabSxAya试探回溯试探2.由于相同左部非终结符的右部能ε且该非终结符FOLLOW集中含有其右部FIRST集的元素。设文法G[S]为:

S→aAS

S→b

A→bAS

A→ε*w=ab#SaASSaASbASSaASεb试探

再试探回溯3.由于文法含有左递归而引起回溯。设文法G[S]为:

S→Sa

S→bw=baa#SbSSaSSabSSaSaSSaSab确定的自顶向下分析方法1.递归子程序法实现思想：对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按LL(1)形式可唯一地确定选择某个候选进行推导。限制：对文法要求高，必须满足LL(1)文法；由于递归调用多，速度慢，占用空间多。2.预测分析法预测分析器：预测分析程序（P.88）先进后出栈预测分析表预测分析表的构造表达式文法：E→E+T|TT→T*F|FF→i|(E)构造过程1.判断文法是否为LL(1)文法消除左递归：E→E+T|TT→T*F|FF→i|(E)E→TE'

E'→+TE'|εT→FT'

T'→*FT'|εF→i|(E)可推出ε的非终结符表：E→TE'

E'→+TE'|εT→FT'

T'→*FT'|εF→i|(E)EE'TT'F否是否是否各非终结符的FIRST集和FOLLOW集：FIRST(E)={(,i}FIRST(E')={+,ε}FIRST(T)={(,i}FIRST(T')={*,ε}FIRST(F)={(,i}FOLLOW(E)={),#}FOLLOW(E')={),#}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={*,+,),#}E→TE'

E'→+TE'|εT→FT'

T'→*FT'|εF→i|(E)查看FOLLOW定义查看FIRST定义各产生式的SELECT集：E→TE'

E'→+TE'|εT→FT'

T'→*FT'|εF→i|(E)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

}FIRST(E)={(,i}FIRST(E')={+,ε}FIRST(T)={(,i}FIRST(T')={*,ε}FIRST(F)={(,i}FOLLOW(E)={),#}FOLLOW(E')={),#}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLL