文档介绍：第二章文法和语言编译过程的核心就是翻译,就是把一种语言翻译成为另一种语言,与自然语言的翻译类似,只不过其工作对象是某种程序设计语言。两个重要的前提: 1)描述和定义程序设计语言 2)识别或分析这种语言 20世纪 50年代,语言学家 Noam Chomsky (乔姆斯基) 提出了一个用来描述语言的数学系统,把用一组数学符号和规则来描述语言的方式叫做形式描述,而把能用数学符号和规则描述的语言称为形式语言。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言。 文法及语言的表示如何来描述一种语言? 1)当一个语言仅含有有限个句子时,可采用枚举法来表示这种语言。对于无限的语言寻找出有限的表示,有两种途径: 2)生成方式( 文法):制定有限条规则,用来生成所要描述的语言中的全部句子。 3)识别方式( 自动机):建立一种装置(更确切的说,是构造一种算法或过程),此装置以某一字母表上的所有符号串作为输入,并识别这些符号串,当一个符号串是此字母表上某给定语言中的句子时,就接受它,反之,则拒绝接受。语言的定义: Webster 定义:为相当大地区的公众所懂得并使用的“话”,以及组成这些“话”的方法的统一体。另一种定义:某一字母表上符号串(句子)的集合一种精确化的语言的要求: (1)为所定义语言中的句子提供一种结构性的描述(2)提供一种手段,准确地判别什么是该语言的正确句子,而什么又不是 基本概念和术语字母表: 元素的非空有穷集合。字母表中的每个元素称为“符号”,因此“字母表”也可称为“符号集”。典型的符号有字母、数字、各种标点符号和各种运算符。例如,集合{a,b,c,+,*}是一个含有 5个符号的字母表, 而字母表{0,1}只有 2个符号。符号串:由字母表上 0个或多个符号所组成的任何有穷序列。特别地,把不包含任何符号的符号串称为空符号串ε。例如有字母表{a,b,c,+,*},则 a,b,c ,+, *, aa,ab,ac,a+,a *, ba,bb,bc,b+,b *, aaa,bbb 等等都是该字母表上的符号串。而所有二进制数都是定义在字母表{0,1}上的符号串。显然,一个字母表上的全部符号串所组成的集合是无穷的。 文法和语言的定义符号串及其集合的运算 1 :指符号串 x中所含符号的个数,记为|x|。如: | abc |=3 ,| abc +* abc |=8 ,|ε|=? 2. 符号串的前缀: 指从符号串 x 的末尾删除 0 或多个符号后得到的符号串,如ε、a、 ab、 abc 都是 abc 的前缀。符号串的后缀:指从符号串 x的开头删除 0或多个符号后得到的符号串,如ε、c、bc、 abc 都是 abc 的后缀。符号串的子串:指从符号串 x的开头和末尾删除 0或多个符号后得到的符号串,如 abc 的子串? 符号串的前缀、后缀都是它的子串。ε、 a 、b 、 c 、 ab、bc、 abc |ε|=0 符号串及其集合的运算 2 :若x、y是两个符号串,则 xy表示连接,是将符号串 y连接在符号串 x的后面。若 x、y是字母表∑上的两个符号串,则 xy也是字母表∑上的符号串。如: x=ab,y=ba,那么 xy=abba 注意:连接没有交换律,即 xy≠yx 对于空串ε有εx=x ε=x 符号串的方幂:一个符号串 x与其自身的 n-1 次连接称为 x的n 次方幂,即: X 0=ε, x 1=x , x 2=xx , …,x n=xx …x=xx n-1=x n-1x 如: x=abc , x 0= ε, x 1=abc , x 2=abcabc ,…符号串及其集合的运算 3 4. 符号串集合的乘积:令A、B 为两个符号串集合, A和B的乘积 AB 定义为: AB={ xy|x ∈ A ,y ∈ B} 例如: A={a , b} B={c ,d},则 AB={ac , ad,bc,bd} 对于{ε}有: {ε}A=A { ε}=A 符号串集合的方幂:设A为符号串集合,则 A的方幂定义为: A 0 ={ε},A 1 =A ,A 2 =AA …… A n =AA … A=AA n-1 =A n-1A 例如: A={a ,b, c} A 0 ={ε}A 1 =={a ,b, c} A 2 =AA={ aa, ab, ac ,ba,bb ,bc, ca , cb, cc} ……符号串及其集合的运算 4 5. 符号串集合的闭包:设 A 为一个集合,则集合 A 的正闭包用 A +表示,定义为: A + =A 1 ∪ A 2 ∪…. ∪ A n∪…集合 A的闭包用 A*表示,定义为: A* =A 0∪ A +例如: A =={a ,b