第五章自顶向下语法分析方法

第五章自顶向下语法分析方法课前思考为了了解自顶向下（自上而下）分析的一般过程和问题，首先回顾在“文法和语言”一章中介绍的有关基本概念：

句子、句型和语言的定义是什么？

什么叫最左推导？

什么叫最右推导和规范推导？

什么叫确定的自顶向下语法分析？

自顶向下语法分析是从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。

确定的自顶向下语法分析中用的是哪种推导？

在确定的自顶向下语法分析过程中，当以同一个非终结符为左部的产生式有多个不同右部时，如何选择用哪个产生式的右部替换当前的非终结符？

确定的自顶向下语法分析对文法有何限制？

2026/8/242学习目标确定的自顶向下分析方法虽对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。要求通过本章的学习后达到以下要求：

能够对一个给定的文法判断是否是LL(1)文法；

能构造预测分析表；

能用预测分析方法判断给定的输入符号串是否是该文法的句子；

能对某些非LL(1)文法做等价变换：

①消除左递归

②提取左公共因子

可能会变成LL(1)文法。这样可扩大自顶向下分析方法的应用。2026/8/243学习指南确定的自顶向下分析由于实现方法简单、直观、便于手工构造，因此，仍是目前常用的语法分析方法之一，尤其对小型编译器的实现较为适合。对初学编译技术的学员也较容易入门。确定的自顶向下分析要求文法是LL(1)的，所以，能否用确定的自顶向下分析方法构造语法分析器，首先必须对所给文法进行判断。由此构造LL(1)分析器的关键问题是对文法的LL(1)判别。而判断LL(1)文法时用到文法符号串的开始符号集合（FIRST集）和非终结符的后跟符号集合（FOLLOW集）的计算。本章的学习要求学员对给定的文法能熟练、准确地计算出产生式右部符号串的开始符号集合和每个非终结符的后跟符号集合，只有这两个集合的元素计算准确无误，才能对LL(1)文法的判断得出正确结论，从而正确构造LL(1)分析表。对非LL(1)文法的等价变换特别要注意的是：消除了左递归、提取了左公共因子后不一定就能满足LL(1)文法的条件。

2026/8/244难重点语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。本章将主要介绍确定的自顶向下分析思想和对文法的要求。确定的自顶向下分析要求文法满足LL(1)文法。本章主要介绍内容为：

LL(1)文法的定义和判别

非LL(1)文法的等价变换

确定的自顶向下分析方法

递归子程序法

预测分析方法

2026/8/2452026/8/246重点:

①LL(1)文法的定义和判别

②非LL(1)文法的等价变换

③预测分析方法

难点:

对一个文法如何判断是否是LL(1)文法，由于在判断LL(1)文法时用到文法符号串的开始符号集合（FIRST集）和非终结符后跟符号集合（FOLLOW集）的计算，而往往因概念不清或不够细心对这两个集合的计算常常出错，导致判断和分析结果的错误。知识结构2026/8/247句型、句子、语言的定义句型:

有文法G[S]，若Sx，且x∈V*则称x是文法G[S]的句型。

符号表示经过0步或若干步的推导。句子:

有文法G[S]，若Sx，且x∈VT*，则称x是文法G[S]的句子。例：G[S]：S→0S1，S→01

可有推导S0S100S11000S11100001111

说明00001111是G[S]的句子。最左（最右）推导：在推导的任何一步

(其中

、

是句型)，都是对

中的最左（右）非终结符进行替换。

最右推导被称为规范推导。

由规范推导所得的句型称为规范句型。句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。

从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。分析算法分类：自上而下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的最左推导。自下而上分析法：从输入符号串开始，逐步进行归约（最右推导的逆过程），直至归约到文法的开始符号。2026/8/249自上而下的语法分析自下而上的语法分析句型分析的有关问题

①如何选择使用哪个产生式进行推导？

假定要被替换的最左非终结符号是V，且左部为V的规则有n条：V→A1|A2|…|An，那么如何确定用哪个右部去替换V呢？

②如何识别可归约的串？

在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中寻找一个子串，看它是否能归约到文法的某个非终结符号，该子串称为“可归约串”。

