安徽大学编译原理第五章 自顶向下语法分析方法

指导教师:杨建国二零零七年十一月编译原理词法分析内容回顾功能输入源程序，输出单词流手工设计词法分析器的主要工作正规式：定义词法规则把正规式描述的规则转化为NFANFA进行确定化得到DFA简化DFA通过程序实现DFA词法分析器的自动生成

Lex语法分析技术概况不确定的

自顶向下分析法递归下降分析法确定的预测分析法LL(1)语法分析方法简单优先分析法

优先分析法

算符优先分析法自底向上分析法

LR(0)分析法

LR分析法SLR(1)分析法

LR(1)分析法

LALR(1)分析法第5章自顶向下语法分析方法语法分析技术概况不确定的

自顶向下分析法递归下降分析法确定的预测分析法LL(1)语法分析方法简单优先分析法

优先分析法

算符优先分析法自底向上分析法

LR(0)分析法

LR分析法SLR(1)分析法

LR(1)分析法

LALR(1)分析法第5章第6章第7章1.自上而下语法分析的基本思想2.求FIRST、FOLLOW、SELECT集合的方法3.提取左公因子与消除左递归的方法4.递归下降分析程序的构造5.LL(1)文法的判定，分析表的构造与输入串的分析过程学习目标第一节确定的自顶向下分析思想第二节LL(1)文法的判别第三节某些非LL(1)文法到LL(1)文法的等价变换第四节不确定的自顶向下分析思想第五节确定的自顶向下分析方法第六节典型例题及解答教学内容知识结构由于正规式与正规文法是等价的，它们的描述能力有限，而高级程序语言的语法结构适合用上下文无关文法描述，因此我们把上下文无关文法作为语法分析的基础。

引言

1、语法分析的地位是编译程序的核心部分。2、语法分析的任务

识别由词法分析得出的单词序列是否是给定文法的句子。3、语法分析的理论基础上下文无关文法和下推自动机按照语法分析树的建立方法，我们可以粗略地把语法分析分成两类，一类是自顶向下分析法，另一类是自底向上分析法。自顶向下分析法：从文法的开始符号出发，通过推导过程试图产生与输入串匹配的句子。

从树根开始，往下构造语法树，直到建立每个树叶的分析方法。自底向上分析法：从输入串出发，通过归约过程试图归约到文法的开始符。

从语法树的末端开始，向上归约，直至根结点的分析方法。不论是哪一种方法，语法分析器都是自左向右地扫描输入字符串。4、语法分析的方法若Z

S则S

L(G[Z])否则S

L(G[Z])+G[Z]存在主要问题:

左递归问题回溯问题主要方法:

递归子程序法

LL分析法自顶向下分析算法的基本思想为：若Z

S则S

L(G[Z])否则S

L(G[Z])+G[Z]自底向上分析算法的基本思想为：存在主要问题:

句柄的识别问题主要方法:

算法优先分析法

LR分析法

自顶向下分析法通常分为确定的和不确定的两种，确定的分析方法对文法有一定限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，是目前常用的分析方法之一；相反，由于不确定的分析方法带有回溯，效率低、代价高，因而极少使用。一.确定分析的条件5.1确定的自顶向下分析思想从文法的开始符号出发，如能根据当前的输入符号（单词符号）唯一地确定选用哪个产生式进行推导，则分析是确定的。特征——根据下一个输入符号为当前要处理的非终结符选择产生式要求——文法是LL(1)的第一个L从左到右扫描输入串

第二个L

生成的是最左推导

向前看一个输入符号（lookahead)例1

设有文法G1[S]:

S→pA|qB

A→cAd|a

B→dB|b

若输入串W=pccadd。自顶向下的推导过程为:SSApcAdcAda=>pA=>pcAd=>pccAdd=>pccaddG1[S]有如下特点：每条产生式的右部由终结符开头;同一非终结符的不同产生式的右部由不同的终结符开头。

例2

设有文法G2[S]为:S→Ap|BqA→a|cAB→b|dBpAScAcAa=>ccapS=>cAp=>ccAp=>Ap该例说明:(1)产生式右部以终结符或非终结符开头（无空产生式）；(2)同一非终结符的不同产生式的右部由不同的符号开头。对于这种文法，在推导过程选用哪条产生式不直观，关键是判断产生式右部推出的开始符号（集），分析过程可能是确定的若输入串W=ccap,自顶向下的推导过程为：分析能确定推导原因：前提：2型文法中无空产生式在文法中，对于每个非终结符A的定义

