第01讲-编译原理-课程简介

1、编译原理编译原理 Principles of Compiling 大连理工大学软件学院大连理工大学软件学院 2021-7-12 2 2021-7-12 3 2021-7-12 4 词法分析词法分析语法分析语法分析语义语义分析分析 中间代码生成中间代码生成 5 编译原理课程在计算机科学技术中的地位：编译原理课程在计算机科学技术中的地位： 程序设计语程序设计语 言言 离散数学离散数学 数据结构数据结构 编译原理编译原理 操作系统操作系统 系统软件系统软件 应用软件应用软件 软件工程软件工程 信息系统信息系统 电子商务电子商务 6 v编译理论与方法编译理论与方法 计算机科学与技术中理论和实践相结合计

2、算机科学与技术中理论和实践相结合 的的最好典范最好典范 ACM ACM 图灵奖，授予在计算机技术领域作出图灵奖，授予在计算机技术领域作出 突出贡献的科学家突出贡献的科学家 程序设计语言、编译理论与方法约占程序设计语言、编译理论与方法约占1/31/3 7 v课程内容课程内容 介绍编译器构造的一般原理和基本实现方法介绍编译器构造的一般原理和基本实现方法 介绍的理论知识：形式语言和自动机理论、语介绍的理论知识：形式语言和自动机理论、语 法制导的定义和属性文法、类型论等法制导的定义和属性文法、类型论等 v课程特点课程特点 强调强调形式化描述技术形式化描述技术 强调对编译原理和技术的强调对编译原理和技术

3、的宏观理解宏观理解，不把注意，不把注意 力分散到枝节算法，不偏向于某种源语言或目力分散到枝节算法，不偏向于某种源语言或目 标机器标机器 8 v学习的意义学习的意义 计算机专业的核心课程。计算机专业的核心课程。 深刻的理解编程语言的设计和实现，有深刻的理解编程语言的设计和实现，有 利于学习编程语言，知其然知其所以然。利于学习编程语言，知其然知其所以然。 9 v学习的意义学习的意义 从软件工程看，编译器是一个很好的实例（基从软件工程看，编译器是一个很好的实例（基 本设计、模块划分等），本设计、模块划分等）， 所介绍的概念和技所介绍的概念和技 术能应用到一般的软件设计之中。术能应用到一般的软件设计之

4、中。 编译器也许是在本科阶段分析最透彻的实例。编译器也许是在本科阶段分析最透彻的实例。 能了解到软件工程中的一些技术（如基于事件能了解到软件工程中的一些技术（如基于事件 驱动的编程）。驱动的编程）。 大多数程序员同时是语言的设计者，虽然是一 些简单的语言（如输入输出），本课程的学习 有助于提高对这些语言的设计水平。 10 v学习的意义学习的意义 可以肯定地说，你们中的可以肯定地说，你们中的95%95%以上的人在以上的人在 一辈子的生涯中都没有机会去实现一个一辈子的生涯中都没有机会去实现一个 真正的复杂语言的编译器。但是每一个真正的复杂语言的编译器。但是每一个 人都绝对遇到需要使用编译技术的项目

5、。人都绝对遇到需要使用编译技术的项目。 以下就是一些小的以下就是一些小的“编译器编译器”. . 11 v学习的意义学习的意义 12 自动聊天机器人自动聊天机器人 13 14 本讲纲要本讲纲要 v课程简介课程简介 v编译技术概述编译技术概述 15 虚拟机虚拟机 16 vBASICBASIC年代的解释器年代的解释器 功能：它将高级语言的源程序翻译成一种中间功能：它将高级语言的源程序翻译成一种中间 语言程序，然后对中间语言程序进行解释执行语言程序，然后对中间语言程序进行解释执行 在那个年代，编译和解释两个功能是合在一个在那个年代，编译和解释两个功能是合在一个 程序中，该程序被称为解释器程序中，该程序

6、被称为解释器 vJavaJava年代的解释器年代的解释器 解释器的上述两个功能分在两个程序中解释器的上述两个功能分在两个程序中 前一个叫做前一个叫做编译器编译器，它把源程序翻译成一种叫，它把源程序翻译成一种叫 做字节码的中间语言程序做字节码的中间语言程序 后一个叫做后一个叫做解释器解释器，它对字节码程序进行解释，它对字节码程序进行解释 执行执行 17 18 编程语言演义编程语言演义 v编程语言编程语言 机器语言机器语言 汇编语言汇编语言 高级语言（高级语言（Fortran, C, Java, )Fortran, C, Java, ) 19 编程语言演义编程语言演义 v机器语言特点机器语言特点

