自顶向下语法分析方法

第五章自顶向下语法分析方法分析学习目标:掌握：LL(1)文法的判别，法，递归子程序的构造方法理解：LL（1）文法了解：不确定的自顶向下分析语法分析是编译过程的

部分，它的主要任务是按照程序语言的语则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序叫语法分析程序或语法分析器。语法分析程序以词法分析输出的符号串作为输入，

在分析过程中检查这个符号串是否为该程序语言的句子。若是，输出该句子的分析树；若不是，则表示源程序存

在语法错误，需要报告错误的性质和位置。例如，对于C程序语句“IF

(a<10)b=5；”，词法分析识别出了IF、(、标识符、…等单词符号，而语法分析则要检查这些单词之间的搭配、结构是否正确。IF后面是否为(，(后面是否为正确的表达式等等。语法分析语法分析的作用是识别由词法分析给出的单词序列是否是给定文法的正确句子分类:确定的自顶向下分析不确定的算法优先分析（第六章）自底向上分析LR分析（第七章）自顶向下的基本思想:从文法的开始符出发企图推导出与输入的单词串完全相匹配的句子.确定的自顶向下分析思想确定分析的条件开始符号集

(α)的定义后跟符号集FOLLOW(A)的定义选择集合SELECT(A→α)的定义LL(1)文法的定义1

确定分析的条件从文法的开始符出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。例1

设有文法G1[S]:S→pA|qBA→cAd|aB→dB|b若输入串W=pccadd。自顶向下的推导过程为:SApAc

dc

A

daS

=>pA

=>pcAd=>pccAdd

=>pccaddG1[S]有如下特点：(1)

每个产生式的右部由终结符开头;

(2)

同一非终结符的不同产生式的右部由不同的终结符开头。对于这种文法，在推导过程可以根据当前的输入符号唯一确定选哪个产生式往下推导，即分析过程是确定的。例2：设有文法G2[S]为:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS

=>Ap

=>cAp

=>ccAp该例说明，当产生式右部以终结符或非终结符开头（无空产生式）；同一非终结符的不同产生式的右部由不同的符号开头。对于这种文法，在推导过程选用哪个产生式不直观，关键是判断产生式右部推出的开始符号（集），分析过程可能是确定若输入串W=ccap,自顶向下的推导过程为：例3：设有文法G3[S]S→aA|dA→bAS|

εG3文法的特点是:包含空产生式对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集），分析过程可能是确定的。若输入串W=abd，自顶向下的推导过程为：Sa

Ab

A

Sε

dS

=>aA

=>abAS

=>abS

=>abd要进行确定的自顶向下的分析，文法要满足一定的限制——即文法是LL(1)文法。先研究三个定义开始符号集后跟符号集FOLLOW选择集合SELECT2

开始符号集

(α)的定义定义:设G=(VN,VT,P,

S)是上下文无关文法，()

=

{a|

*

a,

a∈

VT

,,

∈V*}若

*

ε

则规定ε

∈

()直观上说文法符号串

的开始符号集是由推导出的开头的终结符（包括ε）组成。集合构造方法对于文法G的任一符号串α=X1X2…Xn可按下列步骤(α)集合：(α)=φ(X1)中的一切非ε符号加进(α)；构造其置将若ε∈(X1)，将

(X2)中的一切非ε符号加(α)

；

若ε∈

(X1)

和(X3)中的一切非ε符号加进(X2)，将(α)；余此类进推。(Xi)，则将ε符号加4)若对于一切1≤i≤n，ε∈进

(α)。例文法G2[S]:S→ApS→BqA→aA→cAB→bB→dB(Ap)={a,c}(Bq)={b,d}={a

}(cA)={c}={b}(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后的那些终结符（包括#）组成。注意：在FOLLOW集合中无ε得d

∈FOLLOW(A)*例文法G3[S]:S→aA|dA→bAS|ε由S=>aA

得#∈FOLLOW(A)由S=*>abAS=*>abAaA

得a

∈FOLLOW(A)…

=*>abAd

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

得#∈FOLLOW(S)由S=>aA=>abAS=>abbASS=>abbASaA…=>abbASdFOLLOW(S)={#,a,d}说明：对于非终结符A的两个产生式A→bAS

和A→ε，当输入符号∈

(bAS)={b}时，选A→bAS推导，当输入符号∈FOLLOW(A)={#,a,d

}时，选A→ε推导。由于

(bAS)∩FOLLOW(A)=ф，所以可进行确定的自顶向下分析。对于文法中的符号A∈Vn，其FOLLOW(A)集合可反复应用下列规则计算，直到其FOLLOW(A)集合不再增大为止：1)

对于文法的开始符

#∈FOLLOW(S)2)若G中有形如A→αBβ

的产生式，且β

≠ε，则将(β)中的一切非ε符号加进FOLLOW(B)。3)

若G中有形如A→αB或A→αBβ

的产生式，且ε∈

(β)，则FOLLOW(A)中的全部元素均属于FOLLOW(B)。注意：在FOLLOW集合中无ε。4

选择集合SELECT(A→α)的定义定义对给定的上下文无关文法的产生式A→α，A∈VN，α∈V*，=(

(α)-{ε})∪FOLLOW(A)*若α≠>ε,则SELECT(A→α)=

(α)若α=*>ε,则SELECT(A→α)解释当A面对应输入符a，在自顶向下的分析中应选择这样的产生式A→进行推导：

()中包含a；此外若可能导出空串，A自动获得匹配，输入符a有可能与A后的一个符号匹配，所以当a应属于Follow(A)时，选择产生式A→也是可以的。直观上说某产生式A→α的选择集合是指遇到哪些输入符号（包括#）时选用该产生式向下推导。例G

[S]:3S→aAS→dA→bASA→εSELECT(S→aA)=SELECT(S→d)=SELECT(A→bAS)=(aA)={a}(d)={d}(bAS)={b}SELECT(A→ε)=FOLLOW(A)={#,a,d}(α)=(

(α)-{ε})∪FOLLOW(A)*若α≠>ε,则SELECT(A→α)=若α=*>ε,则SELECT(A→α)说明：同一非终结符的不同产生式A→α与A→β，若

SELECT(A→α)∩SELECT(A→β)=Φ，则一定可以进行确定的自顶向下分析5

LL(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.2

LL(1)文法的判别要判别一个上下文无关文法是否是LL(1)文法分为五步：求能推出ε的非终结符集计算每个产生式右部α的

(α)集计算每个非终结符A的FOLLOW(A)集计算每个产生式A→α的SELECT(A→α)集按LL(1)文法的定义判别求出能推出ε的非终结符集算法:用S表示能推出ε的非终结符集第一步令S={

Aj

| Aj→

ε

产生式集}对

每

个

产

生

式

p:

Ap→X1....Xn，

若X1....XnS，则S:=S

{Ap

}重复第二步的循环，直至S

收敛（不再变化）为止。例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c非终结符集S初值{A,B}第一次{A,B,S}第二次{A,B,S}收敛能推出ε的非终结符集为{A,B,S}2.

计算每个产生式右部α的

(α)集(X)首先对每一文法符号X

(XVT

VN)，求的算法:(A)={ε}(A)={}对每个产生式A→X1…Xj…Xn

做：= (A)

Section

(X1…Xj…Xn)对每个a

VT

：

(a)={

a

}对每个A

VN

：若A

*

ε

则否则其中

Section

(X1…Xj…Xn)=

(((X1)

-{ε})

((Xj)

-{ε})

(X2)-{ε})…(Xj+1)Xj+1是产生式右部中第一个不能推出ε的符号*若X1

≠>ε则Section

(X1…Xj…Xn)=

(X1)若X1…Xn全可推出ε则Section

(X1…Xn)=

(X1)∪…∪

(Xn)4.

重复3直到每个符号的

集合都不再增大为止。例

G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c已求出能推出ε的非终结符集为{A,B,S}集(0)集(1)集(2)集(3)Sεε

bε

b

aε

b

aAεε

bεbεbBεε

aεaεaCbb

a

cb

a

cDaca

cacaaaaabbbbb集求符号串的利用求出每个文法符号的集(X1)(Xj),(Xj)

-{ε})则=(∪(α)(X1)

-

{ε})

∪…∪((Xj+1)i3.

若对所有i

(1≤i≤n)，都有ε∈则

(α)=

(X1)∪…∪(Xn)设α=X1X2…Xn当X1不能=*>

ε

，则

(α)=若对任何j

(1≤j＜n）都有ε∈例G[S]

S→AB|bCA→b|εB→aD|εC→AD|bD→aS|c集合如下:(A)={b,

ε}(C)={a,b,c}已求出非终结符的(S)={a,b,

ε}(B)={a,

ε}(D)={a,c}产生式右部符号串的开始符集合为:(A)∪(B)∪{ε}={a,b,ε}(A)-{ε})∪(D)

={b,a,c}S→ABS→bCA→εA→bC→ADD→aS(AB)=(bC)=

{b}(ε)=

{ε}(b)={b}(AD)=((aS)=

{a}Follow(B)=Follow(B)

Follow(B)=Follow(B)((y)

否则(y)-{ε})

Follow(A)3.重复2，直至对所有NAV

，Follow(A)收敛为止。3．计*

算每个非终结符A的FOLLOW(A)集因为S=>S，显然#∈FOLLOW(S)对所有AVN

令Follow(A)={ };

对开始符S，

令Follow(S)={#

}对每条产生式A→xBy，

产生式右部的每一非终结符B，

x,y

∈V*，如果y不能推出ε若a∈FOLLO*

W(A),则表明S=*>…Aa…，由于A→xBy，且y=>ε,则有S*=>…Aa…=>…xBya=>…xBa…，即S=*>…xBa…,

所以a∈FOLLOW(B)即为：对于文法中的符号A∈Vn，其FOLLOW(A)集合可反复应用下列规则计算，直到其

FOLLOW(A)集合不再增大为止：1)

对于文法的开始符

#∈FOLLOW(S)2)若G中有形如A→αBβ

的产生式，且β

≠ε，则将(β)中的一切非ε符号加进FOLLOW(B)。3)

若G中有形如A→αB或A→αBβ

的产生式，且ε∈

(β)，则FOLLOW(A)中的全部元素均属于FOLLOW(B)。注意：在FOLLOW集合中无ε。例G[S]：[1]S→AB[2]S→bCA→bA→ε[5]B→aDB→εC→ADC→b[9]D→aS[10]D→c集合如下:(A)={b,

ε}(C)={a,b,c}已求出非终结符的(S)={a,b,

ε}(B)={a,

ε}(D)={a,c}Follow集(0)Follow集(1)Follow集(2)S＃＃＃Aa

#

ca

#

cB##C##D##4．计算每个产生式A→α的SELECT(A→α)集按定义计算SELECT(A→α)：(α)(α)-{ε})∪FOLLOW(A)若α

*

ε，则≠>SELECT(A→α)=若α=*>ε，则SELECT(A→α)=(例G[S]：S→AB|bCA→b|εB→aD|εC→AD|bD→aS|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}是否*

ε=>First集Follow集S是{a,

b,ε}{#}A是{b,ε}{a,

c,#}B是{a,ε}{#}C否{a,b,c}{#}D否{a,c}{#}5.

按LL(1)文法的定义判别产生式的select集如下:SELECT(S→AB)=

{b,a,#}SELECT(A→ε)=

{a,c,#}SELECT(B→ε)=

{#}SELECT(C→AD)=

{b,a,c}SELECT(D→aS)=

{a}SELECT(S→bC)=={b}SELECT(A→b)=

{b}SELECT(B→aD)={a}SELECT(C→b)

={b}SELECT(D→c)=

{c}由于SELECT(S→AB)∩SELECT(S→bC)={b}≠фSELECT(C→AD)∩SELECT(C→b)={b}≠ф所以文法G[S]不是LL(1)文法5.3

某些非LL(1)文法到LL(1)文法的等价变换非LL(1)文法含有左公共因子的文法若文法中含有形如：A→αβ|αr

的产生式，称文法含有左公共因子。显然,SELECT(A→αβ)∩SELECT(A→α

r)≠ф,文法不是LL(1)文法含有左递归的文法文法中只要含有下列形式的产生式（含有a或含有b或二者皆有）则称文法含有左递归：A→AβA→Bβ

B→Aα在a)中含有左递归的产生式，称为直接左递归；在b)中虽然没有含左递归的产生式，但A=>Bβ=>Aαβ即A+=>A…,称为间接左递归以直接左递归为例，若有如下产生式A→A

|

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

A→A)

)

(

A

)

(

)Select(

A→

))

