编译原理课件第1章概述.ppt

《编译原理课件第1章概述.ppt》由会员分享，可在线阅读，更多相关《编译原理课件第1章概述.ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、编编 译译 原原 理理长春理工大学长春理工大学一月一月23与课程有关的问题与课程有关的问题 时间安排时间安排：讲课：讲课：4848学时学时 实验：实验：1 16 6学时学时 参考书参考书 ：程序设计语言编译原理程序设计语言编译原理，陈火旺等，第三版，国防工业出版社，陈火旺等，第三版，国防工业出版社 计算机编译原理计算机编译原理 ，第二版，第二版，张幸儿，科学出版社，张幸儿，科学出版社 编译程序原理与技术编译程序原理与技术，李赣生、王华民，清华大学出版社，李赣生、王华民，清华大学出版社 作业作业：视所讲内容布置视所讲内容布置1-21-2道习题道习题 成绩成绩 ：以考试为主，参考平时成绩以考试为主

2、，参考平时成绩(作业、实验等作业、实验等)与课程有关的问题与课程有关的问题 本课程的性质、目的和任务本课程的性质、目的和任务 ：本课程是计算机类专业的专业课，目的是使学生了解并掌握编译本课程是计算机类专业的专业课，目的是使学生了解并掌握编译程序的基本理论和方法，具有分析和实现编译程序的初步能力。程序的基本理论和方法，具有分析和实现编译程序的初步能力。本课程的基本要求本课程的基本要求 ：通过对本课程的学习，对形式语言有初步了解，并能对编译程序通过对本课程的学习，对形式语言有初步了解，并能对编译程序的整个结构有较清楚地了解，熟悉和掌握几种主要编译方法。的整个结构有较清楚地了解，熟悉和掌握几种主要编

3、译方法。课程内容的重点、深度与广度课程内容的重点、深度与广度 ：重点是：重点是：文法和形式语言、词法分析和有穷自动机、语法分析、文法和形式语言、词法分析和有穷自动机、语法分析、语义分析。语义分析。此外还涉及到此外还涉及到目标代码的生成，此外还要求掌握和了解符目标代码的生成，此外还要求掌握和了解符号表的构造、存储分配与管理、代码优化和错误校正。号表的构造、存储分配与管理、代码优化和错误校正。课程内容课程内容 第第1 1章章 ：编译程序概述编译程序概述 第第2 2章章 ：文法和语言的形式定义文法和语言的形式定义 第第3 3章章 ：有穷自动机与词法分析有穷自动机与词法分析 第第4 4章章 ：语法分析

4、语法分析 第第5 5章章 ：语义分析和中间代码生成语义分析和中间代码生成 第第6 6章章 ：符号表的组织与管理符号表的组织与管理 第第7 7章章 ：代码优化代码优化 第第8 8章章 ：运行阶段的存储组织与分配运行阶段的存储组织与分配 第第9 9章章 ：目标代码生成目标代码生成 第第1010章章 ：并行编译技术基本知识并行编译技术基本知识本节内容简介本节内容简介 程序的翻译程序的翻译 编译程序的工作过程编译程序的工作过程 编译程序的结构编译程序的结构 编译程序的组织方式编译程序的组织方式 编译程序的构造编译程序的构造1.1.1 1翻译程序与编译程序翻译程序与编译程序问题问题:计算机只能识别二进制

5、数计算机只能识别二进制数0 0、1 1表示的指令和数构成的本计算表示的指令和数构成的本计算机系统的机器语言。如何让计算机执行高级语言程序呢？机系统的机器语言。如何让计算机执行高级语言程序呢？高级语言高级语言 begin x:=9+2 begin x:=9+2 endend1.11.1.1 .1 程序设计语言的发展程序设计语言的发展 机器语言机器语言 001110010010001110010010 汇编语言汇编语言 ADD R1 2ADD R1 2 所谓所谓翻译程序翻译程序是指这样一种程序，它能将用甲语言是指这样一种程序，它能将用甲语言（源语言）编写的程序翻译成与之等价的用乙语言（目标（源语言

