编译原理课程第1讲.ppt

1、编译原理和技术,大连理工大学软件学院 贾棋 87571625,编译原理课程在计算机科学技术中的地位：,课 程 简 介,编译理论与方法 计算机科学与技术中理论和实践相结合的最好典范 ACM 图灵奖，授予在计算机技术领域作出突出贡献的科学家 程序设计语言、编译理论与方法约占1/3,课 程 简 介,教材和参考书 陈意云、张昱，编译原理，高等教育出版社， 2008年第二版 Alfred V.Aho, Ravi Sethi, Jeffrey D.Ullman, .编译原理 技术与工具（英文版） 人民邮电出版社. 中文版：机械工业出版社,课 程 简 介,成绩评定 学期总评 = 考试成绩占70%，平时成绩3

2、0分（作业+上机实验+平时点名） 平时点名4次，每次2分。4次都不到的取消期末考试资格。 作业+上机=22分,课 程 简 介,课程要求 目标：师生共同努力，帮助大家学有所得 讲课进度较快，平时不复习并加深理解，后面将听不懂 作业较多，要求独立完成 上机实验，不要轻视 阅读PL/0编译器，会有很大收获 课件下载：ftp:.jiaqi,课 程 简 介,课程内容 介绍编译器构造的一般原理和基本实现方法 介绍的理论知识：形式语言和自动机理论、语法制导的定义和属性文法、类型论等 课程特点 强调形式化描述技术 强调对编译原理和技术的宏观理解，不把注意力分散到枝节算法，不偏向于某种源语

3、言或目标机器,课 程 简 介,学习的意义 它是计算机专业的核心课程。对编程语言的设计和实现有深刻的理解，有利于学习编程语言，知其然知其所以然。,if (c = 5) then if (c = 5) then,if (5 = c) then if (5 = c) then,编译器不报错，但实际上错了,编译器报错,课 程 简 介,学习的意义 从软件工程看，编译器是一个很好的实例（基本设计、模块划分等）， 所介绍的概念和技术能应用到一般的软件设计之中。编译器也许是大家在本科阶段分析最透彻的实例了。从本课程的学习也能了解到软件工程中的一些技术（如基于事件驱动的编程）。本课程所介绍的概念和技术能应用到一

4、般的软件设计之中。 大多数程序员同时是语言的设计者，虽然是一些简单的语言（如输入输出），本课程的学习有助于提高对这些语言的设计水平。,课 程 简 介,学习的意义 可以肯定地说，你们中的95%以上的人在一辈子的生涯中都没有机会去实现一个真正的复杂语言的编译器。但是每一个人都绝对遇到需要使用编译技术的项目。 以下就是一些小的“编译器”.,课 程 简 介,学习的意义,普通计算器,可编程计算器,课 程 简 介,学习的意义,自动聊天机器人,课 程 简 介,学习的意义,各种数据库查询语言及专家系统,select 课程 from table 课程表 where 任课老师=贾棋,课 程 简 介,学习的意义 在

5、计算机专业考研或者各大公司招聘时，必考内容。,在x86/Linux工作站上，以下两个结构的size分别是20和16，为什么不一样？ typedef struct _atypedef struct _b char c1; char c1; long i; charc2; charc2; long i; double f; double f; a; b;,vc结果vs Linux下gcc的结果,vc6中的编译选项有 /Zp1|2|4|8|16 ，/Zp1表示以1字节边界对齐，相应的，/Zpn表示以n字节边界对齐。n字节边界对齐的意思是说，一个成员的地址必须安排在成员的尺寸的整数倍地址上或者是n的整

6、数倍地址上，取它们中的最小值。 要使用这个选项，可以在vc6中打开工程属性页，c/c+页，选择Code Generation分类，在Struct member alignment可以选择。,第一章 引 论,翻译器：把一种语言变换到另外一种语言的软件。这两种语言分别称为源语言和目标语言。 编译器：一种翻译器，它的目标语言比源语言低级。,第一章 引 论,编译器,编译器从逻辑上可以分成若干阶段，每个阶段把源程序从一种表示变换成另一种表示,翻译家,第一章 引 论,FORTRAN (FORmula TRANslation) 第一个实用的高级语言 擅长于数学函数运算 常用于科学计算中 第一个编译器 历史上

