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

编译器的作用与重要性
01
编译器是将高级语言程序翻译成机器语言程序的软件工具，是 软件开发的基础设施之一。
02
编译器可以提高程序的执行效率，使得程序能够在各种计算机
上运行。
编译器还可以对程序进行优化，提程简介
01
02
03
词法分析
将输入的源程序分解成一 个个的单词符号，即词法 单元。
词法分析器的构造
构造原理
根据词法规则构造出识别相应单 词符号的有限自动机，然后将有 限自动机转换为对应的程序代码
构造方法
手工构造法、自动生成法
注意事项
处理好单词符号的二义性问题； 识别出源程序中的错误并进行适 当的处理。
04
语法分析
语法分析概述
语法分析的任务
根据语言的语法规则，对输 入的符号序列进行合法性检 查，并构造出相应的语法结
中间代码的形式
常见的中间代码形式有三地址码、四元式、树形表示等。
中间代码生成算法
根据源程序的语法结构和语义规则，生成相应的中间代码序列。
符号表管理
符号表的作用
符号表用于记录源程序中各种标识符的属性信息，如类型、作用域 和存储地址等。
符号表的组织方式
常见的符号表组织方式有线性表、散列表和树形结构等。
循环优化
通过循环展开、循环合并、循环交换等技术来改进循环的性能。
目标代码生成方法
机器无关代码生成
机器相关代码生成
生成与特定机器无关的中间代码，然后在 运行时将其转换为特定机器上的目标代码 。
直接生成特定机器上的目标代码，这需要 考虑机器的指令集、寄存器分配、内存访 问等因素。
汇编语言代码生成
高级语言虚拟机代码生成

编译原理的重要性
01
02
03
编译原理是计算机科学领域中非 常重要的一门课程，它不仅在理 论上有很高的价值，而且在实践 中也有广泛的应用。
通过学习编译原理，可以深入理 解计算机如何处理和执行程序， 提高对计算机系统的整体认识。
此外，编译原理在编译器设计、 软件工程、系统软件开发等方面 也有着广泛的应用，对于从事这 些领域的人员来说，掌握编译原 理是非常必要的。
类型安全检查
在语义分析阶段进行类型安全检查，确保类型 安全，预防运行时错误。
控制流分析
对程序的控制流进行分析，识别潜在的逻辑错误和安全漏洞。
运行时存储管理
内存管理
自动分配和释放内存，管理内存空间，避免内存 泄漏和野指针问题。
垃圾回收
自动识别并清除不再使用的内存，释放资源，减 轻程序员负担。
内存优化
编译原理王生原课件
目录
• 编译原理概述 • 编译过程 • 编译器设计 • 高级编译技术 • 编译原理的应用 • 编译原理实验
CHAPTE是计算机科学的一个分支， 主要研究如何将高级语言编写的源代 码转换成机器语言或低级语言，以供 计算机执行。
它涉及到程序设计语言的设计、实现 、分析和理解，以及计算机体系结构 、操作系统和网络等多个领域的知识 。
编译原理的发展历程
编译原理的发展历程可以追溯到20世纪50年代，当时计算机刚刚问世不久，人们开始研究如何将高级 语言编写的程序转换成机器语言程序。
随着计算机技术的不断发展，编译原理也在不断演变和完善，从最初的简单编译器到现在的复杂编译器 ，编译原理的应用范围也越来越广泛。
目前，编译原理已经成为计算机科学领域中一门非常重要的课程，许多高校都开设了相关的课程，培养 了大批优秀的编译器设计师和软件工程师。

