前面我们提到过可以用一张图表示一个句型的推导，这种表示称为语法分析树，

或简称为语法树。语法树有助于理解一个句子语法结构的层次。语法树通常表示成一棵倒立的树，根在上，枝叶在下。语法树的根结由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生出下一代新结，候选式中自左至右的每个符号对应一个新结，并用这些符号标记其相应的新结。每个新结和其父结间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型。例如，对于文法(2.1)，关于(i*i+i)的推导(2.2)的语法树如图2.2所示。

E(根) （ E ） E + E E * E i i i 图2.2 语法树

这就是说，一棵语法树表示了一个句型种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。这样的一棵语法树是这些不同推导过程的共性抽象，是它们的代表。

如果我们坚持使用最左(最右)推导，那么，一棵语法树就完全等价于一个最左(最右)推导，这种等价性包括树的步步成长和推导的步步展开之间的完全一致性。但是，一个句型是否只对应唯一的一棵语法树呢?也就是，它是否只有唯一的一个最左(最右)推导呢?不尽然。 3.1.3 形式语言鸟瞰

前面乔姆斯基把文法分成四种类型，即0型，1型，2型，和3型。0型强于1

型，1型强于2型，2型强于3型。这几类文法的差别在于对产生式施加不同的限制。

0型文法：也称短语文法，其能力相当于图灵机。任何0型语言都是递归可枚举

的，反之，递归可枚举集必定是一个0型语言。

1型文法：也称上下文有关文法，对非终结符进行替换时务必联系上下文，并且

一般不允许替换成空串。

2型文法：也称上下文无关文法

3型文法：也称右线性文法，这类文法等价于正规式，所以也称正规文法。只有

下面两种形式的产生式：A→Ba 或A→a。 3.2.1文法等价的概念：

若L(G1)=L(G2),则称文法G1和G2是等价的

例如：下列两个文法是等价的

G1[A]: A 0R A 01 R A1 G2[A]：S 0S1 S 01 因为L(G1)=L(G2)={0n1n|n ≥1}

13

定义：对文法进行变换，使变换后的文法满足某种要求并于原文法等价，这种变换成

为文法的等价变换。 3.2.2、增广文法 定义：设文法G[S]={VN,VT,P,S}，构造文法G‘[S‘]=(VN∪{S‘},VT,P‘,S‘),其中，P‘={A

α|A α ∈P}∪{S‘ S},显然L(G)= L(G‘)，称G‘为文法G的增广文法。 例：[Z]:Z →abZA|a A→b

经等价变换后可得到增广文法G[A?]: Z‘ →Z

Z →abZA|a A→b

3.2.3、提取左因子 定义：若文法中有产生式P→δβ1|δβ2|…|δβn,则称该文发含有左因子δ。其中

P ∈VN ，β1，β2… βn ∈ (VN∪ VT)*。 例：文法[S]: S →iEtS|iEtSeS|a E →b 提取左因子该文法变为： G[S]: S →iEtSS‘|a S‘ →eS|ε E →b 3.2.4、消除左递归

定义：若文法中存在推导：P ?+ Pα,则称该文法含有左递归。若存在产生式P ? P

α,则称该文法含有直接左递归。若存在产生式P ? P1α，P1 ?P2β, ……,Pn-1 ?Pnγ，Pn ? Pδ,则称该文法含有间接左递归。其中P,P1, …,Pn ∈ VN, α, β, γ,δ ∈ (VN∪ VT)*。 直接左递归的消除方法：

假设非终结符P存在产生式P ?Pα|β 删除左递归产生式P ?Pα

引入新的非终结符P‘消除文法中的左递归，得： P ?βP‘ P‘ ?αP‘|ε

间接左递归的消除方法：

将间接左递归转化为直接左递归； 消除直接左递归；

化简文法，删除含有从起始符号无法到达的非终结符的产生式 最后，作为描述程序语言的上下文无关文法，我们对它有几点限制。

（1）文法中不含任何下面形式的产生式： P→P因为这种产生式除了产生二义性

外没有任何用处。

（2）每个非终结符P必须有用处。这一方面意味着，必须存在含P的句型；也就是，从开始符号出发，存在推导 S?*?P?.

另一方面意味着，必须存在终结符串??VT*,使得P?+?；也就是，对于P不存在

永不终结的回路。

我们以后所讨论的文法均假定满足上述两条件。

14