5.1确定的自顶向下分析思想确定的自顶向下分析方法，首先要解决从某文法的开始符号出发，对给定的输入符号串如何根据当前的输入符号(单词符号)唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树。若能够推导出给定的输入符号串，或能构造出语法树其末端结点以从左向右的顺序连接正好为给定的输入符号串，则所给的输入符号串为该文法的句子。例5.1若有文法G1[S]:

S→pA|qB

A→cAd|a

B→dB|c

识别输入串w=pccadd是否是G1[S]的句子

试探推导过程：

SpApcAdpccAddpccadd

试探成功。

例5.1文法有以下两个特点：

①每个产生式的右部都由终结符号开始。

②如果两个产生式有相同的左部，那么它们的右部由不同的终结符开始。

对于这样的文法显然在推导过程中完全可以根据当前的输入符号决定选择哪个产生式往下推导，因此分析过程是唯一确定的。例5.2若有文法G2[S]:

S→Ap|Bq

A→a|cA

B→b|dB

识别输入串w=ccap是否是G2[S]的句子，那么试探推出输入串的推导过程为：

SApcApccApccap

试探推导成功。

例5.2文法的特点是：

①产生式的右部不全是由终结符开始。

②如果两个产生式有相同的左部，它们的右部是由不同的终结符或非终结符开始。

③文法中无空产生式。

定义5.1设G=(VT，VN，S，P)是上下文无关文法

FIRST(

)={a|

a

,a∈VT,

,

∈V*}

若

,则规定

∈FIRST(

)．称FIRST(

)为

的开始符号集或首符号集。

不难求出在例5.2文法G2中

FIRST(Ap)={a,c}

FIRST(Bq)={b,d}S→Ap|Bq

A→a|cA

B→b|dB对每一文法符号X∈V计算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;当Y1Y2…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)∪{

}例，对如下文法G，求各非终结符的开始符号集1）E→TE'2）E'→+TE'3）E'→ɛ4）T→FT'5）T'→*FT'6）T'→ɛ7)F→(E)8）F→i例5.3若有文法G3[S]:

(1)S→aA(2)S→d

(3)A→bAS(4)A→

识别输入串w=abd是否是G3[S]的句子

试探推导出abd的推导过程为：

SaAabAS

abSabd

试探推导成功。

定义5.2设G=(VT，VN，S，P)是上下文无关文法，A∈VN，S是开始符号

FOLLOW(A)=｛a|S

A

,且a∈VT,a∈FIRST(

),

∈VT*,

∈V+｝

若S

A

,且

,则#∈FOLLOW(A)。

这里我们用‘#’作为输入串的结束符，或称为输入串括号。也可定义为：FOLLOW(A)={a|S…Aa…,a∈VT}

若有S…A，则规定#∈FOLLOW(A)对文法中每一个A∈VN计算FOLLOW(A)

(a)设S为文法中开始符号，把{#}加入FOLLOW(S)中(这里“#”为句子括号)。

(b)若A→

B

是一个产生式，则把FIRST(

)的非空元素加入FOLLOW(B)中。

如果

则把FOLLOW(A)也加入FOLLOW(B)中。

(c)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。例，对如下文法G，求各非终结符的后跟符号集1）E→TE'2）E'→+TE'3）E'→ɛ4）T→FT'5）T'→*FT'6）T'→ɛ7)F→(E)8）F→i因此当文法中含有形如：

A→

和A→

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

,

∈V*，当

,

不同时推导出空时，设

,

,则当FIRST(

)∩(FIRST(

)∪FOLLOW(A))=φ时，对于非终结符A的替换仍可唯一地确定候选。定义5.3给定上下文无关文法的产生式A→

,A∈VN,

∈V*,若

,则SELECT(A→

)=FIRST(

)

如果

，则SELECT(A→

)=(FIRST(

)-{

})∪FOLLOW(A)

定义5.4一个上下文无关文法是LL(1)文法的充分必要条件是：对每个非终结符A的两个不同产生式，A→

，A→

，满足

SELECT(A→

)∩SELECT(A→

)=φ

其中

，

不同时能

