《编译原理实用教程》-杨德芳-电子教案 第2章　形式语言概述

《《编译原理实用教程》-杨德芳-电子教案 第2章　形式语言概述》由会员分享，可在线阅读，更多相关《《编译原理实用教程》-杨德芳-电子教案 第2章　形式语言概述（97页珍藏版）》请在金锄头文库上搜索。

1、第二章 形式语言概述,本章学习目标,形式语言由Chomsky于1956年提出，主要讨论语言和文法的数学机制以及语言和文法的分类。形式语言 的形成和发展，对编译原理和技术产生了重要的影响。本章主要内容是: 文法和语言的形式定义 文法的分类 句型的分析和语法树,2.1字母表和符号串,任何一种语言都是由基本符号构成的。计算机高级语言作为计算机的语言，程序有语句构成，语句有一些基本符号构成，这些基本符号是保留字如main，if，then等、字母、数字和专用符号等。每个程序可以看成基本符号串。将所有的基本符号定义成一个基本符号集合，则语言可以看成是在这个基本符号集合上定义的，按一定的规则构成的一切基本符

2、号串组成的集合，给出如下的一些基本概念。,2.1.1字母表,定义2.1 字母表是元素的非空有穷集合，字母表中的元素称为符号，因此字母表也称为符号表。高级语言如C语言的字母表是由字母、数字、特殊符号和一些专用符号构成。 例 =a,b， =0,1， =0,1，2，3，4，5，6，7，8，9， =a,b,c,z,if,then,else,main,1,2,3,4,9,0,=,=,;（，）,2.1.2符号串,1符号串 定义2.2 符号串是由字母表中的符号所组成的有穷序列。 例2.1 某个字母表=a,b,c,z,if,then,else,main,1,2,3,4,9,0,=,=,;，则建立在上的符号串有

3、：if (2+3=5) then a=6 else b=8; 2符号串的长度 符号串x中所包含的符号的个数称为符号串x的长度，记为|x| 。例如字母表0，1，则|010110|=6。记为空串，长度为0。,3子字符串 定义2.3 设有非空符号串u=xvy，其中x、v、y是符号串，且v，则称v为符号串u的子符号串。 例题2.2设字母表=a，b，c，d，+，-，*，/，(，)上有符号串x=a+b*(c+d)，则a、a+b*与（c+d）等都是x的子符号串，且其长度分别为a=1、a+b*=4与(c+d)=5 4符号串的头和尾 定义2.4 如果z=xy是一个符号串，则x是z的头,而y是z的尾。如果y非空，

4、则x是z的固有头，又称为真前缀；若x非空，则y是z的固有尾，又称为真后缀。,例题2.3 假设字母表=a,b,c上的符号串z=abc，则、a、ab、abc都是z的头，且除abc外都是x的固有头；、c、bc、abc都是z 的尾，且除abc外都是z的固有尾。 若只对符号串的头部感兴趣，记做z=x。若只对尾部感兴趣，则记为z=x。 5符号串的运算 定义2.5 符号串的连接运算 ：设 x与y是同一个字母表上的两个符号串，把y的各个符号相继写在x的符号后所得到的符号串称为x与y的连接，记为xy。,例题2.4设在字母表a,b,c上有符号串 x=ab与y=cba，则z=xy=abcba。这里x=2, y=3,

5、 z=5。对于字母表上的任何符号串x，都有x=x=x 定义2.6 符号串的方幂：设x是某个字母表上的符号串，把x自身连接n次，即z=xxx（n个x），称为符号串x的n次方幂，记为z=xn。 例如，x=ab 则x3=ababab,2.1.3符号串集合,1符号串集合的定义 定义2.6 若集合A中一切元素都是某字母表上的符号串，则称A是该字母表上的符号串的集合。 字母表上的符号串的集合通常用大写字母来表示A、B、C、表示。 例题2.5 设某个字母表a,b,c,d上有两个符号串的集合记为A=a,bc,B=abc,cd,ab,2符号串集合的运算 定义2.7 两个符号串集合A和B的乘积AB定义为： AB=