些不再使用的变量占据的内存 Java设计来支持代码移植和代码移动
编译器技术的应用
针对计算机体系结构的优化 计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要 并行化 • 编译器重新整理指令，使得指令级并行更有效 • 编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上 内存分层 • 编译器优化历来集中在优化处理器的执行上，但是现在更强调要使内存分层更有效
编译器技术的应用
程序翻译 二进制翻译 • 编译器技术可用于把一种机器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令 集编译的代码 数据库查询解释器 • 数据库查询由一些谓词组成，这些谓词由包含关系运算的布尔表达式组成，可以被解释执行,也 可以被编译成搜索数据库的命令
编译器技术的应用
提高软件开发效率的工具 源于编译器中代码优化技术的程序分析一直在
改进软件开发效率 类型检查
类型检查是一种捕捉程序中前后不一致的成熟并且有效的技术 边界检查
数据流分析技术可用来定位缓冲区溢出 内存管理
自动的内存管理删除内存泄漏等内存管理错误
内容提要
编译器构造法的研究目的 编译器的结构
编译的基本原则 编译器应有的性质 编译器技术的应用 关于学习编译原理
5.代码优化
temp1 = inttoreal(60) temp2 = id3 * temp1 temp3 = id2 + temp2 id1 = temp3
代码优化器
temp1 = id3 * 60.0 id1 = id2 + temp1
任务：对于前阶段产生的中间代码进行加工 变换，以期在最后阶段产生更高效的目标代 码。
化的新研究 支持用户定义的聚合数据类型和高级控制流，如数组和记录、循环和过程调用：C、Fortran 面向对象的主要概念是数据抽象和性质继承，使得程序更加模块化并易于维护：Smalltalk、

编译器的作用
语法分析
编译器负责解析源代码并检查其语法是否正确。
代码优化
编译器可以通过代码优化技术提高程序的执行效 率。
语义分析
编译器会对代码进行语义分析，确保它们符合语 言规范和规则。
代码生成
编译器最终将源代码编译为可执行的机器语言。
编译器的类型
1 前端编译器
2 后端编译器
负责将源代码转换为中间代码或抽象语法树。
负责将中间代码或抽象语法树转换为目标机 器代码。
3 即时编译器
将源代码转换为机器代码并立即执行。
4 解释器
逐行解释源代码并执行。
编译器开发环境
文本编辑器
选择适合自己的文本编辑器，如Sublime Text或 Visual Studio Code。
命令行界面
熟悉命令行界面，以便在编译器开发中使用各种命 令。
结束语
编译器是计算机科学中的重要概念，了解它的工作原理和开发过程将使您成 为一个更优秀的程序员。感谢您参加编译原理课程的第一），以便跟踪和管理代码 的变更。
调试工具
掌握调试工具的使用，以便找到和修复代码中的错 误。
Lex和Yacc入门
为了进行更高级的编译器开发，我们将学习Lex和Yacc分别用于词法分析和语法分析。 Lex工具可以将输入的字符流分解为标记，而Yacc工具是一个语法分析器生成器，可以生成用于语法和语义分 析的解析器。
编译原理第一章： Introduction to Course
欢迎来到编译原理课程！在本章节中，我们将介绍课程背景和编译器的重要 性。准备好迎接编译器的魅力吧！
什么是编译器？
编译器是一种软件工具，它将高级语言代码转换为机器语言。它起着将程序 翻译成计算机可执行代码的作用。

词法分析过程
输入
源程序的字符流。
01
输出
源程序的标记流。
02
1. 初始化
设置初始状态和缓冲区。
03
2. 循环
04 从缓冲区中取出一个字符，根
据当前状态和该字符确定下一 个状态和标记。
3. 输出
05 输出当前标记，并更新状态和
缓冲区。
4. 结束条件
06 当缓冲区为空且所有字符都被
处理时，结束词法分析。
三地址代码的生成
三地址代码定义
三地址代码是一种中间代码形式，由一系列的三元式组成，每个三 元式包含三个操作数和两个操作符。
三地址代码的特点
三地址代码具有简单、直观和易于优化的特点，能够清晰地表示程 序中的控制流程和数据流。
三地址代码的生成算法
常见的三地址代码生成算法包括递归下降分析法和语法制导翻译法 。
示中间代码，以便进行有效的优化和转换。
代码生成器的构造
代码生成器通常由指令选择、控制流优化、循环优化等 模块组成。
控制流优化模块负责对控制流进行分析和优化，如消除 冗余计算、消除无用代码等。
指令选择模块负责从中间代码中选择合适的机器指令， 并进行指令调度和并行化。
循环优化模块负责对循环结构进行优化，如循环展开、 循环合并等。
编译原理的应用非常广泛，如编译器设计、程序分析、软件工程等。
编译过程的基本概念
源程序
用高级语言编写的程序，也称为源代码。
目标程序
编译后的程序，也称为目标代码或机器代码。
编译程序
将源程序翻译成目标程序的软件。
编译过程
将源程序通过词法分析、语法分析、语义分析、中间代码生成、优化 、目标代码生成等阶段，最终生成目标程序的过程。