A→α1|α2|...|αn

任给i,j(1≤i,j≤n,i<>j),从αi和αj推导出来的第一个终结符号集合(称为开始符号集FIRST)不相交,即:FIRST(αi)∩FIRST(αj)=Φ结论：在推导过程中完全可以根据向前看符号是属于哪条产生式右部的开始符号集合而决定选择相应的产生式进行推导，因此，分析过程是完全确定的。二.串

开始符号集FIRST

设G=(VT,VN,S,P)是2型文法，

FIRST(α)={a|α

aβ,a∈VT,α,β∈V*}

若αε，则规定ε∈FIRST(α)直观定义理解：

FIRST(α)={a｜αa……，a∈ＶT}FIRST(α)包含了α对应的串的所有可能的首终结符号集(选择产生式的依据)*

*

*

例3

文法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}由于同一非终结符的两个产生式的右部推导出来的开始符号集不相交，因此可根据当前输入符号属于哪条产生式右部的开始符号集而决定选哪条产生式进行推导，可以进行确定的自顶向下分析。例4

设有文法G3[S]S→aA|dA→bAS|ε若输入串W=abd，自顶向下的推导过程为：AaSbSAεd=>abd

S=>abAS=>abS文法的特点是:包含空产生式对于空产生式左部的非终结符，关键是判断该非终结符的后跟符号（集），分析过程可能是确定的。=>aA选择A的产生式的依据FIRST(bAS)={b}FIRST(ε)={ε}分析：无d，但若A为ε，则A的后面能推出d思考：若A有一条产生式能推出ε，则需要寻找什么？寻找A后面的符号串能否推出首字符是d的符号串，即：寻找紧跟在A后面的符号有哪些。设G=(VT,VN,S,P)是上下文无关文法，A∈VN,S是开始符号。

FOLLOW(A)={a|S

A且a∈FIRST(),

∈VT*,

∈V+}

若SA,且

ε，则规定#∈FOLLOW(A)直观定义理解：

FOLLOW(A)={a｜S…Aa…，a∈ＶT

}若S……A，则规定#∈FOLLOW(A)#作为输入串的结束符，或称为句子括号，如：

#输入串#FOLLOW(A)表示句型中可能紧跟在A后面的终结符号

*

*

*

*

*

三.非终结符A的后跟符号集FOLLOW例5

文法G3[S]:

S→aA|d

A→bAS|ε由SaA得#∈FOLLOW(A)

由SabAS

abAaA

得a∈FOLLOW(A) …abAd

得d∈FOLLOW(A)