6、）编写的程序翻译成与之等价的用乙语言（目标语言）书写的程序。语言）书写的程序。程序翻译的方式：程序翻译的方式：一是一是“编译编译”方式，二是方式，二是“解释解释”方式。方式。1.1.1 1 翻译程序与编译程序翻译程序与编译程序1.1.1.21.2翻译程序翻译程序 编译方式是一种分阶段进行的翻译方式。编译方式是一种分阶段进行的翻译方式。翻译阶段翻译阶段高级语言或汇高级语言或汇编语言源程序编语言源程序机器语言的目机器语言的目标程序标程序翻译程序翻译程序运行阶段运行阶段1.1.1 1翻译程序与编译程序翻译程序与编译程序输入数据输入数据运行结果运行结果目标程序目标程序运行子程序运行子程序1.1.1.3

7、 1.3 编译方式编译方式 编译程序编译程序高级语言高级语言源程序源程序汇编语言或机器语言汇编语言或机器语言目标程序目标程序编译程序编译程序 汇编程序汇编程序汇编语言汇编语言源程序源程序机器语言机器语言目标程序目标程序汇编程序汇编程序 编译程序编译程序编译方式下的编译方式下的 翻译程序翻译程序1.1.1 1 程序的翻译程序的翻译编译方式编译方式在编译方式下，源程序的执行需要在编译方式下，源程序的执行需要分阶段分阶段。如果目标程序是机器语言程序，如果目标程序是机器语言程序，则源程序的执行分则源程序的执行分 为为两大阶段两大阶段：编译阶段和运行阶段。：编译阶段和运行阶段。如果目标程序是汇编语言程序

8、，如果目标程序是汇编语言程序，则源程序的执行分则源程序的执行分 为为三大阶段三大阶段：编译阶段、汇编阶段和运行阶段。：编译阶段、汇编阶段和运行阶段。编译方式下，编译方式下，生成了目标代码生成了目标代码，且可多次执行。，且可多次执行。编译方式的特点编译方式的特点1.1.1 1 程序的翻译程序的翻译编译方式编译方式关于编译程序的几点说明关于编译程序的几点说明编编译译程程序序生生成成的的目目标标程程序序不不一一定定是是机机器器语语言言的的程程序序，也有可能是汇编语言程序；也有可能是汇编语言程序；编编译译程程序序与与具具体体的的机机器器和和语语言言有有关关，即即任任何何一一个个具具体体的的编编译译程程

9、序序都都是是某某一一特特定定类类型型的的计计算算机机系系统统中中关关于于某某一一特特定定语言的编译程序；语言的编译程序；对编译程序而言，对编译程序而言，源程序源程序是输入数据，是输入数据，目标程序目标程序是输出是输出结果。结果。关于编译程序的几点说明关于编译程序的几点说明（4 4）编译程序实际上只可能发现并报告在）编译程序实际上只可能发现并报告在静态可计算性静态可计算性制约下制约下的那些错误的那些错误。（5 5）理想的编译程序应该具有）理想的编译程序应该具有单独编译某个模块单独编译某个模块的能力，的能力，同时它不应因为源程序的一两处修改就对源程序重新编同时它不应因为源程序的一两处修改就对源程序

10、重新编译。译。完成解释工作的解释程序将按源程序中完成解释工作的解释程序将按源程序中语句的动语句的动态顺序态顺序，逐句地进行分析解释，并立即予以执行。，逐句地进行分析解释，并立即予以执行。1.1.1 1 程序的翻译程序的翻译 解释方式解释方式1.1.1.4 1.4 解释方式解释方式源程序解释执行的历程源程序解释执行的历程 计算机计算机解解 释释 程程 序序源程序源程序（高级语言）（高级语言）初始数据初始数据计计 算算 结结 果果 在解释方式下，在解释方式下，并不生成目标代码并不生成目标代码，而是直接执行源程序本，而是直接执行源程序本身。这是编译方式与解释方式的根本区别。身。这是编译方式与解释方式

11、的根本区别。所谓编译过程是指将所谓编译过程是指将高级语言程序高级语言程序翻译为等价的翻译为等价的目目标程序标程序的过程。的过程。翻译外文资料：翻译外文资料：1、能识别出句子中的一个单词；、能识别出句子中的一个单词；2、分析句子的语法结构；、分析句子的语法结构；3、根据句子的含义进行初步翻译；、根据句子的含义进行初步翻译；4、对译文进行修饰；、对译文进行修饰；5、写出最后的译文。、写出最后的译文。1.21.2编译程序的组成编译程序的组成翻译和编译工作的比较翻译和编译工作的比较翻译外文翻译外文编译程序编译程序分析分析识别单词识别单词分析句子分析句子根据语义进根据语义进行初步翻译行初步翻译词法分析词

