Microsoft PowerPoint - ch1.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - ch1.ppt [兼容模式]"

浇国
6 years ago
Views:

1 编译原理和技术中国科学技术大学计算机科学与技术学院张昱

2 致谢本系列讲稿是在陈意云教授撰写的编译原理和技术讲稿之上完成, 特此感谢陈老师!

3 课程简介课程内容介绍编译器构造的一般原理和基本实现方法包括的理论知识 : 形式语言和自动机理论语法制导的定义和属性文法类型论与类型系统程序分析原理, 等等强调形式描述技术和自动生成技术强调对编译原理和技术的宏观理解, 不把注意力分散到枝节算法, 不偏向于任何源语言或目标机器

4 课程简介学习意义深刻理解 : 编程语言的设计和实现了解 : 和编程语言有关的理论编译器是软件工程的一个很好的实例编译技术的应用和编译技术的发展高级语言设计计算机体系结构的优化 ( 并行内存分层 )) 新型计算机体系结构设计 (GPU + CPU ) 程序翻译提高软件开发效率的工具高可信软件

5 课程简介教材和参考书陈意云张昱, 编译原理, 高等教育出版社, 2008 A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools,2nd edition, Addison-Wesley, 2007 陈意云张昱, 编译原理习题精选与解析, 高等教育出版社,2005 教学资源网页 : cn/~yiyun

6 课程简介课程要求质量上的目标 : 师生共同努力, 达国内最好水平讲课进展较快, 平时需预习和复习以加深理解作业 : 周一课间交作业课程设计 : 基础 + 扩展 + 自由发挥考试 (2 次 ): 开卷, 灵活运用知识学期总评 = 考试成绩占 40% + 作业占 10% + 课程设计 50%

7 课程简介课程设计要求基础 : 阅读 PL/0 编译器源码, 写对应的 C 子集 C0 编译器与课堂衔接, 循序渐进, 课堂抽查扩展 : 独立地研发 C0 扩展语言的编译器和解释器目标 : 巩固对理论和技术的理解, 提高程序设计能力技术准备 :Linux +GCC 编程环境,C 语言编程考查方式 : 课堂抽查, 多次提交检查, 集中评测 2006~2010 年课程设计的经验和教训对该课程设计的综合性认识不足对考查的动真格认识不足

8 第一章引论名词解释翻译器 (translator) 编译器(compiler) 解释器 (interpreter) 编译器从逻辑上可以分成若干个阶段每个阶段把源程序从一种表示变换成另一种表示本章通过描述编译器的各个阶段来介绍编译这个课题

9 1.1 编译器概述源程序符号表词法分析器语法分析器语义分析器中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码

10 1.1 编译器概述 position = initial + rate 60 字符流符号表 1 position... 词法分析器 2 3 initial rate id, 1 = id, 2 + id, 3 60 记号流

11 1.1 编译器概述表达式的语法特征任何一个标识符都是表达式任何一个数都是表达式如果 e 1 和 e 2 都是表达式, 那么 e 1 + e 2 e 1 * e 2 (e 1 ) 也都是表达式表达式表达式 + 表达式标识符表达式 * 表达式 (initial) 标识符数 (rate) (60) initial + rate * 60 的分析树

12 1.1 编译器概述 id, 1 = id, 2 + id, 3 60 记号流符号表 1 position... 语法分析器 2 initial... 3 rate... = id, 1 + id, 2 id, 3 60 语法树

13 id, 1 id, 1 = + id, 2 id, 编译器概述语义分析器 = + id, 2 id, 3 60 语法树语法树 inttofloat 60 符号表 position... initial... rate...

14 1.1 编译器概述 = id,, 1 + 语法树 id, 2 符号表 id, 3 inttofloat 1 position initial... 中间代码生成器 3 rate... t1 = inttofloat(60) t2 = id3 t1 t3=id2+t2 t2 id1 = t3 三地址中间代码

15 1.1 编译器概述 t1 = inttofloat(60) t2 = id3 t1 t3 = id2 + t2 id1 = t3 代码优化器三地址中间代码符号表 1 position... 2 initial... 3 rate... t1 = id3 * 60.0 id1 = id2 + t1 三地址中间代码

16 1.1 编译器概述 t1 = id3 * 60.0 id1 = id2 + t1 代码生成器 MOVF id3, R2 MULF #60.0, 0 R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 三地址中间代码符号表 1 position... 2 initial... 3 rate... 汇编代码

17 解释器和编译器的区别 1.1 编译器概述源程序词法分析器语法分析器语义分析器中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码

18 解释器和编译器的区别解释器不生成目标代源程序码, 而是直接执行源程序所指定的运算词法分析器 1.1 编译器概述语法分析器语义分析器中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码