6、xyxA ，且yB 例题2.6 设A=a,b，B=c,d,e 则AB=ac,ad,ae,bc,bd,be 对于任何空集合，都有A=A=A 类似于符号串的方幂，可以定义符号串集合的方幂，特别地定义字母表A的方幂为： A0=，A1=A，An=An-1A (n0),3字母表的闭包与正闭包的运算 设有字母表A，由它做方幂A0，A1，A2， An, 。A的闭包定义如下： 定义 2.8 A的闭包A*=A0A1 A2 An,其中，An （n=0，1，2，3，）中所有的符号串的长度为n，因此字母表A的闭包 A*为字母表上一切长度为n的符号串所组成的集合。 如果不允许包含空串，则得到字母表A的正闭包。 定义2.

7、9 A的正闭包 A+=A1 A2 An 显然，A*= A0 A+ ，且A+=AA*=A*A。,例题2.7 设字母表=a,b,c,依次写出长度为1、2的符号串，可得到 的正闭包 + ：+=a,b,c,aa,ab,ac,bb,bc,在+上添入空串即得*。 说明：根据闭包和正闭包的定义，则有+=*=* 由于一个字母表的正闭包包含了该字母表中的符号所能组成的一切符号串，而语言是该字母表上某个符号串的集合，因此，在某个字母表上的语言是该字母表上正闭包的子集，且是真子集。对于C语言，可以说，C语言是基本符号集合的正闭包的真子集。,2.2 文法的定义及其分类,什么是文法，文法的直观概念是，文法作为一种工具，

8、不仅严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。,2.2.2文法的形式定义,1重写规则 定义2.10 重写规则，也叫产生式规则，或称为生成式，是形如或:的（,）有序对,其中, 是某个字母表V+中的一个元素，是V* 中的一个元素。称为规则的左部，称为规则的右部。 例如 AB读作“A定义为B”，也就是说它是一条关于A的规则（产生式）。 2文法 定义2.11 文法G是一个四元组，G=（VN，VT，P，S），其中，VN、VT分别是非空有限的非终结符号集和终结符号集，VNVT=，P是产生式的集合，SVN 称为文法的识别符号或开始符号。 例题

9、2.8在程序设计语言中，假设我们定义标识符的命名规则为字母a、b、c开头的，字母a、b、c和数字1、2、3的序列。命名规则为：, a b c 1 2 3,我们一般用大写字母代表左边的非终结符，设N 代表，D代表，L代表，则定义标识符的文法是： G=(VN，VT，P，N) 其中，VN=N，L，D VT=a,b,c,1,2,3 P为产生式的规则： NL， NNL ，NND ，La ，Lb ，Lc ，D1 ，D2，D3 S 是开始符号,为N. 关于产生式的规则说明一点，即若A，A，A可写成A| 。“|”读做“或者”。 上面的产生式规则可以改写为：,P为产生式的规则： NL|NL|ND La|b| c

10、 D1|2|3 ,2.2.3文法的分类,自从乔姆斯基（Chomsky）于1956年建立形式语言的描述以来，把文法分成四种类型，即0型、1型、2型和3型文法。 0型文法(短语文法) 设G=（VN，VT，P，S），如果它的每个产生式是这样一种结构：（VNVT ）+ ，且至少含有一个非终结符，而（VNVT ）*，则称G是一个0型文法。0型文法又称短语文法，它的能力相当于一个图灵机。 例如，A,1型文法（上下文有关文法） 设G=（VN，VT，P，S）为一文法，若P中的每一个产生式均满足，仅仅S除外，则文法G是1型文法或上下文有关文法。 所谓上下文有关文法即：=1A2，=12，符号串1 和2可以认为是上

