This PPT is about Chapter 2 of Compiler Principles: High-Level Languages and Their Syntax Descriptions.

This PPT is about Chapter 2 of Compiler Principles: High-Level Languages and Their Syntax Descriptions.

1. 第二章 高级语言及其语法描述

2. 主要内容
2.1 程序语言的定义
2.2 高级语言的分类
2.3 程序语言的语法描述

3. 2.1 程序语言的定义
一个程序语言是一个记号系统。程序语言主
要由语法和语义两个方面定义。

4. 语法
任何语言程序都可看成是一定字符集（称为字母
表）上的一字符串（有限序列）。但是，什么样的
字符串才算是一个合式的程序呢？
所谓一个语言的语法是指这样的一组规则，用它可
以形成和产生一个合式的程序。
这些规则的一部分称为词法规则，另一部分称为语
法规则（或产生规则）。

5. 词法规则 是指单词符号的形成规则。
语言的单词符号是由词法规则所确定的。
词法规则规定了字母表中哪样的字符串是
一个单词符号。
单词符号一般包括：各类型的常数、标识
符、基本字、算符和界符等。

6. 语言的语法规则规定了如何从单词符号形成更大的
结构（即语法单位），换言之，语法规则是语法单
位的形成规则。
一般程序语言的语法单位有：表达式、语句、分程
序、函数、过程和程序等等。
语言的词法规则和语法规则 定义了程序的形式结构，
是判断输人字符串是否构成一个形式上正确（即合
式）程序的依据。

7. 语义
一个语言的语义是指这样的一组规则，使用
它可以定义一个程序的意义。这些规则称为
语义规则 。

8. 2.2 高级语言的分类
一、强制式语言
二、应用式语言
三、基于规则的语言
四、面向对象语言

9. 2.3 程序语言的语法描述
重点讨论上下文无关文法、语法分析树，以
及文法的二义性问题。最后还将对形式语言
进行简单概述。
设Σ是一个有穷字母表，它的每个元素称为
一个符号。
1、Σ上的一个符号串： 是指由Σ中的符号所
构成的一个有穷序列。不包含任何符号的序
列称为空字，记为ε。用Σ﹡表示Σ上的所有
符号串的全体，空字 ε也包括在其中。

10. 例如，
∑＝{a,b}，则 ∑﹡={ε,a,b,aa,ab,ba,bb,aaa,
…｝。
Ф表示不含任何元素的空集｛｝。
注意：要注意空字 ε、{}和{ε}的区别。
2、语言：是给定字母表上一个任意的可数的
串集合。

11. 语言运算
1、 ∑﹡的子集L和M的并运算

12. 2、∑﹡的子集L和M的（连接）积
LM＝｛αβ|α∈L&β∈M}
即集合LM中的符号串是由 L和M的符号串
连接而成的。
注意，一般而言， LM≠ML，但(LM)W=L(M
W）。
3、V自身的n次（连接）积：
记为 Vⁿ=VV……V
规定：V°={ε}
令 V
﹡
= V
0
∪V¹∪V²∪V ³∪……
称V
*
是V的闭包。记 V
﹢
=VV
*
，称V
+
是V的正
则闭包。

13. 例：L表示字母集合 {A,B,…,Z，a,b,….z},D表示
数位的集合 {0,1，…9},则
DL
4
L
*
L
*
)(DLL

D
LD

14. DL
4
L
*
L
*
)(DLL

D
字母和数位的集合：语言包含 62个长度为
1的串，每个串是一个字母或一个数位。
LD
所有由字母构成的串的集合，包括空串 ε
包含520个长度为 2的串的集合，每个
串是一个字母跟一个数位
所有由四个字母构成的串的集合
所有由字母开头的，由字母和数位组成的串的集合
由一个或多个数位构成的串的集合

15. 上下文无关文法
文法是描述语言的语法结构的形式规则
（即语法规则 ）。
上下文无关文法 所定义的语法范畴（或语
法单位）是完全独立于这种范畴可能出现
的环境的。
上下文无关文法不宜于描述任何自然语言，
但对于现今的程序语言来说，上下文无关
文法基本上是够用了。

16. 从一个具体英文例句的分析出发，引进有关上下文无关文法的
基本概念。比如，我们
写了这样一个句子：
He gave me a book．
这是一个语法上正确的句子，
因为它满足英语中的基本语法规则。
有下面语法规则：
＜
句子＞→＜主语＞＜谓语＞＜间接宾语＞＜直接宾语＞
＜
主语＞→
<代
词
>
＜
谓语＞→
<动
词
>
＜间
接宾语＞→＜代词＞
＜直
接宾语＞→＜冠词＞＜名词＞
<代
词＞→
He
＜代
词＞→
me
＜冠
词＞→
a
＜动
词
>→gave
＜名
词＞→
book

17. ＜
句子＞
==> ＜
主语＞＜谓语＞＜间接宾语＞＜直接
宾
语＞
==> ＜代
词＞＜谓语＞＜间接宾语＞＜直接宾语＞
==> He＜
谓语＞＜间接宾语＞＜直接宾语＞
==> He＜动
词＞＜间接宾语＞＜直接宾语＞
==> He gave＜间
接宾语＞＜直接宾语＞
==>He gave＜代
词＞＜直接宾语＞
==> He gave me＜直
接宾语＞
==> He gave me＜冠
词＞＜名词＞
==> H gave me a＜名
词＞
==> He gave me a book

18. 语法分析树 :用一种
图示化的方法来表示这种 推导
句子
主语 谓语 间
接宾语
直
接宾语
代
词
动
词
冠
词
名
词
He gave me a book
代
词

19. 上下文无关文法描述
一个上下文无关文法 G包括四个组成部分：
一组
终结符号
，一组
非终结符号
，一个开
始
符号，以及一组产生式 。
终
结符号
乃
是组成语言的基本符号，在程序
语言中
就是以前屡次提到的单词符号，如基
本字、标识符、常数、算符和界符等。从语
法分析的
角度来看， 终结符号是一个语言的
不可
再分的基本符号。

20. 非终
结符号（也称语法 变量）
用来
代表语法
范畴。例如，
“算术表达式”、“布尔表达式”、
“赋值
句”、“分程序”、“过程”等。
开
始符号
是一个
特殊的非终结符号，它 代表
所定义的语言中我们最
终感兴趣 的语法范畴，
这个语法范畴
通常称为
“
句子”

21. 产生式（也称产生规则或简称规则）
是定义语法范畴的一种
书写规则。一个产生式的形
式是A→α
其中，
箭头（有时也用：：＝） 左边的
A是一个
非终
结符，称为产生式的 左部符号；箭头右边
α
的是由
终结符号或
/与非终
结符号组成的一符号串，
称为产生式的
右部。

22. 例：
“变量
是一个算术表达式；若
E和E2是算
术表达式，
则E1＋E2,E1*E2和（El）也是算
术表达
式。
”
对于这个定义，
若用产生式来描述，则可将它 写成：
E→i
E→E＋E
E→E * E
E→（E)
E：表示
“算术表达式”
i：表示
“变量”