源程序的 执行结果
编译相当于全文翻译，全部翻译完才执行。 解释就相当于同声翻译，边翻译边执行。
特点：
1．编译器：工作效率高，即时间快、空间省；
交互性与动态特性差、可移植性差。大多数 采用此种方法翻译； 2．解释器：工作效率低，即时间慢、空间费； 交互性与动态特性好、可移植性好。基本功 能：二者相同； 所采用的技术：从翻译的角度来讲，两种方 式所涉及的原理、方法、技术相似。
编译原理在反病毒技术中的研究和应用
交叉编译技术：如嵌入式应用 硬件描述语言及其编译技术：如芯片设计 为计算机分析和理解自然语言提供参考

5.课程考核方法
闭卷考试,同时作业完成情况和上机实践的结
果占一定的比例。 考试成绩 = 80%考试成绩+考勤和作业 （20%）
6. 教材和参考书
各级语言的比较
比较 硬件识别
是否可直 接执行
机器语言
汇编语言
高级语言 不可识别
不可，需编译/解 释、连接 面向问题/对象 占用内存大 执行速度相对慢 标准化程度高 便于程序交换， 使用方便 高级语言，种类多， 常用
特点
是唯一可以识 不可识别 别的语言 可直接执行 不可，需汇 编、连接 面向机器 面向机器 占用内存少 占用内存少 执行速度快 执行速度快 使用不方便 较为直观 与机器语言 一一对应
英文ቤተ መጻሕፍቲ ባይዱ一版
中文第一版
红 龙 书
本科教学版
中文第二版
英文第二版
紫 龙 书
英文第三版？？？
绿 龙 书
Alfred
V．Aho 哥 伦比亚大学，美国 科学与艺术学院及 国家工程学院院士， 曾获得IEEE的 冯· 诺伊曼奖。

静态存储分配
动态存储分配
1> 静态存储分配
若在编译时能完全确定程序所需空间大小,并能确定每个数 据项的地址,就可在编译时分配所需空间,这种分配方法称为静态 存储分配.
内情向量表组织如下：
L1
u1
d1
L2
u2
d2
Ln
un
dn
a
c
n
elemlength
17
整理课件
3）结构类型------- 记录
是由多种类型的数据组合起来的一种数据结构。Pascal 语 言中，可如下定义一种记录类型
type < 记录类型名> = record <域名 1>:<类型1>; <域名 2>:<类型2>;
26
整理课件
1>传值 调用程序把实际参数的值传递到形式参数的空间中.
a1 1 b1 1 a2 4 b2 5
x1 1 y1 1 x2 4 y2 5
主程序空间
子程序空间
这种方式,子程序一般不改变实际参数的值.
27
整理课件
2>传地址 调用程序把实际参数的地址传递到形式参数的空间中.
a1 1 b1 1 a2 4 b2 5
type <类型名> = set of <基类型>; <类型名> = array of <基类型>; <类型名> = record
end;
21
整理课件
2> 变量说明段 var <变量名表<类型2>;
<变量名表n>:<类型n>; 3> 函数及过程定义
function <函数名> (参数说明):<函数类型>; <函数体>; procedure <过程名> (参数说明) ; <过程体>; 4> 赋值句