7、第一个实用的编译器(John Backus)： Fortran compiler for the IBM 704/709/7090/7094 John Backus，引入了编译器的“阶段”或称为“遍”的概念，是编译设计的模块化的开始,编译器从逻辑上可以分成若干阶段 每个阶段把源程序从一种表示变换成另一种表示 本章通过描述编译器的各个阶段来介绍编译这个课题,第一章 引 论,词法分析：源程序 -词法记号（token）流,第一章 引 论,任何一个标识符都是表达式； 任何一个数都是表达式； 如果e1和e2都是表达式，那么 e1 + e2 e1 * e2 (e1) 也都是表达式,语法分析：词法记号（to

8、ken）流-语法短语,任何名词都可以作宾语； 如果e1和e2都是宾语，那么 e1 和e2 e1 与e2 也都可以作宾语 如果e1是定语， e2是宾语，那么e1 e2也可以作宾语。,第一章 引 论,语法分析器,id, 1 = id, 2 + id, 3 60,语法分析：词法记号（token）流-语法短语,名词1 动词 形容词 名词2,语法分析,第一章 引 论,语义分析：检查程序的语义正确性，如类型检查等,你们是优秀的大工学子,你们是一个优秀的大工学子。,第一章 引 论,第一章 引 论,中间代码生成器,temp1 := inttoreal(60) temp2 := id3 * temp1 temp

9、3 := id2 + temp2 id1 := temp3,英语文本生成,You are good DLUTers.,第一章 引 论,代码优化器,temp1 := inttoreal(60) temp2 := id3 * temp1 temp3 := id2 + temp2 id1 := temp3,temp1 := id3 * 60.0 id1 := id2 + temp1,You are good DLUTers.,英语文本改进,You are excellent DLUTers,第一章 引 论,日语文本生成,You are excellent DLUTers,君大連理工大学 優秀学生。,

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

11、效率 取一个编译器的前端，重写它的后端以产生同一源语言在另一机器上的编译器 不同的前端使用同一个后端，从而得到一个机器上的几个编译器（采用同一中间语言）,第一章 引 论,第一章 引 论,源程序,目标机器1,目标机器2,目标机器3,目标机器n,编译器,不区分前端和后端的编译器,源程序,目标机器1,目标机器2,目标机器3,目标机器n,编译器前端,编译器后端,区分前端和后端的编译器,第一章 引 论,遍,编译的几个阶段常用一遍（pass）扫描实现，一遍扫描包括读一个输入文件和写一个输出文件。,第一章 引 论,遍,类比：刷墙艺术中的“遍”的概念,网线,水泥,瓷砖,任务：在一面墙上布置网线，并粉刷水泥，然

12、后贴上瓷砖,第一章 引 论,遍,类比：刷墙艺术中的“遍”的概念,方法一：,第一遍：布上全部网线,网线,水泥,瓷砖,第一章 引 论,遍,类比：刷墙艺术中的“遍”的概念,方法一：,第二遍：粉刷全部墙面的水泥,网线,水泥,瓷砖,第一章 引 论,遍,类比：刷墙艺术中的“遍”的概念,方法一：,第三遍：给整个墙面贴上瓷砖,网线,水泥,瓷砖,第一章 引 论,遍,类比：刷墙艺术中的“遍”的概念,方法二：,一遍：一边布网线，一边粉刷水泥，一边贴瓷砖,网线,水泥,瓷砖,遍（趟）： 一遍或一趟：是指编译程序在编译时刻把源程序或源程序的等价物（中间程序）从头到尾扫描一遍并转换成另一紧邻的等价物的全过程。 单遍扫描与多