7、0,10,1串串 打卡输入打卡输入 c7 06 0000 0002 c7 06 0000 0002 mov x, c mov x, c 其中符号其中符号x x的地址是的地址是00000000， c=2c=2 v计算机可以直接理解机器语言程计算机可以直接理解机器语言程 序序 v机器语言缺点机器语言缺点 可读性差可读性差 可维护性差可维护性差 20 编程语言演义编程语言演义 v汇编语言形式汇编语言形式 mov x,2mov x,2 c7 06 0000 0002 c7 06 0000 0002 v变量变量x x的地址可以由汇编器维护，的地址可以由汇编器维护， 而不需要固定到某个绝对地址而不需要固定

8、到某个绝对地址 21 编程语言演义编程语言演义 v高级语言形式高级语言形式 赋值语句：赋值语句：x=2x=2 v贴近人类思维方式，贴近实际问贴近人类思维方式，贴近实际问 题描述形式题描述形式 计算机无法直接理解计算机无法直接理解 需要编译器辅助，将其转换为机器需要编译器辅助，将其转换为机器 语言形式语言形式 22 v 完成从源语言到目标语言的转换完成从源语言到目标语言的转换 源语言：通常是高级语言（源语言：通常是高级语言（C,Java,C,Java,） 目标语言：汇编语言，或者其他形式的目标语言：汇编语言，或者其他形式的 低级语言（如低级语言（如JavaJava字节码）字节码） v编译器实现技

9、术已经发展成熟，并且编译器实现技术已经发展成熟，并且 划分为功能相对明确的多个功能模块划分为功能相对明确的多个功能模块 23 24 v FORTRAN (FORmula TRANslation) FORTRAN (FORmula TRANslation) 第一个实用的高级语言第一个实用的高级语言 擅长于数学函数运算擅长于数学函数运算 常用于科学计算中常用于科学计算中 v 第一个编译器第一个编译器 历史上第一个实用的编译器历史上第一个实用的编译器(John Backus)(John Backus)： Fortran compiler for the IBM 704/709/7090/7094 J

10、ohn BackusJohn Backus，引入了编译器的，引入了编译器的“阶段阶段”或称或称 为为“遍遍”的概念，是编译设计的模块化的开始的概念，是编译设计的模块化的开始 25 26 27 28 29 30 31 v遍（趟）：遍（趟）： 一遍或或一趟：是指编译程序在编译时刻把源程序或源程序的是指编译程序在编译时刻把源程序或源程序的 等价物（中间程序）从头到尾扫描一遍并转换成另一紧邻的等等价物（中间程序）从头到尾扫描一遍并转换成另一紧邻的等 价物的全过程。价物的全过程。 单遍扫描与多遍扫描：每一遍的扫视可完成上述一个阶段每一遍的扫视可完成上述一个阶段 或多个阶段的工作。每一遍的输入都是上一遍的

11、输出，第一遍或多个阶段的工作。每一遍的输入都是上一遍的输出，第一遍 的输入是源程序正文，最后一遍的输出是目标代码。的输入是源程序正文，最后一遍的输出是目标代码。 单遍与多遍的比较： 遍数多：编译器结构清晰，但时间效率不高遍数多：编译器结构清晰，但时间效率不高 遍数少：编译速度快，但对机器的内存要求高遍数少：编译速度快，但对机器的内存要求高 遍数的确定：主要因素是源程序和机器（目标机）的特征。主要因素是源程序和机器（目标机）的特征。 32 词法分析器词法分析器 id, 1 = id, 2 + id, 3 60 position = initial + rate 60 33 34 id, 1 =

12、id, 2 + id, 3 60 35 36 37 38 39 40 词法分析器词法分析器 语法分析器语法分析器 语义分析器语义分析器 源程序源程序 中间代码生成器中间代码生成器 代码优化器代码优化器 代码生成器代码生成器 目标程序目标程序 出错管理器出错管理器符号表管理器符号表管理器 后三个阶后三个阶 段对源程段对源程 序进行综序进行综 合合 41 词法分析器词法分析器 语法分析器语法分析器 语义分析器语义分析器 源程序源程序 中间代码生成器中间代码生成器 代码优化器代码优化器 代码生成器代码生成器 目标程序目标程序 出错管理器出错管理器符号表管理器符号表管理器 42 43 v前端和后端：前