23. 一个上下文无关文法 G是一个四元式
（V
T
,V
N
,
S,
ρ)，
其中
V
T是一个
非空有限集，它的每个元素称为 终结符号；
V
N是一个
非空有限集，它的每个元素称为 非终结符
号，V
T∩V
N＝φ
S是一个
非终结符号，称为开 始符号；
ρ是一个产生式集合（有限），每个产生式的形式
是P→α，其中， P€
V
N
， α €(
V
T
∪V
N
)
*
。开
始
符号S至少必须
在某个产生式的 左部出现一次。

24. 对于多个
左部相同的产生式：
P→α1
P→α2
……
P→αn
可
写为：
P→α1|

α2…… αn
其中每个 αi称为是P的一个
候选式。

→
读
为“定义为”，
|

读
为“或”。

25. 一般，用大
写字母
A
,B,C…
或
汉语词组
（如，算
术表达式） 代表非终结符号，
用
小写字母
a,b,
c…
代
表终结符，用
α、β、γ等
代表由终结符和非终结符
组成的符号串。

26. 上下文无关文法定义一个语言的中
心思想是
：
从文法的开
始符号出发， 反复连续使用产生式，
对
非终结符施行替换和展开。
0 αAβ直
接推出
αγβ，
即αAβ=
>
αγβ
仅当A→γ是一个产生式，
且
α、β∈(
V
T∪V
N)
*
。
如
果
αl
=>
α2 =
> ... =>
αn，则我们称这个序列
是从αl至αn的一个
推导。
若存
在一个从
αl至αn的
推导，则称
αl可
推导出
αn
.

27. 假
定
G是一个文法， S是它的开
始符号。
如
果
S
=>
α，则称α是一个句型。
仅含
终
结符号的句型是一个
句子。
文法G所产生的句子的全体是一个 语言，
将它记为 L
(G)
L
(G) =
｛α|S
=>
α&α∈
V
T
﹡
｝

28. E =>(E) =>(E＋E) =>(E*E＋E） =>
（i*E＋E) =>(i＊i＋E) =>(i＊i＋i)
是从开
始符号
E到(i*i＋i）的一个
推导。
而E，（E），（E＋E），（E*E＋
E），…，（i*i＋i）都是这个文法的
句型。

29. 下面
介绍几个简单文法的例子：
例2.1考虑
一个文法
G1:
S→bA A→aA|a 它定义了一个什么语言呢？
从开
始符
S出发，我们可以
推出如下句子：
SbA ba
SbA baA baa
………..
SbA baA  …  baa…a
可以
写为：
L(G1)={ba
n
|n 1}
≥

30. 例2.2 设有文法 G
S P|aPPb
→
P ba|bQa
→
Q ab
→
求
语言
L(G).
解
：
L(G)={ba,baba,abab,ababab… }
例2。3 构
造一个文法
G3使
L(G3)={a
n
b
n
|n 1}
≥
解; S aSb|ab
→

31. 最
左
(最
右
)推导
所谓最
左推导
指：任何一
步
a =
>
β都是对α中
的最
左非终结符进行 替换的。
同
样，可定义最 右推导。
（i
*i
＋i
)
的最
右推导：
E =>(E)
=>(E＋E)
=>(E＋i)
=>(E*E＋i)
=>(E*i＋i)
=>(i*i＋i)