LL（1）文法也可定义为:一个文法G是LL(1)的，当且仅当对于G的每一个非终结符Ａ的任何两个不同产生式A→

，下面的条件成立：1.FIRST(

)∩FIRST(

)=

，也就是

和

推导不出以同一个终结符a为首的符号串；它们应该都不能推出空字

．2.假若

，那么，FIRST(

)∩FOLLOW(A)＝，也就是，若

.则

所能推出的串的首符号不应在FOLLOW(A)中．结论：

LL(1)文法是无二义的．2026/8/2428LL(1)文法的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，'1'表明只需向右看一个符号便可决定选择哪个产生式(规则)进行推导，类似也可以有LL(K)文法，也就是需向前查看K个符号才可确定选用哪个产生式。通常采用K=1，个别情况采用K=2。

例5.3的文法G3[S]为：

S→aA

S→d

A→bAS

A→

不难看出由定义5.3可得：

SELECT(S→aA)=

SELECT(S→d)=

SELECT(A→bAS)=

SELECT(A→)=

所以SELECT(S→aA)∩SELECT(S→d)={a}∩{d}=φ

SELECT(A→bAS)∩SELECT(A→

)={b}∩{a,d,#}=φ

{a}{d}{b}{a,d,#}例5.4设文法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）文法，也就不可能用确定的自顶而下分析。对输入串W=ab的试探推导

S→aAS

S→b

A→bA

A→

5.2LL(1)文法的判别当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL(1)文法。因而我们对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。所谓文法是经过压缩的是指：

文法中不得含有有害规则和多余规则

有害规则：形如U→U的产生式。会引起文法的二义性

多余规则：指文法中任何句子的推导都不会用到的规则

①文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。

②文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。

含有①、②情况非终结符的产生式都为多余规则。

例5.5若文法G7[S]为：

S→AB

S→bC

A→

A→b

B→

B→aD

C→AD

C→b

D→aS

D→c判别步骤：1.求出能推出

的非终结符

首先建立一个以文法的非终结符个数为上界的一维数组，其数组元素为非终结符，对应每一非终结符有一标志位，用以记录能否推出

。其值有三种情况："未定"、"是"、"否"。计算能推出ε的非终结符步骤如下：①将数组X[]中对应每一非终结符的标记置初值为"未定"。非终结符SABCD初值未定未定未定未定未定②扫描文法中的产生式

(a)删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为"否"，说明该非终结符不能推出

。

(b)若某一非终结符的某一产生式右部为

，则将数组中对应该非终结符的标志置为"是"，并从文法中删除该非终结符的所有产生式。例中对应非终结符A、B的标志改为"是"。非终结符SABCD初值未定未定未定未定未定第一次扫描是是否③扫描产生式右部的每一符号。

(a)若所扫描到的非终结符号在数组中对应的标志是"是"，则删去该非终结符，若这使产生式右部为空，则对产生式左部的非终结符在数组中对应的标志改"是"，并删除该非终结符为左部的所有产生式。

(b)若所扫描到的非终结符号在数组中对应的标志是"否"，则删去该产生式，若这使产生式左部非终结符的有关产生式都被删去，则把在数组中该非终结符对应的标志改成"否"。④重复③，直到扫描完一遍文法的产生式，数组中非终结符对应的特征再没有改变为止。2.计算FIRST集①根据定义计算

由定义5.1对每一文法符号X∈V计算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;当Y1Y2…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)∪{

}由此可计算出文法G7[S]各非终结符的FIRST集FIRST(S)={FIRST(A)-{

}}∪{FIRST(B)-{

}}∪{

}∪{b}={b,a,

}

FIRST(A)={b}∪{

}={b,

}

FIRST(B)={

}∪{a}={a,

}

FIRST(C)={FIRST(A)-{

}}∪FIRST(D)∪FIRST(b)={b,a,c}

FIRST(D)={a}∪{c}={a,c}

所以最终求得：

FIRST(S)={a,b,

}

FIRST(A)={b,

}

FIRST(B)={a,

}

FIRST(C)={a,b,c}

FIRST(D)={a,c}求出每个文法符号的FIRST集合后也就不难求出每一个符号串的FIRST集合。若符号串

∈V*,

=X1X2…Xn,当X1不能推出

,则置FIRST(

)=FIRST(X1)。若对任何j(1≤j≤i-1，2≤i≤n),

∈FIRST(Xj),则

FIRST(

)=(FIRST(Xj)-{

})∪FIRST(Xi)当所有FIRST(Xj)(1≤j≤n)都含有{

}时，则FIRST(

)=(FIRST(Xj))∪{

}每个产生式的右部符号串的开始符号集合为：

FIRST(AB)={a,b,

}

FIRST(bC)={b}

FIRST(

)={

}

FIRST(b)={b}

FIRST(aD)={a}

FIRST(AD)={a,b,c}

FIRST(b)={b}

FIRST(aS)={a}

FIRST(c)={c}

②由关系图法求文法符号的FIRST集

由关系图法求得文法非终结符的FIRST集结果如下：

FIRST(S)={b,a,

}

FIRST(A)={b,

}

FIRST(B)={a,

}

FIRST(C)={a,b,c}

FIRST(D)={a,c}3.计算FOLLOW集①根据定义计算

对文法中每一A∈VN计算FOLLOW(A)

(a)设S为文法中开始符号，把{#}加入FOLLOW(S)中(这里“#”为句子括号)。

(b)若A→

B

是一个产生式，则把FIRST(

)的非空元素加入FOLLOW(B)中。

如果

则把FOLLOW(A)也加入FOLLOW(B)中。

(c)反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。现计算文法G7[S]各非终结符的FOLLOW集。

FOLLOW(S)={#}∪FOLLOW(D)

FOLLOW(A)=(FIRST(B)-{

})∪FOLLOW(S)∪FIRST(D)

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)={#}用关系图法求非终结符的FOLLOW集

4.计算SELECT集每个产生式的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→

)=(FIRST(

)-{ɛ})∪FOLLOW(B)={#}

SELECT(B→aD)=FIRST(aD)={a}

SELECT(C→AD)=FIRST(AD)={a,b,c}

SELECT(C→b)=FIRST(b)={b}

SELECT(D→aS)=FIRST(aS)={a}

SELECT(D→c)=FIRST(c)={c}由以上计算结果可得相同左部产生式的SELECT交集为：

SELECT(S→AB)∩SELECT(S→bC)={b,a,#}∩{b}={b}≠φ

SELECT(A→

)∩SELECT(A→b)={a,c,#}∩{b}=φ

SELECT(B→

)∩SELECT(B→aD)={#}∩{a}=φ

SELECT(C→AD)∩SELECT(C→b)＝{b,a,c}∩{b}＝{b}≠φ

SELECT(D→aS)∩SELECT(D→c)={a}∩{c}＝φ

5.3某些非LL(1)文法到LL(1)文法的等价变换前面指出确定的自顶向下分析要求对给定语言的文法必须是LL(1)形式。然而，不一定每个语言都有LL(1)文法。对一个语言的非LL(1)文法是否能变换为等价的LL(1)形式以及如何变换是本节讨论的主要问题。由LL(1)文法的定义可知若文法中含有直接或间接左递归，或含有左公共因子则该文法肯定不是LL(1)文法。因而，我们设法消除文法中的左递归，提取左公共因子对文法进行等价变换，在某些特殊情况下可能使其变为LL(1)文法。1.提取左公共因子若文法中含有形如：A→

|

的产生式，这导致了对相同左部的产生式其右部的FIRST集相交，也就是SELECT(A→

)∩SELECT(A→

)≠φ，不满足LL(1)文法的充分必要条件。现将产生式A→

|

进行等价变换为：

A→(|)

其中'('，')'为元符号，可进一步引进新非终结符A'，去掉'('，')'使产生式变换为：

A→

A'

A'→

|

写成一般形式为：

A→

1|

2|…|

n，提取左公共因子后变为：

A→

(

1|

2|…|

n)，再引进非终结符A'，变为：

A→

A'

A'→

1|

2|…|

n

若在

i、

j、

k…(其中1≤i，j，k≤n)中仍含有左公共因子，这时可再次提取，这样反复进行提取直到引进新非终结符的有关产生式再无左公共因子为止。

例5.6若文法G1的产生式为：

(1)S→aSb

(2)S→aS

(3)S→

请提取文法中的左公因子。

对产生式(1)、(2)提取左公因子后得：

S→aS(b|

)

S→

进一步变换为文法G'1：

S→aSA

A→b

A→

S→

例5.7若文法G2的产生式为：

(1)A→ad

(2)A→Bc

(3)B→aA

(4)B→bB

请提取文法中的隐式左公因子。

(1)A→ad

(2)A→aAc

(3)A→bBc

(4)B→aA

(5)B→bB

提取产生式(1)、(2)的左公共因子得：

A→a(d|Ac)

A→bBc

B→aA

B→bB引进新非终结符A'，去掉'('，')'后得G'2为：

(1)A→aA'

(2)A→bBc

(3)A'→d

(4)A'→Ac

(5)B→aA

(6)B→bB例5.8若有文法G3的产生式为：

(1)S→aSd

(2)S→Ac

(3)A→aS

(4)A→b用产生式(3)、(4)中右部替换产生式(2)中右部的A，文法变为：

(1)S→aSd

(2)S→aSc

(3)S→bc

(4)A→aS

(5)A→b对(1)、(2)提取左公共因子得：

S→aS(d|c)

引入新非终结符A'后变为：

(1)S→aSA'

(2)S→bc

(3)A'→d|c

(4)A→aS

(5)A→b例5.9若有文法G4的产生式为：

(1)S→Ap|Bq

(2)A→aAp|d

(3)B→aBq|e用(2)、(3)产生式的右部替换(1)中产生式的A、B使文法变为：

(1)S→aApp|aBqq

(2)S→dp|eq

(3)A→aAp|d

(4)B→aBq|e对(1)提取左公共因子则得：

S→a(App|Bqq)

再引入新非终符S'结果得等价文法为：

(1)S→aS'

(2)S→dp|eq

(3)S'→App|Bqq

(4)A→aAp|d

(5)B→aBq|e由上面所举例子可以说明以下问题：

①不一定每个文法的左公共因子都能在有限的步骤内替换成无左公共因子的文法，上面文法G4就是如此。

②一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL(1)文法，否则还需用LL(1)文法的判别方式进行判断才能确定是否为LL(1)文法。

2.消除左递归设一个文法含有下列形式的产生式。

1)A→A

A∈VN,

∈V*

2)A→B

B→A

A,B∈VN,

,

∈V*

可称含1)中产生式的文法为含有左递归的规则或称直接左递归的。含2)中产生式的文法有AA…则称文法中含有左递归或间接左递归，文法中只要含有1)或含有2)的产生式或二者皆有均认为文法是左递归的，然而，一个文法是左递归时不能采用自顶向下分析法。例5.10所能产生的语言L=｛ban|n≥0｝，对输入串baaaa#是该语言的句子，但用自顶向下分析时可看出当输入符为b时，为与b匹配则应选用S→b来推导，但这样就推不出后边部分，而若用S→Sa推导则出现右图的情况，无法确定到什么时候才用S→b替换另一方面，用递归子程序法时，在处理S的过程中，没有对当前输入符号匹配就又进入递归调用处理S的过程，这样就会造成死循环。文法G5含有直接左递归：

