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

1、第二章语法和语言，编译过程的核心是翻译。这是一个非常复杂的信息处理过程，其处理对象是用某种高级语言程序编写的程序。对于英语翻译，首先要深入了解英语，掌握英语的语法和词汇，才能翻译。节目编译的任务是将高级语言编写程序翻译成机器语言程序，因此在学习和掌握编译技术之前，需要对高级语言有深刻的了解。首先要知道如何正确说明或定义一个编程语言，然后才能识别和分析下一种语言。20世纪50年代，语言学家Noam Chomsky提出了描述语言的数学系统，用数学符号和规则集描述语言的方式称为形式描述，用数学符号和规则描述的语言称为形式语言。这种理论在编程语言设计和编译程序的结构中起着重要作用。编程语言在介绍形式语

2、言、2.1字母表、符号字符串、语法和语言之前，先介绍符号、符号字符串等基本概念。所有语言是由该语言的基本符号组成的符号字符串集的子集。例如，英语基本符号包括26个字符、标点符号以及由这些基本符号组成的各种可能序列的符号字符串构成无限集合，英语是牙齿集合中的子集。同样，C语言的默认符号是if、while、for、字母、数字和、-、(，)、=等分隔符，由这些符号组成的各种可能序列的符号字符串构成无限集，C语言是牙齿集的子集。所有C语言程序都是在牙齿集合中定义的符号字符串。也就是说，所有C语言程序都是由这些基本符号组成的序列。2.1.1字母，“字母”是元素非空的穷集。字母表中的每个元素名称称为“符号

3、”，因此“字母”有时称为“符号集”。典型符号包括文字、数字、各种标点符号和各种运算符。例如，集合A、B、C、*是包含5个符号的字母，但是字母0，1中只有2个符号。2.1.2符号字符串，“符号字符串”是字母表中包含零个或多个符号的所有有限序列。例如，字母a、b、c、*、a、b、c、*、aa、ab、AC、a、a *、ba、bb、BC、b、b *。由0个符号组成。显然，字母表中所有符号字符串的集合是无限的。2.1.3符号字符串和该集的运算1，1。符号字符串的长度：表示符号字符串x中包含的符号数，写为|x|。例如，|abc|=3，|abc *abc|=8和|=0 2。符号字符串相同。如果x，y是字母表

4、中的两个符号字符串，则仅当构成x的每个符号与构成y的每个符号按顺序相同时，符号字符串才是示例：x=abbc，y=abbc x=y；xy 3(如果X=ab，y=ba)。符号字符串的前缀：表示从符号字符串x的结尾删除零个或多个符号后得到的符号字符串(例如，u、uni、university都是university的前缀)。4.符号字符串的后缀：表示从符号字符串x开头删除零个或多个符号后得到的符号字符串(例如，ty、sity和university都是university的后缀)。2.1.3符号字符串及其集合的运算2，5。符号字符串的子字符串：表示从符号字符串x的开头和结尾删除零个或多个符号后得到的符号

5、字符串。例如，ver是university的子字符串，符号字符串的前缀和后缀是子字符串。6.连接符号字符串：如果x，y是两个符号字符串，则xy表示连接，符号字符串y连接在符号字符串x之后。如果x，y是字母表中的两个符号字符串，则xy也是字母表中的符号字符串。例如：x=AB，y=ba，xy=AB=ac注意：连接没有交换率，即xy yx，对于空字符串，x=x=x，2.1.3符号字符串和该集合中的运算3，7。有聚合乘积运算，在Ad、BC、BD null集合中，A=A=A 8。符号字符串的功率运算。如果x是符号字符串，则x的功率运算定义为X0=、x1=x、x2=xx、xn=XXX，其中2.1.3符号字

6、符串和该集中的运算4，9。集的功率运算：如果将a设定为符号字串集，则a的功率运算为A0=aA=aa2=aA an=AAA=aA n-1=a n-；2.1.3符号字符串及其集合的运算4，10。如果将集合的正闭包和集合的闭包：A设置为集合，集合A的正闭包将显示为A，A=A1 A2 .A n集A定义的闭包显示为A*。定义为a *，2.2语法，在英语学习的时候，知道句子是由主语、谓语、主语、冠词、形容词、名词组成的。这是句子构成的规则。在形式语言中，牙齿规则可以表示为“:3360=”、“:3360=”。分析一个句子是否正确，就是基于牙齿规则。语法实际上是描述语言语法结构的形式规则。2.2.1语法格式定

7、义1，表达语法时要说明语言的语法成分，句子的符号和语法结构。例如，可以解释文章“the monkey ate the banana”的语法如下：这些规则说明句子由主语和谓语组成，主语由冠词和名词等组成，冠词由the组成，名词由banana或monkey组成。牙齿语法共有8条规则，在每条规则中，3360=左侧的符号充当语法成分，可以替换为：3360=右侧的符号。The、ate和banana等符号仅出现在规则中：3360=的右侧，不能替换为其他符号。=:=3:=3:3:=33:3360=333:=333:以上示例中的符号、等。Vt是一个非空的穷集合，牙齿集合中的每个元素称为终止符号。在上例中，符号