19 解释器和编译器的区别解释器不生成目标代源程序码, 而是直接执行源程序所指定的运算词法分析器 1.1 编译器概述解释器也需要对源程序进行词法语法和语义分析, 中间代码生成语法分析器语义分析器中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码

20 1.1 编译器概述 BASIC,Perl 解释器功能 : 它将高级语言的源程序翻译成一种中间语言程序, 然后对中间语言程序进行解释执行编译和解释两个功能是合在一个程序中, 该程序被称为解释器 Java 解释器编译和解释分在两个程序中前一个叫做编译器, 它把源程序翻译成一种叫做字节码的中间语言程序后一个叫做解释器, 它对字节码程序进行解释执行

21 1.1 编译器概述 Java 的主流编译运行方式 Java 编译器 :Java 源程序翻译成 Java 字节码 Java 虚拟机 : 对 Java 字节码进行即时编译 (Just- in-time Compiling) 流水线编译架构对当前要运行的 method 进行 : 1 ) 若存在目标代码且无须进一步的优化, 则执行该目标代码 2) 否则, 编译优化 -> > 生成目标代码 -> > 执行

22 源程序词法分析器 1.1 编译器概述阶段分组前端后端语法分析器语义分析器中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码

23 源程序 1.1 编译器概述阶段分组遍词法分析器语法分析器语义分析器中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器目标机器代码

24 1.2 编译器技术的应用高级语言的实现高级编程语言易于编程, 但程序运行较慢低级语言编程时可实施更有效的控制方式, 得到更有效的代码, 但难编写易出错难维护流行编程语言的大多数演变都是朝着提高抽象级别的方向每一轮编程语言新特征的出现都刺激编译器优化每轮编程语言新特征的出现都刺激编译器优化的新研究

25 1.2 编译器技术的应用高级语言的实现每一轮编程语言新特征的出现都刺激编译器优化的新研究支持用户定义的聚合数据类型和高级控制流, 如数组和记录循环和过程调用 :C Fortran 面向对象的主要概念是数据抽象和性质继承, 使得程序更加模块化并易于维护 :Smalltalk C++ C# Java 类型安全的语言 :Java 没有指针, 也不允许指针算术它用无用单元收集机制来自动地释放那些不再使用的变量占据的内存 Java 设计来支持代码移植和代码移动

26 1.2 编译器技术的应用针对计算机体系结构的优化计算机体系结构的迅速演化需要新的编译器技术并行化编译器重新整理指令, 使得指令级并行更有效编译器从传统的串行程序自动生成并行代码, 使之运行于多处理器上内存分层编译器优化历来集中在优化处理器的执行上, 但是现在更强调要使内存分层更有效

27 1.2 编译器技术的应用新计算机体系结构的设计计算机系统的性能不仅仅取决于它的原始速度, 还取决于编译器能否生成充分利用其特征的代码在现代计算机体系结构的研究中, 在处理器的设计阶段就开发编译器, 并将编译生成的代码在模拟器上运行, 以评价拟采用体系结构的特征编译器技术影响计算机体系结构设计的一个著名例子是精简指令集计算机 (RISC) 的发明最近 : 图形处理器 GPU+CPU 结合的异构结构 CUDA 语言处理图形处理器上的运算

28 1.2 编译器技术的应用程序翻译二进制翻译把一种机器的二进制代码翻译成另一种机器的代码, 以运行原先为别的指令集编译的代码数据库查询解释器数据库查询由一些谓词组成, 这些谓词由包含关系运算的布尔表达式组成, 可以被解释执行, 也可以被编译成搜索数据库的命令

29 1.2 编译器技术的应用提高软件开发效率的工具源于编译器中代码优化技术的程序分析一直在改进软件开发效率类型检查类型检查是一种捕捉程序中前后不一致的成熟而有效的技术边界检查数据流分析技术可用来定位缓冲区溢出内存管理自动的内存管理删除内存泄漏等内存管理错误

<4D F736F F F696E74202D20B5DA31D5C220D2FDC2DB2E BD6BBB6C15D205BBCE6C8DDC4A3CABD5D>

<4D F736F F F696E74202D20B5DA31D5C220D2FDC2DB2E BD6BBB6C15D205BBCE6C8DDC4A3CABD5D> 编译原理与技术中国科学技术大学计算机科学与技术学院张昱陈意云 0551-3603804, 3607043 yuzhang, yiyun@ustc.edu.cn cn 课程简介课程内容介绍编译器构造的一般原理和基本实现方法包括的理论知识 : 形式语言和自动机理论语法制导的定义等课程特点强调对编译原理和技术的宏观理解, 不把注意力引导到理论和一些枝节算法上不偏向于任何源语言或目标机器