第一章第一章 引论引论n主要内容：主要内容：介绍编译程序的概念，编译过程概述，编译程序的结构，介绍编译程序的概念，编译过程概述，编译程序的结构，编译程序与程序设计环境，编译程序的生成等内容编译程序与程序设计环境，编译程序的生成等内容n基本要求：基本要求：理解编译程序的作用，从宏观上理解组成、功能划分及开理解编译程序的作用，从宏观上理解组成、功能划分及开发步骤。发步骤。n重点与难点：重点与难点：编译程序的组成、功能划分。编译程序的组成、功能划分。 1.1 1.1 什么叫编译程序什么叫编译程序回顾：程序设计语言及程序设计语言的处理方式（编译和解释）回顾：程序设计语言及程序设计语言的处理方式（编译和解释）翻译程序：翻译程序：编译程序编译程序: :是指这样的程序，它能够把某种是指这样的程序，它能够把某种“高级语言高级语言”的程序转换成另的程序转换成另一种一种“低级语言低级语言”的程序，而后者与前者在逻辑上是的程序，而后者与前者在逻辑上是等价等价的。的。如果源语言是诸如如果源语言是诸如FORTRANFORTRAN、PascalPascal、C C、SmalltalkSmalltalk或或JavaJava这样的这样的“高级高级语言语言”，而目标语言如汇编语言之类的，而目标语言如汇编语言之类的“低级语言低级语言”这样的翻译程序这样的翻译程序则称之为则称之为编译程序编译程序。第一章 引 论Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.编译程序的分类编译程序的分类n根据不同的用途和侧重点：根据不同的用途和侧重点：n诊断编译器：用于程序的开发和调试诊断编译器：用于程序的开发和调试n优化编译器：具有优化能力，提高目标代码的效率优化编译器：具有优化能力，提高目标代码的效率n交叉编译器：该编译器产生不同于其交叉编译器：该编译器产生不同于其宿主机宿主机的机器代码的机器代码n宿主机：运行编译程序的计算机宿主机：运行编译程序的计算机n目标机：运行目标代码的计算机目标机：运行目标代码的计算机编译与解释编译与解释解释程序解释程序：它以该语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源：它以该语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。程序本身。编译与解释的区别编译与解释的区别：是否产生目标程序：是否产生目标程序 解释程序的特点解释程序的特点：结构简单，占用内存少，规模较小的语言采用，如：结构简单，占用内存少，规模较小的语言采用，如BASICBASIC；但效率；但效率低低第一章 引 论Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.英译与编译的比较英译与编译的比较 英译英译1.1.识别出句子中的一个个单词识别出句子中的一个个单词2.2.分析句子的语法结构分析句子的语法结构3.3.初步翻译句子的含意初步翻译句子的含意4.4.译文修饰译文修饰5.5.写出最后译文写出最后译文 编译编译1.1.词法分析词法分析2.2.语法分析语法分析3.3.语义分析中间代码生成语义分析中间代码生成4.4.优化优化5.5.目标代码生成目标代码生成第一章 引 论分分 析析 过过 程程综综 合合 过过 程程汇编程序汇编程序:是指这样的程序，它能够把汇编语言的源程序转换成机器语言的目标程序。 源程序：用汇编语言编写的程序 目标程序：用机器语言编写的程序 1.2 编译过程概述 主要工作：把高级语言写的程序翻译成等价的目标程序。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第一章 引 论1.2.1 1.2.1 词法分析词法分析主要工作：主要工作：n读入源程序，对构成源程序的字符串进行扫描和分解，读入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词识别出一个个单词（也称单词符号，或简称符号）（也称单词符号，或简称符号）n源程序的格式化处理：删除无用的符号（空格、回车符等），删除注释语句源程序的格式化处理：删除无用的符号（空格、回车符等），删除注释语句n进行词法检查，报告发现的词法错误（拼写错误）进行词法检查，报告发现的词法错误（拼写错误） 在词法分析阶段工作所依循的是语言的在词法分析阶段工作所依循的是语言的词法规则词法规则。描述词法规则的有效工具是正。描述词法规则的有效工具是正规式和有限自动机。规式和有限自动机。例：例：for i:=1 to 30 do /* for i:=1 to 30 do /* 循环语句循环语句*/*/1.2.2 1.2.2 语法分析语法分析语法：语法：定义了语言各语法成分的形式或结构定义了语言各语法成分的形式或结构 语法分析的任务：语法分析的任务：在词法分析的基础上，根据语言的语法规则，在词法分析的基础上，根据语言的语法规则，把单词符号划分把单词符号划分成各类语法单位成各类语法单位（语法范畴），如（语法范畴），如“短语短语”、“句子句子”、 “子句子句”、“程序段程序段”等，确定整个输入串是否构成语法上正确的程序。等，确定整个输入串是否构成语法上正确的程序。 语法规则通常用语法规则通常用上下文无关文法上下文无关文法描述。描述。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.1.2.3 1.2.3 语义分析与中间代码的产生语义分析与中间代码的产生语义：语义：定义了各语法成分的功能和含义，即规定了他们的属性或在执行时应进行的运定义了各语法成分的功能和含义，即规定了他们的属性或在执行时应进行的运算。算。这一阶段通常包括两方面的工作这一阶段通常包括两方面的工作:首先对各种语法范畴进行静态语义检查，如果正确则首先对各种语法范畴进行静态语义检查，如果正确则进行另一方面的工作，即进行中间代码的翻译。进行另一方面的工作，即进行中间代码的翻译。 通常使用通常使用属性文法属性文法描述语义规则描述语义规则 所谓所谓“中间代码中间代码”是一种含义明确，便于处理的记号系统。是一种含义明确，便于处理的记号系统。 中间代码除四元式外，还有三元式、间接三元式、逆波兰记号、树形表示等。中间代码除四元式外，还有三元式、间接三元式、逆波兰记号、树形表示等。1.2.4 1.2.4 优化优化优化的目的：优化的目的：生成高质量的代码生成高质量的代码优化的任务：优化的任务：在于对前段产生的中间代码进行加工，以期在最后阶段产生更为高效在于对前段产生的中间代码进行加工，以期在最后阶段产生更为高效（省时间和空间）的目标代码（省时间和空间）的目标代码优化所依循的原则：优化所依循的原则：是程序的等价变换规则是程序的等价变换规则其方法有：公共子表达式的提取、循环优化、删除无用代码等。其方法有：公共子表达式的提取、循环优化、删除无用代码等。第一章 引 论Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.代码优化示例代码优化示例For k:=1 to 100 do beginm:=i+10*k;n:=j+10*k;end第一章 引 论M=i;n=j;k=1For k:=1 to 100 do beginm:=m+10;n:=n+10;endFor k:=1 to 100 do beginm:=i+10*k;n:=j+10*k;endFor k:=1 to 100 do begint=10*k;m:=m+t;n:=n+t;endEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.1.2.5 1.2.5 目标代码生成目标代码生成 这一阶段的任务这一阶段的任务：把中间代码（或经优化处理后）变换成特定机器上的低级语言：把中间代码（或经优化处理后）变换成特定机器上的低级语言代码。生成的目标代码的形式依赖于硬件系统结构和机器指令含义。代码。生成的目标代码的形式依赖于硬件系统结构和机器指令含义。主要工作主要工作：存储空间的分配，寄存器的调度，机器指令的选择等等：存储空间的分配，寄存器的调度，机器指令的选择等等目标代码的形式目标代码的形式：绝对指令代码；可重定位的指令代码；汇编指令代码：绝对指令代码；可重定位的指令代码；汇编指令代码第一章 引 论词法分析词法分析语法分析语法分析语义分析与中间代码产生语义分析与中间代码产生优化优化目标代码生成目标代码生成编译过程总结Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.1.3 1.3 编译程序的结构编译程序的结构第一章 引 论表格管理词法分析器语法分析器语义分析与中间代码产生优化器目标代码生成器源程序单词符号语法单位中间代码中间代码目标代码出错处理Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.1.3.2 1.3.2 表格与表格管理表格与表格管理 在编译程序使用的表格中最重要的是在编译程序使用的表格中最重要的是符号表符号表它用来登记源程序中出现它用来登记源程序中出现的每一个名字以及名字的各种属性。如一个名字是常量名、变量名，还是的每一个名字以及名字的各种属性。如一个名字是常量名、变量名，还是过程名等；如果是变量名它的类型又是什么、所占内存是多大、地址是什过程名等；如果是变量名它的类型又是什么、所占内存是多大、地址是什么等。么等。1.3.3 1.3.3 出错处理出错处理 一个编译程序不仅能对书写正确的程序进行编译，而且应能对处现在一个编译程序不仅能对书写正确的程序进行编译，而且应能对处现在源程序中的错误进行处理。如果源程序有错，编译程序应设法发现错误，源程序中的错误进行处理。如果源程序有错，编译程序应设法发现错误，把有关错误报告给用户。这部分的工作是由专门的一组程序（叫做把有关错误报告给用户。这部分的工作是由专门的一组程序（叫做出错处出错处理程序理程序）完程的。）完程的。1.3.4 1.3.4 遍遍n遍遍n：对源程序或源程序的中间结果从头到尾的一次扫描，并作有关的加工和对源程序或源程序的中间结果从头到尾的一次扫描，并作有关的加工和处理，生成新的中间结果或目标程序。处理，生成新的中间结果或目标程序。n遍与各编译过程之间的关系：一遍可以包含几个阶段；一个阶段的工作也遍与各编译过程之间的关系：一遍可以包含几个阶段；一个阶段的工作也可以分为若干遍，比如优化可以在多遍扫描中完成。可以分为若干遍，比如优化可以在多遍扫描中完成。n编译程序的组织：依赖于源程序，计算机的硬件，以及设计要求等编译程序的组织：依赖于源程序，计算机的硬件，以及设计要求等第一章 引 论Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.1.3.5 1.3.5 编译前端与后端编译前端与后端 前端前端主要由与源语言有关但与目标机主要由与源语言有关但与目标机无关的那些部分组成。无关的那些部分组成。 后端后端包括编译程序中与目标代码有关包括编译程序中与目标代码有关的部分。的部分。第一章 引 论词法分析器词法分析器语法分析器语法分析器语义分析与中间代码产生语义分析与中间代码产生优化器优化器目标代码生成器目标代码生成器编编译译前前端端编编译译后后端端 1.4 1.4 编译程序与程序设计环境编译程序与程序设计环境编译程序无疑是实现高级语言的一个最重要的工具。但支持程序设计人员进行程序设计开发通常还需要其它一些工具：如编辑程序、连接程序、调试程序等。编译程序与这些程序设计工具一起构成所谓的程序设计环境。 在一个程序设计环境中，编译程序起着中心的作用。连接程序、调试程序、程序分析等工具直接依赖于编译程序所产生的结果，而其它工具的构造也常常要用到编译的原理、方法和技术。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.1.5 1.5 编译程序的生成编译程序的生成 以前构造编译程序大多是用机器语言或汇编语言作工具的。以前构造编译程序大多是用机器语言或汇编语言作工具的。 但是越来越多的人已经使用高级语言作工具来写编译程序。但是越来越多的人已经使用高级语言作工具来写编译程序。用用L1L1语言编写语言编写L2L2的编译程序的编译程序前提：前提：如果如果A A机器上已有一个用机器上已有一个用A A机器码实现的某高级语言机器码实现的某高级语言L1L1的编译程序的编译程序我们可以用我们可以用L1L1语言编写另一种高级语言语言编写另一种高级语言L2L2的编译程序，把写好的的编译程序，把写好的L2L2编译程序经过编译程序经过L1L1编译程序编译后就可得到编译程序编译后就可得到A A机器代码实现的机器代码实现的L2L2编译程序。编译程序。采用采用移植移植的方法进行编译程序的开发的方法进行编译程序的开发n本质：本质：将语言将语言L L的编译器从的编译器从A A机器上移植到机器上移植到B B机器机器n前提：前提：A A机器上有机器上有L L语言的编译器语言的编译器n步骤：步骤：n在在A A机器上用机器上用L L语言写一个能将语言写一个能将L L语言翻译成语言翻译成B B语言的编译器语言的编译器C1C1n在在A A机器上对机器上对C1C1进行编译，得到用进行编译，得到用A A代码写的代码写的B B编译器编译器C2C2，该编译器能将，该编译器能将L L语言语言翻译成翻译成B B语言语言n用用C2C2编译器对编译器对C1C1重新进行编译，得到一个重新进行编译，得到一个B B语言表示的语言表示的B B机器上的编译器机器上的编译器第一章 引 论Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.自编译方式自编译方式 我们还可以采用我们还可以采用“自编译方式自编译方式”产生编译程序。方法是，先对语言的产生编译程序。方法是，先对语言的核心部分构造一个小小的编译程序（可用低级语言实现），再以他为工具核心部分构造一个小小的编译程序（可用低级语言实现），再以他为工具构造一个能够编译更多语言成分的较大编译程序。如此扩展下去，就像滚构造一个能够编译更多语言成分的较大编译程序。如此扩展下去，就像滚雪球一样，越滚越大，最后形成人们所期望的整个编译程序。雪球一样，越滚越大，最后形成人们所期望的整个编译程序。n本章小结本章小结n什么是编译器什么是编译器n编译器的基本结构及基本功能编译器的基本结构及基本功能n编译程序的结构编译程序的结构n编译程序与程序运行环境编译程序与程序运行环境n编译程序的开发编译程序的开发第一章 引 论Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.自测练习题自测练习题1.1.选择题选择题( (从下列各题从下列各题4 4个备选答案中选出一个或多个正确答案写在题干的横线上个备选答案中选出一个或多个正确答案写在题干的横线上) )(1)(1)若源程序是高级语言编写的程序，目标程序若源程序是高级语言编写的程序，目标程序 是是 ，则称它为编译程序。，则称它为编译程序。 A A汇编语言程序或高级语言程序汇编语言程序或高级语言程序 B B高级语言程序或机器语言程序高级语言程序或机器语言程序 C C汇编语言程序或机器语言程序汇编语言程序或机器语言程序 D D连接程序或运行程序连接程序或运行程序(2)(2)编译程序是对编译程序是对 程序进行翻译。程序进行翻译。 A A高级语言高级语言 B B机器语言机器语言 C. C.自然语言自然语言 D. D.汇编语言汇编语言(3)(3)如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段： . . A A编译阶段编译阶段 B. B.汇编阶段汇编阶段 C. C.运行阶段运行阶段 D D置初值阶段置初值阶段(4)(4)编译程序的工作过程一般可划分为下列编译程序的工作过程一般可划分为下列5 5个基本阶段：个基本阶段：词法分析、词法分析、 、代码优化和目标代码生成。、代码优化和目标代码生成。 A A出错处理出错处理 B B语义分析和中间代码生成语义分析和中间代码生成 C C语法分析语法分析 D D表格管理表格管理 (5) (5)编译过程中，词法分析阶段的任务是编译过程中，词法分析阶段的任务是 。 A A识别表达式识别表达式 B. B.识别语言单词识别语言单词 C C识别语句识别语句 D D识别程序识别程序. . 第一章 引 论Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.2.2.判断题判断题(1)(1)编译程序是种常用的应用软件。编译程序是种常用的应用软件。 ( ) ( )(2)C(2)C语言的编译程序可以用语言的编译程序可以用C C语言来编写。语言来编写。 ( ) ( )(3)(3)编译方式与解释方式的根本区别在于是否生成目标代码编译方式与解释方式的根本区别在于是否生成目标代码.( ).( )(4)(4)编译程序与具体的语言无关。编译程序与具体的语言无关。( )( )(5)(5)编译程序与具体的机器有关。编译程序与具体的机器有关。( )( )(6)(6)对编译程序而言，代码优化是不可缺少的部分。对编译程序而言，代码优化是不可缺少的部分。( )( )(7)(7)对编译程序而言，中间代码生成是不可缺少的一部分。对编译程序而言，中间代码生成是不可缺少的一部分。( )( )(8)(8)编译程序生成的目标程序一定是可执行的程序。编译程序生成的目标程序一定是可执行的程序。 ( ) ( )(9)(9)含有优化部分的编译程序的执行效率高。含有优化部分的编译程序的执行效率高。 ( ) ( )作业作业1.什么叫编译程序？编译程序和解释程序的区别是什么？什么叫编译程序？编译程序和解释程序的区别是什么？2.描述一下编译程序的结构和各组成部分的功能，并画出编译程序的结构框图。描述一下编译程序的结构和各组成部分的功能，并画出编译程序的结构框图。3.描述一下编译器生成的几种方法。描述一下编译器生成的几种方法。第一章 引 论Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述第二章第二章 高级语言及其语法描述高级语言及其语法描述n程序设计语言的语法 程序设计语言的语义n程序设计语言的特点 程序设计语言的语法描述2.1 程序语言的定义n任何语言实现的基础是语言的定义。n在定义方面，编译程序研制者与一般用户有所不同u用户关心语言如何使用u开发人员关心文法的定义。他们对哪些构造允许出现更感兴趣。即使一时不能看出某种构造的实际应用，或者判断实现该结构会导致严重的困难，但仍必须严格根据语言的定义实现它。n程序语言主要由语法和语义两方面定义。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述2.1.1 语法u所谓一个语言的语法是指这样的一组规则，用它可以形成和产生一个合适的程序。u这些规则一部分称为词法规则，另一部分能称为语法规则（或产生规则）。几个概念a.一个语言只是用一个有限字符集作为字母表；b.词法规则是指单词符号的形成规则。单词符号一般包括：各类型的常数、标识符、基本字、算符和界符等。C.语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位或语法范畴），换言之，语法规则是语法单位的形成规则。一般程序语言的语法单位有：表达式、语句、分程序、函数、过程和程序等。2.1.2 2.1.2 语义语义n对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题。n语义是指这样的一组规则，使用它可以定义一个程序的意义。n我们采用的方法为：属性文法和基于属性文法的语法制导翻译方法。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述 n程序语言的基本功能是描述数据和对数据的运算。所谓程序，从本质上来说是描述一定数据的处理过程。程序程序子程序子程序或或分程序分程序语句语句表达式表达式算符算符函数调用函数调用数据引用数据引用程序程序Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述程序设计语言的定义n建立在有限字母集之上的一个符号系统n有一定的语法和语义规则n语法规则：词法规则和语法规则n语义规则：描述语法单位的功能和含义n程序设计语言的功能是描述数据和对数据的运算2.2 高级语言的一般特性2.2.1 高级语言分类2.2.2 程序结构2.2.3 数据类型与操作2.2.4 语句与控制结构Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述2.2.1 高级语言分类 从不同的角度看，对高级程序设计语言有不同的分类方法。如果我们从语言范型分类，当今的大多数程序设计语言可划分为四类。 一、强制式语言 强制式语言也称过程式语言。其特点是命令驱动，面向语句。一个强制式语言程序由一系列的语句组成，每个浯句的执行引起若干存储单元中的值的改变。这种语言的语法形式通常具有如下形式： 语句1； 语句2； 语句n； 许多广为使用的语言，如FORTRAN、C、Pascal，等等，属于这类语言。四、面向对象语言 面向对象语言如今已成为最流行、最重要的语言。它主要的特征是支持封装性、继承性和多态性等。把复杂的数据和用于这些数据的操作封装在一起，构成对象；对简单对象进行扩充、继承简单对象的特性，从而设计出复杂的对象。通过对象的构造可以使面向对象程序获得强制式语言的有效性，通过作用于规定数据的函数的构造可以获得应用式语言的灵活性和可靠性。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述2.2.1 高级语言分类 二、应用式语言 与强制式语言不同的是，应用式语言更注重程序所表示的功能，而不是一个语句接一个语句地执行。程序的开发过程是从前面已有的函数出发构造出更复杂的函数，对初始数据集进行操作直至最终的函数可以用于从初始数据计算出最终的结果。这种语言通常的语法形式是： 函数n(函数2(函数1(数据)因此，这种语言也称函数式语言。LISP和ML属于这种语言。三、基于规则的语言 基于规则的语言程序的执行过程是：检查一定的条件，当它满足值，则执行适当的动作。最有代表性的基于规则语言是Prolog，它也称逻辑程序设计语言，因为它的基本允许条件是谓词逻辑表达式。这类语言的语法形式通常为： 条件1动作l 条件2动作2 条件n动作3Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述2.2.2 程序结构n不同程序语言都有各自的程序结构nC语言程序可以包含多个函数nPascal 支持过程的嵌套定义n程序结构的不同，决定了符号表构造方法的不同 2.2.3 数据类型与操作数据类型与操作程序设计语言支持特定的数据类型与操作。一个数据类型通常包括以下三种要素：na.用于区别这种类型的数据对象的属性nb.这种类型的数据对象可以具有的值nc.可以作用于这种类型数据对象的操作Pascal 是一个允许子程序嵌套定义的语言 program main procedure P1; procedure P11; begin end; begin end; procedure P2; begin end; begin end Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述一.初等数据类型（基本数据类型） 常见的初等数据类型有：a.数值数据 b.逻辑数据c.字符数据d.指针类型不同的数据类不同的数据类型占存储空间型占存储空间不同，表示的不同，表示的数的范围也不数的范围也不相同相同名字和标识符标识符：无意义的符号串 名字：可以看成是代表一个抽象的存储单元名字的值：名字所代表的单元的内容则认为是此名字的值。名字的属性： 一个名字的属性包括类型和作用域。标识符、名字与存储空间的关系:同一标识符可以表示不同的名字；同一名字可以表示不同的存储空间；同一存储空间可以有多个名字Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述二.构造数据类型 a. 数组n特点：一个数组是由同一类型数据所组成的某种n维矩形结构。每个元素占相同的存储空间n下标：沿着每一维的距离称为一个下标。n数组元素的命名：数组名+下标n确定数组与可变数组：在编译时数组所需的存储空间是否确定n数组元素的存储与地址的计算n内情向量表：数据类型，数组的维数，下标的变化范围，首地址设计符号表的构造方设计符号表的构造方法，需要在符号表中法，需要在符号表中存储更多的信息，并存储更多的信息，并需要定义不同的属性需要定义不同的属性文法以便对其语义进文法以便对其语义进行描述行描述b.记录 从逻辑上说，记录结构是由已知类型的数据组合起来的一种结构。 记录结构是许多程序语言的一类重要的数据结构。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述Pascal语言采用下面形式定义记录：CARD: record NAME: array120 of char; AGE:integer; MARRIED:boolean end;struct Node char data； int a;int mark;； 特点：多种基本数据类型组成的新的数据类型记录分量的访问：记录名.分量名记录的存放：连续存放记录的长度：每个分量的长度之和记录分量地址的计算：首地址+各分量相对于首地址的偏移（offset）如：就CARD而言，NAME,AGE,MARRIED 的相对数OFFSET分别为0、20、24。于是，假定CARD的首地址为a，那么， CARD.NAME 地址为 a CARD.AGE 地址为 a+20 CARD.MARRIED 地址为 a+24 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述2.2.4 语句与控制结构n表达式 数值、关系、逻辑、字符串n语句 赋值语句 控制语句（无条件、条件、循环、过程调用、返回） 说明句 简单句和复合句一.表达式组成：运算量（亦称操作数，即数据引用或函数调用）和算符组成的。表示形式:前缀式： +a*bc 中缀式：a+b*c 后缀式：abc*+Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述表达式中的算符算符的优先级和结合性 乘幂 （ * 或 ）一元负 （ - ）乘、除 （ * ， /， ）加、减 （ + ， - ）关系符 （ , =, , = ) 非 （ ， not, 或 .NOT. )与 （， &, and 或 .AND. )或 （ ， or 或 .OR . )消除文法的二消除文法的二义性义性算符的代数性质作用：（交换率、结合率和分配率）常常可用来优化目标程序的质量。但是必须注意两点：代数性质引用到什么程度视具体语言的不同而不同。如在ALGOL中把A*B+C*D 处理成C*D+A*B, 则至少是对ALGOL不够忠实。数学上成立的代数性质在计算机上未必完全成立。如：(A+B)+C=A+(B+C)在计算机上并不普遍成立。决定了在优化的决定了在优化的过程中应采取的过程中应采取的优化策略优化策略Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述二.语句n从功能上说语句大体可分执行性语句和说明性语句，说明性语句旨在定义不同数据类型的变量或运算。n执行性语句旨在描述程序的动作。n对不同的语句，编译器的处理方式不同。n执行性语句又可分赋值语句、控制语句和输入/输出语句.n从形式上说，语句还可分为简单句、复合句和分程序等。根据属性文法的定义根据属性文法的定义进行处理进行处理Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述2.3 程序语言的语法描述n对于高级程序语言及编译程序而言，语言的语法定义是非常重要的。n本节将介绍语法结构的形式描述问题。与文法定义相关的几个概念和术语与文法定义相关的几个概念和术语n字母表：由若干元素组成的有限非空集合，用表示，它的每个元素称为一个符号。n符号串： 由中的符号所构成的有穷序列。n符号串的前缀和后缀及子串：设x是一个符号串，将x的尾（前）部删掉几个字符后形成的符号串，称为x的前（后）缀；从一个符号串中删去他的一个前缀和后缀后所剩下部分称为x的子串。n空串（字）：不包含符号的序列称为空串（字） ，记为。n用*表示上的所有符号串的全体，空字也包括在其中。如：若=a,b则*=,a,b,aa,ab,bb,aaa,。表示不含人何元素的空集。这里要注意、和的区别。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述符号串及符号串集合的运算n符号串的连接运算：设x和y是两个符号串，如果将y直接拼接在x之后，称这种操作为符号串的连接,记作： x.yn符号串的方幂：一个符号串与其自身的n-1的任意连接称为符号串的n次幂，记作：xn xn = xn-1.x=x.xn-1 特别地:x0= n字符串集合的和(等价于集合的并运算)：设A、B是两个符号串的集合，则将集合A、B的和记为A+B或AB,定义为：AB=w|wA或wBn符号串集合的连接：*的子集U和V中的（连接）积定义为: UV=U & V 即集合UV中的符号串是由U和V的符号串连接而成的。注意，一般UVVU，但（UV)W=U(VW).Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述令令X1=“abc”, X2=“def”表示、表示、术语 举例例|X1| |abc|= 3 |= 0X1.X2 “abc”“def”=“abcdef”Xn “abc”3 =“abcabcabc”X1的前的前缀 “abc”的前的前缀可以是：可以是：，a，ab, abcX1的后的后缀“abc”的前的前缀可以是：可以是：，c，bc, abcX1的子串的子串 “abc”的子串可以是：的子串可以是： ，a，b, c, X1的真前的真前缀“abc”的真前的真前缀可以是：可以是：a，abX1的真后的真后缀？X1的真子串的真子串？X1的子序列的子序列 “abdf”是是“abcdef”的一个子序列（的一个子序列（X中去掉中去掉0或若干或若干个不一定个不一定连续的字符后形成的字符串的字符后形成的字符串 ）Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述n符号串集合V自身的n次（连接）积记为： Vn = V VV =Vn-1V =VVn-1 (n个V)规定 V0 = .nV的闭包：令： V* = V0 V1 V2 称 V*是V的闭包。nV的正则包（正闭包，正则闭包）：记V+ = VV*, 称 V+是V的正则包，即V+ =V1 V2 V3 。一个例子有一个字母表：A=a,b,cA0=A1=？A2=？A3=？A*=？ A+=?Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述 文法是描述语言的语法结构的形式规则（即语法规则）。所谓上下文无关文法是这样一种文法，它所定义的语法范畴（或语法单位)是完全独立于这种范畴可能出现的环境的。特点：独立性缺点：不能用来描述自然语言，但对于程序语言基本上够用，所以以后凡“文法”一词，若无特殊说明，均指上下文无关文法引例例子：对于英文句子：He gave me a book.是由如下语法规则产生的：2.3.1 上下文无关文法上下文无关文法Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述由语法规则“推导”出句子的过程“推导” 过程对应的语法分析树Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述上下文无关文法的定义n一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符，一个开始符号，以及一组产生式。n形式上定义一个上下文无关文法是一个四元式（，P）上下文无关文法的形式定义形式上定义一个上下文无关文法形式上定义一个上下文无关文法是一个四元式是一个四元式（，P P）其中）其中是一个非空有限集，它的每一个元素称为终结符号；是一个非空有限集，它的每一个元素称为终结符号；是一个非空有限集，它的每一个元素称为非终结符号，是一个非空有限集，它的每一个元素称为非终结符号， ；是一个非终结符号，称为开始符号；是一个非终结符号，称为开始符号；P P是一个产生式（有限）集合，每个产生式形式是是一个产生式（有限）集合，每个产生式形式是AA ，其中，其中， （）开始符号开始符号S S至少必须在某一产生式的左部出现一次。至少必须在某一产生式的左部出现一次。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述上下文无关文法的定义1.所谓终结符号乃是组成语言的基本符号，“终结”含义在于是具有独立意义的最小语法单位，即不能再分解了的语法单位，如， He， book，如程序语言中的基本字，标识符，常数，算符和界符等.如： *,+,a,b,c,(,),+,-n终结符号一般用小写字母表示上下文无关文法1.所谓非终结符号（也称语法变量）用来代表语法范畴。如“算术表达式”、“布尔表达式”、“过程”等。一个非终结符代表一个一定的语法概念。因此非终结符是一个类（或集合）记号，而不是个体记号。2.非终结符号一般用大写字母表示3.如：E，T，FEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述1.开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最感兴趣的语法范畴。 例：E上下文无关文法上下文无关文法1.产生式（也称为产生规则或简称规则）是定义语法范畴的一种书写规则。1.一个产生式的形式是 A 1.其中箭头左边的A是一个非终结符，称为产生式的左部符号；2.箭头右边的是终结符号或与非终结符号组成的一符号串，称为产生式的右部，或称候选式。上下文无关文法Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述文法简写约定n只写出产生式集合；n第一个产生式的左部符号约定为文法的开始符号n所有产生式中的大写字母组成文法的非终结符号集；小写字母组成文法的终结符号集；关于产生式n可能用多个产生式对一个非终结符进行定义 Ei （）产生式实例变量是一个算术表达式；若E1和E2是算术表达式，E1+E2是算术表达式E1*E2是算术表达式(E1)是Ei （）算术表达式定义产生式，可以采用递归的形式直接递归间接递归Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述利用语法规则进行分析的方法n推导对于当前符号串中的非终结符，用对应的产生式的右部去替换之。n构造语法树文法的开始符号作为根结点，每推导一步，将非终结符作为父结点，对应的产生式的右部作为其孩子结点。用文法定义语言n采用推导的方法：利用产生式，对非终结符进行替换、展开 Ei （）推导与直接推导直接推导：仅当A 是一个产生式，有A 该推导称为直接推导（直接导出）推导的描述形式：*：任意次推导+：至少一次推导Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述句型与句子假定G是一个文法，S是它的开始符号。如果S*(表示从S出发，经0步或若干步可推出），则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G). L(G)=|S + & VT 句型与句子例如：终结符号串（i*i+i)是文法 EE+E|E*E|(E)| (2.1) 的一个句子。 E(E)(E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i)从开始符号E至 （i*i+i)的一个推导。E,(E),(E*E+E)等是文法的句型。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述 例2.1考虑一个文法G1: SbA AaA|a 它定义了一个什么语言呢？从开始符S出发，我们可以推出如下句子： SbA ba SbA baA baa SbA baA baaa可以写为：L(G1)=ban|n1例2.2 设有文法G SP|aPPb P ba|bQa Q ab 求语言L(G). 解： L(G)=ba,baba,abab,ababab Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述例2.3 构造一个文法G3使 L(G3)=an|n1 解; SaS|a例2.4 构造一个文法G3使 L(G3)=anb|n1 解; SaS|ab例2.5 构造一个文法G3使 L(G3)=anbm|n1,m 1 解; SABAaA|aBbB|b例2.6 构造一个文法G3使 L(G3)=anbn|n0 解; SaSb| 例2.7： 已知语言L=anbbn| n 1, 写出产生L的文法。解： GS: S aAb A aAb|b如果写成GS: S aSb|b 可不可以？例2.8： 试构造生成语言L=anbnci|n0, i 1的文法 解：G(Z): ZAB A aAb| B cB|cEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述 例2.9： 已知语言L=x | xa,b,c*,且x的排列是对称的（aabcbaa,aabbaa,等) 写出该语言的文法。解：G(Z)： Z aZa|bZb|cZc|a|b|c|最左（右）推导最左推导或最右推导：所谓最左推导是指：任何一步都是对中的最左非终结符进行替换的。同样，可定义最右推导。最左推导又称为规范推导。2.3.2 2.3.2 语法分析树与二义性语法分析树与二义性语法分析树：简称语法树。用来表示推导过程。Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述语法树示例 例如对于文法 EE+E|E*E|(E)|,关于（i*i+i)的推导形成语法树如图Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述语法树的构造： 1.语法树的根结点由开始符号所标记。2.随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结点就产生了下一代新结点。每个新结点和其父亲结点间都有一条连线。3.在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结点自左至右排列起来就是一个句型。语法树的不唯一性一个句型是否只对应唯一的一棵语法树呢？也就是说它是否只有唯一的一个最左（最右)推导呢？语法树的不唯一性EE+E|E*E|(E)|,关于（i*i+i)的推导E(E) (E*E) (i*E) (i*E+E) (i*i+E) (i*i+i)E(E)(E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i)2.3.2 语法分析树与二义性Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述 EE+E|E*E|(E)|EE+E|E*E|(E)|, ,关于（关于（i*i+i)i*i+i)的语法树的语法树Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述文法的二义性二义文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法存在某个句子，它有两个不同的最左（最右)推导，则这个文法是法是二义的。 文法二义性的几个问题n文法二义不等于语言二义n文法的二义性是不可判定的n文法的二义性证明：找出一个句子，它有两个不同的最左推导或最右推导n文法二义性的消除：给每个产生式定义优先级 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述消除文法二义性示例n一个二义文法nE-E+EnE-E*EnE-(E)nE-in二义原因分析n没有定义运算符优先级和结合性n消除方法n定义优先级和结合性n给每个候选式定义一个优先级n引入新的非终结符，建立新的产生式n一个二义文一个二义文法法nE EE+EE+EnE EE*EE*EnE E(E)(E)nE Eiin一个无二义文法一个无二义文法nE ET|E+TT|E+TnT TF|T*FF|T*FnF F(E)(E)nF FiiEvaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述0型文法G=(VT ,VN ,S ,P) 是一个0型文法，如果它的每个产生式是这样的结构 (VNVT)* 且至少有一个非终结符，而(VNVT)* 。0型文法也称短语文法0型文法的描述能力相当于图灵机该文法所描述的语言称为0型语言，或者称递归可枚举语言1型文法特点：产生式的形式为其中|=|, 但S 除外，且S不得出现于任何产生式的右部1型文法又称为上下文有关文法另一种定义形式:A 该文法所描述的语言又称上下文有关语言Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述2型文法n特点：该文法的产生式满足：AA为非终结符，为终结符和非终结符组成的符号串，可以是空串n该文法又称为上下文无关文法n该文法所描述的语言又称为上下文无关语言 3型文法特点：该文法的产生式满足：AB 或 ABA为非终结符， 为终结符组成的符号串，可以是空串该文法又称为右线性文法，或左线性文法，通称正规文法该文法所描述的语言又称为正规语言Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述四种文法的比较产生式形产生式形式式文法名称文法名称定义的语言定义的语言描述能描述能力力包含关系包含关系0型文法型文法短语文法短语文法递归可枚举语递归可枚举语言言最强最强1型文法型文法| | |=|0 Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述 解：偶数的组成和特点：可以是一位偶数，例如2，4，6，8，可以是多位偶数，首位不能为0，末位只能是0，2，4，6，8，中间为任意 G(Z): FA|CNDN NE|E| E 0|CD 0|AC A|B B |1|3|5|7|9 A 2|4|6|8例例2.11 试构造文法，该文法可以生成所有不试构造文法，该文法可以生成所有不能以能以0开头的偶数。开头的偶数。例2.12:试构造文法，该文法可以生成所有不能以0开头的奇数。解：奇数的组成和特点：可以是一位偶数：例如1， 3，5，7，9，可以是多位奇数：首位不能为0，末位只能是1，3，5，7，9 ，中间为任意。 G(Z): D1|3|5|7|9|BDB1|2|3|4|5|6|7|8|9|B0G(Z):FB|CNBN NE|E| E 0|CC A|B B |1|3|5|7|9A 2|4|6|8Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述句型句型Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.第二章 高级语言及其语法描述作业课本P36：6-11Evaluation only.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Copyright 2004-2011 Aspose Pty Ltd.