大连理工大学编译原理课件.ppt

1、编译原理和技术刘馨月自我介绍自我介绍刘馨月，女，博士，副教授刘馨月，女，博士，副教授主讲课程：数据结构与算法，编译技术主讲课程：数据结构与算法，编译技术研究方向：数据挖掘，信息检索研究方向：数据挖掘，信息检索数据结构与算法教学团队成员数据结构与算法教学团队成员智能信息处理研究所成员（智能信息处理研究所成员（）课程定位课程定位核心课程核心课程分类分类课程名称课程名称课程定位课程定位备注备注 计算机基础计算机基础计算机导论入门算法和数据结构基础高级语言程序设计（1，2）必备工具 计算机理论计算机理论（离散数学（离散数学1,2,3）数理逻辑计算机数学集合论和图论组合数学 计算机硬件类课程计算机硬件类

2、课程数子电路和数字逻辑硬件基础课程含实验计算机原理和汇编语言部件原理含实验计算机接口与通讯部件间通讯含实验计算机体系结构体系结构含实验计算机网络 计算机软件类课程计算机软件类课程编译技术编译技术系统软件层系统软件层含课程设计含课程设计操作系统含课程设计数据库系统原理含课程设计软件工程信息系统分析与设计应用类计算机图形学（多媒体技术）应用类操作系统编译理论与方法计算机科学与技术中理论和实践相结合的最好典范 Intel公司的公司的David Kuck院士曾经将编译器誉院士曾经将编译器誉为为“计算机科学与技术的皇后计算机科学与技术的皇后”ACM图灵奖“计算机界的诺贝尔奖”，授予在计算机技术领域作出突

3、出贡献的科学家程序设计语言、编译理论与方法约占1/3课程简介课程简介本专业人员本专业人员4 4种基本的专业能力种基本的专业能力计算思维能力计算思维能力算法的设计与分析能力算法的设计与分析能力程序设计和实现能力程序设计和实现能力计算机软硬件系统的认知、分析、设计与应用计算机软硬件系统的认知、分析、设计与应用能力能力计算思维能力计算思维能力逻辑思维能力和抽象思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述构造模型对问题进行形式化描述理解和处理形式模型理解和处理形式模型陈火旺、刘春林等编著陈火旺、刘春林等编著 程序设计语言编译原理（第程序设计语言编译原理（第3版）版），国防工业出版社，

4、国防工业出版社，2001年年4月月蒋立源等主编蒋立源等主编 编译原理编译原理(第第2版版)，西北工业大学出版，西北工业大学出版社，社，2002年年1月。月。张素琴，吕映芝等编著张素琴，吕映芝等编著 编译原理，清华大学出版社，编译原理，清华大学出版社，2005年年 胡伦骏等胡伦骏等 编译原理编译原理电子工业出版社电子工业出版社 2005 年年 编译原理、技术和工具编译原理、技术和工具 Compilers:Principles,Techniques,and Tools（美）阿霍，等（美）阿霍，等/2003-8-1/机械工业出版机械工业出版社社/55.00/平装平装/李建中李建中2009年第二版，年

5、第二版，89.00 “龙书龙书”。龙书是龙书是Alfred V.Aho等人于等人于1986年出版的，由于出版年代较早，其中包年出版的，由于出版年代较早，其中包含部分过时的技术并且没有反映一些新的编含部分过时的技术并且没有反映一些新的编译技术。新编的译技术。新编的编译原理编译原理抛弃诸如算符抛弃诸如算符优先分析等过时技术，增加面向对象编译、优先分析等过时技术，增加面向对象编译、类型检查等新技术。类型检查等新技术。课程简介课程简介现代编译原理现代编译原理-C语言描述语言描述/Modern Compiler Implementation in C（美）安佩尔（美）安佩尔/2006-4-1/人民邮电出