(

)故A→A

和A→

的Select集相交，不是LL(1)文法。对非LL(1)文法进行等价变换提取左公共因子消除左递归注意：变换后的文法不一定是LL(1)文法，文法不含左递归和左公共因子只是LL(1)文法的必要条件。1

提取左公共因子将产生式A→αβ|αr

等价变换为:A→α(β|r)，将括号内用一新引入的非终结符A’表示,得A→αA’，A’→β|r一般形式：若A→αβ1|αβ2|…|αβn,提取左公共因子后变为A→αA’，A’→

β1|β2|…|βn若在βi中仍含有左公共因子,可再次提取.例文法G1：S→aSb|aS|ε提左因子得:S→aS(b|ε)|ε引进新的非终结符得:S→aSS’|εS’

→b|ε2.

消除左递归1)

消除直接左递归文法G:S→Sa|b可改写成S→bS’S’

→aS’|ε一般情形:含直接左递归的文法G：A→Aα1|Aα2|…|Aαm|β1|β2|…|βn消除左递归后改写成：A→β1A’|β2A’|…|βnA’A’→α1

A’|α2

A’|…|αm

A’|ε2)

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

→Aj…中的Aj最后，得到的左部为Ai的产生式若有直接左递归，则消除之3.去掉无用产生式。例