授课题目（教学章、节或主题）： 第三章 语法分析——自上而下分析 课时安排 12 第4周 第3-6节 授课时间 第6周 第1-6节 第7周 第1-2节

教学目的、要求（分掌握、熟悉、了解三个层次）： 了解确定的自顶向下分析思想 熟悉某些非LL（1）文法到LL（1）文法的等价变换 掌握LL（1）文法的判别、确定的自顶向下分析方法 教学重点和难点：语法分析器的功能、确定的自顶向下分析思想、LL（1）文法的判别、某些非LL（1）文法到LL（1）文法的等价变换、不确定的自顶向下分析思想、确定的自顶向下分析方法 授课类型（请打√）：理论课? 讨论课□ 实验课? 练习课? 其他□ 教学方式（请打√）：讲授? 讨论□ 示教□ 指导? 其他□ 教学资源（请打√）：多媒体? 模型□ 实物□ 挂图□ 音像□ 其他□ 讨论、思考题、作业： P81：1，2，4 教学内容

第三章 语法分析——自上而下分析

3.1 语法分析器的功能

语法分析器：是这样的一个程序，它将按文法的产生式，识别输入符号串是否为

一个句子。输入串是指由单词符号（文法的终结符）组成的有限序列。

语法分析的方法：可大致分为两类，一类是自下而上分析法，另一类是自上而下分析法。所谓自下而上分析法就是从输入串开始，逐步进行?归约?，直至归约到文法的开始符号。自上而下分析过程恰好与此相反，它从文法的开始符号出发，反复使用各种产生式，寻找?匹配?于输入串的推导。 3.2 自上而下分析面临的问题

本节主要是通过例子使我们认识到，作自上而下分析所遇到的主要困难是语法的左递归性使分析陷入无限循环；回溯的不确定性，要求我们将已经完成工作推倒重来，为解决这些问题我们要消除左递归和消除回溯。 3.3 LL(1)分析法

自上而下分析方法不允许文法含有任何左递归。为构造不带回溯的自上而下分析算法，首先要消除文法的左递归性，并找出克服回溯的充分必要条件。 3.3.1 左递归的消除

假定关于非终结符P的规则为 :P--> P|αβ

15

其中，每个 都不以P开头，那么我们可以把P的规则改写成如下的非直接左递归形式：

p --βp'

p'-- αp'|ε(ε 为空字)

这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。 3.3.2 消除回溯、提左因子

我们首先来看一下在不得回溯的情况下对于文法有什么要求。前面已经说过，欲实行自上而下的分析，文法不得含左递归。令G是一个不含左递归的文法，对G 的所有的非终结符号的每个候选?定义它的终结首符集FIRST(?)为：

FIRST(?)={a|??*a…,a?VT}

特别是，若??*ε，则规定ε?FIRST(?)。换句话说FIRST(?)是?的所有可能推导的开头终结符或可能的ε。如果非终结符A的所有候选首符集两两不相交，即A

的

任

何

两

个

不

同

的

候

选

?i

和

?j

FIRST(?i)?FIRST(?j) = ?那么，当要求A匹配输入串时，A 就能根据它所面临的第一个输入符号a，准确地指派某个候选前去执行任务。这个候选就是那个终结首符集含a的?。

如何把一个文法改造成任何终结首符集的所有候选首符集两两不相交呢？其办法是提取公共左因子。例如，假定关于A 的规则是

A???1|??2|…|??n|?1|?2|… |?m （其中每个?不以?开头）那么，可以把这些规则改写成：A??A‘|?1|?2|… |?m

A‘?|?1|?2|…|?n

3.3.3 LL(1)分析条件

假定S是文法G的开始符号，对于任何非终结符A我们定义：

FOLLOW(A) = { a | S?*…Aa…,a?VT}

特别是，若S?*…A， 则规定#?FOLLOW(A). 也就是说，FOLLOW(A)是所有句型中出现在紧接A之后的终结符或者?#‘。判断某给定文法是否为LL(1)文法其条件为：

（1）文法不含左递归。

（2）对于文法中每个非终结符A的各个产生式的候选首符集两两不相交。

即，若 A?a1 | a2 |…| an 则： FIRST(?i)?FIRST(?j) = ?（i?j ）

(3) 对文法中每一个终结符A，若它存在某个候选首符集包含ε，则

FIRST(A) ?FLLOW(A)= ?一个文法若满足以上条件，则称该文法G为LL(1)文法

16