6、版人民邮电出版社社/C语言描述语言描述/45.0/平装平装/沈志宇沈志宇/黄黄春春/赵克佳赵克佳 “虎书虎书”。虎书出版比较晚，与虎书出版比较晚，与编译原理编译原理的知识点差不多，但增加的知识点差不多，但增加了数据流分析、循环优化、内存管理等了数据流分析、循环优化、内存管理等内容。与虎书比，内容。与虎书比，编译原理编译原理更适合更适合国内的编译原理课程教学。这本是国内的编译原理课程教学。这本是C版，版，还有还有java版和版和ML版。版。课程简介课程简介高级编译器设计与实现高级编译器设计与实现/Advanced Compiler Design and Implementation（美）马其尼克

7、（美）马其尼克/2005-7-1/机械工业出版机械工业出版社社/75.0/平装平装/沈志宇沈志宇/赵克佳赵克佳 “鲸书鲸书”。鲸书侧重在对编译器后端优鲸书侧重在对编译器后端优化的处理。在本科阶段的编译教学中旨在让化的处理。在本科阶段的编译教学中旨在让学生对程序设计语言的编译全过程有系统的学生对程序设计语言的编译全过程有系统的理解，因此会介绍编译器后端的处理技术，理解，因此会介绍编译器后端的处理技术，但不注重优化技术。但不注重优化技术。与其他自然科学相比，计算机科学的发展历史并与其他自然科学相比，计算机科学的发展历史并不久远，是较新的学科体系，尚有许多未知的领不久远，是较新的学科体系，尚有许多未

8、知的领域有待探索。因此，本专业学生或工程技术人员域有待探索。因此，本专业学生或工程技术人员仅仅满足于学习或应用几门程序设计语言是远远仅仅满足于学习或应用几门程序设计语言是远远不够的。一些看似抽象的课程才是提高专业人员不够的。一些看似抽象的课程才是提高专业人员“内功内功”修为的秘技，例如修为的秘技，例如数据结构、操作系统、数据结构、操作系统、编译原理、计算机系统结构、计算机网络编译原理、计算机系统结构、计算机网络等。不等。不过，经典课程的学习并不是一蹴而就的，如何学过，经典课程的学习并不是一蹴而就的，如何学习与理解习与理解课程的精髓课程的精髓是值得关注的。是值得关注的。学习的意义学习的意义l 有

9、人认为，编译技术似乎已经相当成熟了，继续深入研究是没有任何意义的。有人认为，编译技术似乎已经相当成熟了，继续深入研究是没有任何意义的。实际上，任何科学技术都是发展变化的。表面上看，编译器设计的高层问题实际上，任何科学技术都是发展变化的。表面上看，编译器设计的高层问题似乎已经形成了完美的体系，但当我们深入其内核就会发现事实并非如此。似乎已经形成了完美的体系，但当我们深入其内核就会发现事实并非如此。现代编译器设计面临的挑战是来自目标计算机系统结构、新颖程序设计语言现代编译器设计面临的挑战是来自目标计算机系统结构、新颖程序设计语言及本身的计算资源等多方面的。其中，任何一方面的因素都足以颠覆某些传及本

10、身的计算资源等多方面的。其中，任何一方面的因素都足以颠覆某些传统理论与算法。统理论与算法。l 当然，当然，从更高的层次上从更高的层次上讲，学习编译器设计的目的还不仅仅局限于其本身的讲，学习编译器设计的目的还不仅仅局限于其本身的理论与技术。作为一个系统软件的设计学科，其理论与技术。作为一个系统软件的设计学科，其解决问题的思路与方法更是解决问题的思路与方法更是值得读者细细品味的值得读者细细品味的。这可能是一个漫长而艰辛的历程，不过，这才是经典这可能是一个漫长而艰辛的历程，不过，这才是经典学科的魅力所在。学科的魅力所在。以品味经典为目的来学习与研究操作系统、数据库技术、以品味经典为目的来学习与研究操

11、作系统、数据库技术、计算机网络、编译技术等学科是诸君努力方向。计算机网络、编译技术等学科是诸君努力方向。对软件工程来说，编译器是一个很好的实例（基本设对软件工程来说，编译器是一个很好的实例（基本设计、模块划分等），也是本科期间能碰到的唯一的大计、模块划分等），也是本科期间能碰到的唯一的大型例子，从本课程的学习也能了解到软件工程中的一型例子，从本课程的学习也能了解到软件工程中的一些技术（如基于事件驱动的编程）。本课程所介绍的些技术（如基于事件驱动的编程）。本课程所介绍的概念和技术能应用到一般的软件设计之中。概念和技术能应用到一般的软件设计之中。大多数程序员同时是语言的设计者，虽然是一些简单大多数