12、法分析语法分析语法分析语义分析、生成中间代码语义分析、生成中间代码综合综合修辞加工修辞加工写出译文写出译文代码优化代码优化目标代码生成目标代码生成编译过程编译过程词法分析词法分析语法分析语法分析语义分析及中间代码生成语义分析及中间代码生成代码优化代码优化目标代码生成目标代码生成习惯上是将编译过程划分为习惯上是将编译过程划分为5 5个基本阶段：个基本阶段：1.2 1.2 编译程序的工作过程编译程序的工作过程例：一个简要的C 程序Main()/*used for illustrating compiling process*/Int a,b,c,x;a=a+b*c+b*c;x=a*3-b*c;b=

13、a+)b*(x-;依据语言依据语言词法规则词法规则，分析由字符组成的源程序，把它识别，分析由字符组成的源程序，把它识别为一个一个具有独立意义的为一个一个具有独立意义的最小语法单位最小语法单位，即，即“单词单词”，并识，并识别出与其相关的属性别出与其相关的属性(如是标识符，是界限符，还是数，等等如是标识符，是界限符，还是数，等等)，再转换成，再转换成长度上统一长度上统一的标准形式的标准形式(这种统一的标准形式既刻这种统一的标准形式既刻画了单词本身，又刻画了它所具有的属性，称为属性字画了单词本身，又刻画了它所具有的属性，称为属性字)，以，以供其它部分使用。供其它部分使用。1.2 1.2 编译程序的

14、工作过程编译程序的工作过程词法分析词法分析 上述源程序通过词法分析识别出如下单词符号：上述源程序通过词法分析识别出如下单词符号：基本字：基本字：main,main,intint 标识符：标识符：a,b,c,xa,b,c,x 常数：常数：3 3 运算符：运算符：,*,*,界符：界符：(,),;,/*/*,*/*/,=长度上统一的标准形式长度上统一的标准形式TOKENTOKEN串串TOKENTOKEN串是一个二元组：（单词类别，单词的值）串是一个二元组：（单词类别，单词的值）其中：其中：“单词的类别单词的类别”用既已存在的一组整数值（称为单词的种别用既已存在的一组整数值（称为单词的种别 码）表示。

15、用以区分不同种类的单词。码）表示。用以区分不同种类的单词。“单词的值单词的值”是单词的机内表示形式。一般是是单词的机内表示形式。一般是ASCIIASCII码。码。Main()/*used for illustrating compiling process*/Int a,b,c,x;a=a+b*c+b*c;x=a*3-b*c;b=a+)b*(x-;依据依据语法规则语法规则，逐一分析词法分析时得到的单词，把单词，逐一分析词法分析时得到的单词，把单词串分解成各类语法单位，即确定串分解成各类语法单位，即确定它们是怎样组成说明和语句它们是怎样组成说明和语句，以及以及说明和语句又是怎样组成程序的说明和语

16、句又是怎样组成程序的。分析时如发现有不合语。分析时如发现有不合语法规则的地方，便将出错的位置及出错性质打印报告给程序员；法规则的地方，便将出错的位置及出错性质打印报告给程序员；如无语法错误，则用另一种中间形式给出正确的语法结构，供如无语法错误，则用另一种中间形式给出正确的语法结构，供下一阶段分析使用。下一阶段分析使用。1.2 1.2 编译程序的工作过程编译程序的工作过程 语法分析语法分析通过语法分析，识别出：通过语法分析，识别出：a,b,xa,b,x 是是 这个语法单位；这个语法单位；a+ba+b*c+bc+b*c*c组合成组合成 这样的语法单位；这样的语法单位；识别出识别出 ，这样的语法单位

17、，并检查这样的语法单位，并检查正确性。例如，正确性。例如，由由 =构成；构成；这里发现这里发现 b=b=a+)ba+)b*(x-*(x-的语法错误的语法错误。原因是原因是 a+)ba+)b*(x-*(x-错误错误Main()/*used for illustrating compiling process*/Int a,b,c,x;a=a+b*c+b*c;x=a*3-b*c;b=a+)b*(x-;依依据据语语言言的的语语义义规规则则对对语语法法分分析析得得到到的的语语法法结结构构进进行行静静态态语语义义检检查查(确确定定类类型型、类类型型和和运运算算合合法法性性检检查查、识识别别含含义义与与相

18、相应应的的语语义义处处理理及及其其它它一一些些静静态态语语义义检检查查)，并并用用另另一一种种内内部部形形式（如中间代码）表示出来，或者直接用目标语言表示出来。式（如中间代码）表示出来，或者直接用目标语言表示出来。凡在编译时可以确定的内容称为凡在编译时可以确定的内容称为“静态静态”的；凡必须推迟的；凡必须推迟到程序运行时才能确定的内容称为到程序运行时才能确定的内容称为“动态动态”的。的。1.2 1.2 编译程序的工作过程编译程序的工作过程 语义分析语义分析具体说来语义分析包括两方面：具体说来语义分析包括两方面：（1 1）静态语义检查）静态语义检查。要检查标识符是否被定义，前后的数据类型是否。要

19、检查标识符是否被定义，前后的数据类型是否一致。如上述源程序中一致。如上述源程序中x=a*3-b*cx=a*3-b*c，要查看赋值号左右的变量和表达，要查看赋值号左右的变量和表达式的类型是否一致。式的类型是否一致。（2 2）进行语义处理）进行语义处理。针对不同类型的语句语义处理的方式不同。对说。针对不同类型的语句语义处理的方式不同。对说明语句，要将说明性语句中所定义的变量名字及其有关信息送进符明语句，要将说明性语句中所定义的变量名字及其有关信息送进符号表，并为之分配存储单元；对可执行语句（如赋值语句、条件语号表，并为之分配存储单元；对可执行语句（如赋值语句、条件语句、循环语句等），就要生成可表达

20、语义的中间代码。句、循环语句等），就要生成可表达语义的中间代码。分析到说明语句分析到说明语句intint a,b,c,xa,b,c,x;后，应把变量后，应把变量a,b,ca,b,c的类型的类型intint填入符填入符号表中，分析到号表中，分析到 后，将产生以下四元式序列：后，将产生以下四元式序列：运算符运算符 左运算对象左运算对象 右运算对象右运算对象 工作单元工作单元 注释注释(1)*b c T1 b*c(1)*b c T1 b*cT1T1(2)+a T1 T2 a+T1(2)+a T1 T2 a+T1T2 T2 (3)*b c T3 b*c3)*b c T3 b*cT3T3(4)+T2 T

21、3 T4 a+b*c+b*c(4)+T2 T3 T4 a+b*c+b*cT4T4(5)=T4 _ a T4(5)=T4 _ a T4a a(6)*a 3 T5 a*3(6)*a 3 T5 a*3T5T5(7)*b c T6 b*c7)*b c T6 b*cT6T6(8)_ T5 T6 T7 a*3-b*c(8)_ T5 T6 T7 a*3-b*cT7T7(9)=T7 _ x T7(9)=T7 _ x T7x x 语义翻译工作通常穿插在语法分析过程当中，因而语义翻译程序是语义翻译工作通常穿插在语法分析过程当中，因而语义翻译程序是由一组语法子程序构成的。由一组语法子程序构成的。a:=a+b*c+b