32. 例： G = ({E}, {i, +, *, (, ) } , P , E)
P： E  E + E | E * E | ( E ) | i
句子 ( i * i + i)的语法树：
(1) E  (E)  (E + E)  (E * E + E) (i * E + E)  (i *i + i)
(2) E  (E)  (E + E)  (E * E + E) (i * E + E)  (i *i + i)

35. 语法分析树
与二义性
用一
张图表示一个句型的 推导，这种表示
称为语法分析树， 或简称为语法树。
一
棵语法树表示了一个句型种种可能的
（但
未必是所有的）不 同推导过程，包括
最
左（最右）推导。
如
果一个文法 存在某个句子对应两 棵不同
的语法树，则称这个 文法是二义 的。也
就
是说，
若一个文法中 存在某个句子，它有
两个不
同的最左（最右）推导，则这个文
法是二义的。

36. 注意，文法的二义性 和语言的二义性 是
两个不
同的概念。我们可能有两个不 同
的文法G和G‘．
其中一个是二义的而另
一个是无二义的，但是
却有
L(G)=L
(G’），也
就是说，这两个文法所产生
的语言是
相同的。

37. 在文法(2.1)中，
假若规定了运算符
‘十’与‘*
’
的
优先顺序和结合规则 ．比方说，
让‘*
’
的
优先性高于‘＋’，且它们都服从左
结合，
那么，就可以构造出一个无二义
文法：
E→T | E十T
T →F | T*F
F→（E) | i

38. 作
为描述程序语言的上下文无关文法，对它有 几点限
制。
第一，文法中不含任何下面形式的产生式
P→P
因
为，这种产生式 除了引起二义性外没有任何用处。
第二，每个
非终结符
P必须
都有用处。这一方面意 味
着
，必须存在含
P的句型
；也就是，从开始符号
S
出发，
存在推导
S
=>
αPβ
另一方面意
味着，必须存在终结符串
γ€V
T
*
，使
得
P

=
>
γ,也
就是，对于
P不
存在永不终结的回路。

39. 形式语言
鸟瞰
乔姆斯
基把文法分成四种类型，即
0型、l
型、2型和3型。
0型强于1型，l型强于2型，2型强于3
型。
这
几类文法的 差别在于对产生式 施加不同的限
制。

40. ö G=(V
T
,V
N
,S ,) 是一个0型文法，如
果
它的每个产生式 是这样的结构
(V
NV
T)
*
且至少
有一个非终结符，而

(V
NV
T)
*
。0型文法也称
短语文法。
如
果
对0型文法分别
施加以下的第
i条
限制
，则我们
就
得到
第
i型文法:
(1)G的任何产生式 
均满足
||≤ ||（其中|
|和||分别为和的长度
；仅
S例
外，但
S不
得
出现在任何产生式的 右部。
(2)G的任何产生式为 A, AV
N， (V
NV
T)
*
。
(3)G的任何产生式为 AB或 A，其中
V
T
*
，A、B  V
N 。



41. 其中1型文法也称上下文有关文法 。这种文
法意
味着，对非终结符进行 替换式务必考虑
上下文并
且一般不允许替换成空串
。
※2型文法也称上下文无关文法 ，注意其语言
定义：
G的任何产生式为 A→β，A∈
V
N， β∈（V
N∪V
T)
*
　　　　
表明凡出现在产生式 左边的符号都是
非终
结符。

42. ※3型文法也称
右线性文法。
3型文法还有另一种形式，称
左线性文法：一
个文法G为
左线性文法，如 果
G的任何产生
式为
A→B 或A→ ，其中∈V
T
*
,

A
、B
∈ V
N

由于3型文法等
价
于正规式所以也称正规文法。

43. 例题
与习题解答
[例2.1]：
试
构造生成语言
L={a
n
b
n
c
i
|n1, i 0}的文法
分析：要
求
a和b的个数一样多，并
至少为一个，而
c的个数为 0个以上即可，所以可以用一个
非终结
符
去生成
a
n
b
n
串，用另一个
非终结符去生成
c
i

。
G(Z): ZAB
A aAb|ab
B cB|

44. [例2.2]：
已知
语言
L={a
n
bb
n
| n 1}, 写
出产生
L的文法。
[解]： G[S]: S aAb
A aAb|b
[例2.3]：
已知
文法
G=({A,B,C},{a,b,c},A,P)
其中产生式 P由以下组成：
A abc A aBbc
Bb bB Bc Cbcc
bC Cb aC aaB
aC aa
问：
此文法表式的语言是什么？

45. [解]：由于A为开
始符。
由于AaBbc abBc abCbcc
aCbbcc
aabbcc
语言为： {a
n
b
n
c
n
, n>0 }

46. ，
[例2.4]：
已知语言
L={x | x{a,b,c}*,且x
重
复排列是对称的（
aabcbaa,aabbaa,等)
写
出该语言的文法。

[例2.4]：
解：
G(Z)： Z aZa|bZb|cZc|a|b|c|