12、程序员同时是语言的设计者，虽然是一些简单的语言（如输入输出），本课程的学习有助于提高对的语言（如输入输出），本课程的学习有助于提高对这些语言的设计水平。这些语言的设计水平。自学能力的考查自学能力的考查,抽象思维能力的锻炼抽象思维能力的锻炼课课 程程 简简 介介学习的意义学习的意义在计算机专业考研或者各大公司招聘时，必在计算机专业考研或者各大公司招聘时，必考内容。考内容。在在x86/Linuxx86/Linux工作站上，以下两个结构的工作站上，以下两个结构的sizesize分别是分别是2020和和1616，为什么不一样？为什么不一样？typedef struct _atypedef struct

13、 _atypedef struct _btypedef struct _bchar char c1;c1;char c1;char c1;long long i;i;char char c2;c2;charcharc2;c2;long i;long i;double f;double f;double f;double f;a;a;b;b;在在C程序设计中我们经常需要用到一种数据程序设计中我们经常需要用到一种数据类型的长度类型的长度(占内存的字节数占内存的字节数),例如：例如：int*p=NULL;p=(int*)malloc(10*sizeof(int);/*用用sizeof(int)来得到

14、来得到int类型的长度类型的长度*/vc结果结果 vs Linux下下gcc的结果的结果vc6中的编译选项有中的编译选项有/Zp1|2|4|8|16，/Zp1表示表示以以1字节边界对齐，相应的，字节边界对齐，相应的，/Zpn表示以表示以n字节边字节边界对齐。界对齐。n字节边界对齐的意思是说，一个成员字节边界对齐的意思是说，一个成员的地址必须安排在成员的尺寸的整数倍地址上或的地址必须安排在成员的尺寸的整数倍地址上或者是者是n的整数倍地址上，取它们中的最小值。的整数倍地址上，取它们中的最小值。要使用这个选项，可以在要使用这个选项，可以在vc6中打开工程属性页，中打开工程属性页，c/c+页，选择页，

15、选择Code Generation分类，在分类，在Struct member alignment可以选择。可以选择。字节对齐是为了字节对齐是为了提高提高CPU的读取效率的读取效率.比如有些平比如有些平台每次读都是从偶地址开始台每次读都是从偶地址开始,如果一个如果一个int型（假设型（假设为为32位系统）如果存放在偶地址开始的地方位系统）如果存放在偶地址开始的地方,那么那么一个读周期就可以读出这一个读周期就可以读出这32bit,而如果存放在奇而如果存放在奇地址开始的地方地址开始的地方,就需要就需要2个读周期个读周期,并对两次读出并对两次读出的结果的高低字节进行拼凑才能得到该的结果的高低字节进行拼

16、凑才能得到该32bit数据数据.显然在读取效率上下降很多显然在读取效率上下降很多.类型类型字节数字节数char1short2int4float4long4long long8double8long double10Intel和微软公司同时出现的面试题，练习一下：和微软公司同时出现的面试题，练习一下：#pragma pack(8)/*指定按指定按8字节对齐字节对齐*/struct s1 short a;long b;struct s2 char c;s1 d;long long e;#pragma pack()/*取消指定对齐，恢复缺省对齐取消指定对齐，恢复缺省对齐*/问题问题：1.sizeof

17、(s2)=?2.s2的的c后面空了几个字节接着是后面空了几个字节接着是d？答案：答案：sizeof(S2)结果为结果为24。s2的的c后面空了后面空了3个字节接着是个字节接着是d。分析：分析：S1中，成员中，成员a是是2字节默认按字节默认按2字节对齐，指定对齐参数为字节对齐，指定对齐参数为8，这两个值中取，这两个值中取2，a按按2字节对齐；同理，成员字节对齐；同理，成员b是是4个字节，按个字节，按4字节对齐，所以字节对齐，所以sizeof(S1)应该应该为为8;a bS1的内存布局：的内存布局：11*,1111 S2 中中,c按按1字节对齐字节对齐,而而d 是个结构是个结构,它是它是8个字节个

18、字节,它按什么对齐呢它按什么对齐呢?对于结构来说对于结构来说,它的默认对齐方式就是它的所有成员使用的有效对齐值中最大的它的默认对齐方式就是它的所有成员使用的有效对齐值中最大的一个一个,S1的就是的就是4.所以所以,成员成员d就是按就是按4字节对齐字节对齐.成员成员e是是8个字节个字节,它是默认按它是默认按8字字节对齐节对齐,和指定的一样，所以它对到和指定的一样，所以它对到8字节的边界上字节的边界上,这时这时,已经使用了已经使用了12个字节个字节了了,所以添加了所以添加了4个字节的空个字节的空,从第从第16个字节开始放置成员个字节开始放置成员e。这样一共使用了。这样一共使用了24个字节。个字节。

19、c S1.a S1.b dS2的内存布局：的内存布局：1*,11*,1111,*11111111程序设计语言的发展程序设计语言的发展机器语言（机器指令）汇编语言面向用户的语言面向问题的语言低级语言低级语言高级语言高级语言C70600000002MOVx,2x=2低级语言（Low level Language)字位码、机器语言、汇编语言特点：与特定的机器有关，功效高，但使用复杂、繁琐、费时、易出错高级语言 -Fortran、Pascal、C 语言等语言等特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。用高级语言编制的程序，计算机不能立即执行，用高级语言编制的程序，计算机不能立即执