文法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’处理结果为：R→Sa|aS’

→abcS’|εQ→Sab|ab|bS→abcS’|bcS’|cS’

S’

→abcS’|ε由于Q，R是不可到达的非终结符，其产生式应删除。最终得文法G’：S→abcS’|bcS’|cS’

S’→abcS’|ε示例说明：当非终结符顺序为R，Q，S，消除左递归的最终结果为：S→abcS’|bcS’|cS’S’

→abcS’|ε若非终结符顺序为S，Q，R，则消除左递归的最终结果为：S→Qc|cQ→Rb|bR→bcaR’|caR’|aR’R’

→bcaR’|ε结论：当非终结符的排序不同时，结果的产生式形式不同，但它们是等价的。5.4

不确定的自顶向下分析思想不确定的自顶向下分析也称带回溯的自顶向下分析定义：不确定是指某个非终结符有多条产生式，而当前输入符无法唯一确定选用哪条产生式进行推导，只好逐个试探。当分析不成功时，则

分析退回到适当位置重新试探其余候选可能的推导，直到把所有可能的推导序列都试完仍不成功，才能确认输入串不是该文法的句子。A→ab|a，对输入串w=xay，推导例1设有文法

S→xAy树为Sx

A

yS

回溯

Sx

A

y

x

A

