编译原理蒋立源文法和语言

《编译原理蒋立源文法和语言》由会员分享，可在线阅读，更多相关《编译原理蒋立源文法和语言（56页珍藏版）》请在金锄头文库上搜索。

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

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

3、，准确地判别什么是该语言的正确句子，而什么又不 是2.2.1基本概念和术语 字母表：元素的非空有穷集合。字母表中的每个元素称为“ 符号”，因此“字母表”也可称为“符号集”。典型的符号有字 母、数字、各种标点符号和各种运算符。例如，集合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等等都是该字母 表上的符号串。而所有二进制数都是定义在字母

4、表0，1上的符号串。显然，一个字母表上的全部符号串所组成的集合是无穷的。 2.2 文法和语言的定义 符号串及其集合的运算11.符号串的长度：指符号串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 、a

5、b 、bc 、abc|=0符号串及其集合的运算23.符号串的连接：若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=xxx=xxn-1=xn-1x 如：x=abc, x0= , x1=abc, x2=abcabc,符号串及其集合的运算34.符号串集合的乘积：令A、B为两个符号串集合，A

6、和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=AAAn=AAA=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 . A n 集合A的闭包用A*表示，定义为： A* =A 0 A+ 例如：A =a，b ，c则

7、A+ =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 文法和语言的形式定义 在学习英语时，我们知道句子由主语、谓语组成，主语由冠词 、形容词及名词组成等等，这就是说明句子组成的规则。而在 形式语言里，这种规则可采用“:=”、“:=”这种形式来表示。分析一个句 子是否正确，就是根据这些规则进行的。实际上，文法就是描 述语言语法结构的形式规则。 从“产生语言”的角度出发

8、，给出方法和语言的形式定义。产生语言：指制定出有限个规则，借助这些规则可以产生此语 言的全部句子。 文法形式定义1 在表示文法时，要说明语言的语法成分(语法范畴），句子中的 符号以及语法结构。例如，能够描述句子“the monkey ate a banana”的文法如下：在这个文法里，其中用“”符号 括起来的部分，表示评议的一个语法 实体。符号“:=”是一个整体，其含义是 “定义为”，也就是左边的语法实 体可进一步定义为右边的符号串。在 推导过程中，就是一种“替换”关系 。而像the、ate、banana这样的符号只 在规则中:=的右边出现，不需要进 一步定义，这些符号不能用其它符号 代替。我

9、们最终需定义的语法成分是 。每条规则的形式都是:=。1) := 2) := the 3) := 4) := 5) := monkey6):= banana 7) := ate 8) := has9) := the 10) := a“:=”表示“ 定义为”文法形式定义2 = = = the = the = the monkey = the monkey ate = the monkey ate a = the monkey ate a banana如何用上述规则去 产生或推导出相应 语言的句子呢？=+ the monkey ate a banana“=”表示一步推导“=+”表示多步推导文法形式定

10、义3文法的形式定义：文法可表示为一个四元组GS=（ VN ， VT ，P，S）VN是一个非空有穷集合，该集合中的每个元素称为非终结符号。如上例中 VN=、VT是一个非空有穷集合，该集合中的每个元素称为终结符号。如上例中 VT=monkey、banana、ate、has、the、a 并且VNVT=，而VNVT称为该文法的字汇表。P是一个非空的有穷集合，它的每个元素叫做产生式或规则。产生式的形式 为： 或:=是产生式的左部且不能为空，是产生式的右部，并且、V。S是VN集合的一个特殊的非终结符号，称为文法的开始符号。它至少必须在 某个产生式的左部出现一次。就是上例文法的识别符号。 文法形式定义4文法

11、分4种类型（见2.5小节），程序设计语言文法主要为2型 文法，这种文法也叫前后文无关文法，本书后面说的文法都 是指这种文法。在前后文无关文法中，产生式的左部是一个非终结符号，而 右部是由终结符号和非终结符号组成的有穷符号串。这样只 要给出产生式集合，所有产生式的左部符号就构成了非终结 符号集合VN，而只出现在产生式右部的那些符号构成终结符 号集合VT，因此，在表示文法时只需给出规则集合并指定识 别符号即可。为了进一步简化，在给出规则集时，可约定将 左部符号为开始符号的规则作为规则集合的第一条规则，这 样表示文法时只需给出规则的集合即可。显然，上例就是一 个简化的文法表示。 文法形式定义5例2.

12、2，有如下简化表示文法 ，只给出规则集，写出该文法的 终结符号集合、非终结符号集合 和开始符号。1.2.3.4.05.16.27.38.49.510.611.712.813.9解：根据简化约定，可确定：非终结符号集合：VN=,终结符号集合：VT=0,1,2,3,4,5,6,7,8,9开始符号S： 文法的EBNF表示 所谓文法的EBNF表示，就是在书写文法的规则时，可采用一些特殊的符 号“|”、“”和“”、 “（” 和“）”、“” 和“”来表示文法，这些符号叫做元 符号。其中“”和“”、 “（” 和“）”、“” 和“”这些元符号总是成对出现。 下面介绍各种元符号的含义。 1.元符号“|”：表示“

13、或”.对于具有相同左部的那些规则如 1、 、 n，可以缩写为: 1 | 2 | n例2.3，对例2.2文法的13条规则可缩写成： | 0|1|2|3|4|5|6|7|8|9 文法的EBNF表示2.元符号“”和“”：表示可重复连接，tnm表示符号串t可重复连 接n到m次，而t表示符号串t可重复连接0到无穷次。例如，13 与 | 相同EE+T|T 与 ET+T 相同而字母打头、后面可跟数字或字母的不超过8个字符的标识符文法则为：|07文法的EBNF表示3.元符号“”和“ ”：表示括起的内容可有可无。如t表示符号串t 可有可无。例如：IF THEN IF THEN ELSE 可写成：IF THEN

14、ELSE 4.元符号“（”和“）”：表示括号内的成分优先。常用于在规则中 提取公因子。例如，Uxy|xw|xz 可写成：Ux（y|w|z）从上述有关元符号的定义和例子可看出，这些元符号为表示文法 提供了很大方便。 直接推导 设GS是一文法, 是该文法的一个产生式，对于符号串 xy ，其中x和y是该文法的任意符号串(可为空),推导就是用 产生式的右部替换左部，从而得到新的符号串xy。表 示为：xy=xy其中“=”表示一步推导。我们称xy直接推导出xy,或 xy直接产生xy。若从反方向看，则称xy直接归约到xy 。 x,yV*直接推导例如有文法 1） 2） |3） 0|1|2|3|4|5|6|7|

15、8|9对符号串利用规则1可直接推导出：= 对符号串利用规则2可直接推导出：= 对符号串利用规则3可直接推导出2：= 2 将上述三个推导连接起来，可得如下推导过程：= = = 2推导 如果文法GS存在一直接推导序列0=1=n，其中n0, 那么我们 说 0推导出n或n归约到0,并记作0 =+n,推导长度为n。如果有0= + n 或0 = n, 即n 0,则记作0= * n 。可见，n0的推导和n=0分别称为“+推导”和“*推导”。例如，从开始，分别利用规则1、2、2、3、3，可产生如下推 导过程：=2=23这个推导过程可记作：=+23 ， 其推导长度n=5，而从到的推导，无须使用任何规则，可记作：=* ，其推导长度n=0。 句型和句子 推导产生的结果可能是句型，也可能是句子。设文法G的识别符 号为S，则句型、句子的定义如下：1. 如果S =*, 且 V*, 则称是文法GS