编译原理-课程简介.ppt

1,编译原理和技术Principles of Compiling,大连理工大学软件学院徐秀娟,2,编译原理课程在计算机科学技术中的地位：,程序设计语言,离散数学,数据结构,编译原理,操作系统,系统软件,应用软件,软件工程,信息系统,电子商务,3,本讲纲要,课程简介编译技术概述,4,课 程 简 介,编译理论与方法计算机科学与技术中理论和实践相结合的最好典范 ACM 图灵奖，授予在计算机技术领域作出突出贡献的科学家程序设计语言、编译理论与方法约占1/3,5,课 程 简 介,教材和参考书陈意云、张昱，编译原理，高等教育出版社，2008年第二版陈火旺、刘春林等编著 程序设计语言编译原理（第3版），国防工业出版社，2001年4月蒋立源等主编 编译原理(第2版)，西北工业大学出版社，2002年1月。张素琴，吕映芝等编著 编译原理，清华大学出版社，2005年胡伦骏等 编译原理电子工业出版社 2005 年,6,课 程 简 介,教材和参考书Compilers:Principles,Techniques,and Tools 编译原理 技术与工具（英文版）Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman,人民邮电出版社.中文版：机械工业出版社http:/dragonbook.stanford.edu/“龙书”。龙书是于1986年出版第一版，由于出版年代较早，其中包含部分过时的技术并且没有反映一些新的编译技术。新版的编译原理抛弃诸如算符优先分析等过时技术，增加面向对象编译、类型检查等新技术。,7,课 程 简 介,教材和参考书现代编译原理-C语言描述/Modern Compiler Implementation in C（美）安佩尔/2006-4-1/人民邮电出版社/C语言描述/45.0/平装/沈志宇/黄春/赵克佳“虎书”。虎书出版比较晚，与编译原理的知识点差不多，但增加了数据流分析、循环优化、内存管理等内容。与虎书比，编译原理更适合国内的编译原理课程教学。本书包括C版，还有java版和ML版,8,课 程 简 介,教材和参考书高级编译器设计与实现/Advanced Compiler Design and Implementation（美）马其尼克/2005-7-1/机械工业出版社/75.0/平装/沈志宇/赵克佳“鲸书”。鲸书侧重在对编译器后端优化的处理。在本科阶段的编译教学中旨在让学生对程序设计语言的编译全过程有系统的理解，因此会介绍编译器后端的处理技术，但不注重优化技术。,9,课 程 简 介,成绩评定学期总评=考试成绩占70%，平时成绩30分（作业+上机实验+平时点名）平时点名4次，每次2分。4次都不到的取消期末考试资格。作业+上机=22分,1-16周上课每周12次时间紧、任务重,10,课 程 简 介-要求,抄袭：不允许禁止c&p同学网上惩罚零分Deadline最后时间:每周第一次课课间交作业No Extension,11,课 程 简 介,课程要求目标：师生共同努力，帮助大家学有所得讲课进度较快，平时不复习并加深理解，后面将听不懂作业较多，要求独立完成上机实验，不要轻视阅读PL/0编译器，会有很大收获,12,课 程 简 介,课程内容介绍编译器构造的一般原理和基本实现方法介绍的理论知识：形式语言和自动机理论、语法制导的定义和属性文法、类型论等课程特点强调形式化描述技术强调对编译原理和技术的宏观理解，不把注意力分散到枝节算法，不偏向于某种源语言或目标机器,13,if(c=5)then if(c=5)then,编译器不报错，但实际上错了,课 程 简 介,学习的意义它是计算机专业的核心课程。深刻的理解编程语言的设计和实现，有利于学习编程语言，知其然知其所以然。,14,课 程 简 介,学习的意义从软件工程看，编译器是一个很好的实例（基本设计、模块划分等），所介绍的概念和技术能应用到一般的软件设计之中。编译器也许是在本科阶段分析最透彻的实例。能了解到软件工程中的一些技术（如基于事件驱动的编程）。大多数程序员同时是语言的设计者，虽然是一些简单的语言（如输入输出），本课程的学习有助于提高对这些语言的设计水平。,15,课 程 简 介,学习的意义可以肯定地说，你们中的95%以上的人在一辈子的生涯中都没有机会去实现一个真正的复杂语言的编译器。但是每一个人都绝对遇到需要使用编译技术的项目。以下就是一些小的“编译器”.,16,普通计算器,可编程计算器,课 程 简 介,学习的意义,17,课 程 简 介,自动聊天机器人,学习的意义,18,各种数据库查询语言及专家系统,select 课程 from table 课程表 where 任课老师=徐秀娟,课 程 简 介,学习的意义,19,在x86/Linux工作站上，以下两个结构的size分别是20和16，为什么不一样？typedef struct _atypedef struct _bchar c1;char c1;long i;charc2;charc2;long i;double f;double f;a;b;,课 程 简 介,学习的意义在计算机专业考研或者各大公司招聘时，必考内容。,20,typedef struct _atypedef struct _bchar c1;char c1;long l;charc2;charc2;long l;double f;double f;a;b;,课 程 简 介,sizeof(a):20a的首地址:0 xbf9a97c4a.c1的首地址:0 xbf9a97c4a.l的首地址:0 xbf9a97c8a.c2的首地址:0 xbf9a97cca.d的首地址:0 xbf9a97d0,Linux下测试结果：,sizeof(b):16b的首地址:0 xbf9a97d8b.c1的首地址:0 xbf9a97d8b.c2的首地址:0 xbf9a97d9b.l的首地址:0 xbf9a97dcb.d的首地址:0 xbf9a97e0,21,typedef struct _atypedef struct _bchar c1;char c1;long l;charc2;charc2;long l;double f;double f;a;b;,课 程 简 介,sizeof(a):24a的首地址:0012FF18a.c1的首地址:0012FF18a.l的首地址:0012FF1Ca.c2的首地址:0012FF20a.d的首地址:0012FF28,VC下测试结果：,sizeof(b):16b的首地址:0012FF08b.c1的首地址:0012FF08b.c2的首地址:0012FF09b.l的首地址:0012FF0Cb.d的首地址:0012FF10,22,在C程序设计中经常需要用到一种数据类型的长度(占内存的字节数),例如：int*p=NULL;p=(int*)malloc(10*sizeof(int);/*用sizeof(int)来得到int类型的长度*/,23,vc6中的编译选项有/Zp1|2|4|8|16，/Zp1表示以1字节边界对齐，相应的，/Zpn表示以n字节边界对齐。n字节边界对齐的意思是说，一个成员的地址必须安排在成员的尺寸的整数倍地址上或者是n的整数倍地址上，取它们中的最小值。要使用这个选项，可以在vc6中打开工程属性页，c/c+页，选择Code Generation分类，在Struct member alignment可以选择。,24,字节对齐是为了提高CPU的读取效率.比如有些平台每次读都是从偶地址开始,如果一个int型（假设为32位系统）如果存放在偶地址开始的地方,那么一个读周期就可以读出这32bit,而如果存放在奇地址开始的地方,就需要2个读周期,并对两次读出的结果的高低字节进行拼凑才能得到该32bit数据.显然在读取效率上下降很多.,25,26,本讲纲要,课程简介编译技术概述,27,编辑器,源程序,编译器,操作系统,可执行程序.exe,解释器,中间代码,可执行程序.exe,Edit,Word,Notepad,Vi,gcc,vc,bc31,虚拟机,集成开发环境,编译技术研究对象：编译器的构造与分析,28,BASIC年代的解释器功能：它将高级语言的源程序翻译成一种中间语言程序，然后对中间语言程序进行解释执行在那个年代，编译和解释两个功能是合在一个程序中，该程序被称为解释器Java年代的解释器解释器的上述两个功能分在两个程序中前一个叫做编译器，它把源程序翻译成一种叫做字节码的中间语言程序后一个叫做解释器，它对字节码程序进行解释执行,课 程 简 介,29,编译器和解释器的区别,三种奶牛三种嗜好,30,编译器和解释器的区别,改进后的方案,31,编译器和解释器的区别,牧草 我们的各种编程语言，C/C+/C#,Java,Pascal,PHP,Perl,Java Script等切割机 各种编译器奶牛 各种CPU，比如x86，ARM，MIPS等奶牛会有吃不同形状牧草的嗜好，这个奇怪的比喻是为了表示不同的CPU接受的不同的机器语言。,32,编译器和解释器的区别,33,编译器和解释器的区别,34,第一章 引论,翻译器：把一种语言变换到另外一种语言的软件。这两种语言分别称为源语言和目标语言。编译器：一种翻译器，它的目标语言比源语言低级。编译器处理的对象：编程语言,35,编程语言演义,编程语言机器语言汇编语言高级语言（Fortran,C,Java,),36,编程语言演义,机器语言特点0,1串打卡输入c7 06 0000 0002 mov x,c 其中符号x的地址是0000，c=2计算机可以直接理解机器语言程序机器语言缺点可读性差可维护性差,机器语言汇编语言高级语言,37,编程语言演义,汇编语言形式mov x,2c7 06 0000 0002 变量x的地址可以由汇编器维护，而不需要固定到某个绝对地址,机器语言汇编语言高级语言,38,编程语言演义,高级语言形式赋值语句：x=2贴近人类思维方式，贴近实际问题描述形式计算机无法直接理解需要编译器辅助，将其转换为机器语言形式,机器语言汇编语言高级语言,39,编译器功能,完成从源语言到目标语言的转换 源语言：通常是高级语言（C,Java,）目标语言：汇编语言，或者其他形式的低级语言（如Java字节码）编译器实现技术已经发展成熟，并且划分为功能相对明确的多个功能模块,40,编译器,编译器从逻辑上可以分成若干阶段，每个阶段把源程序从一种表示变换成另一种表示,翻译家,第一章 引 论,41,第一章 引 论,FORTRAN(FORmula TRANslation)第一个实用的高级语言 擅长于数学函数运算 常用于科学计算中 第一个编译器 历史上第一个实用的编译器(John Backus)：Fortran compiler for the IBM 704/709/7090/7094 John Backus，引入了编译器的“阶段”或称为“遍”的概念，是编译设计的模块化的开始,42,遍,编译的几个阶段常用一遍（pass）扫描实现，一遍扫描包括读一个输入文件和写一个输出文件。,第一章 引 论,43,遍,类比：刷墙艺术中的“遍”的概念,网线,水泥,瓷砖,任务：在一面墙上布置网线，并粉刷水泥，然后贴上瓷砖,第一章 引 论,44,遍,类比：刷墙艺术中的“遍”的概念,方法一：,第一遍：布上全部网线,网线,水泥,瓷砖,第一章 引 论,45,遍,类比：刷墙艺术中的“遍”的概念,方法一：,第二遍：粉刷全部墙面的水泥,网线,水泥,瓷砖,第一章 引 论,46,遍,类比：刷墙艺术中的“遍”的概念,方法一：,第三遍：给整个墙面贴上瓷砖,网线,水泥,瓷砖,第一章 引 论,47,遍,类比：刷墙艺术中的“遍”的概念,方法二：,一遍：一边布网线，一边粉刷水泥，一边贴瓷砖,网线,水泥,瓷砖,第一章 引 论,48,遍（趟）：一遍或一趟：是指编译程序在编译时刻把源程序或源程序的等价物（中间程序）从头到尾扫描一遍并转换成另一紧邻的等价物的全过程。单遍扫描与多遍扫描：每一遍的扫视可完成上述一个阶段或多个阶段的工作。每一遍的输入都是上一遍的输出，第一遍的输入是源程序正文，最后一遍的输出是目标代码。单遍与多遍的比较：遍数多：编译器结构清晰，但时间效率不高遍数少：编译速度快，但对机器的内存要求高遍数的确定：主要因素是源程序和机器（目标机）的特征。,第一章 引 论,49,词法分析：源程序-词法记号（token）流,第一章 引 论,50,任何一个标识符都是表达式；任何一个数都是表达式；如果e1和e2都是表达式，那么 e1+e2 e1*e2(e1)也都是表达式,语法分析：词法记号（token）流-语法短语,任何名词都可以作宾语；如果e1和e2都是宾语，那么 e1 和e2 e1 与e2 也都可以作宾语如果e1是定语，e2是宾语，那么e1 e2也可以作宾语。,第一章 引 论,51,语法分析器,id,1=id,2+id,3 60,语法分析：词法记号（token）流-语法短语,名词1 动词 形容词 名词2,语法分析,第一章 引 论,52,语义分析：检查程序的语义正确性，如类型检查等,你们是优秀的大工学子,你们是一个优秀的大工学子。,第一章 引 论,53,第一章 引 论,54,中间代码生成器,temp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3,英语文本生成,You are good DLUTers.,第一章 引 论,55,代码优化器,temp1:=inttoreal(60)temp2:=id3*temp1temp3:=id2+temp2id1:=temp3,temp1:=id3*60.0id1:=id2+temp1,You are good DLUTers.,英语文本改进,You are excellent DLUTers,第一章 引 论,56,日语文本生成,You are excellent DLUTers,君大連理工大学優秀学生。,第一章 引 论,57,第一章 引 论,58,第一章 引 论,59,前端后端,前端：依赖于源语言，独立于目标机器。,后端：依赖于目标机器，独立于源语言。,第一章 引 论,60,前端和后端：把编译过程分成前端和后端两部分前端：只依赖于源程序，独立于目标机器（生成中间代码）后端：依赖于目标机器，与源程序无关，只与中间语言有关（从中间代码生成目标代码）好处：提高开发编译器的效率取一个编译器的前端，重写它的后端以产生同一源语言在另一机器上的编译器不同的前端使用同一个后端，从而得到一个机器上的几个编译器（采用同一中间语言）,第一章 引 论,61,源程序,目标机器1,目标机器2,目标机器3,目标机器n,编译器,不区分前端和后端的编译器,源程序,目标机器1,目标机器2,目标机器3,目标机器n,编译器前端,编译器后端,区分前端和后端的编译器,第一章 引 论,62,高级语言的实现高级编程语言易于编程，但程序运行较慢低级语言编程时可实施更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护流行编程语言的大多数演变都是朝着提高抽象级别的方向每一轮编程语言新特征的出现都刺激编译器优化的新研究,1.2 编译器技术的应用,63,程序翻译二进制翻译 编译器技术可用于把一种机器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令集编译的代码数据库查询解释器 数据库查询由一些谓词组成，这些谓词由包含关系运算的布尔表达式组成，可以被解释执行,也可以被编译成搜索数据库的命令,1.2 编译器技术的应用,64,提高软件开发效率的工具源于编译器中代码优化技术的程序分析一直在改进软件开发效率类型检查 类型检查是一种捕捉程序中前后不一致的成熟而有效的技术边界检查 数据流分析技术可用来定位缓冲区溢出内存管理 自动的内存管理删除内存泄漏等内存管理错误,1.2 编译器技术的应用,65,语法制导的结构化编辑器,程序格式化工具,软件测试工具,程序理解工具,高级语言的翻译工具,等等。,编译技术的应用,66,编译原理的内容及学习意义翻译器、编译器的定义编译器的阶段划分及前端、后端的概念“遍”的概念,小 结,67,习题1：1.1,1.2(编译器与解释器的区别是什么)单周第一次课课间时交作业,作业,