S→Sa

S→b例5.11含有间接左递归的文法G6为：

(1)A→aB

(2)A→Bb

(3)B→Ac

(4)B→d若有输入串为adbcbcbc#，a)消除直接左递归把直接左递归改写为右递归，如对文法G5：

S→Sa

S→b

可改写为：

S→bS'

S'→aS'|

改写后的文法和原文法产生的语言句子集都为：｛ban|n≥0｝。一般情况下，假定关于A的全部产生式是：

A→A

1|A

2|…|A

m|

1|

2|…|

n

其中,

i(1≤i≤m)不等于

,

j(1≤j≤n)不以A开头，消除直接左递归后改写为：

A→

1A'|

2A'|…|

nA'

A'→

1A'|

2A'|…|

mA'|

例：文法G：(1)E→E+T|T(2)T→T*F|F(3)F→(E)|i转化为G'：(1)E→TE'E'→+TE'|ɛ(2)T→FT'T'→*FT'|ɛ(3)F→(E)|i例：文法G：P→PaPb|BaP转化为：(1)P→BaPP'(2)P'→aPbP'|ɛ注：只有最左边的P参加变换b)消除间接左递归

对于间接左递归的消除需先将间接左递归变为直接左递归，然后再按a)消除直接左递归。

练习以文法G6为例：