22、*c;x:=a*3-b*c;b:=a+)b*(x-依据程序的依据程序的等价变换规则等价变换规则，尽量压缩，尽量压缩目标程序运行所需的目标程序运行所需的时间时间和和所占的存储空间所占的存储空间，以提高目标程序的质量。，以提高目标程序的质量。代码优化分为两类：代码优化分为两类：(1)(1)与机器有关的优化：主要涉及如何分配寄存器。这种优化与机器有关的优化：主要涉及如何分配寄存器。这种优化是在生成目标代码时进行的。是在生成目标代码时进行的。(2)(2)与机器无关的优化：包括对中间代码的优化，局部优化和与机器无关的优化：包括对中间代码的优化，局部优化和循环优化。循环优化。1.2 1.2 编译程序的工作

23、过程编译程序的工作过程 代码优化代码优化上述四元式经优化得：上述四元式经优化得：（1 1）（）（*，b,c,T1b,c,T1）（2 2）(+,a,T1,T2)(+,a,T1,T2)（3 3）(+,T1,T2,T4)(+,T1,T2,T4)（4 4）(=,T4,_,a)(=,T4,_,a)（5 5）(*,a,3,T5)(*,a,3,T5)（6 6）(_,T5,T1,T7)(_,T5,T1,T7)（7 7）(=,T7,_,x)(=,T7,_,x)编译程序所产生的目标代码质量的高低，主要取决于这一阶段里代编译程序所产生的目标代码质量的高低，主要取决于这一阶段里代码优化程序功能的强弱码优化程序功能的强

24、弱。如果语义分析时把源程序表示成中间形式而不是表示成目如果语义分析时把源程序表示成中间形式而不是表示成目标指令，则由本部分完成标指令，则由本部分完成从中间形式到目标指令的转换从中间形式到目标指令的转换。如果。如果语义分析时，已直接生成目标指令，则无需另外再做代码生成语义分析时，已直接生成目标指令，则无需另外再做代码生成工作。工作。目标指令可能是目标指令可能是绝对指令代码绝对指令代码，或，或可重新定位的指令代码可重新定位的指令代码或或汇编指令代码汇编指令代码。该阶段的工作有赖于硬件系统结构和机器指。该阶段的工作有赖于硬件系统结构和机器指令含义。令含义。1.2 1.2 编译程序的工作过程编译程序的

25、工作过程 代码生成代码生成 登记源程序中出现的登记源程序中出现的每个名字以及名字的各种属性每个名字以及名字的各种属性。有些。有些名字的属性需要在各个阶段才能填入。即编译各阶段的工作都名字的属性需要在各个阶段才能填入。即编译各阶段的工作都涉及到构造、查找或更新有关的符号表，编译过程的绝大部分涉及到构造、查找或更新有关的符号表，编译过程的绝大部分时间是用在造表、查表和更新表格的事务上。因此，编译程序时间是用在造表、查表和更新表格的事务上。因此，编译程序中还应包括一个表格管理程序。中还应包括一个表格管理程序。1.2 1.2 编译程序的工作过程编译程序的工作过程 表格管理表格管理 源程序中的错误有源程

26、序中的错误有语法错误语法错误和和语义错误语义错误两种。两种。语语法法错错误误：源源程程序序中中不不符符合合语语法法(或或词词法法)规规则则的的错错误误，它们可在词法分析或语法分析时检测出来。它们可在词法分析或语法分析时检测出来。语语义义错错误误：源源程程序序中中不不符符合合语语义义规规则则的的错错误误，一一般般在在语语义义分分析析时时检检测测出出来来，有有的的语语义义错错误误要要在在运运行行时时才才能能检检测测出出来来。通常包括：说明错误、作用域错误、类型不一致等等。通常包括：说明错误、作用域错误、类型不一致等等。1.2 1.2 编译程序的工作过程编译程序的工作过程 出错处理出错处理1.3 1

27、.3 编译程序的结构编译程序的结构1.4.11.4.1 遍遍(趟，趟程趟，趟程)所谓一趟或一遍是指一个编译程序在编译时刻把所谓一趟或一遍是指一个编译程序在编译时刻把源程序或源程源程序或源程序的等价物序的等价物(中间程序中间程序)从头到尾扫描一遍并做有关的加工处理，生从头到尾扫描一遍并做有关的加工处理，生成新的源程序的中间形式或目标程序。成新的源程序的中间形式或目标程序。根据编译程序在完成翻译任务的过程中需要对源程序或其中间根据编译程序在完成翻译任务的过程中需要对源程序或其中间等价物扫描的遍数，可以把编译程序分为等价物扫描的遍数，可以把编译程序分为单遍扫描单遍扫描的编译程序的编译程序(只只需扫描

28、一遍需扫描一遍)和和多遍扫描多遍扫描的编译程序的编译程序(需扫描多遍需扫描多遍)。1.4 1.4 编译程序的组织形式编译程序的组织形式单遍扫描的编译程序单遍扫描的编译程序 多遍扫描的编译程序多遍扫描的编译程序例如，可以把词法分析作为第一遍；语法分析和语义分例如，可以把词法分析作为第一遍；语法分析和语义分析作为第二遍；代码优化和存储分配作为第三遍；代码析作为第二遍；代码优化和存储分配作为第三遍；代码生成作为第四遍：从而构成一个四遍扫描的编译程序。生成作为第四遍：从而构成一个四遍扫描的编译程序。每遍完成上述某个阶段的一部分、全部或几个阶段的工每遍完成上述某个阶段的一部分、全部或几个阶段的工作，并将

29、结构存入外存储器里，作为下一遍的输入。作，并将结构存入外存储器里，作为下一遍的输入。那么一个编译程序究竟应分成几遍，这和源程序语言的结构与那么一个编译程序究竟应分成几遍，这和源程序语言的结构与目标机器的特征有关。目标机器的特征有关。分多遍完成编译过程的分多遍完成编译过程的优点优点：可以使整个编译程序的逻辑结构：可以使整个编译程序的逻辑结构更清晰，能减少对主存容量的要求，使优化工作更为充分，并更清晰，能减少对主存容量的要求，使优化工作更为充分，并为可移植创造条件。为可移植创造条件。缺点缺点：遍数多势必增加读写中间文件的次：遍数多势必增加读写中间文件的次数，从而消耗过多的时间。数，从而消耗过多的时

30、间。总之，对一个具体的编译器，要确定用几遍扫描来完成，需要总之，对一个具体的编译器，要确定用几遍扫描来完成，需要综合考虑各种因素，从中取得最佳方案。综合考虑各种因素，从中取得最佳方案。前前端端主主要要由由与与源源语语言言有有关关但但与与目目标标机机器器无无关关的的那那些些部部分分组组成成，如如词词法法分分析析、语语法法分分析析、语语义义分分析析与与中中间间代代码码生生成成及及部部分分代代码码优优化化工作。工作。后后端端主主要要包包括括编编译译中中与与目目标标机机器器有有关关的的那那些些部部分分，如如与与目目标标机机有有关关的的代代码码优优化化和和目目标标代代码码生生成成等等。后后端端不不依依赖

31、赖于于源源语语言言而而仅仅依依赖赖于中间语言。于中间语言。可以通过改变编译程序的后端来实现编译程序的可以通过改变编译程序的后端来实现编译程序的移植移植。1.4 1.4 编译程序的组织形式编译程序的组织形式编译的前端和后端编译的前端和后端 如果宿主机的内存空间有限，则需要外存辅助，这种情况下，如果宿主机的内存空间有限，则需要外存辅助，这种情况下，编译程序可以按照下面的方式组织。编译程序可以按照下面的方式组织。首先在内存中开辟三个覆盖区（共享区）：一个存放最大的首先在内存中开辟三个覆盖区（共享区）：一个存放最大的Comp1Comp1；一个存放输入对象（扫描对象）；一个存放加工结果一个存放输入对象（

32、扫描对象）；一个存放加工结果（部分处理结果）。（部分处理结果）。然后在外存开辟编译程序的暂存区和输入对象然后在外存开辟编译程序的暂存区和输入对象/加工结果的加工结果的存放区。并且由存放区。并且由“编译总控程序编译总控程序”负责控制和调度编译程序的负责控制和调度编译程序的各遍。各遍。外存内存编译总控Comp1扫描对象部分处理结果Comp1Comp2Compn加 工结 果输 入对 象 覆盖编译程序组织方式 构造编译程序可以用构造编译程序可以用机器言语机器言语、汇编语言汇编语言和和高级语言高级语言。高级语言的高级语言的自编译性自编译性：一个语言可以用来编写自己的编：一个语言可以用来编写自己的编译程序

33、。译程序。1.5 1.5 编译程序的构造及相关技术编译程序的构造及相关技术 P5P51.5.11.5.1 高级语言的自编译性高级语言的自编译性 通过一系列通过一系列自展自展途径而形成编译程序的过程。途径而形成编译程序的过程。先对语言的核心部分构造一个小小编译程序先对语言的核心部分构造一个小小编译程序(可用低级语可用低级语言实现言实现)，再以它为工具构造一个能够编译更多语言成分的较，再以它为工具构造一个能够编译更多语言成分的较大编译程序。如此扩展下去，越滚越大，最后形成所期望的大编译程序。如此扩展下去，越滚越大，最后形成所期望的整个编译程序。整个编译程序。1.5 1.5 编译程序的构造及相关技术

34、编译程序的构造及相关技术1.5.21.5.2 编译的自展技术编译的自展技术 将一个机器（将一个机器（宿主机宿主机）上的一个具有自编译性的高级语）上的一个具有自编译性的高级语言编译程序移植到另一个机器（言编译程序移植到另一个机器（目标机目标机）上。）上。利用利用A A机器机器上的高级语言上的高级语言L L编写能在编写能在B B机器机器上运行的高级语上运行的高级语言言L L的编译程序。的编译程序。1.5 1.5 编译程序的构造及相关技术编译程序的构造及相关技术1.5.31.5.3 编译的移植编译的移植 1.5 1.5 编译程序的构造及相关技术编译程序的构造及相关技术1.5.21.5.2编译程序的自

35、动化编译程序的自动化在编译程序自动化进程中，开发早且应用广泛的是词法分析程在编译程序自动化进程中，开发早且应用广泛的是词法分析程序生成器和语法分析程序生成器。序生成器和语法分析程序生成器。词法分析程序生成器：词法分析程序生成器：LEXLEX。它输入的是正规表达式，输出的是。它输入的是正规表达式，输出的是词法分析程序。词法分析程序。LEXLEX的基本思想是由正规表达式构造有穷自动机的基本思想是由正规表达式构造有穷自动机。语法分析程序生成器：基于语法分析程序生成器：基于LALRLALR（1 1）文法的文法的YACCYACC（Yet Yet Another Compiler Another Comp

36、iler CompilerCompiler）。它接受。它接受LALRLALR（1 1）文法，生成文法，生成一个相应的一个相应的LALRLALR（1 1）分析表以及一个分析表以及一个LALRLALR（1 1）分析器，而且，分析器，而且，YACCYACC生成的语法分析器可以和扫描器连接生成的语法分析器可以和扫描器连接。第第1 1章内容小结章内容小结 什么是编译程序什么是编译程序 编译方式的特点编译方式的特点 解释方式的特点解释方式的特点 编译方式与解释方式的根本区别编译方式与解释方式的根本区别 编译程序的工作过程编译程序的工作过程 编译程序的结构编译程序的结构 遍与编译程序的组织形式遍与编译程序的

37、组织形式 编译程序的构造方法编译程序的构造方法下章内容简介下章内容简介 文法的形式定义与文法分类文法的形式定义与文法分类 语言的形式定语言的形式定义义 为语言构造文法为语言构造文法 与语法分析有关的概与语法分析有关的概念念 文法的实用限制文法的实用限制1.1.判断下面的陈述是否正确。判断下面的陈述是否正确。（1）编译程序的五个组成部分缺一不可。）编译程序的五个组成部分缺一不可。（2）高级语言程序到低级语言程序的转换是基于语义）高级语言程序到低级语言程序的转换是基于语义的等价变换。的等价变换。（3）含有优化部分的编译程序的执行效率高。）含有优化部分的编译程序的执行效率高。（4）因为编译程序和解释

38、程序具有不同的功能，所以）因为编译程序和解释程序具有不同的功能，所以它们的实现技术也完全不同。它们的实现技术也完全不同。（5）编译程序和解释程序的根本区别在于解释程序对）编译程序和解释程序的根本区别在于解释程序对源程序并没有真正进行翻译。源程序并没有真正进行翻译。（6）无论一遍扫描的编译器还是多遍扫描的编译器都）无论一遍扫描的编译器还是多遍扫描的编译器都要对源程序扫描一遍。要对源程序扫描一遍。答案：答案：(1)F (2)T(3)F (4)F (1)F (2)T(3)F (4)F (5)F (6)T(5)F (6)T 2 2计计算算机机执执行行用用高高级级语语言言编编写写的的程程序序有有哪哪些些途途径径？它它们之间的主要区别是什么？们之间的主要区别是什么？3 3画画出出编编译译程程序序的的总总体体逻逻辑辑结结构构图图，简简述述各各部部分分的的主主要功能。要功能。练习练习请请指出下列错误信息是编译的哪个阶段报告的指出下列错误信息是编译的哪个阶段报告的(1)else没有匹配的没有匹配的if；(2)使用的函数没有定义；使用的函数没有定义；(3)在数中出现非数字字符。在数中出现非数字字符。答案：答案：(1)(1)语法语法 (2)(2)语义语义 (3)(3)词词法法THEEND