编译原理和技术1

编译原理和技术计算机科学技术系课程简介课程内容–介绍编译器构造的一般原理和基本实现方法–介绍的理论知识：形式语言和自动机理论、语法制导的定义和属性文法、类型论、程序分析原理等–强调形式描述技术和自动生成技术–强调对编译原理和技术的宏观理解，不把注意力分散到枝节算法，不偏向于任何源语言或目标机器课程简介学习的意义–对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用–从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中–编译技术的应用和编译技术的发展高级语言设计、计算机系统结构的优化（并行、内存分层）、新型计算机系统结构设计、程序翻译、提高软件开发效率的工具、高可信软件课程简介课程要求–目标：师生共同努力，达国内最好水平–讲课进展较快，平时不复习并加深理解，后面将听不懂–作业：少而精，周一课间交作业–课程设计：自己动手，丰产丰收–考试：开卷，灵活运用知识–学期总评=考试成绩占50%，作业占10%，课程设计40%–上课、设计、考试时间安排课程简介课程设计要求–内容：合作构造某简单语言的编译器–目标：巩固对理论和技术的理解，提高程序设计能力–技术准备：面向对象编程、Java语言及编程环境、Linux的用户界面–考查与评分：对截止时间前提交的程序，通过测试和答辩进行公开评分–大约在第四周提供课程设计指导教材第一章引论•翻译器(translator)、编译器(compiler)、解释器(interpreter)•编译器从逻辑上可以分成若干阶段•每个阶段把源程序从一种表示变换成另一种表示•本章通过描述编译器的各个阶段来介绍编译这个课题1.1编译器概述词法分析器语法分析器语义分析器源程序中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码符号表符号表positioninitialrate.........123词法分析器id,1=id,2+id,360position=initial+rate601.1编译器概述1.1编译器概述表达式的语法特征•任何一个标识符都是表达式•任何一个数都是表达式•如果e1和e2都是表达式，那么e1+e2e1*e2(e1)也都是表达式表达式表达式表达式标识符表达式表达式(initial)标识符(rate)数(60)*+initial+rate*60的分析树符号表positioninitialrate.........123语法分析器id,1=id,2+id,360=+60id,1id,2id,3语法树1.1编译器概述符号表positioninitialrate.........1231.1编译器概述语义分析器=+60id,1id,2id,3=+inttorealid,1id,2id,360符号表positioninitialrate.........123中间代码生成器t1=inttoreal(60)t2=id3t1t3=id2+t2id1=t3=+inttorealid,1id,2id,3601.1编译器概述符号表positioninitialrate.........123代码优化器t1=inttoreal(60)t2=id3t1t3=id2+t2id1=t3t1=id3*60.0id1=id2+t11.1编译器概述符号表positioninitialrate.........123代码生成器MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1t1=id3*60.0id1=id2+t11.1编译器概述1.1编译器概述解释器和编译器的区别词法分析器语法分析器语义分析器源程序中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码1.1编译器概述解释器和编译器的区别词法分析器语法分析器语义分析器源程序中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码解释器不生成目标代码，而是直接执行源程序所指定的运算1.1编译器概述解释器和编译器的区别词法分析器语法分析器语义分析器源程序中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码解释器不生成目标代码，而是直接执行源程序所指定的运算解释器也需要对源程序进行词法,语法和语义分析,中间代码生成1.1编译器概述•BASIC年代的解释器–功能：它将高级语言的源程序翻译成一种中间语言程序，然后对中间语言程序进行解释执行–在那个年代，编译和解释两个功能是合在一个程序中，该程序被称为解释器•Java年代的解释器–解释器的上述两个功能分在两个程序中–前一个叫做编译器，它把源程序翻译成一种叫做字节码的中间语言程序–后一个叫做解释器，它对字节码程序进行解释执行1.1编译器概述阶段分组•前端•后端词法分析器语法分析器语义分析器源程序中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码1.1编译器概述词法分析器语法分析器语义分析器源程序中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码阶段分组•遍1.2编译器技术的应用•高级语言的实现–高级编程语言易于编程，但程序运行较慢–低级语言编程时可实施更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护–流行编程语言的大多数演变都是朝着提高抽象级别的方向–每一轮编程语言新特征的出现都刺激编译器优化的新研究1.2编译器技术的应用•高级语言的实现每一轮编程语言新特征的出现都刺激编译器优化的新研究–支持用户定义的聚合数据类型和高级控制流，如数组和记录、循环和过程调用：C、Fortran–面向对象的主要概念是数据抽象和性质继承，使得程序更加模块化并易于维护：Smalltalk、C++、C#、Java–类型安全的语言：Java没有指针，也不允许指针算术。它用无用单元收集机制来自动地释放那些不再使用的变量占据的内存–Java设计来支持代码移植和代码移动1.2编译器技术的应用•针对计算机体系结构的优化–计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要–并行化编译器重新整理指令，使得指令级并行更有效编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上–内存分层编译器优化历来集中在优化处理器的执行上，但是现在更强调要使内存分层更有效1.2编译器技术的应用•新计算机体系结构的设计–现在计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利用其特征的代码–在现代计算机体系结构的研究中，在处理器的设计阶段就开发编译器，并将编译生成的代码在模拟器上运行，以评价拟采用体系结构的特征–编译器技术影响计算机体系结构设计的一个著名例子是精简指令集计算机（RISC）的发明1.2编译器技术的应用•程序翻译–二进制翻译编译器技术可用于把一种机器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令集编译的代码–数据库查询解释器数据库查询由一些谓词组成，这些谓词由包含关系运算的布尔表达式组成，可以被解释执行,也可以被编译成搜索数据库的命令1.2编译器技术的应用•提高软件开发效率的工具源于编译器中代码优化技术的程序分析一直在改进软件开发效率–类型检查类型检查是一种捕捉程序中前后不一致的成熟而有效的技术–边界检查数据流分析技术可用来定位缓冲区溢出–内存管理自动的内存管理删除内存泄漏等内存管理错误