ya

baSx

A

y集交由于A的两条产生式：A→ab

和A→a

右部集不为空，从而引起回溯例2

文法G：S→aAS

S→b

A→bAS A→

ε输入串w=ab，推导树为:Sa

A

S回溯S

Sa

A

S

a

A

SSbASa

A

Sε

b由于A的产生式A→

ε右部能=>*

ε，且Follow(A)

∩ (bAS)

={b}≠ф

，从而引起回溯例3

文法G：S→Sa

S→b输入串w=baa，推导树为:SSbSbSSa回溯S回溯a

SaSaSSaSab由于文法含有左递归而引起回溯5.5

确定的自顶向下分析方法确定的自顶向下分析方法有：递归子程序法(recursive-descent

parser)分析法(predictive

parser)两种方法都要求文法是LL(1)文法。递归子程序法实现思想：对文法中的每个非终结符编写一个递归过程，识别由该非终结符推出的串。当非终结符有多条产生式时，按当前输入符属于哪条产生式的SELECT集可唯一确定选择哪个产生式进行匹配。当识别到终结符时，与当前输入符号匹配，并

下一输入符；当识别到非终结符时，则调用该非终结符相应的过程。例算术表达式文法GE→E+T│TT→T*F│FF→(E)│i1）消除左递归得

G':E'→+TE'│εT'→*FT'│εE→TE'T→FT'F→(E)│iSELECT(E'→+TE'

)

=

{

+

}SELECT(E'→ε

)=

{

),#

}SELECT(T→FT'

)

=

{

(,i

}SELECT(T'→*FT'

)

=

{

*

}SELECT(T'→ε

)

=

{

+,),#}SELECT(F→(E)

)

=