2020/9/3
6
教材
• 王生原等，《编译原理》 (第3版) ，清华大学 出版社，2015年6月
• 张素琴等，《编译原理》 (第2版) ，清华大学 出版社
2020/9/3
7
参考书目
• 陈火旺，程序设计语言编译原理(第3版)，国防工业出 版社，2000
• 陈意云、张昱，编译原理(第3版)，高等教育出版社， 2014
2020/9/3
3
课程性质与任务
• 是计算机专业的一门核心专业课，旨在介绍编译 程序构造的一般原理和基本方法
• 既是一门理论性、技术性与实验性很强的课程， 又是理论与实践紧密结合的课程
• 本课程主要任务是介绍程序设计语言编译程序构 造的基本原理和设计方法。通过本课程学习：
– 掌握和理解编译一般过程、编译各个阶段功能、以及一 些常用的编译设计方法和技巧
• 钱焕延，编译技术(第2版)，东南大学出版社
• K. C. Louden，编译原理及实践，冯博琴译，机械工业
出版社
2020/9/3
8
相关课程
• 编译原理：3学分，理论、方法与技术 • 编译原理课程实践：1学分，实践，单独一门课
2020/9/3
9
概论
• 课程简介 • 什么是编译程序 • 为什么学习编译原理 • 编译过程概述 • 编译程序结构 • 编译程序生成
2020/9/3
11
58 20 1020 (1000) 59 20 1024 (1004) 47 C0 1014 (1008) 50 20 1028 (100C) 47 F0 101C (1010) 58 20 1024 (1014) 50 20 1028 (1018)
LD R2, x CP R2, y BNG LESS ST R2, max JMP EXIT LESS: LD R2, y ST R2, max

第31页
2021/3/17
《编译原理实践及应用》
第31页
1.3 编译程序的结构
2021/3/17
《编译原理实践及应用》
第32页
2021/3/17
《编译原理实践及应用》
第33页
• 几个概念 – 符号表：登记源程序中出现的名字以及名字的各种属性。 – 遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新 的中间结果或目标程序。 – 编译前端：主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法 分析、语义分析和中间代码生成，与机器无关部分的代码优化。 – 编译后端：指与目标机器有关的部分。如与机器有关的优化、目标代码生成。
end;
单词
begin result
:=
5 + B * C + B * C end
;
类型
关键字 标识符
界符
常数 算符 标识符 算符 标识符 算符 标识符 算符 标识符 关键字
界符
内部形式
$begin id1 :=
int1 + id1 * id2 + id2 * id3 $end
;
2021/3/17
《编译原理实践及应用》
第12页
• 问题： • 1. 什么是编译程序？ • 2. 编译程序的工作过程是什么样的？ • 3. 编译程序的总体结构是什么样的？ • 4. 什么叫编译前端、编译后端？ • 5. 什么叫“遍”（pass）？ • 6. 编译程序有哪些生成方法？
2021/3/17
《编译原理实践及应用》
第13页
1.1 编译程序是什么
编译原理课程教案第1章编译原理 概述
教材及主要参考资料

本课程的目的
构造编译器基本知识
编译的阶段和相关的活动 相关数据结构和算法
计算机科学中相关的基础理论
形式语言与自动机
进一步加深对软件开发的认识
第一章 概述
【课前思考】 ◇ 什么是编译程序？ ◇ 编译过程和编译程序的结构？ 【学习目标】 介绍语言翻译的基本概念
程序和语言 翻译和解释
介绍翻译的步骤和相关的活动 介绍编译器的开发方法
输入字符串（即源程序） 输出单词符号（最基本的语法单位） 。
词法分析举例
一个C源程序片段：
int a; a=a+2; 词法分析后返回(如右 图)：
单词类型 保留字 标识符 界符 标识符 算符(赋值) 标识符 算符(加) 整数 界符 单词值 int a ; a = a + 2 ；
(2) 语法分析（Syntax analysis）
程序的执行方式
高级语言程序通常采用两种方式执行：解释方 式和翻译方式 解释方式：逐个语句地分析和执行，如Basic， Prolog
优点：易于查错 缺点：效率低，运行速度慢
翻译方式：对整个程序进行分析，翻译成等价 机器语言程序后执行，如Pascal，Fortran，C
优点：只需分析和翻译一次， 缺点：在运行中发现的错误必须在源程序中查找
编译程序的功能
从功能上看，一个 编译程序就是一个 语言翻译程序。 源语言通常是一个 高级语言，如 FORTRAN，C 或 Pascal。 目标语言通常是一 个低级语言,如汇编 或机器语言。
出错和警告信息
编译程序
源语言程序
目标语言程序
T形图
常用T形图来表示编译程序涉及的三个语言： S I 其中： S:源语言(程序)，Source language(program) O:目标语言(程序), target/object language(program) I:实现语言, implementation language O