第二章前后文无关文法和语言 编译过程是十分复杂的信息加工过程,加工对象是用 高级语言编写的程序。 为完成编译工作,需解决两个问题 如何确切地描述和定义一种程序设计语言 如何识别和分析这种语言 在20世纪50年代, N. Chomsky首先对语言的描述问题 进行了探讨。他提出了一种用来描述语言的数学系统, 并以此定义了四类性质不同的语言,称为语言(文法) Chomsky分类。 人们把用一组数学符号和规则来描述语言的方式称为 形式描述,把所用的数学符号和规则称为形式语言
1 第二章 前后文无关文法和语言 编译过程是十分复杂的信息加工过程，加工对象是用 高级语言编写的程序。 为完成编译工作，需解决两个问题： – 如何确切地描述和定义一种程序设计语言 – 如何识别和分析这种语言 在20世纪50年代，N.Chomsky首先对语言的描述问题 进行了探讨。他提出了一种用来描述语言的数学系统， 并以此定义了四类性质不同的语言，称为语言（文法） 的Chomsky分类。 人们把用一组数学符号和规则来描述语言的方式称为 形式描述，把所用的数学符号和规则称为形式语言
形式语言与自动机 此后,对形式语言以及识别语言的自动机的理 论与应用展开了深入研究,并取得了丰硕成果, 这些成果对编译理论、信息工程、人工智能以 及数理语言学、计算语言学产生了深远影响。 目前,形式语言与自动机理论已成为计算机科 学中的一个重要分支 本章将初步介绍形式语言中的某些基本概念和 知识,重点是与编译技术密切相关的一些术语 和概念,诸如文法、语言、句子、句型、短语、 句柄以及句型分析等
2 形式语言与自动机 此后，对形式语言以及识别语言的自动机的理 论与应用展开了深入研究，并取得了丰硕成果， 这些成果对编译理论、信息工程、人工智能以 及数理语言学、计算语言学产生了深远影响。 目前，形式语言与自动机理论已成为计算机科 学中的一个重要分支。 本章将初步介绍形式语言中的某些基本概念和 知识，重点是与编译技术密切相关的一些术语 和概念，诸如文法、语言、句子、句型、短语、 句柄以及句型分析等
21文法及语言的表示 据统计,在世界各地,人们所使用的语言达2700多种。 什么是语言? Webster的定义:“为相当大地区的公众所懂得并 使用的话’,以及组成这些‘话’的方法的统 体 上述定义对于建立语言的数学理论而言不够精确。 另一定义:“某一字母表上符号串(句子)的集合” 仍需进一步精确化: 1)为所定义的句子提供一种结构性的描述(语法规则); 2)再提供一种手段,以便能准确地判别什么是该语言中 的正确句子(即识别方法、分析方法等)
3 2.1 文法及语言的表示 据统计，在世界各地，人们所使用的语言达2700多种。 什么是语言？ – Webster的定义：“为相当大地区的公众所懂得并 使用的‘话’，以及组成这些‘话’的方法的统一 体” – 上述定义对于建立语言的数学理论而言不够精确。 另一定义：“某一字母表上符号串（句子）的集合” 仍需进一步精确化： 1）为所定义的句子提供一种结构性的描述（语法规则）； 2）再提供一种手段，以便能准确地判别什么是该语言中 的正确句子（即识别方法、分析方法等）
21文法及语言的表示(续) 如果能刻画出一种语言的所有句子,也就定义出了这 种语言。 遗憾的是,对于自然语言来说,目前尚无能够完全刻 画一语言全部句子的结构的方法 然而,对大多数程序设计语言(或者形式语言)来说 此问题已被解决。1960年,ENr& J. Backus首先用 BNF( Backus-Naur- Formal(范式))对 ALGOL语 言进行了描述。 应指出,BNF成功地解决了程序设计语言的语法描述 问题,但描述其语义,还必须借助自然语言
4 2.1 文法及语言的表示（续） 如果能刻画出一种语言的所有句子，也就定义出了这 种语言。 遗憾的是，对于自然语言来说，目前尚无能够完全刻 画一语言全部句子的结构的方法。 然而，对大多数程序设计语言（或者形式语言）来说， 此问题已被解决。1960年，P.Naur & J.Backus首先用 BNF（Backus-Naur-Formal（范式））对ALGOL语 言进行了描述。 应指出，BNF成功地解决了程序设计语言的语法描述 问题，但描述其语义，还必须借助自然语言
21文法及语言的表示(续) 通常,可用如下方式表示或定义一种语言: (1)若语言的句子有限时,可用枚举法。例如,只含两 个句子的语言:{“ am a teacher”,“ You are students”} (2)制定有限条规则,用于产生所要描述的语言的全部 句子(可无限多),这些规则构成了该语言的文法 (3)设计一种装置(算法或过程),它以某字母表上的 符号串为输入,判别该符号串是否为所描述语言的句 子。此装置称为自动机
5 2.1 文法及语言的表示（续） 通常，可用如下方式表示或定义一种语言： （1）若语言的句子有限时，可用枚举法。例如，只含两 个句子的语言：{“I am a teacher”, “You are students”}; （2）制定有限条规则，用于产生所要描述的语言的全部 句子（可无限多），这些规则构成了该语言的文法。 （3）设计一种装置（算法或过程），它以某字母表上的 符号串为输入，判别该符号串是否为所描述语言的句 子。此装置称为自动机
22文法和语言的定义 2.21基本概念和术语 符号表(呲符号集)由若干符号组成的有限 空集合。如{a,b,c,S,T,,+,;y,8,} 2。符号电用符号表中的符号所组成的任何有限 序列。 符号的长度=符号串中所含符号的个数 例:mbm的长度为3。记为:|aba|=3 空不含任何符号的符号串,记为ε。显然, E|=0 6
6 2.2 文法和语言的定义 2.2.1 基本概念和术语 1。符号表（或符号集） 由若干符号组成的有限 非空集合。如{a,b,c,S,T,*,+,;,.,8,$} 2。符号串 用符号表中的符号所组成的任何有限 序列。 符号串的长度 = 符号串中所含符号的个数 例：aba的长度为3。记为：|aba|=3 空串 不含任何符号的符号串，记为 。显然，| |= 0
2.2,基祝念和术语(续) 3。符号串的前(后)缀及子申 设8x是符号串,若=以则aB和6都是的子串 当α=ε时,称β是x的前缀。当δ=ε时,称β是x的后缀。 x的任何前缀或后缀都是x的子串,反之不成立 E和x本身既是x的前缀和后缀,也是x的子串 4。符号串的连接和方幂 连接设xy是符号串,将y直接地拼接到x之后 所得的新符号串称为x与y的连接,记为xy 7
7 2.2.1 基本概念和术语（续） 3。符号串的前（后）缀及子串 设,,,x是符号串，若x= ,则,和 都是x的子串； 当= 时，称 是x的前缀。 当= 时，称 是x的后缀。 x的任何前缀或后缀都是x的子串，反之不成立。 和x本身既是x的前缀和后缀，也是x的子串。 4。符号串的连接和方幂 连接 设x,y是符号串，将y直接地拼接到x之后 所得的新符号串称为x与y的连接，记为xy
2.2,基祝念和术语(续) 注意,一般说来,q不等x;但 =8x 方幂符号串x与其自身的n-次连接称为x的 n次方幂,记为 x即 n-1 xX 这里,我们约定:x0=E ,8
8 2.2.1 基本概念和术语（续） 注意，一般说来，xy不等于yx；但 x=x=x 方幂 符号串x与其自身的n-1次连接称为 x 的 n 次方幂，记为 = = = = − 0 1 1 , : 2,3,...... x x x x x x n x n n n 这里 我们约定 即
2.2,基祝念和术语(续) 5。符号串集合的和与积 设A,B为两个符号串集合,定义 和A+B(或4UB)={w|w∈A,或和∈B 积AB(或AB)={xy∈A,y∈B A+=+A=A;A=A=;{}A=A{e}=A 6。符号串集的方幂与闭包 设A是符号串的集合,定义A的方幂 A(n>0) oo A的正闭包:A+=UA2=A+A2+ 字A的自反传递闭包:A=A++{}
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 0 1 = + = = + + = = + = + − A A A A A A A A A A A A n A A i i n n 的自反传递闭包 的正闭包 设 是符号串的集合 定义 的方幂
9.2,基本概和术语(续) 如果把符号表视为由长度为的符号串构成的符号串集 时,就可定义符号表上的连接、积、方幂等运算。 例A={a,b,c A=a, b,c) A=aa, ab, ac, ba, bb, bc, ca,cb, cc) A+={a,b,c,a,ab,…} A=8, a, b, c, aa, ab, .. A+实际上就是A上所有符号串构成的集合,A比A多含一个空串E
10 2.2.1 基本概念和术语（续） 如果把符号表视为由长度为1的符号串构成的符号串集 时，就可定义符号表上的连接、积、方幂等运算。 例 A={a,b,c} + 实际上就是 上所有符号串构成的集合 比 + 多含一个空串 + = = = = A A A A A a b c aa ab A a b c aa ab A aa ab ac ba bb bc ca cb cc A a b c * * 2 1 , { , , , , , , } { , , , , , } { , , , , , , , , } { , , }