编译原理 第二章文法和语言 上海交通大学 张冬茉 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的一个子 序列
4语言 定义24: 给出字母表∑,则Σ上任一字符串集合,称为∑上的一个语 言,记为L,该语言的每一个字符串,便是语言L的一个语 句或句子。 例24设∑={a,b,c},则L={a,aa,ab,aa,ab,aba,abb,}为上 的一个语言,如果a表示字母,b表示数字,c看作其他符号 则L通常是程序语言中的标识符集。其中每个标识符便是标 识符集的一个句子。 由有限个字符串组成的集合为一有穷语言,反之为无 穷语言 6
6 4.语言 定义2.4 : 给出字母表，则上任一字符串集合，称为上的一个语 言，记为L，该语言的每一个字符串，便是语言L的一个语 句或句子。 [例2.4]设={a,b,c},则L={a,aa,ab,aaa,aab,aba,abb,…}为上 的一个语言，如果a表示字母，b表示数字，c看作其他符号, 则L通常是程序语言中的标识符集。其中每个标识符便是标 识符集的一个句子。 • 由有限个字符串组成的集合为一有穷语言，反之为无 穷语言
●对于字母表Σ,用∑*表示∑上所有字符串的集合 如∑={a,b},则Σ*={,a,b,ab,bb,ba…}。 显然∑上的任一语言L,都有Lc∑ 对于Σ,令∑+=∑*-{e},它是Σ上不含空串的字符串集合。 ●对于Σ的子集L,M,(它们都∑上的语言),可以定义下列 四种语言之间的运算。 定义25:语言L和M的连接,LM={xy|x∈ L and y∈M} 基于同一律,{ε}L=L{e}=L,除此而外,通常LM≠ML,即 连接不满足交换律,但满足结合律,即(LM)N=L(MN) 通常记L2=LL,并约定L。={E} 7
7 •对于字母表，用*表示上所有字符串的集合。 如={a,b}，则*={ ,a,b,aa,ab,bb,ba,…}。 显然上的任一语言L，都有L * 对于 ，令+=*-{}，它是上不含空串的字符串集合。 •对于*的子集L，M，(它们都上的语言)，可以定义下列 四种语言之间的运算。 定义2.5 :语言L和M的连接，LM={xy | x∈L and y∈M}。 基于同一律，{}L=L {}=L，除此而外，通常LM≠ML，即 连接不满足交换律，但满足结合律，即(LM)N=L(MN)。 通常记L²=LL,并约定Lº={}
定义26: 语言L和M的合并,LUM={x|x∈Lor|x∈M} 如同集合间的合并运算那样,它满足结合律,交换律。 定义27: 语言L的闭包,L*=L°UL∪L2UL3U.Ln。 定义28: 语言L的正闭包L+=LUL2UL3U.Ln。 如果Σ把看成是字母表Σ上长度为1的字符串集合,它当然也 是字母表∑上的一个语言,则是语言的自身连接,它也是上 的一个语言,特别令∑°={e},: ∑*=∑∪∑1U∑2Uz3U.∑n ∑+=∑1U∑2U∑3U..∑n 8
8 定义2.6 : 语言L和M的合并，L∪M={x | x∈L or | x∈M}。 如同集合间的合并运算那样，它满足结合律，交换律。 定义2.7 : 语言L的闭包，L*= Lº∪L¹∪L²∪L³∪…L ⁿ 。 定义2.8 : 语言L的正闭包L+= L¹∪L²∪L³∪…L ⁿ 。 如果把看成是字母表上长度为1的字符串集合，它当然也 是字母表上的一个语言，则是语言的自身连接，它也是上 的一个语言，特别令º= {}， ： 则 : *= º∪ ¹∪ ²∪ ³∪… ⁿ += ¹∪ ²∪ ³∪… ⁿ
「例25设字母集合L={a,b,c,…,,数字集合 D={0,1,,9},则 L∪D是字母数字集 LD是一个字母后跟一个数字的字符串集 L*是由字母组成的字符串(包括)集合。 L(L∪D)*是由字母开头的字母数字串的集合。 D+是长度大于等于1的数字串的集合
9 [例2.5]设字母集合L={a,b,c,…z}，数字集合 D={0,1,…9}，则 • L∪D是字母数字集 • LD是一个字母后跟一个数字的字符串集。 • L*是由字母组成的字符串（包括）集合。 • L(L∪D) *是由字母开头的字母数字串的集合。 • D+是长度大于等于1的数字串的集合
二、文法 1.文法的定义 定义29文法G是一个四元组,G=(Vt,vn,S,P),其中 Vt为终结符号集,这是个非空有限集; Vn为非终结符号集,它也是个非空有限集; S为一文法开始符,是一特殊的非终结符, P是产生式的非空有限集,其中每个产生式(或称规则)是 序偶,通常写作:a→β 或 读成是β或定义β为。a是产生式左部,β为产生式右部。 a都是由终结符和非终结符组成的符号串,只是a ∈(tUvn)+且至少有一个非终结符,而β∈(VUVn)*。 10
10 二、文法 1.文法的定义 定义2.9 文法G是一个四元组，G=(Vt,Vn,S,P) ，其中： Vt为终结符号集，这是个非空有限集； Vn为非终结符号集，它也是个非空有限集； S为一文法开始符，是一特殊的非终结符， P是产生式的非空有限集，其中每个产生式(或称规则)是一 序偶,通常写作：α→β 或 α::=β 读成α是β或α定义β为。 α是产生式左部， β为产生式右部。 α,β 都是由终结符和非终结符组成的符号串，只是α ∈(Vt∪Vn)+且至少有一个非终结符，而β∈(Vt∪Vn)*