8、the、ate、banana等都是终止符号。VtVn=，即Vt集合和Vn集合的交集为空。Vt和Vn相结合的VtVn是牙齿语法的词汇(即词汇字母表)。p是一个非空的穷集合，它的每个元素称为生成式或规则。生成格式：或：3360=生成表达式的左侧部分，不能为空。生成表达式的右侧部分。(VtVn)*、或 :3360=表示“定义”，Z是Vn集合的特殊未终止符号，称为语法的标识符或起始符号。它至少应该在某个生成式的左边出现一次。就是上面例子语法的识别符号。2.1语法格式定义3，语法分为4茄子类型(见2.13节)，编程语言语法主要是2型语法，牙齿语法也称为上下文无关文法()，牙齿书后面说的语法都是指这种语法

9、。上下文无关文法中，生成式的左边是未终止的符号，右边是由终止者和未终止的符号组成的可怜符号字符串。这样，如果只给出了生成表达式集，则所有生成表达式的左侧符号构成了未终止的符号集Vn，仅出现在生成表达式右侧部分的符号构成了终止符号集Vt，因此，在表示语法时，只需提供规则集并指定标识符即可。为了进一步简化，提供规则集时，左侧符号为标识符的规则可以用作规则集中的第一个规则。这样，在表示语法时，只需要提供规则集。显然，以上例子是简单的语法表达。2.1语法格式定义4，示例2.1，根据语法格式定义表达常例语法。解决方案：根据语法的格式定义，语法G1=(Vn，Vt，P，Z)非终止符号集： Vn=文章，主语，

10、谓语，冠词，名词，动词，直接宾语终止符号集： Vt=the The ate，1 . 2 . 3 . 4 . 0 5 . 1 6 . 2 7 . 3 8 . 4 9 . 5 10 . 6 11 . 7 12 . 8 13 . 9，解决方案：可以根据简化规则确定：未终止的符号集：Vn=，终止符号集：vt=0这些符号称为元符号。其中，“”和“”、“”、“”和“”、“”、“”、“”和“”这些元符号始终成对出现，以下说明了各种元符号的含义：1 .元符号“|”:“或”。具有相同左侧的规则(1，n)可以缩写为： 1 | 2 | n示例2.3，示例2.2语法的13个规则可以缩写为33603333，等。3.元符

11、号“”和“”:表示可重复连接tnm表示符号字符串t可重复连接n到m次；t表示符号字符串t可重复连接0到无限。例如，13等于| |的EE T|T等于E T，字母开头，后面可以跟数字或字母的8个字符以下的标识符语句规则是|07，2.2.2语法的EBNF表示法，4 .元符号“”和“:”。t表示符号字符串t是可选的。例如：IF THEN IF THEN ELSE可以写如下：IF THEN ELSE 5 .元符号“(”和“)”:表示括号中的组件优先。常用于从规则中萃取公用系数。例如，Uxy|xw|xz可以写为Ux(y|w|z)。如上元符号的定义和示例所示，这些元符号在表达语法方面非常方便。2.3柔道，如

12、果给出了语法，就可以从语法的开始符号开始，根据语法规则进行推理。通过归纳可以生成语法定义的句子。例如，根据示例2.1语法的规则，可以从起始符号推送，根据规则，推送可以表示为：=此处“=”表示一级派生，上述派生过程可以通过两级派生来派生。2.5.1直接派生，g假定为语法，假定为语法的生成表达式，具有现有未终止符号的符号字符串xy。其中x和y是语法中的所有符号字符串(可以为空)，派生使用生成表达式替换符号字符串xy中的未终止符号，从而得到符号字符串xy。Xy=xy。其中“=”表示一级派生。我们称xy直接诱导xy，或xy直接生成xy。从相反的方向看，xy直接返回xy。2.5.1直接派生(例如语法1)

13、:=2)3360:=| 3):3360=0 | 1 | 2 | 3 | 4 | 5 |，如果0=n或0=n，即n 0牙齿，则记录为0=* n。例如，您可以分别使用规则1、2、2、3和3从头开始创建以下衍生进程：=2=23牙齿衍生程序可以记录为=23。导出长度n=5产生23或23，从到的导出不使用任何规则，而是记录为=*，导出长度n=0。2.3.3规格柔道，规格推导也称为最右边推导。也就是说，每个步骤推导仅转换最右侧的非端点符号。对于直接衍生xy=xy，如果y仅包含终止符号或为空符号字符串，则此类衍生称为规范衍生或最右侧的衍生(如果仅包含终止符号或为空符号字符串，则称为最左侧的衍生)，并将写入为

14、3360 xUy=|=xuy。其中，y Vt*导出0=n的每个步骤都是规格，则导出0=n称为规格，记录为： 0 0=|=n。例如，衍生序列如下：=3=3=23牙齿派生序列是规范派生的，=假设语法G的标识符是Z，GZ，词汇VtVn，句型和句子定义如下：1.如果Z=*x，xV*，则X称为语法GZ的句型。2.如果Z=x且xVt*，则x称为语法GZ中的句子。文章模式是符号字符串，它可以由从标识符开始的终止符号和非终止符号组成，并且可以衍生零个或多个步骤。句子是由从语法标识符派生的完整终止符号组成的符号字符串。文章是一种特殊的句型，完全由终止符号构成的句型。语法的起始符号是用规则推导的。一旦派生了句子，派生过程就不能再继续进行了。因为句子中没有未终止的符号。假设符号字符串是衍生结果，句子的充分必要条件是从到的衍生长度大于或等于Z=x，并且Z=*x不能。这是因为标识符Z不是终止，而是终止符字符串。显然不能等价，所以不能通过阶段诱导等价。2.4句型和文章，句型有一个叫规范型的句型，这是可以引导到规范的句型。每个句子都有规范诱导，但不是每个句型都有规范诱导。只能归纳为规范的句型是规范句型。例如，