11、下文，A只有出现在上下文之间中，才可以被符号串替代，成为=1A2=12因此，1型文法又称为上下文有关文法。,32型文法（上下文无关文法） 设G=(VN，VT，P，S)，若P中的每个产生式满足: 是一个非终结符, (VNVT ) *，则此文法称为2 型文法或上下文无关文法。有时将2型文法的产生式表示为形如：A，其中AVN 。 也就是当用取代非终结符A时，与A所在的上下文无关。上下文无关文法有足够的能力描述现今的程序设计语言。,例题2.10 2 型文法 G=（VN，VT，P，N） 其中，VN=N，D VT=0，1，2，3，4，5，6，7，8，9 P=NNDD，D0123456789 该文法描述的符

12、号串的集合是整数。,3型文法（右线性文法或正规文法） 对2型文法的产生式做进一步的限制，限制产生式右部是单一终结符或单一终结符跟着单一非终结符，即： Aa AaB 则称该文法为3型文法，又称为右线性文法或正规文法，其中A、BVN，aVT. 例题2.11 3型文法 G=（VN，VT，P，S） 其中，VN=S，A，B VT=0，1 P=S011A0B，A 1A0B，B010B 该文法产生的是二进制整数。,2.2.4文法举例,例题2.15 正规文法G=（VN，VT，P，A） 其中, VN=A,B,C,D VT=x,y,z P=AxByC BzB yyC CxD D yDx 例题2.162型文法G=（

13、VN，VT，P，E） 其中，VN=E，T，F VT=+，*，（，），i P=EE+T|T, TT*F|T, F(E)|i 该文法能推出具有乘和加运算的算术表达式。,例题2.17正规文法G=（VN，VT，P，S）其中VN=S，A，B，G，H，VT=d，+， P=SdB|+A|A|.G AdB|.G BdB|.H|d GdH HdH|d 其中，d代表十进制数字。 根据以上我们对文法的定义我们不难发现3型文法类是2型文法类的特殊情况，2型文法类是1型文法类的特殊情况。每一类文法都是在前一类文法的基础上加上一些限定规则而产生的。因此，四类文法产生的语言就会有如下关系： 3型语言2型语言1型语言0型语言

14、,2.2.5各类文法与自动机的关系,语言是句子的集合，而句子又是由字母表上的符号串组成的。对于程序设计语言来讲，程序由语句构成，语句则有数字、标识符、保留字、数字等单词构成。因此对程序的编译事实上就是对句子进行检查。方法就是编写一个检查过程，运行该过程来判断编写的程序是否合法。合法就回答“正确”，不合法就回答“不正确”，并且将错误报出。,编写该过程的算法，抽象成一个数学模型，该数学模型称为自动机。将算法对程序的合法与否的检查转化为数学模型对程序中的句子的识别过程。自动机给出了用有穷方式来描述潜在的无穷的语言的另一种手段。自动机能够识别的句子的集合称为语言。对于每一类Chomsky语言类，正好有

15、一类自动机与它相对应。,10型语言与图灵机,图灵机是识别0型文法的识别装置。图灵机被引进作为描述过程的数学模型，过程的直观概念被看成是能机械实现的有穷指令的序列。图灵机的基本模型如图2-1所示。它有一个有限控制器、一个被分成若干单元的输入带和一个一次读入一个单元的读头组成,21型文法与线性界限自动机相对应,。 上下文有关文法所对应的自动机称为线性界限自动机。其功能是能够识别上下文无关语言，缩写为LBA。,32型语言与下推自动机,2型语言或上下文无关语言对应的自动机称为下推自动机。它是识别上下文无关语言的数学模型。缩写为PDA。,3型语言与有穷状态自动机,3型语言或正则语言所对应的自动机称为有穷自动机。缩写为FA。 无论那种自动机都分为确定性和非确定性之分,2.2.6文法分类的意义,一个文法实际上是某种语言的一个简明、确切的描述，它表示了该语言中所允许的一类语法结构。从一个文法能推导出多个终结符的句子。但是知道了如何去构造属于某一个语言的一个合法串只是问题的一个方面。同时我们还要有能力判定一个串是否合法。