(1)A→aB

(2)A→Bb

(3)B→Ac

(4)B→d

消除文法中的左递归，并检验改写后的文法是否为LL(1)文法。用产生式(1)、(2)的右部代替产生式(3)中的非终结符A得到左部为B的产生式为：

(1)B→aBc

(2)B→Bbc

(3)B→d

消除左递归后得：

B→(aBc|d)B'

B'→bcB'|ε

再把原来其余的产生式A→aB，A→Bb加入，最终文法为：

(1)A→aB

(2)A→Bb

(3)B→(aBc|d)B'

(4)B'→bcB'|

可以检验改写后的文法不是LL(1)文法。

c)消除文法中一切左递归的算法。

对文法中一切左递归的消除要求文法中不含回路即无AA的推导。满足这个要求的充分条件是，文法中不包含形如A→A的有害规则和A→

的空产生式。算法步骤：

1)把文法的所有非终结符按某一顺序排序；

如A1，A2，…，An

2)从A1开始消除左部为A1的产生式的直接左递归，然后把左部为A1的所有规则的右部逐个替换左部为A2右部以A1开始的产生式中的A1，并消除左部为A2的产生式中的直接左递归。继而以同样方式把A1，A2的右部代入左部为A3右部以A1或A2开始的产生式中，消除左部为A3的产生式之直接左递归，直到把左部为A1，A2，…,An-1的右部代入左部为An的产生式中，从An中消除直接左递归。

