编译原理实用教程 杨德芳 第2章 形式语言概述

《编译原理实用教程 杨德芳 第2章 形式语言概述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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符号串是由字母表中的符号

3、所组成的有穷序列。例2.1某个字母表∑={a,b,c,…z,if,then,else,main,1,2,3,4,…,9,0,=,==,>,<,;}，则建立在∑上的符号串有：if(2+3==5)thena=6elseb=8;2．符号串的长度符号串x中所包含的符号的个数称为符号串x的长度，记为

4、x

5、。例如字母表{0，1}，则

6、010110

7、=6。ε记为空串，长度为0。3．子字符串定义2.3设有非空符号串u=xvy，其中x、v、y是符号串，且v≠ε，则称v为符号串u的子符号串。例题2.2设字母表Σ={a，b，c，d，+，-，*

8、，/，(，)}上有符号串x=a+b*(c+d)，则a、a+b*与（c+d）等都是x的子符号串，且其长度分别为∣a∣=1、∣a+b*∣=4与∣(c+d)∣=54．符号串的头和尾定义2.4如果z=xy是一个符号串，则x是z的头,而y是z的尾。如果y非空，则x是z的固有头，又称为真前缀；若x非空，则y是z的固有尾，又称为真后缀。例题2.3假设字母表={a,b,c}上的符号串z=abc，则ε、a、ab、abc都是z的头，且除abc外都是x的固有头；ε、c、bc、abc都是z的尾，且除abc外都是z的固有尾。若只对符号串的头部感

9、兴趣，记做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,∣z∣=5。对于字母表上的任何符号串x，都有εx=xε=x定义2.6符号串的方幂：设x是某个字母表上的符号串，把x自身连接n次，即z=xx…x（n个x），称为符号串x的n次方幂，记为z=xn。例如，

10、x=ab则x3=ababab2.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={xy∣x∈A，且y∈B}例题2.6设A={a,b}，B={c,d,e}则AB={ac,ad,ae,bc,bd,be}对于任

11、何空集合Φ，都有ΦA=AΦ=A类似于符号串的方幂，可以定义符号串集合的方幂，特别地定义字母表A的方幂为：A0={ε}，A1=A，An=An-1A(n>0)3．字母表的闭包与正闭包的运算设有字母表A，由它做方幂A0，A1，A2，…An,…。A的闭包定义如下：定义2.8A的闭包A*=A0∪A1∪A2∪…∪An∪…,其中，An（n=0，1，2，3，…）中所有的符号串的长度为n，因此字母表A的闭包A*为字母表上一切长度为n的符号串所组成的集合。如果不允许包含空串ε，则得到字母表A的正闭包。定义2.9A的正闭包A+=A1∪A2∪…

12、∪An∪…显然，A*=A0∪A+，且A+=AA*=A*A。例题2.7设字母表Σ={a,b,c},依次写出长度为1、2…的符号串，可得到Σ的正闭包Σ+：Σ+={a,b,c,aa,ab,ac,bb,bc,…},在Σ+上添入空串ε即得Σ*。说明：根据闭包和正闭包的定义，则有Σ+=Σ*Σ=ΣΣ*由于一个字母表的正闭包包含了该