20、行，必须通过一个必须通过一个“翻译程序翻译程序”加工，转化为与其等价的加工，转化为与其等价的机器语言程序，机器才能执行。机器语言程序，机器才能执行。这种翻译程序，称之为这种翻译程序，称之为“编译程序编译程序”。源程序源程序 用汇编语言或高级语言编写的程序称为源程序。目标程序目标程序 用目标语言目标语言所表示的程序。目标语言：目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言。翻译程序翻译程序将源程序源程序转换为目标程序目标程序的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。基

21、本概念基本概念虚拟机虚拟机BASIC年代的解释器功能：它将高级语言的源程序翻译成一种中间语言程序，然后对中间语言程序进行解释执行在那个年代，编译和解释两个功能是合在一个程序中，该程序被称为解释器Java年代的解释器解释器的上述两个功能分在两个程序中前一个叫做编译器，它把源程序翻译成一种叫做字节码的中间语言程序后一个叫做解释器，它对字节码程序进行解释执行编译器和解释器的区别编译器和解释器的区别编译器和解释器的区别编译器和解释器的区别编译器与解释器的区别编译器与解释器的区别编译器是把源程序的每一条语句都编译成编译器是把源程序的每一条语句都编译成机器语言机器语言,并保存成二进制文件并保存成二进制文件

22、,这样运行时这样运行时计算机可以直接以机器语言来运行此程序计算机可以直接以机器语言来运行此程序,速度很快速度很快;而解释器则是只在执行程序时而解释器则是只在执行程序时,才一条一条才一条一条的解释成机器语言给计算机来执行的解释成机器语言给计算机来执行,所以运所以运行速度是不如编译后的程序运行的快的行速度是不如编译后的程序运行的快的.编译器从逻辑上可以分成若干阶段每个阶段把源程序从一种表示变换成另一种表示本章通过描述编译器的各个阶段来介绍编译这个课题词法分析器词法分析器 id,1 =id,2 +id,3 60 position=initial+rate 60 id,1 =id,2 +id,3 60

23、 第一章 引 论 词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器目标程序目标程序出错管理器出错管理器符号表管理器符号表管理器后三个阶后三个阶段对源程段对源程序进行综序进行综合合第一章 引 论 词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器目标程序目标程序出错管理器出错管理器符号表管理器符号表管理器在上列6个阶段中都要做两件事：（1）建表和查表；（2）出错处理；所以编译程序中都要包括符号表管理和出错处理两部分。

