编译原理 第二章文法和语言 上海交通大学 张冬茉 Email:Zhang-dm@cssjtu.edu.cn 2004年2月
1 编译原理 第二章 文法和语言 上海交通大学 张冬茉 Email:zhang-dm@cs.sjtu.edu.cn 2004年2月
本章目的 自然语言是人与人交流思想的工具,程序语言是 人和计算机之间传达信息的工具。为了描述程序语言, 本章将引进有关形式语言的基本概念。文法是程序语 言的生成系统,自动机是程序语言的识别系统,用文 法来精确定义一个语言,然后根据这个文法构造识别 这个语言的自动机,因此文法对程序语言和编译程序 的构造来说意义重大。随着计算机的发展,形式语言 学发展很快。 N. Chomsky将文法分成四类,程序语言 的词法可用正规文法描述,语法可用上下文无关文法 描述,语义则要借助于上下文有关文法来描述。因此 我们的注意力是针对这几类文法,特别是上下文无关 文法 2
2 本章目的 自然语言是人与人交流思想的工具，程序语言是 人和计算机之间传达信息的工具。为了描述程序语言， 本章将引进有关形式语言的基本概念。文法是程序语 言的生成系统，自动机是程序语言的识别系统，用文 法来精确定义一个语言，然后根据这个文法构造识别 这个语言的自动机，因此文法对程序语言和编译程序 的构造来说意义重大。随着计算机的发展，形式语言 学发展很快。N.Chomsky将文法分成四类，程序语言 的词法可用正规文法描述，语法可用上下文无关文法 描述，语义则要借助于上下文有关文法来描述。因此 我们的注意力是针对这几类文法，特别是上下文无关 文法
第二章文法和悟言 §2.1基本概念 语言 1.字母表 定义21符号的非空有穷集合称为字母表,通常用∑表示。字母 表中每个元素称为一个符号或一个字符 不同语言的字母表可能是不同的,例如二进制数这个语言的字 母表∑=(0,1}。程序语言中的标识符,它的字母表 ∑={a,b,,0,1,,9}。通常程序语言的字母表是ASCⅡ字符集。 2.字符串 定义22由字母表∑中的字符所组成的有穷序列,称为字母表 上的符号串,或字符串,字。 例2.,如,字母表∑={0,1},则0,1,001,10,1,00010,,都是 ∑上的字符串,如则a,b,,ab,ba,bb,aa分别是∑上的字符 串 3
3 第二章 文法和语言 §2.1 基本概念 一、语言 1. 字母表 定义2.1 符号的非空有穷集合称为字母表，通常用∑表示。字母 表中每个元素称为一个符号或一个字符。 不同语言的字母表可能是不同的，例如二进制数这个语言的字 母表∑={0,1}。程序语言中的标识符，它的字母表 ∑={a,b,..,z,0,1,..,9}。通常程序语言的字母表是ASCⅡ字符集。 2. 字符串 定义2.2 由字母表∑中的字符所组成的有穷序列，称为字母表 上的符号串，或字符串，字。 [例2.1]如,字母表∑={0,1},则0,1,00,01,10,11,000,001,010,…都是 ∑上的字符串，如则a, b, , ab, ba, bb, aaa…分别是∑上的字符 串。
空串:不包含任何字符的字符串,用表示,它是∑上的 个特殊的字符串。对任一字母表∑,都有E是∑上的字符串。 字符串的长度:是指字符串x中的字符的个数,用K表示。 如x=abc,则kx|=3。特别地有|c|=0 字符串的联结:设xy是∑上的字符串,则它们的联结xy是 将y的符号相继连接在x的符号后所得到的新的字符串 如,x=aba,y=bba,则xy= ababa 联结是字符串上的一种运算,满足结合律,但不满足交换 律。但8x=Xg=x则另当别论。 4
4 •空串：不包含任何字符的字符串，用ε表示，它是∑上的一 个特殊的字符串。对任一字母表∑，都有ε是∑上的字符串。 •字符串的长度：是指字符串x中的字符的个数，用|x|表示。 如x=abc，则|x| =3。特别地有| ε | =0. •字符串的联结：设x,y是∑上的字符串，则它们的联结xy是 将y的符号相继连接在x的符号后所得到的新的字符串， 如,x=aba,y=bba,则xy=ababba. 联结是字符串上的一种运算，满足结合律，但不满足交换 律。但εx=xε=x则另当别论
3.子串 字符串的前缀和后缀:设zx则x是z的前缀,y是z的后缀, 特别当y≠时x是z的真前缀,当x时,y是z的真后缀 「例22设x=abc,则,a,ab,abc都是x的前缀,其,a,ab为真前 缀,而abe,bc,c,E都是x的后缀,其中bc,c,e为真后缀。 定义23一个非空字符串x删去它的前缀和后缀后所得的字 符串为x的子串,如果删去的前缀和后缀不同时为E,则该 子串为真子串。 例23设x=abe,其子串为abc,ab,be,a,c,b,E真子串为ab, bc,a,c,b,e请注意ac不是子串,它只是字符串abc的一个子 序列
5 3.子串 •字符串的前缀和后缀：设z=xy则x是z的前缀，y是z的后缀, 特别当y≠ε时x是z的真前缀,当x≠ε时,y是z的真后缀. [例2.2]设x=abc,则ε,a,ab,abc都是x的前缀，其ε,a,ab为真前 缀，而abc,bc,c, ε都是x的后缀，其中bc,c, ε为真后缀。 定义2.3 一个非空字符串x删去它的前缀和后缀后所得的字 符串为x的子串，如果删去的前缀和后缀不同时为ε ，则该 子串为真子串。 [例2.3]设x=abc，其子串为abc, ab, bc, a, c, b, ε 真子串为 ab, bc, a, c, b, ε请注意ac不是子串，它只是字符串abc的一个子 序列