13、遍扫描：每一遍的扫视可完成上述一个阶段或多个阶段的工作。每一遍的输入都是上一遍的输出，第一遍的输入是源程序正文，最后一遍的输出是目标代码。 单遍与多遍的比较： 遍数多：编译器结构清晰，但时间效率不高 遍数少：编译速度快，但对机器的内存要求高 遍数的确定：主要因素是源程序和机器（目标机）的特征。,第一章 引 论,另一种实现形式,编译技术研究对象：编译器的构造与分析,BASIC年代的解释器 功能：它将高级语言的源程序翻译成一种中间语言程序，然后对中间语言程序进行解释执行 在那个年代，编译和解释两个功能是合在一个程序中，该程序被称为解释器 Java年代的解释器 解释器的上述两个功能分在两个程序中 前

14、一个叫做编译器，它把源程序翻译成一种叫做字节码的中间语言程序 后一个叫做解释器，它对字节码程序进行解释执行,编译器和解释器的区别,三种奶牛三种嗜好,编译器和解释器的区别,改进后的方案,编译器和解释器的区别,牧草 我们的各种编程语言，C/C+/C#, Java, Pascal, PHP, Perl, Java Script等切割机 各种编译器奶牛 各种CPU，比如x86，ARM，MIPS等奶牛会有吃不同形状牧草的嗜好，这个奇怪的比喻是为了表示不同的CPU接受的不同的机器语言。,编译器和解释器的区别,编译器与解释器的区别,编译器是把源程序的每一条语句都编译成机器语言,并保存成二进制文件,这样运行时

15、计算机可以直接以机器语言来运行此程序,速度很快; 而解释器则是只在执行程序时,才一条一条的解释成机器语言给计算机来执行,所以运行速度是不如编译后的程序运行的快的.,1.2 编译器技术的应用,高级语言的实现 高级编程语言易于编程，但程序运行较慢 低级语言编程时可实施更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护 流行编程语言的大多数演变都是朝着提高抽象级别的方向 每一轮编程语言新特征的出现都刺激编译器优化的新研究,编程语言演义,编程语言 机器语言 汇编语言 高级语言（Fortran, C, Java, ),编程语言演义,机器语言特点 0,1串 打卡输入 c7 06 0000 000

16、2 mov x, c 其中符号x的地址是0000，c=2 计算机可以直接理解机器语言程序 机器语言缺点 可读性差 可维护性差,机器语言 汇编语言 高级语言,编程语言演义,汇编语言形式 mov x,2 c7 06 0000 0002 变量x的地址可以由汇编器维护，而不需要固定到某个绝对地址,机器语言 汇编语言 高级语言,编程语言演义,高级语言形式 赋值语句：x=2 贴近人类思维方式，贴近实际问题描述形式 计算机无法直接理解 需要编译器辅助，将其转换为机器语言形式,机器语言 汇编语言 高级语言,1.2 编译器技术的应用,高级语言的实现 每一轮编程语言新特征的出现都刺激编译器优 化的新研究 支持用户

17、定义的聚合数据类型和高级控制流，如数组和记录、循环和过程调用：C、Fortran 面向对象的主要概念是数据抽象和性质继承，使得程序更加模块化并易于维护：Smalltalk、C+、C#、Java 类型安全的语言：Java没有指针，也不允许指针算术。它用无用单元收集机制来自动地释放那些不再使用的变量占据的内存,1.2 编译器技术的应用,针对计算机体系结构的优化 计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要 并行化 编译器重新整理指令，使得指令级并行更有效 编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上 内存分层 编译器优化历来集中在优化处理器的执行上，但是现在更强调要使内存分层更有效,1.2 编译器技术的应用,新计算机体系结构的设计 现在计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利用其特征的代码 在现代计算机体系结构的研究中，在处理器的设计阶段就开发编译器，并将编译生成的代码在模拟器上运行，以评价拟采用体系结构的特征 编译器技术影响计算机体系结构设计的一个著名例子是精简指令集计算机（RISC）的发明,1.2 编译器技术的应用,程序翻译 二进制翻译 编译器技术可用于把一种机器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令集编译的代码 数据库查询解释器 数据库查询由