编译原理蒋立源 第2章 文法和语言.ppt

编译原理蒋立源 第2章 文法和语言.ppt第二章文法和语言编译过程的核心就是翻译,就是把一种语言翻译成为另一种语言,与自然语言的翻译类似,只不过其工作对象是某种程序设计语言。两个重要的前提:1)描述和定义程序设计语言2)识别或分析这种语言20世纪50年代,语言学家NoamChomsky(乔姆斯基)提出了一个用来描述语言的数学系统,把用一组数学符号和规则来描述语言的方式叫做形式描述,而把能用数学符号和规则描述的语言称为形式语言。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言。?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}上的符号串。显然,一个字母表上的全部符号串所组成的集合是无穷的。:指符号串x中所含符号的个数,记为|x|。如:|abc|=3,|abc+*abc|=8,|ε|=?:指从符号串x的末尾删除0或多个符号后得到的符号串,如ε、a、ab、abc都是abc的前缀。符号串的后缀:指从符号串x的开头删除0或多个符号后得到的符号串,如ε、c、bc、abc都是abc的后缀。符号串的子串:指从符号串x的开头和末尾删除0或多个符号后得到的符号串,如abc的子串?符号串的前缀、后缀都是它的子串。ε、a、b、c、ab、bc、abc|ε|=:若x、y是两个符号串,则xy表示连接,是将符号串y连接在符号串x的后面。若x、y是字母表∑上的两个符号串,则xy也是字母表∑上的符号串。如:x=ab,y=ba,那么xy=abba注意:连接没有交换律,即xy≠yx对于空串ε有εx=xε=x符号串的方幂:一个符号串x与其自身的n-1次连接称为x的n次方幂,即:X0=ε,x1=x,x2=xx,…,xn=xx…x=xxn-1=xn-1x如:x=abc,x0=ε,x1=abc,x2=abcabc,…:令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的方幂定义为:A0={ε},A1=A,A2=AA……An=AA…A=AAn-1=An-1A例如:A={a,b,c}A0={ε}A1=={a,b,c}A2=AA={aa,ab,ac,ba,bb,bc,ca,}……:设A为一个集合,则集合A的正闭包用A+表示,定义为:A+=A1∪A2∪….∪An∪…集合A的闭包用A*表示,定义为: A*=A0∪A+例如:A=={a,b,c}则A+={a,b,c,aa,ab,ac,ba,bb,bc,ca,,aaa,aab,…}A*={ε,a,b,c,aa,ab,ac,ba,bb,bc,ca,,aaa,aab,…}可见,字母表A的正闭包A+就是由A中字母所构成的一切符号串的集合,而A*仅比A+多个ε。,我们知道句子由主语、谓语组成,主语由冠词、形容词及名词组成等等,这就是说明句子组成的规则。而在形式语言里,这种规则可采用“<句子>::=<主语><谓语>”、“<主语>::=<冠词