24、出错处理出错处理规模较大的源程序难免有多种错误，编译程序必须要有出错处理的功能。即能诊察出错误，并能报告用户错误的性质和位置，以便用户修改源程序。出错处理能力的大小是衡量编译程序质量好坏的一个重要指标。符号表管理符号表管理在整个编译过程中始终都要贯穿着建表（填表）和查表的工作。即要及时地把源程序中的信息和编译过程中所产生的信息登记在表格中，而在随后的编译过程中同时又要不断地查找这些表格中的信息。分析和综合：把编译过程分成分析和综合两步把编译过程分成分析和综合两步分析：分析源程序以计算其特性所涉及到的分析源程序以计算其特性所涉及到的操作（词法分析、语法分析、语义分析）操作（词法分析、语法分析、语

25、义分析）综合：生成目标代码时所涉及到的操作（生成目标代码时所涉及到的操作（中中间代码生成、代码优化、代码生成）间代码生成、代码优化、代码生成）辅助：符号表管理、出错处理符号表管理、出错处理8项功能对应8个模块。第一章 引 论前端和后端：把编译过程分成前端和后端两部分把编译过程分成前端和后端两部分前端：只依赖于源程序，独立于目标机器只依赖于源程序，独立于目标机器（生成中间代码）（生成中间代码）后端：依赖于目标机器，与源程序无关，只与中间：依赖于目标机器，与源程序无关，只与中间语言有关（从中间代码生成目标代码）语言有关（从中间代码生成目标代码）好处：提高开发编译器的效率提高开发编译器的效率取一个编

26、译器的前端，重写它的后端以产生同一源语言在取一个编译器的前端，重写它的后端以产生同一源语言在另一机器上的编译器另一机器上的编译器不同的前端使用同一个后端，从而得到一个机器上的几个不同的前端使用同一个后端，从而得到一个机器上的几个编译器（采用同一中间语言）编译器（采用同一中间语言）遍（趟）：一遍或或一趟：是指编译程序在编译时刻把源程序或源程序的是指编译程序在编译时刻把源程序或源程序的等价物（中间程序）从头到尾扫描一遍并转换成另一紧邻的等等价物（中间程序）从头到尾扫描一遍并转换成另一紧邻的等价物的全过程。价物的全过程。单遍扫描与多遍扫描：每一遍的扫描可完成上述一个阶段每一遍的扫描可完成上述一个阶段

27、或多个阶段的工作。每一遍的输入都是上一遍的输出，第一遍或多个阶段的工作。每一遍的输入都是上一遍的输出，第一遍的输入是源程序正文，最后一遍的输出是目标代码。的输入是源程序正文，最后一遍的输出是目标代码。单遍与多遍的比较：遍数多：编译器结构清晰，但时间效率不高遍数多：编译器结构清晰，但时间效率不高遍数少：编译速度快，但对机器的内存要求高遍数少：编译速度快，但对机器的内存要求高遍数的确定：主要因素是源程序和机器（目标机）的特征。主要因素是源程序和机器（目标机）的特征。1.2 编译器技术的应用高级语言的实现高级编程语言易于编程，但程序运行较慢低级语言编程时可实施更有效的控制方式，得到更有效的代码，但难

28、编写、易出错、难维护流行编程语言的大多数演变都是朝着提高抽象级别的方向每一轮编程语言新特征的出现都刺激编译器优化的新研究1.2 编译器技术的应用 程序翻译二进制翻译 编译器技术可用于把一种机器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令集编译的代码数据库查询解释器 数据库查询由一些谓词组成，这些谓词由包含关系运算的布尔表达式组成，可以被解释执行,也可以被编译成搜索数据库的命令1.2 编译器技术的应用 提高软件开发效率的工具源于编译器中代码优化技术的程序分析一直在类型检查 类型检查是一种捕捉程序中前后不一致的成熟而有效的技术改进软件开发效率边界检查 数据流分析技术可用来定位缓冲区溢出内存管理 自动的内存管理删除内存泄漏等内存管理错误编译技术的应用编译技术的应用 语法制导的结构化编辑器语法制导的结构化编辑器 程序格式化工具程序格式化工具 软件测试工具软件测试工具 程序理解工具程序理解工具 高级语言的翻译工具高级语言的翻译工具 等等。等等。