编译原理与实现02第2章文法和语言

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

1、第二章文法和语言编译过程的核心就是翻译，这是一个十分复杂的信息加工过程，其加工的对象是用某种高级语言编写的程序。对于一个英文翻译来说，首先必须对英文有很深的了解，掌握英文的语法和词汇，才能进行翻译。而编译程序的任务就是将高级语言编写的程序翻译成机器语言程序，因此，在学习和掌握编译技术之前，就需要对高级语言有深刻的了解。首先要了解如何确切地描述或定义一种程序设计语言，其次才能识别和分析这种语言。20世纪50年代，语言学家NoamChomsky（乔姆斯基）提出了一个用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方

2、式叫做形式描述，而把能用数学符号和规则描述的语言称为形式语言。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言2.1字母表和符号串介绍文法和语言之前，首先介绍符号、符号串等基本概念。任何一种语言都是由该语言的基本符号所组成的符号串集合的子集。例如，英语的基本符号有26个字母和一些标点符号，由这些基本符号所组成的各种可能序列的符号串构成一个无穷的集合，而英语就是这个集合的子集。同理，C语言的基本符号有if,while,for,…,字母、数字和+、-、（、）、>=等分界符，由这些符号组成的

3、各种可能序列的符号串构成一个无穷的集合，而C语言就是这个集合的子集。任何一个C语言程序都是定义在这个集合上的符号串，即任何一个C语言程序都是由这些基本符号所组成的序列。2.1.1字母表“字母表”是元素的非空有穷集合。字母表中的每个元素称为“符号”，因此“字母表”也可称为“符号集”。典型的符号有字母、数字、各种标点符号和各种运算符。例如，集合{a，b，c，+，*}是一个含有5个符号的字母表，而字母表{0，1}只有两个符号。2.1.2符号串“符号串”是由字母表上0个或多个符号所组成的任何有穷序列。例如有字母表{a，b，c，+

4、，*}，则a,b,c,+,*,aa,ab,ac,a+,a*,ba,bb,bc,b+,b*,aaa,bbb等等都是该字母表上的符号串，而所有二进制数都是定义在字母表{0，1}上的符号串。要注意ε也是字母表上的符号串，它由0个符号组成。显然，一个字母表上的全部符号串所组成的集合是无穷的。2.1.3符号串及其集合的运算11.符号串的长度：指符号串x中所含符号的个数，记为

5、x

6、。如

7、abc

8、=3，

9、abc+*abc

10、=8，而

11、ε

12、=02.符号串相等：若x、y是字母表∑上的两个符号串，那么当且仅当组成x的各符号与组成y的各符号依次

13、相等时，则符号串x与符号串y相等，记作x=y。如：当x=abbc，y=abbc时，则x=y；而当x=ab，y=ba时，则x≠y3.符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串，如u、uni、university都是university的前缀。4.符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串，如ty、sity、university都是university的后缀。2.1.3符号串及其集合的运算25.符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的符号串，如ver是univer

14、sity的子串,符号串的前缀、后缀都是它的子串。6.符号串的连接：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表∑上的两个符号串，则xy也是字母表∑上的符号串。例如：x=ab，y=ba，那么xy=abba注意：连接没有交换率，即xy≠yx而对于空串ε有εx=xε=x2.1.3符号串及其集合的运算37.集合的乘积运算：令A、B为两个符号串集合，A和B的乘积AB定义为：AB={xy

15、x∈A，y∈B}例如：A={a，b}B={c，d}，则AB={ac，ad，bc，bd}对于空集合有{ε

16、}有：{ε}A=A{ε}=A8.符号串的幂运算：若x是符号串，则x的幂运算定义为：X0=ε,x1=x,x2=xx,…，xn=xx…x=xxn-1=xn-1x,其中n>0例如：x=abc,x0=ε,x1=abc,x2=abcabc,…2.1.3符号串及其集合的运算49.集合的幂运算：设A为符号串集合，则A的幂运算定义为：A0={ε}A1=AA2=AA……An=AA…A=AAn-1=An-1A，其中n>0例如：A=={a，b}，则A0={ε}A1={a,b}A2={aa,ab,ba,bb}2.1.3符号串及其集合的运算410

17、.集合的正闭包和集合的闭包：设A为一个集合，则集合A的正闭包用A+表示，定义为：A+=A1∪A2∪….∪An∪…集合A的闭包用A*表示，定义为：A*=A0∪A+例如：A=={a，b}，则A+={a,b,aa,ab,ba,bb,aaa,aab,…}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}一个集合