编译原理

课 程 简 介 课程内容 介绍编译器构造的一般原理和基本实现方法 介绍的理论知识：形式语言和自动机理论、语法制导的翻译、属性文法等 强调形式化描述技术 强调对编译原理和技术的宏观理解 1．本课程介绍编译器构造的一般原理和基本实现方法，主要介绍编译器的各个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。反映直至20世纪末的一些重要成果，如有关类型制导的编译思想。 2．本课程在介绍命令式程序设计语言实现技术的同时，强调一些相关的理论知识，如形式语言和自动机理论、语法制导的定义和属性文法、类型论等。它们是计算机专业理论知识的重要一部分，在本书中结合应用来介绍这些知识，有助于学生较快领会和掌握。 3．本课程强调形式化描述技术，并以语法制导定义作为翻译的主要描述工具。 4．本课程强调对编译原理和技术在宏观上的理解，而不把读者的注意力分散到一些枝节的算法上，如计算开始符号集合和后继符号集合的算法，回填技术等。作为原理性的教材，本书介绍基本的理论和方法，而不偏向于某种源语言或目标机器。

课 程 简 介 学习的意义 对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用。 从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中。 成熟的理论，广泛的应用，深刻的影响。 虽然只有少数人从事构造或维护程序设计语言的编译器，但是本课程对本科生来说是一门重要课程。 1．本课程能使学生对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论（形式语言和自动机理论、类型论等）有所了解，对宏观上把握编程语言来说，起一个奠基的作用。 2．对软件工程来说，编译器是一个很好的实例（基本设计、模块划分等），也是本科期间能碰到的唯一的大型例子，学生从本课程的学习也能了解到软件工程中的一些技术（如基于事件驱动的编程）。本课程所介绍的概念和技术能应用到一般的软件设计之中。 3．大多数程序员同时是语言的设计者，虽然是一些简单的语言（如输入输出），本课程的学习有助于提高对这些语言的设计水平。 4．编译技术在软件逆向工程、程序理解和软件安全等方面有着广泛的应用 软件逆向工程：以另外一种形式创建系统同一层次的表示或者更高层次的抽象， 应用：技术仿造、软件维护。 程序理解：通过分析、抽象和一般化来获取软件知识的演绎过程。（1）基于机器代码和中间代码层的理解，需要借助于反汇编和反编译技术；（2）基于源代码的理解；（3）基于语法层的理解，程序分段、程序切片和程序分析等技术就是其中的最典型代表；（4）基于程序语义层的理解，模式匹配、格局识别(plan recognition)、概念赋值（concept assigned）和概念分析(concept analysis)等都是进行语义级的软件理解和分析技术。 软件安全：满足安全策略。基本安全策略：类性安全、控制流安全和内存安全。还有信息流安全。用到词法、语法和语义分析、类性系统和类性检查、控制流分析和数据流分析等。编译器将走向类型制导的编译器。 美国的名牌大学：都有编程语言和编译器方面的课程，80%有这方面的研究。国内对这方面的人才需求将增加。

课 程 简 介 教材和参考书： （1）陈火旺，编译原理，国防工业出版社 （2）A. Aho, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools 人民邮电出版社

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

1.1 什么叫编译程序 编译器(编译程序):compiler 能将一种计算机高级语言程序(源语言程序)转换成另一种等价的计算机低级语言程序(目标语言程序)

解释器(解释程序):interpreter 也是一种翻译程序,以一种语言写的源程序作为输入,但不产生目标代码,而是边解释边执行。 解释器与编译器的区别: 编译分成两步完成：先翻译，再运行 解释只用一步完成：边解释边执行

可变目标编译程序(Retargetable Compiler) 交叉编译程序(Cross Compiler)

英译与编译的比较 1 识别出句子中的一个个单字 2 分析句子的语法结构 3 初步翻译句子的含意 4 译文修饰 5 写出最后译文

1.2 编译程序的组成 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器

一 词法分析过程 for i=1 to 100 do 词法分析器 符号序列 符 号 表 保留字 标识符 赋值号 for . . i. 一 词法分析过程 词法分析器 符号序列 for i=1 to 100 do 符 号 表 保留字 标识符 赋值号 for . . i. . =. . 1 2 3

二 语法分析过程 1。2。2语法分析 语法分析的任务：在词法分析的基础上，根据语言的语法规则，把单词符号分解成各类语法单位（语法范畴），如“短语”、“句子”、 “子句”、“程序段”等。 语法规则通常用上下文无关文法描述。 先介绍语法，然后才介绍语法分析。

1.2.3语义分析与中间代码的产生 这一阶段通常包括两方面的工作首先对各种语法范畴进行静态语义检查，如果正确则进行另一方面的工作，即进行中间代码的翻译。 通常使用属性文法描述语义规则 所谓“中间代码”是一种含义明确，便于处理的记号系统。 中间代码除四元式外，还有三元式、间接三元式、逆波兰记号、树形表示等。

中间代码 temp1=c*d temp2=b+temp1 a=temp2 (* , c , d , tempt1) a=b+c*d temp1=c*d temp2=b+temp1 a=temp2 (* , c , d , tempt1) (+ , b, tempt1 ,tempt2) (= , tempt2 , , a)

前三个阶段的作用 前三个阶段完成对源程序的分析 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器 前三个阶段完成对源程序的分析

1.2.4 优化 优化的任务在于对前段产生的中间代码进行加工，以期在最后阶段产生更为高效（省时间和空间）的代码 优化所依循的原则是程序的等价变换规则 其方法有：公共子表达式的提取、循环优化、删除无用代码等。

六 目标代码的产生过程 代码生成器 temp1 := id3 * 60.0 id1 := id2 * temp1 MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1

后三个阶段的作用 后三个阶段对源程序进行综合 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器 后三个阶段对源程序进行综合

词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器

前端 后端 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器

前端 后端 遍 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 代码优化器 代码生成器 目标程序 出错管理器 符号表管理器

如何学习构造编译程序 源语言,对被编译的源程序要深刻理解其结构和含义 目标语言,假定目标语言是机器语言,就必须搞清楚硬件的系统结构和操作系统的功能 编译方法,把一种语言翻译成另一种语言的方法很多,课程重点 本章作业：画出编译程序结构图，说明各部分功能