3)去掉无用产生式。上述算法归结为：

若非终结符的排序为A1，A2，…，An。

FORi∶=1TONDO

BEGIN

FORj∶=1TOi-1DO

BEGIN

若Aj的所有产生式为：

Aj→

1|

2|…|

k

替换形如Aj→Ajr的产生式变为：

Ai→

1r|

2r|…|

kr

END

消除Ai中的一切直接左递归。

END

最后删除无用产生式。

例如，有文法的产生式为：

(1)S→Qc|c

(2)Q→Rb|b

(3)R→Sa|a若非终结符排序为S、Q、R,左部为S的产生式(1)无直接左递归，(2)中右部不含S，所以把(1)右部代入(3)得：

(4)R→Qca|ca|a

再将(2)的右部代入(4)得：

(5)R→Rbca|bca|ca|a

对(5)消除直接左递归得：

R→(bca|ca|a)R'

R'→bcaR'|

最终文法变为：

S→Qc|c

Q→Rb|b

R→(bca|ca|a)R'

R'→bcaR'|

注：1）若非终结符排列顺序不同，改写后的文法也不同，但他们是等价的2）开始符号不能改变5.4不确定的自顶向下分析思想1.由于相同左部的产生式的右部开始符号集合交集不为空而引起回溯若有文法G:

S→xAy

A→ab|a

若当前输入串为xay2.由于相同左部非终结符的右部存在能ε的情况且该非终结符的后跟符号的集合中含有其它右部开始符号集合的元素。若有文法G:

(1)S→aAS

(2)S→b

(3)A→bAS

(4)A→ε

对输入串ab#的试探推导

3.由于文法含有左递归而引起回溯若有文法G:

(1)S→Sa

(2)S→b

若推导baa#5.4确定的自顶向下分析方法5.4.1递归子程序法递归子程序法是比较简单直观易于构造的一种语法分析方法。它要求文法满足LL(1)文法。它的实现思想是对应文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选时能够按LL(1)形式可唯一地确定选择某个候选进行推导。

由于递归子程序法对每个过程可能存在直接或间接递归调用，所以对某个过程在退出之前可能又被调用，因此有些信息需要保留，通常在入口时需保留某些信息，出口时需恢复。由于递归过程是遵循先进后出规律，所以通常开辟先进后出栈来处理。

5.4.2预测