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

《编译原理-蒋立源第2章文法和语言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章文法和语言编译过程的核心就是翻译，就是把一种语言翻译成为另一种语言，与自然语言的翻译类似，只不过其工作对象是某种程序设计语言。两个重要的前提：1）描述和定义程序设计语言2）识别或分析这种语言20世纪50年代，语言学家NoamChomsky（乔姆斯基）提出了一个用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方式叫做形式描述，而把能用数学符号和规则描述的语言称为形式语言。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言。2.1文法及语言的表示如何来描

2、述一种语言？1）当一个语言仅含有有限个句子时，可采用枚举法来表示这种语言。对于无限的语言寻找出有限的表示，有两种途径：2）生成方式（文法）：制定有限条规则，用来生成所要描述的语言中的全部句子。3）识别方式（自动机）：建立一种装置（更确切的说，是构造一种算法或过程），此装置以某一字母表上的所有符号串作为输入，并识别这些符号串，当一个符号串是此字母表上某给定语言中的句子时，就接受它，反之，则拒绝接受。语言的定义：Webster定义：为相当大地区的公众所懂得并使用的“话”，以及组成这些“话”的方法的统一体

3、。另一种定义：某一字母表上符号串（句子）的集合一种精确化的语言的要求：（1）为所定义语言中的句子提供一种结构性的描述（2）提供一种手段，准确地判别什么是该语言的正确句子，而什么又不是2.2.1基本概念和术语字母表：元素的非空有穷集合。字母表中的每个元素称为“符号”，因此“字母表”也可称为“符号集”。典型的符号有字母、数字、各种标点符号和各种运算符。例如，集合{a，b，c，+，*}是一个含有5个符号的字母表，而字母表{0，1}只有2个符号。符号串：由字母表上0个或多个符号所组成的任何有穷序列。特别地，

4、把不包含任何符号的符号串称为空符号串ε。例如有字母表{a，b，c，+，*}，则a,b,c,+,*,aa,ab,ac,a+,a*,ba,bb,bc,b+,b*,aaa,bbb等等都是该字母表上的符号串。而所有二进制数都是定义在字母表{0，1}上的符号串。显然，一个字母表上的全部符号串所组成的集合是无穷的。2.2文法和语言的定义符号串及其集合的运算11.符号串的长度：指符号串x中所含符号的个数，记为

5、x

6、。如：

7、abc

8、=3，

9、abc+*abc

10、=8，

11、ε

12、=？2.符号串的前缀：指从符号串x的末尾删除0

13、或多个符号后得到的符号串，如ε、a、ab、abc都是abc的前缀。符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串，如ε、c、bc、abc都是abc的后缀。符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的符号串，如abc的子串？符号串的前缀、后缀都是它的子串。ε、a、b、c、ab、bc、abc

14、ε

15、=0符号串及其集合的运算23.符号串的连接：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表∑上的两个符号串，则xy也是字母表∑上的符号

16、串。如：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,…符号串及其集合的运算34.符号串集合的乘积：令A、B为两个符号串集合，A和B的乘积AB定义为：AB={xy

17、x∈A，y∈B}例如：A={a，b}B={c，d}，则AB={ac，ad，bc，bd

18、}对于{ε}有：{ε}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，cb，cc}……符号串及其集合的运算45.符号串集合的闭包：设A为一个集合，则集合A的正闭包用A+表示，定义为：A+=A1∪A2∪….∪An∪…集合A的闭包用A*表示，定义为：A*=A0∪A+例如：A=={a，b，c}则A

19、+={a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,…}A*={ε,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,…}可见，字母表A的正闭包A+就是由A中字母所构成的一切符号串的集合，而A*仅比A+多个ε。2.2.2文法和语言的形式定义在学习英语时，我们知道句子由主语、谓语组成，主语由冠词、形容词及名词组成等等，这就是说明句子组成的规则。而在形式语言里，这种规则可采用“<句子>::=<主语><谓语