{

(}SELECT(F→

i

)

=

{

i

}G’是LL(1)文法1

判断是否可以应用递归子程序法2）求出G’的选择集合SELECT(E→TE'

)

=

{

(,i

}2构造文法G'的递归下降分析器定义：当一个文法满足LL(1)条件时，就为它构造一个不带回溯的自顶向下的分析程序，这个分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。组成：递归下降分析器由一个主程序MAIN和每个非终结符对应的一个递归过程组成。用到的一些子过程：过程GETNEXT负责读入下一个TOKEN字过程ERROR负责报告语法错误约定：变量TOKEN存放已读入的TOKEN字过程进入时变量TOKEN存放了一个待匹配的TOKEN字退出过程时，变量TOKEN中仍存放着一个待匹配的TOKEN字。非终结符相应的分析子程序的构造方法对于每个非终结符U，编写一个相应的子程序P(U);对于产生式U→x1

|x2

|…|xn，x1,...xn都≠ε关于U的子程序P(U)按如下方法构造：if

TOKEN

in (x1)

thenp(x1)(x2)

then

p(x2)(xn)

thenp(xn)else

if

TOKEN

inelse

…….if

TOKEN

inelse

ERROR3)如果U还有空产生式U→ε,则算法中的语句：(xn)

thenp(xn) else

ERRORif

TOKEN

in改写为if

TOKEN

in(xn)

then

p(xn)else

if

TOKENnot

in

follow(U)

then

ERROR4)对于符号串x=y1y2…yn；p(x)的含义为：begin

p(y1);p(y2);…;p(yn)

end如果yi∈VN，则P(yi)就代表调用yi的子程序；yi∈VT，则P(yi)为形如下述语句的一段程序if

TOKEN=yi

then

GETNEXT(TOKEN)

else

ERROR/*

主程序*/(1)

program

MAIN;beginGETNEXT

(TOKEN);E

(TOKEN);/*

转匹配E→TE'

*/if TOKEN

≠'#'

then

ERROR构造文法G’：

E→TE'E'→+TE'│εT→FT'T'→*FT'│ε

F→(E)│i

的递归下降分析器/*匹配E→TE'*//*转匹配T→FT'*//*转匹配E'→+TE'│ε*/end.(2)

procedure E

(TOKEN);beginT

(TOKEN);E’

(TOKEN)end;/*匹配E'→+TE'│ε*//*选择产生式E'→+TE'*/(3)

procedure E’

(TOKEN);beginif

TOKEN=’+’

thenbeginGETNEXT

(TOKEN);/*匹配’+’,读下一个TOKEN字*//*转匹配T→FT'*//*转匹配E'→+TE'│ε*/T(TOKEN);E’(TOKEN)endelse/*E’→ε对应的语句*/if TOKEN≠’)’

and

TOKEN≠’#’

then

ERRORend;/*

匹配T'→*FT'│ε

*//*

选择产生式T'→*FT'

*//*

匹配'*'，读下一TOKEN字*//*

转匹配F→(E)│i

*//*

转匹配T'→*FT'│ε

*//*

T‘→ε对应的语句*/if

TOKEN≠'+'

and

TOKEN≠')'

and

TOKEN≠'#'

then

ERRORend;/*匹配T→FT'*//*转匹配F→(E)│i*//*转匹配T'→*FT'│ε*/procedure T

(TOKEN);beginF

(TOKEN);T’

(TOKEN)end;procedure T'

(TOKEN);beginif TOKEN

=

'*'

thenbeginGETNEXT

(TOKEN);F

(TOKEN);T'

(TOKEN)endelse/*

匹配F→(E)│i

*//*选择产生式F→(E)

*/(6)

procedure F

(TOKEN);beginif TOKEN

=

'('

thenbeginGETNEXT(TOKEN);/*

匹配'('，读下一TOKEN字*/E

(TOKEN);

/*

转匹配E→TE'

*/if

TOKEN=')'

then GETNEXT

(TOKEN)/*

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

ERRORendelse/*

选择产生式F→i

*/if

TOKEN=‘i’

then GETNEXT

(TOKEN)else

ERRORend;特点：优点：简单直观、易于构造缺点：对文法要求高，必须满足LL(1)文法；递归调用多，速度慢，占用空间多实用性：许多高级语言，如Pascal、c等编译系统常常采用此方法。5.5.2分析方法一个分析器由三个部分组成：分析程序：控制分析过程的进行。分析栈：存放从文法开始符号出发的自顶向下推导过程中等待匹配的文法符号。开始时放入‘#’和文法开始符，结束时栈应是空的。分析表：是一张二维表，元素M[A,a]的内容是当非终结符A

输入符号a（终结符或句子括号＃）时应选取的产生式，当无产生式时，元素内容为转向出错处理。1.

构