13、端和后端： 把编译过程分成前端和后端两部分把编译过程分成前端和后端两部分 前端前端：只依赖于源程序，独立于目标机器只依赖于源程序，独立于目标机器 （生成中间代码）（生成中间代码） 后端后端：依赖于目标机器，与源程序无关，只与中间语言：依赖于目标机器，与源程序无关，只与中间语言 有关（从中间代码生成目标代码）有关（从中间代码生成目标代码） 好处好处：提高开发编译器的效率提高开发编译器的效率 取一个编译器的前端，重写它的后端以产生同一源语言在另一取一个编译器的前端，重写它的后端以产生同一源语言在另一 机器上的编译器机器上的编译器 不同的前端使用同一个后端，从而得到一个机器上的几个编译不同的前端使用

14、同一个后端，从而得到一个机器上的几个编译 器（采用同一中间语言）器（采用同一中间语言） 44 45 v高级语言的实现 高级编程语言易于编程，但程序运行较慢 低级语言编程时可实施更有效的控制方式， 得到更有效的代码，但难编写、易出错、 难维护 流行编程语言的大多数演变都是朝着提高 抽象级别的方向 每一轮编程语言新特征的出现都刺激编译 器优化的新研究 1.2 编译器技术的应用 46 v程序翻译 二进制翻译 编译器技术可用于把一种机器的二 进制代码翻译成另一种机器的代码，以运 行原先为别的指令集编译的代码 数据库查询解释器 数据库查询由一些谓词组成，这些谓词 由包含关系运算的布尔表达式组成，可以 被

15、解释执行,也可以被编译成搜索数据库 的命令 1.2 编译器技术的应用 47 v 提高软件开发效率的工具 源于编译器中代码优化技术的程序分析一直在改 进软件开发效率 类型检查 类型检查是一种捕捉程序中前后不一致的成熟 而有效的技术 边界检查 数据流分析技术可用来定位缓冲区溢出 内存管理 自动的内存管理删除内存泄漏等内存管理错误 1.2 编译器技术的应用 48 语法制导的结构化编辑器语法制导的结构化编辑器 程序格式化工具程序格式化工具 软件测试工具软件测试工具 程序理解工具程序理解工具 高级语言的翻译工具高级语言的翻译工具 等等。等等。 编译技术的应用编译技术的应用 49 本讲纲要本讲纲要 v课程

16、简介课程简介 v编译技术概述编译技术概述 50 51 Compilers: Principles, Techniques, and Compilers: Principles, Techniques, and Tools Tools http:// “./ “龙书龙书”。 龙书是于龙书是于19861986年出版第一版，年出版第一版，20062006年出版第二版年出版第二版 由于出版年代较早，其中包含部分过时的技术并且由于出版年代较早，其中包含部分过时的技术并且 没有反映一些新的编译技术。没有反

17、映一些新的编译技术。 新版的新版的编译原理编译原理抛弃诸如算符优先分析等过时抛弃诸如算符优先分析等过时 技术，增加面向对象编译、类型检查等新技术。技术，增加面向对象编译、类型检查等新技术。 52 现代编译原理现代编译原理-C-C语言描述语言描述 / Modern Compiler / Modern Compiler Implementation in C Implementation in C （美）安佩尔（美）安佩尔 / 2006-4-1 / / 2006-4-1 / 人民邮电出版社人民邮电出版社 / C/ C 语言描述语言描述 / 45.0 / / 45.0 / 平装平装 / / 沈志宇沈

18、志宇 / / 黄春黄春 / / 赵克赵克 佳佳 “虎书虎书”。 虎书出版比较晚，与虎书出版比较晚，与编译原理编译原理的知识点差不多，的知识点差不多， 但增加了数据流分析、循环优化、内存管理等内容。但增加了数据流分析、循环优化、内存管理等内容。 与虎书比，与虎书比，编译原理编译原理更适合国内的编译原理课更适合国内的编译原理课 程教学。程教学。 本书包括本书包括C C版，还有版，还有javajava版和版和MLML版版 53 高级编译器设计与实现高级编译器设计与实现 / Advanced Compiler / Advanced Compiler Design and Implementation Design and Implementation （美）马其尼克（美）马其尼克 / 2005-7-1 / / 2005-7-1 / 机械工业出版机械工业出版 社社 / 75.0 / / 75.0 / 平装平装 / / 沈志宇沈志宇 / / 赵克佳赵克佳 “鲸书鲸书”。 鲸书侧重在对编译器后端优化的处理。鲸书侧重在对编译器后端优化的处理。 在本科阶段的