1
第二章 前后文无关文法和语言
? 编译过程是十分复杂的信息加工过程，加工对象是用
高级语言编写的程序。
? 为完成编译工作，需解决两个问题,
– 如何确切地描述和定义一种程序设计语言
– 如何识别和分析这种语言
? 在 20世纪 50年代,N.Chomsky首先对语言的描述问题
进行了探讨。他提出了一种用来描述语言的数学系统，
并以此定义了四类性质不同的语言，称为 语言（文法）
的 Chomsky分类 。
? 人们把用一组数学符号和规则来描述语言的方式称为
形式描述，把所用的数学符号和规则称为 形式语言 。
2
形式语言与自动机
?此后，对 形式语言 以及识别语言的 自动机 的理
论与应用展开了深入研究，并取得了丰硕成果，
这些成果对编译理论、信息工程、人工智能以
及数理语言学、计算语言学产生了深远影响。
?目前,形式语言与自动机理论 已成为计算机科
学中的一个重要分支。
?本章将初步介绍形式语言中的某些基本概念和
知识，重点是与编译技术密切相关的一些术语
和概念，诸如 文法, 语言, 句子, 句型, 短语,
句柄 以及 句型分析 等。
3
2.1 文法及语言的表示
? 据统计，在世界各地，人们所使用的语言达 2700多种。
? 什么是语言？
– Webster的定义：, 为相当大地区的公众所懂得并
使用的 ‘ 话 ’,以及组成这些 ‘ 话 ’ 的方法的统一
体,
– 上述定义对于建立语言的数学理论而言不够精确。
? 另一定义：, 某一字母表上符号串（句子）的集合,
? 仍需进一步精确化,
1）为所定义的句子 提供一种结构性的描述（ 语法规则 ） ；
2）再提供一种手段，以便 能准确地判别什么是该语言中
的正确句子（ 即识别方法、分析方法等 ） 。
4
2.1 文法及语言的表示（ 续 ）
? 如果能刻画出一种语言的所有句子，也就定义出了这
种语言。
? 遗憾的是，对于自然语言来说，目前尚无能够完全刻
画一语言全部句子的结构的方法。
? 然而，对大多数程序设计语言（或者形式语言）来说，
此问题已被解决。 1960年,P.Naur & J.Backus首先用
BNF（ Backus-Naur-Formal（范式））对 ALGOL语
言进行了描述。
? 应指出,BNF成功地解决了程序设计语言的语法描述
问题，但描述其语义，还必须借助自然语言。
5
2.1 文法及语言的表示（ 续 ）
?通常，可用如下方式表示或定义一种语言,
（ 1）若语言的句子有限时，可用 枚举法 。例如，只含两
个句子的语言, {“I am a teacher”,“You are
students”};
（ 2）制定 有限条规则,用于产生所要描述的语言的全部
句子（可无限多），这些规则构成了该语言的 文法 。
（ 3）设计一种装置（ 算法或过程）,它以某字母表上的
符号串为输入，判别该符号串是否为所描述语言的句
子。此装置称为 自动机。
6
2.2 文法和语言的定义
2.2.1 基本概念和术语
1。 符号表（或符号集） 由若干符号组成的有限
非空集合。如 {a,b,c,S,T,*,+,;,.,8,$}
2。 符号串 用符号表中的符号所组成的任何有限
序列。
符号串的长度 = 符号串中所含符号的个数
例,aba的长度为 3。记为,|aba|=3
空串 不含任何符号的符号串，记为 ? 。显然,|
? |= 0。
7
2.2.1 基本概念和术语（ 续 ）
3。 符号串的前（后）缀及子串
设 ?,?,?,x是符号串，若 x= ???,则 ?,? 和 ? 都是 x的 子串；
当 ?= ? 时，称 ?是 x的 前缀 。 当 ?= ?时，称 ?是 x的 后缀。
x的任何前缀或后缀都是 x的子串，反之不成立。
?和 x本身既是 x的前缀和后缀,也是 x的子串 。
4。 符号串的连接和方幂
连接 设 x,y是符号串，将 y直接地拼接到 x之后
所得的新符号串称为 x与 y的连接，记为 xy
8
2.2.1 基本概念和术语（ 续 ）
注意，一般说来,xy不等于 yx；但 ? x=x?=x
方幂 符号串 x与其自身的 n-1次连接称为 x 的
n 次方幂，记为
??
???
?
0
11
:,
,......3,2
x
nxxxxx
x
nn
n
我们约定这里
即
9
2.2.1 基本概念和术语（ 续 ）
5。 符号串集合的和与积
设 A,B为两个符号串集合，定义
和 A+B（或 A? B） ={w | w? A，或 w ? B}
积 A?B（或 AB） = { xy |x ? A,y ? B}
A+? = ?+A = A ； A? = ?A = ? ； {?}A = A{?} = A
6。 符号串集的方幂与闭包
}{:
:
)0(}{
:,
*
2
1
10
?
?
??
????
???
?
?
?
?
?
AAA
AAAAA
nAAAA
AA
i
i
nn
的自反传递闭包
的正闭包
的方幂定义是符号串的集合设
??
10
2.2.1 基本概念和术语（ 续 ）
? 如果把符号表视为由长度为 1的符号串构成的符号串集
时，就可定义符号表上的 连接、积、方幂 等运算。
? 例 A={a,b,c}
?
?
多含一个空串比合上所有符号串构成的集实际上就是
??
?
?
?
?
?
AAAA
abaacbaA
abaacbaA
cccbcabcbbbaacabaaA
cbaA
*
*
2
1
,
},,,,,,{
},,,,,{
},,,,,,,,{
},,{
?
?
??
11
2.2 文法和语言的形式定义
? 我们从“产生语言”的角
度出发,讨论文法和语言
的形式定义。
? 产生语言 制定出有限条
规则，借助它们产生此语
言的全部句子。
? 以几个英语句子构成的语
言为例，并设每个句子都
是“主 -谓 -宾”结构。
? 语法规则见右。
① <句子 >::=<主语短语 > <动词短
语 >
② <主语短语 >::= the <名词 >
③ <动词短语 >::=<动词 ><宾语短
语 >
④ <宾语短语 >::=<冠词 ><名词 >
⑤ <名词 >::=monkey
⑥ <名词 >::=banana
⑦ <动词 >::=eat
⑧ <动词 >::=has
⑨ <冠词 >::= the
⑩ <冠词 >::= a
12
推导过程
? < >括起来的部分是语言的一个语法实体（称为语法单
位、语法范畴、语法变量等）。,::=”是用于定义语
法结构的符号,语法规则也称为产生式 (Production)
? 现在讨论如何用上述规则 推导 出相应语言的全部 句子 。
? 推导过程 从语言 最大 的一个 语法变量 （本例中是 <句
子 >（不同于后面定义的文法的句子） ）开始，反复用
语法规则中,,:=” 右侧的符号串取代其左侧符号，直
到所得的符号串中不再含有可被替换 语法变量 。每次
替换称为一步（或直接） 推导,并用符号, ?” 表示。
13
推导示例
? 例如，首先用规则 ① 进行第一步推导 (derivation)，
就可得到 <主语短语 ><动词短语 >,记为 <句子 > ?
<主语短语 ><动词短语 >
? 所得的符号串 <主语短语 ><动词短语 >含有两个 语法变
量,可对其中任一个（例如对 <动词短语 >）进行新的
推导 （替换）,
<句子 > ? <主语短语 ><动词短语 >
? <主语短语 ><动词 ><宾语短语 >
? 重复上述过程，可得到一个推导序列（见下页）。
14
用语法规则进行推导所得的推导序列
推导步骤 所用规则 所得的符号串
1 ① <句子 > ? <主语短语 ><动词短语 >
2 ③ ? <主语短语 ><动词 ><宾语短语 >
3 ② ? the <名词 ><动词 ><宾语短语 >
4 ④ ? the <名词 ><动词 ><冠词 ><名词 >
5 ⑤ ? the monkey<动词 ><冠词 ><名词 >
6 ⑦ ? the monkey eat <冠词 ><名词 >
7 ⑩ ? the monkey eat a <名词 >
8 ⑥ ? the monkey eat a banana
? 从上面的推导看，从 <句子 >出发，经 8步推导 得到了一
个英语句子。故上面的推导称为 长度为 8的推导 。
15
规则定义的 语言
? 若不关心推导的中间过程，可将从一符号串到另一符号
串的推导用记号
? 前面的语法规则可以产生 16个不同的句子,由这 16个句
子组成的集合，就是该规则所定义（或所产生）的 语言 。
? 不过有些句子的含义是 荒谬 的（如 the banana eat a
monkey和 the banana eat the banana等 ）。若不考虑 语
义,它们也是语法上 合法 的句子。
?????????
?
?
?
名词冠词动词句子
步的推导记为例如上例中经过表示
m o n k e yt h e
5,
16
规则的简化表示
? 在前面的语法规则定义中，有些语法变量（如 <名词 >、
<动词 >）有若干条不同的规则来定义它，为简明起见，
可以将它们写在同一个左部语法变量下，将其定义值
用符号 ? |”（ 读作 ‘ 或 ’ ） 隔开，每一个定义值称为
一个候选式或选择项。如 <名词 >,<动词 >,<冠词 >
的定义规则可简记为
<名词 >::= monkey | banana
<动词 >::= eat | has
<冠词 >::= the | a
17
前面语法规则的概括
)()(
.,,
:::),("::"
),()4(
.
,,,)3(
},,,,,{
,.,
,,,)2(
}冠 词,,动词短语,主 语语短,句子{V
有,对前面的例子.表示V用,
其集合称 为,称 为为非终结符,含有一系列需要定 义( 1 )
N
N
符号串和右部变量分别称为规则的左部和通常我们把
所组成的符号串是由终结符和非终结符是非终结符其中
对代替）连接起来的有序（可用
它们都是用符号也称为产生式量的规则有若干用于定义语法变
或识别符号称它为文法的开始符号
任何推导都从它开始句子有一个语法变量在非终结符集中
有本例中表示用集合称为终结符集
其称为终结符号它们不需要进一步定义含有若干基本符号
非终结符集
的语法变量
uU
uU
uUuU
at h eh a se a tb a n a n am o n k e yV
V
T
T
???
??
?
????????? ?
18
文法的定义
? ?
?????
?
??
TNTN
N
TNTN
VVVVV
VS
PVVSPVVSGSG
且词汇表称为符号表文法的开始符号
为产生式集终结符集分别称为非终结符集为非空有限集
其中是一四元组一文法定义
),(.;,,,
,,.,,,][][12
如果定义 2.1中的产生式集符合前面的第 4项特征，则定
义 2.1就定义了一部前后文无关文法。也就是说，在用产
生式 U?u进行推导时，是用符号串 u替换非终结符 U,
此时并不关心 U的前后文，即 U与前后文无关。
以后的讨论中，一般用大写拉丁字母和小写拉丁字母分
别表示非终结符和终结符，而用希腊字母表示符号串。
19
直接（一步）推导的定义
? ?
.,
,.,,,,
,)(
,,,,,,][22
*
? ? ???????
???? ? ?????
??????
??
GG
TN
U
PUVU
iff
VSPVVSG
??
?????
???
?
或的直接推导记为是把
通常且其中和
可分别写成直接产生或的直接推导是
称是一文法设定义
上述定义中的 ?,?都可以是空串 ?。
举例：根据 文法 G[<句子 >]有 直接推导
<主语短语 > <动词短语 > => <主语短语 > <动词 > <宾语短语 >
the <名词 > <动词短语 > => the monkey <动词短语 >
其中的 ?,?,?,?,U,?分别是什么？
20
推导的定义
nn
n
n
nn
n
n
V
VG
????
??
??????
??
??
????
?
????
???
???
?
0
*
0
1010
10,
.),2(;0),1(
1,
,,,,)2(
,)1(
),(
,,,3.2
和的推导分别记为和长度常
通的推导则称为长度为对于步推导称为对于情况
使上的符号串序列存在
或
如果产生推导
的是称上的两个符号串是为一文法设定义
??
21
语言的定义
上的。是定义于字母表故的语言。由于
产生称为则是文法设定义
tt
t
G
VGLVGL
GVwwSwGLSG
)(,)(
},|{)(,][5.2
*
*
*
?
???
.),,(
.,,,][4.2
*
*
*
产生的句子是则称当句型特别地
的一个句型是则称若是文法设定义
GV
GSVSG
t
G
??
???
?
??
如,<句子 >,<主语短语 > <动词短语 >,the monkey
eat a banana,the monkey eat the banana, the banana
eat a monkey等都是文法 G[<句子 >]产生的句型。
问题,L(G[<句子 >])是由（有限的） 16个句子组成的。当语言是
无限集时，能否用有限的规则来描述呢？ 答案,递归文法
22
递归文法
例如，文法 G1[<标识符 >],
<标识符 >? <字母 >|<标识符 ><字母 >|<标识符 ><数字 >
<字母 > ? A|B|… |Z
<数字 >? 0|1|2|… |9
及文法 G2[E],
E ? E+T | T
T ? T*F | F
F ? (E) | i
显然,G1,G2都是递归定义的。 所谓 递归定义,指在定义一
个语法成分时，直接或间接地使用了语法成分自身 。
23
递归文法的定义
例如，文法 G1，含有直接左递归非终结符 <标识符 >，文法 G2
中的 E,T是直接左递归的,F是间接递归的,
F?(E)?(T)?(F)
如果一个语言是无限的，则定义它的文法必然是递归的。
递归文法。的非终结符，则称其为文法至少含有一个递归
是右递归的；若一时，称且是左递归的；当
时，称且为递归的非终结符。当递归的，称生式
则称产若存在推导是直接递归的则称产生式
并且的形式具有若为文法设定义
??????
?????
????
???????
????
???
???
???
AA
AA
AAA
APAG
,;
,,,,6.2
*
24
文法与语言的对应关系
注意, 文法与语言之间无一一对应的关系。一文法可唯
一地确定一语言，但对一语言而言，产生它的文法不
止一个 。
例如，由奇数个 a的符号串构成的语言 L可由文法
G1=({S},{a},{S?aSa|a},S) 或
G2=({S,A},{a},{S?aA|a,A?aS},S)
产生，即 L(G1)=L(G2)=L
25
文法的等价关系
? 前后文无关文法的等价性是不可判定的。
? 可利用文法的等价性对文法进行改造。引理 2.1为文法
的等价性改造提供了途径。
)()(
,7.2
21
2121
GLGLi ff
GGGG
?
是等价的和称是两个文法和设定义
的产生式。产生式是指左部变量为其中
。则
，其中
产生式，又设文法中的全部是
中的产生式，是，并且：设文法引理
B-B
L ( G ))L ( G},,...,,{
}{),,,(
,...,,
),,,(12.
121
111
21
????
?????
????
??
?????????
??
???
??
k
TN
k
TN
AAA
BAPPSPVVG
BPBBB
PBASPVVG
第二章 前后文无关文法和语言
? 编译过程是十分复杂的信息加工过程，加工对象是用
高级语言编写的程序。
? 为完成编译工作，需解决两个问题,
– 如何确切地描述和定义一种程序设计语言
– 如何识别和分析这种语言
? 在 20世纪 50年代,N.Chomsky首先对语言的描述问题
进行了探讨。他提出了一种用来描述语言的数学系统，
并以此定义了四类性质不同的语言，称为 语言（文法）
的 Chomsky分类 。
? 人们把用一组数学符号和规则来描述语言的方式称为
形式描述，把所用的数学符号和规则称为 形式语言 。
2
形式语言与自动机
?此后，对 形式语言 以及识别语言的 自动机 的理
论与应用展开了深入研究，并取得了丰硕成果，
这些成果对编译理论、信息工程、人工智能以
及数理语言学、计算语言学产生了深远影响。
?目前,形式语言与自动机理论 已成为计算机科
学中的一个重要分支。
?本章将初步介绍形式语言中的某些基本概念和
知识，重点是与编译技术密切相关的一些术语
和概念，诸如 文法, 语言, 句子, 句型, 短语,
句柄 以及 句型分析 等。
3
2.1 文法及语言的表示
? 据统计，在世界各地，人们所使用的语言达 2700多种。
? 什么是语言？
– Webster的定义：, 为相当大地区的公众所懂得并
使用的 ‘ 话 ’,以及组成这些 ‘ 话 ’ 的方法的统一
体,
– 上述定义对于建立语言的数学理论而言不够精确。
? 另一定义：, 某一字母表上符号串（句子）的集合,
? 仍需进一步精确化,
1）为所定义的句子 提供一种结构性的描述（ 语法规则 ） ；
2）再提供一种手段，以便 能准确地判别什么是该语言中
的正确句子（ 即识别方法、分析方法等 ） 。
4
2.1 文法及语言的表示（ 续 ）
? 如果能刻画出一种语言的所有句子，也就定义出了这
种语言。
? 遗憾的是，对于自然语言来说，目前尚无能够完全刻
画一语言全部句子的结构的方法。
? 然而，对大多数程序设计语言（或者形式语言）来说，
此问题已被解决。 1960年,P.Naur & J.Backus首先用
BNF（ Backus-Naur-Formal（范式））对 ALGOL语
言进行了描述。
? 应指出,BNF成功地解决了程序设计语言的语法描述
问题，但描述其语义，还必须借助自然语言。
5
2.1 文法及语言的表示（ 续 ）
?通常，可用如下方式表示或定义一种语言,
（ 1）若语言的句子有限时，可用 枚举法 。例如，只含两
个句子的语言, {“I am a teacher”,“You are
students”};
（ 2）制定 有限条规则,用于产生所要描述的语言的全部
句子（可无限多），这些规则构成了该语言的 文法 。
（ 3）设计一种装置（ 算法或过程）,它以某字母表上的
符号串为输入，判别该符号串是否为所描述语言的句
子。此装置称为 自动机。
6
2.2 文法和语言的定义
2.2.1 基本概念和术语
1。 符号表（或符号集） 由若干符号组成的有限
非空集合。如 {a,b,c,S,T,*,+,;,.,8,$}
2。 符号串 用符号表中的符号所组成的任何有限
序列。
符号串的长度 = 符号串中所含符号的个数
例,aba的长度为 3。记为,|aba|=3
空串 不含任何符号的符号串，记为 ? 。显然,|
? |= 0。
7
2.2.1 基本概念和术语（ 续 ）
3。 符号串的前（后）缀及子串
设 ?,?,?,x是符号串，若 x= ???,则 ?,? 和 ? 都是 x的 子串；
当 ?= ? 时，称 ?是 x的 前缀 。 当 ?= ?时，称 ?是 x的 后缀。
x的任何前缀或后缀都是 x的子串，反之不成立。
?和 x本身既是 x的前缀和后缀,也是 x的子串 。
4。 符号串的连接和方幂
连接 设 x,y是符号串，将 y直接地拼接到 x之后
所得的新符号串称为 x与 y的连接，记为 xy
8
2.2.1 基本概念和术语（ 续 ）
注意，一般说来,xy不等于 yx；但 ? x=x?=x
方幂 符号串 x与其自身的 n-1次连接称为 x 的
n 次方幂，记为
??
???
?
0
11
:,
,......3,2
x
nxxxxx
x
nn
n
我们约定这里
即
9
2.2.1 基本概念和术语（ 续 ）
5。 符号串集合的和与积
设 A,B为两个符号串集合，定义
和 A+B（或 A? B） ={w | w? A，或 w ? B}
积 A?B（或 AB） = { xy |x ? A,y ? B}
A+? = ?+A = A ； A? = ?A = ? ； {?}A = A{?} = A
6。 符号串集的方幂与闭包
}{:
:
)0(}{
:,
*
2
1
10
?
?
??
????
???
?
?
?
?
?
AAA
AAAAA
nAAAA
AA
i
i
nn
的自反传递闭包
的正闭包
的方幂定义是符号串的集合设
??
10
2.2.1 基本概念和术语（ 续 ）
? 如果把符号表视为由长度为 1的符号串构成的符号串集
时，就可定义符号表上的 连接、积、方幂 等运算。
? 例 A={a,b,c}
?
?
多含一个空串比合上所有符号串构成的集实际上就是
??
?
?
?
?
?
AAAA
abaacbaA
abaacbaA
cccbcabcbbbaacabaaA
cbaA
*
*
2
1
,
},,,,,,{
},,,,,{
},,,,,,,,{
},,{
?
?
??
11
2.2 文法和语言的形式定义
? 我们从“产生语言”的角
度出发,讨论文法和语言
的形式定义。
? 产生语言 制定出有限条
规则，借助它们产生此语
言的全部句子。
? 以几个英语句子构成的语
言为例，并设每个句子都
是“主 -谓 -宾”结构。
? 语法规则见右。
① <句子 >::=<主语短语 > <动词短
语 >
② <主语短语 >::= the <名词 >
③ <动词短语 >::=<动词 ><宾语短
语 >
④ <宾语短语 >::=<冠词 ><名词 >
⑤ <名词 >::=monkey
⑥ <名词 >::=banana
⑦ <动词 >::=eat
⑧ <动词 >::=has
⑨ <冠词 >::= the
⑩ <冠词 >::= a
12
推导过程
? < >括起来的部分是语言的一个语法实体（称为语法单
位、语法范畴、语法变量等）。,::=”是用于定义语
法结构的符号,语法规则也称为产生式 (Production)
? 现在讨论如何用上述规则 推导 出相应语言的全部 句子 。
? 推导过程 从语言 最大 的一个 语法变量 （本例中是 <句
子 >（不同于后面定义的文法的句子） ）开始，反复用
语法规则中,,:=” 右侧的符号串取代其左侧符号，直
到所得的符号串中不再含有可被替换 语法变量 。每次
替换称为一步（或直接） 推导,并用符号, ?” 表示。
13
推导示例
? 例如，首先用规则 ① 进行第一步推导 (derivation)，
就可得到 <主语短语 ><动词短语 >,记为 <句子 > ?
<主语短语 ><动词短语 >
? 所得的符号串 <主语短语 ><动词短语 >含有两个 语法变
量,可对其中任一个（例如对 <动词短语 >）进行新的
推导 （替换）,
<句子 > ? <主语短语 ><动词短语 >
? <主语短语 ><动词 ><宾语短语 >
? 重复上述过程，可得到一个推导序列（见下页）。
14
用语法规则进行推导所得的推导序列
推导步骤 所用规则 所得的符号串
1 ① <句子 > ? <主语短语 ><动词短语 >
2 ③ ? <主语短语 ><动词 ><宾语短语 >
3 ② ? the <名词 ><动词 ><宾语短语 >
4 ④ ? the <名词 ><动词 ><冠词 ><名词 >
5 ⑤ ? the monkey<动词 ><冠词 ><名词 >
6 ⑦ ? the monkey eat <冠词 ><名词 >
7 ⑩ ? the monkey eat a <名词 >
8 ⑥ ? the monkey eat a banana
? 从上面的推导看，从 <句子 >出发，经 8步推导 得到了一
个英语句子。故上面的推导称为 长度为 8的推导 。
15
规则定义的 语言
? 若不关心推导的中间过程，可将从一符号串到另一符号
串的推导用记号
? 前面的语法规则可以产生 16个不同的句子,由这 16个句
子组成的集合，就是该规则所定义（或所产生）的 语言 。
? 不过有些句子的含义是 荒谬 的（如 the banana eat a
monkey和 the banana eat the banana等 ）。若不考虑 语
义,它们也是语法上 合法 的句子。
?????????
?
?
?
名词冠词动词句子
步的推导记为例如上例中经过表示
m o n k e yt h e
5,
16
规则的简化表示
? 在前面的语法规则定义中，有些语法变量（如 <名词 >、
<动词 >）有若干条不同的规则来定义它，为简明起见，
可以将它们写在同一个左部语法变量下，将其定义值
用符号 ? |”（ 读作 ‘ 或 ’ ） 隔开，每一个定义值称为
一个候选式或选择项。如 <名词 >,<动词 >,<冠词 >
的定义规则可简记为
<名词 >::= monkey | banana
<动词 >::= eat | has
<冠词 >::= the | a
17
前面语法规则的概括
)()(
.,,
:::),("::"
),()4(
.
,,,)3(
},,,,,{
,.,
,,,)2(
}冠 词,,动词短语,主 语语短,句子{V
有,对前面的例子.表示V用,
其集合称 为,称 为为非终结符,含有一系列需要定 义( 1 )
N
N
符号串和右部变量分别称为规则的左部和通常我们把
所组成的符号串是由终结符和非终结符是非终结符其中
对代替）连接起来的有序（可用
它们都是用符号也称为产生式量的规则有若干用于定义语法变
或识别符号称它为文法的开始符号
任何推导都从它开始句子有一个语法变量在非终结符集中
有本例中表示用集合称为终结符集
其称为终结符号它们不需要进一步定义含有若干基本符号
非终结符集
的语法变量
uU
uU
uUuU
at h eh a se a tb a n a n am o n k e yV
V
T
T
???
??
?
????????? ?
18
文法的定义
? ?
?????
?
??
TNTN
N
TNTN
VVVVV
VS
PVVSPVVSGSG
且词汇表称为符号表文法的开始符号
为产生式集终结符集分别称为非终结符集为非空有限集
其中是一四元组一文法定义
),(.;,,,
,,.,,,][][12
如果定义 2.1中的产生式集符合前面的第 4项特征，则定
义 2.1就定义了一部前后文无关文法。也就是说，在用产
生式 U?u进行推导时，是用符号串 u替换非终结符 U,
此时并不关心 U的前后文，即 U与前后文无关。
以后的讨论中，一般用大写拉丁字母和小写拉丁字母分
别表示非终结符和终结符，而用希腊字母表示符号串。
19
直接（一步）推导的定义
? ?
.,
,.,,,,
,)(
,,,,,,][22
*
? ? ???????
???? ? ?????
??????
??
GG
TN
U
PUVU
iff
VSPVVSG
??
?????
???
?
或的直接推导记为是把
通常且其中和
可分别写成直接产生或的直接推导是
称是一文法设定义
上述定义中的 ?,?都可以是空串 ?。
举例：根据 文法 G[<句子 >]有 直接推导
<主语短语 > <动词短语 > => <主语短语 > <动词 > <宾语短语 >
the <名词 > <动词短语 > => the monkey <动词短语 >
其中的 ?,?,?,?,U,?分别是什么？
20
推导的定义
nn
n
n
nn
n
n
V
VG
????
??
??????
??
??
????
?
????
???
???
?
0
*
0
1010
10,
.),2(;0),1(
1,
,,,,)2(
,)1(
),(
,,,3.2
和的推导分别记为和长度常
通的推导则称为长度为对于步推导称为对于情况
使上的符号串序列存在
或
如果产生推导
的是称上的两个符号串是为一文法设定义
??
21
语言的定义
上的。是定义于字母表故的语言。由于
产生称为则是文法设定义
tt
t
G
VGLVGL
GVwwSwGLSG
)(,)(
},|{)(,][5.2
*
*
*
?
???
.),,(
.,,,][4.2
*
*
*
产生的句子是则称当句型特别地
的一个句型是则称若是文法设定义
GV
GSVSG
t
G
??
???
?
??
如,<句子 >,<主语短语 > <动词短语 >,the monkey
eat a banana,the monkey eat the banana, the banana
eat a monkey等都是文法 G[<句子 >]产生的句型。
问题,L(G[<句子 >])是由（有限的） 16个句子组成的。当语言是
无限集时，能否用有限的规则来描述呢？ 答案,递归文法
22
递归文法
例如，文法 G1[<标识符 >],
<标识符 >? <字母 >|<标识符 ><字母 >|<标识符 ><数字 >
<字母 > ? A|B|… |Z
<数字 >? 0|1|2|… |9
及文法 G2[E],
E ? E+T | T
T ? T*F | F
F ? (E) | i
显然,G1,G2都是递归定义的。 所谓 递归定义,指在定义一
个语法成分时，直接或间接地使用了语法成分自身 。
23
递归文法的定义
例如，文法 G1，含有直接左递归非终结符 <标识符 >，文法 G2
中的 E,T是直接左递归的,F是间接递归的,
F?(E)?(T)?(F)
如果一个语言是无限的，则定义它的文法必然是递归的。
递归文法。的非终结符，则称其为文法至少含有一个递归
是右递归的；若一时，称且是左递归的；当
时，称且为递归的非终结符。当递归的，称生式
则称产若存在推导是直接递归的则称产生式
并且的形式具有若为文法设定义
??????
?????
????
???????
????
???
???
???
AA
AA
AAA
APAG
,;
,,,,6.2
*
24
文法与语言的对应关系
注意, 文法与语言之间无一一对应的关系。一文法可唯
一地确定一语言，但对一语言而言，产生它的文法不
止一个 。
例如，由奇数个 a的符号串构成的语言 L可由文法
G1=({S},{a},{S?aSa|a},S) 或
G2=({S,A},{a},{S?aA|a,A?aS},S)
产生，即 L(G1)=L(G2)=L
25
文法的等价关系
? 前后文无关文法的等价性是不可判定的。
? 可利用文法的等价性对文法进行改造。引理 2.1为文法
的等价性改造提供了途径。
)()(
,7.2
21
2121
GLGLi ff
GGGG
?
是等价的和称是两个文法和设定义
的产生式。产生式是指左部变量为其中
。则
，其中
产生式，又设文法中的全部是
中的产生式，是，并且：设文法引理
B-B
L ( G ))L ( G},,...,,{
}{),,,(
,...,,
),,,(12.
121
111
21
????
?????
????
??
?????????
??
???
??
k
TN
k
TN
AAA
BAPPSPVVG
BPBBB
PBASPVVG