FOLLOW(A)={#,a,d}由SS

得#∈FOLLOW(S)

由S=>aA=>abAS=>abbASS=>abbASaA…=>abbASd

FOLLOW(S)={#,a,d}*****说明：对于非终结符A的两个产生式A→bAS和A→ε:当输入符号∈FIRST(bAS)={b}时，选A→bAS推导;当输入符号∈FOLLOW(A)={#,a,d}时，选A→ε推导。由于FIRST(bAS)∩FOLLOW(A)=ф，所以可进行确定的自顶向下分析。当文法中含有形如

A→

A→

的产生式时，其中A∈VN，

，

∈V*，若

和不能同时推导出空，假定ε,

ε则当FIRST()∩(FIRST(

)∪FOLLOW(A))=Ø时，对于非终结符A的替换仍可惟一的确定候选。**四.选择集合SELECT(A→α)

假设A

是文法G的任一规则，定义规则A

的选择集合SELECT为：

SELECT(A

)=其中A∈VN，

∈(VN

VT)*FIRST(

) 若

(FIRST(

)-{

})FOLLOW(A)

若

*/*注：

SELECT集合中不能有ε解释

当A面对应输入符号a，在自顶向下的分析中应选择这样的产生式A→

进行推导：First(

)中包含a；此外若可能导出空串，A自动获得匹配，输入符a有可能与A后的一个符号匹配，所以当a应属于Follow(A)时，选择产生式A→

也是可以的。直观上说

某产生式A→α的选择集合是指遇到哪些输入符号（包括#）时选用该产生式向下推导。例6G3[S]:

S→aA

S→d

A→bAS

A→εSELECT(S→aA)=FIRST(aA)={a}SELECT(S→d)=FIRST(d)={d}SELECT(A→bAS)=FIRST(bAS)={b}SELECT(A→ε)=FOLLOW(A)={#,a,d}说明

同一非终结符的不同产生式A→α与A→β，若SELECT(A→α)∩SELECT(A→β)=Φ，则一定可以进行确定的自顶向下分析五.LL(1)文法1.定义

一个上下文无关文法G是LL(1)文法,当且仅当对G中每个非终结符A的任何两个不同的规则A→α|β，满足其中α、β中至多只有一个能推出ε串。SELECT(A→α)∩SELECT(A→β)=Φ

2.含义第一个L表示从左到右扫描输入串第二个L表示自上而下进行最左推导1表明只需向前看一个符号便可以决定选哪条产生式进行推导，类似地LL(k)文法需要向前看k个符号才可以确定选用哪个产生式。例7文法G[S]是否是LL(1)文法?

S→aA|d

A→bAS|ε

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)文法。例8

设文法G[S]为:

S→aAS|b

A→bA|ε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)文法。思考：输入串#ab#的推导？由于SELECT(A→bA)∩SELECT(A→ε)={b}≠Φ，所以文法G[S]不是LL(1)文法，当A遇输入符b时，不能确定选A→bA还是A→ε去推导。例9文法G[S]:

S→aAS|b

A→bA|ε对输入串w=ab进行推导：S

aAS

aS

abS

aAS

abAS

abS出错正确说明：只有是LL(1)文法，自顶而下方法分析才是确定的SELECT(S→aAS) ={a}

SELECT(S→b) ={b}

SELECT(A→bA) ={b}

SELECT(A→ε) ={a,b}五步判别法5.2

LL(1)文法的判别求能推出ε的非终结符集计算每个产生式右部α的FIRST(α)集计算每个非终结符A的FOLLOW(A)集计算每个产生式A→α的SELECT(A→α)集按LL(1)文法的定义判别注意：假定所给文法是经过压缩的（不包含多余规则）例10G[S]：S→AB|bC

A→b|ε

B→aD|ε

C→AD|b

D→aS|c1.求能推出ε的非终结符集首先建立一个一维数组X[]，它的大小是文法的非终结符个数，其数组元素为非终结符，对应每一非终结符有一标志位，用以记录能否推出ε，其值有三种：未定、是、否。（1）初始化置数组X[]中对应每一非终结符的标记为初值“未定”；（2）扫描文法中的产生式①删除右部含有终结符的产生式，假使以某一非终结符为左部的所有产生式都被删除，并将数组中对应该非终结符的标记值改为“否”，说明该非终结符不能推出ε；

②删除右部仅为ε的产生式，则将数组中对应该非终结符的标志置为“是”，说明该非终结符能推出ε；【注】本次扫描后仅剩下产生式左右均为非终结符的产生式算法：（3）扫描产生式右部的每一符号①若所扫描到的非终结符号在数组中对应的标志为“是”，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改“是”，并删除该非终结符为左部的所有产生式②若所扫描到的非终结符号在数组中对应的标志为“否”，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成“否”（4）重复（3）

直到扫描完毕数组中非终结符对应的特征再没有改变为止。非终结符SABCD初值第1次扫描第2次扫描未定未定未定未定未定是是否是否例10G[S]：S→AB|bC

A→b|ε

B→aD|ε

C→AD|b

D→aS|c2.计算每个产生式右部α的FIRST(α)集（1）定义法首先对每一文法符号X(X

VT

VN)，求FIRST(A)的算法:1.对每个a

VT，First(a)={a}2.对每个A

VN，若Aε，则First(A)={ε}

3.对每个A

VN，若有产生式A→a…,a∈VT,则First(A)={a}4.对每个产生式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)

∪{ε}5.重复4直到每个符号的FIRST集合都不再增大为止。*G[S]:S→AB|bC

A→b|ε

B→aD|ε

C→AD|b

D→aS|cbaacbacεaεbεbaFirst集(3)baacbεaεbεbFirst集(2)ba

εεεFirst集(1)ABCDabSabεεεFirst集(0)已求出能推出ε的非终结符集为{A,B,S}bbabacaacVT和能推出ε的VN右部以VT开头的左部VN右部全为VN的左部VN利用求出每个文法符号的FIRST集求符号串的FIRST集设α=X1X2…Xn当X1ε，则FIRST(α)=FIRST(X1)若对任何j(1≤j＜n）都有ε∈FIRST(Xj),且Xj+1不能导出空串，则

FIRST(α)=(FIRST(X1)-{ε})∪…∪(FIRST(Xj)-{ε})∪FIRST(Xj+1)若对所有i(1≤i≤n)，都有ε∈FIRST(Xi)，

则FIRST(α)=FIRST(X1)∪…∪FIRST(Xn)∪{ε}*已求出非终结符的First集合如下:First(S)={a,b,ε}First(A)={b,ε}First(B)={a,ε}First(C)={a,b,c}First(D)={a,c}产生式右部符号串的开始符集合为:S→AB FIRST(AB)=FIRST(A)∪FIRST(B)∪{ε}={a,b,ε}S→bC

FIRST(bC)={b}A→ε

FIRST(ε)={ε}A→b

FIRST(b)={b}C→AD FIRST(AD)=(FIRST(A)-{ε})∪FIRST(D)={b,a,c}D→aS

FIRST(aS)={a}（2）关系图法①每个文法符号对应图中一个结点，对应VT的结点时用符号本身标记，对应VN的结点用FIRST(A)标记。这里A表示VN②如果文法中有产生式A→VT，则从结点FIRST(A)到结点VT连一条箭弧③如果文法中有产生式A→αVNβ，且α

ε,则从结点FIRST(A)到结点FIRST(VN)连一条箭弧④凡是从FIRST(A)结点有路径可到达的VT结点所标记的VT都为FIRST(A)的成员由判别步骤1确定ε是否为某VN的FIRST集的成员，若是则将ε加入该VN的FIRST集中*FIRST(S)bcaFIRST(A)FIRST(B)FIRST(C)FIRST(D)FIRST(S)={b,a,ε}FIRST(A)={b,ε}FIRST(B)={a,ε}FIRST(C)={a,b,c}FIRST(D)={a,c}3.计算每个非终结符A的FOLLOW(A)集（1）定义法1.对所有A

VN令Follow(A)={};对开始符S，令Follow(S)={#}2.对每条产生式A→xBy，考察产生式右部的每一非终结符B，x,y∈V*，如果y不能推出εFollow(B)=Follow(B)∪First(y)

否则Follow(B)=Follow(B)∪(First(y)-{ε})∪Follow(A)3.重复2，直至对所有A

VN，Follow(A)不再扩大为止。若a∈FOLLOW(A),则表明S=>*…Aa…，由于A→xBy，且y=>*ε,则有

S=>*…Aa…=>…xBya=>…xBa…，即S=>*…xBa…,所以a∈FOLLOW(B)注：FOLLOW集合中不能有ε例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集(0)cFollow集(1)Follow集(2)初始化所有的VN求每条产生式右侧VN所有的后跟符号检查有没有遗漏的VN（2）关系图法①

文法G中的每个符号和“#”对应图中的一个结点，对应VT和“#”的结点用符号本身标记。对应VN的结点，则用FOLLOW(VN)或FIRST(VN)标记②

从结点FOLLOW(S)到“#”号结点连一条箭弧③

如果文法中有产生式A→αBβVN,且β

ε,则从结点FOLLOW(B)到结点FIRST(VN)连一条箭弧如果文法中有产生式A→αBβVT,且β

ε,则从结点FOLLOW(B)到结点VT连一条箭弧**如果文法中有产生式A→αBβ,且β

ε，则从结点FOLLOW(B)到结点FOLLOW(A)连一条箭弧对每一FIRST(A)结点如果有产生式A→αXβ,且

α

ε,则从结点FIRST(A)到结点FIRST(X)连一条箭弧凡是从结点FOLLOW(A)有路径可以到达的终结符或“#”号结点，其所标记的终结符或"#"号即为FOLLOW(A)的成员**FOLLOW(B)#caFIRST(D)FOLLOW(S)FOLLOW(A)FOLLOW(D)FOLLOW(C)FIRST(B)1.逐条产生式建立Follow与First的连接2.逐条产生式建立Follow与Follow的连接3.逐步画出First的有向弧步骤则得:FOLLOW(S)={#}FOLLOW(A)={a,c,#}FOLLOW(B)={#}FOLLOW(C)={#}FOLLOW(D)={#}自学：用关系矩阵法计算FIRST集和FOLLOW集4.计算每个产生式A→α的SELECT(A→α)集按定义计算SELECT(A→α)：若αε，则

SELECT(A→α)=FIRST(α)若αε，则

SELECT(A→α)=(FIRST(α)-{ε})∪FOLLOW(A)**例G[S]：

S→AB|bC

A→b|ε

B→aD|ε

C→AD|b

D→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,#}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}产生式的select集如下:SELECT(S→AB)={b,a,#} SELECT(S→bC)=={b}SELECT(A→ε)={a,c,#} SELECT(A→b)={b}SELECT(B→ε)={#} SELECT(B→aD)={a}SELECT(C→AD)={b,a,c} SELECT(C→b)={b}SELECT(D→aS)={a} 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)文法1.含有左公共因子的文法 文法中只要含有下列形式的产生式[含有a)或含有b)或二者皆有]则称文法含有左递归：

a)A→Aβ

b)A→Bβ

B→Aα

在a)中含有左递归的产生式，称为直接左递归； 在b)中虽然没有含左递归的产生式， 但A=>+Bβ=>Aαβ

即A=>+A…,称为间接左递归2.含有左递归的文法以直接左递归为例，若有如下产生式

A→A|A→其中和

为任意语法符号串。不难证明有下面关系式：

Select(A→A

)

First(A

)

First(

)

Select(A→)First(

)故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]:

S→aSb

S→aS

S→εS→aS(b|ε)

S→εS→aSAS→ε

A→bA→ε

G2[S]：

A→ad

A→Bc

B→aA

B→bBA→adA→aAcA→bBcB→aA

B→bBA→a(d|Ac)A→bBcB→aA

B→bBA→aA'A→bBcA'→dA'→AcB→aA

B→bBG3[S]:

S→aSd

S→Ac

A→aS

A→b1.化为：S→aSd

S→aScS→bc

A→aS

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

S→bc

A→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|dp|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)文法。如果我们在匹配输入串过程中，假定正好轮到要用非终结符U直接匹配输入串，即要用U的右部符号串U¨¨去匹配，为了用U¨¨去匹配，又得用U去匹配，这样无限的循环下去将无法终止。自顶向下分析为什么不能处理左递归文法？2.消除左递归例11

若文法G5的产生式为：（1）S

Sα（2）S

b所能产生的语言L={ban|n≥0},输入串baaaa#是语言的句子如果文法具有间接左递归，则也将发生上述只不过环的圈子兜得更大。要实行自顶向下分析，必须要消除文法的左递归，下面我们将介绍直接左递归的消除方法，在此基础上再介绍一般左递归的消除方法。（1）消除直接左递归将左递归规则改为右递归规则则可改写为：P→

P’

P’→

P’|ε

例12

已知G[E]：

E→T*F|T/F|F

T→F|T*F|T/F

解：左递归改为右递归得：

E→T*F|T/F|F

T→FT’T’→*FT’|/FT’|ε若：P→P

|

（2）消除间接左递归例13

S→Aa|b

A→Sd根源：最左循环依赖解决思路：试图改为单向依赖更改依赖方向基本方法：产生式代入，先把间接左递归转化为直接左递归S→Sda|b

再消除直接左递归S→bS’S’→daS’|ε

消除所有左递归的算法1.把G的非终结符整理成某种顺序A1，A2，……An

，使得：

A1

→δ1|δ2|……δkA2→A1r……A3

→A2u|

A1v…..…….2.for(i=1;i<=n;i++)for(j=1;j<=i-1;j++)

把每个形如Ai→Ajr的规则替换成

Ai→(δ1|δ2|……δk)r

其中Aj

→δ1|δ2|……δk是当前全部Aj

的规则消除Ai规则中的直接左递归

3.化简由2得到的文法即可。间接左递归直接左递归消除直接左递归一般左递归也可以通过改写法予以消除。（3）消除文法中一切左递归的算法删去从文法开始符号不可达的非终结符产生式。例14

文法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’ S’→abcS’|ε

处理结果为：R→Sa|a

Q→Sab|ab|b

S→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|c

Q→Rb|b

R→bcaR’|caR’|aR’

R’→bcaR’|ε结论：当非终结符的排序不同时，结果的产生式形式不同，但它们是等价的。5.4不确定的自顶向下分析思想不确定的自顶向下分析也称带回溯的自顶向下分析定义：

不确定是指某个非终结符有多条产生式，而面临当前输入符无法唯一确定选用哪条产生式进行推导，只好逐个试探。当分析不成功时，则推翻分析退回到适当位置重新试探其余候选可能的推导，直到把所有可能的推导序列都试完仍不成功，才能确认输入串不是该文法的句子。1.由于相同左部产生式的右部FIRST集交集不为空而引起回溯例15设有文法S→xAy，A→ab|a，对输入串w=xay，推导树为SxAySxAybaSxAy回溯aSxAy由于A的两条产生式：A→ab和A→a右部First集交集不为空，从而引起回溯2.由于相同左部非终结符的右部存在能导出ε的产生式，且该非终结符的FOLLOW集中含有其他产生式右部FIRST集的元素例16

文法G：S→aAS， S→b，A→bAS，A→ε

输入串w=ab，推导树为:SaAS回溯S

aASSaASSbASaASεb由于A的产生式A→ε右部能=>*ε，且Follow(A)∩First(bAS)={b}≠ф，从而引起回溯3.由于文法含有左递归而引起回溯例17

文法G：S→Sa，S→b输入串w=baa，推导树为:SSabSbSSa回溯回溯SSaSaSSaSab由于文法含有左递归而引起回溯5.5确定的自顶向下分析方法确定的自顶向下分析方法有：递归子程序法(recursive-descentparser)预测分析法(predictiveparser)

两种方法都要求文法是LL(1)文法。实现思想：

对文法中的每个非终结符编写一个递归过程，识别由该非终结符推出的串。当非终结符有多条产生式时，按当前输入符属于哪条产生式的SELECT集可唯一确定选择哪条产生式进行匹配。当识别到终结符时，与当前输入符号匹配，并读取下一输入符；当识别到非终结符时，则调用该非终结符相应的过程。5.5.1递归子程序法例18

算术表达式文法G

E→E+T│T T→T*F│F

F→(E)│i1）消除左递归得G'

E→TE'E'→+TE'│ε

T→FT'T'→*FT'│εF→(E)│i

2）求出G’的选择集合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}G’是LL(1)文法1判断是否可以应用递归子程序法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)按如下方法构造：

ifTOKENinfirst(x1)thenp(x1)elseifTOKENinfirst(x2)thenp(x2)else…….ifTOKENinfirst(xn)thenp(xn)elseERROR如果U还有空产生式U→ε,则算法中的语句：

ifTOKENinfirst(xn)thenp(xn)elseERROR改写为

ifTOKENinfirst(xn)thenp(xn)elseifTOKENnotin

follow(U)thenERROR对于符号串x=y1y2…yn；p(x)的含义为：

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

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

ifTOKEN=yithenGETNEXT(TOKEN)elseERROR(1)programMAIN;/*主程序*/beginGETNEXT(TOKEN);E(TOKEN);/*转匹配E→TE'*/ifTOKEN≠'#'thenERRORend.

例19

构造文法G’：E→TE’E’→+TE’│εT→FT’T’→*FT’│εF→(E)│i的递归下降分析器(2)procedureE(TOKEN);/*匹配E→TE'*/beginT(TOKEN); /*转匹配T→FT'*/E’(TOKEN)/*转匹配E'→+TE'│ε*/end;(3)procedureE’(TOKEN);/*匹配E'→+TE'│ε*/beginifTOKEN=’+’then/*选择产生式E'→+TE'*/beginGETNEXT(TOKEN);/*匹配’+’,读下一个TOKEN字*/T(TOKEN);/*转匹配T→FT'*/E’(TOKEN)；/*转匹配E'→+TE'│ε*/end else/*E’→ε对应的语句*/ ifTOKEN≠’)’andTOKEN≠’#’thenERROR end;Follow(E’)=Follow(E)={#,)}(4)procedureT(TOKEN);/*匹配T→FT'*/beginF(TOKEN);/*转匹配F→(E)│i*/T’(TOKEN)/*转匹配T'→*FT'│ε*/end;(5)procedureT'(TOKEN);/*匹配T'→*FT'│ε*/beginifTOKEN='*'then/*选择产生式T'→*FT'*/beginGETNEXT(TOKEN);/*匹配'*'，读下一TOKEN字*/F(TOKEN);/*转匹配F→(E)│i*/T’(TOKEN)；/*转匹配T'→*FT'│ε*/end else/*T’→ε对应的语句*/ifTOKEN≠'+'and

TOKEN≠')'andTOKEN≠’#’thenERRORend;Follow(T’)=Follow(T)=(First(E’)-{ε})∪Follow(E)={+,),#}(6)procedureF(TOKEN);/*匹配F→(E)│i*/begini