This PPT is an introduction to the first chapter of Compiler Principles..ppt

这是关于编译原理的课程PPT

1. 编译原理编译原理
主讲教师：刘萍主讲教师：刘萍
Email:[email protected]:[email protected]

2. 课程简介课程简介
先行课程 ：Ｃ (PASCAL)、离散数学、
　　　　　 汇编语言、数据结构
　　　　编译原理课程应用领域编译原理课程应用领域
编译器的设计编译器的设计
一般的软件设计一般的软件设计
例如：例如：
文本编辑器、信息检索系统、文本编辑器、信息检索系统、
模式识别器模式识别器
排版、绘图系统排版、绘图系统
程序验证器程序验证器

3. 课程介绍（一）课程介绍（一）

一、研究内容一、研究内容
主要研究设计和构造编译程序的基本原理。主要研究设计和构造编译程序的基本原理。
•二、编译程序在软件设计中的应用
–1、某一语言 另一种语言
–2、深入了解某种编程语言的结构和应用
–3、编译理论发展比较成熟，已经形成一
套完整的理论和应用，蕴含了大量的程序
设计技巧和算法构造方法。

4. 课程介绍（二）课程介绍（二）

三、学习方法三、学习方法
11、要用循环的观点学习这门课程。、要用循环的观点学习这门课程。
22、学习思考过程中用对比方法、学习思考过程中用对比方法
33、最好不要缺席，原因：、最好不要缺席，原因：

（（11）章节调整；）章节调整；

（（22）比较难学，学好不易；）比较难学，学好不易；

（（33）课堂上的小结或举例，书上可能没有；）课堂上的小结或举例，书上可能没有；

（（44）自学，花的时间多。）自学，花的时间多。
44、适当作笔记。、适当作笔记。
55、问题反馈。、问题反馈。

5. 课程介绍（三）课程介绍（三）

四、学时安排四、学时安排
6464学时学时=48=48学时理论学时理论 +16+16学时实验学时实验

五、评分标准五、评分标准
平时作业与实验 平时作业与实验 2020％％
平时考勤 平时考勤 10%10%
期中测试 期中测试 2020％ ％
期末考试 期末考试 5050％％

6. 1、程序设计语言编译程序 陈火旺等程序设计语言编译程序 陈火旺等
国防工业出版社（第三版）国防工业出版社（第三版）
2、编译原理 吕映芝 清华大学出版社编译原理 吕映芝 清华大学出版社
3、编译原理及实践， Kenneth C. Louden，
冯博琴译，机械工业出版社
主要参考资料

8. •系统地了解程序设计语言编译程序
的构造原理及其具体实现的方法；
•培养利用计算机语言处理技术进行
系统分析和软件设计的能力。
为什么要学习编译原理，
学习的目的是什么？

9. 课程考核方法课程考核方法

主要采用闭卷考试的形式；同时，作业主要采用闭卷考试的形式；同时，作业
完成情况和上机实践的结果占一定的比完成情况和上机实践的结果占一定的比
例。 例。

考试成绩 考试成绩 = = 闭卷考试闭卷考试 + + 考勤和作业完考勤和作业完
成 情况 成 情况 + + 上机上机

10. 联系方式联系方式

作业可通过班长（或课程代表）提交。作业可通过班长（或课程代表）提交。

如有什么建议和问题，课后可通过网络教如有什么建议和问题，课后可通过网络教
学平台或电话联系。学平台或电话联系。

11. 编译原理编译原理
第一章 引论第一章 引论
第二章 高级语言及其语法描述第二章 高级语言及其语法描述
第三章 词法分析第三章 词法分析
第四章 语法分析第四章 语法分析 ——自上向下分析自上向下分析
第五章 语法分析第五章 语法分析 ——自下向上分析自下向上分析
第
六章 属性文法与语法 制导翻译
第
六章 属性文法与语法 制导翻译
第
七章 语义分析和中间代 码生成
第
七章 语义分析和中间代 码生成
第
八章 符号表
第
八章 符号表
第
九章 运行时存储空间组织
第
九章 运行时存储空间组织
第
十章 优化
第
十章 优化
第
十一章 目标代 码生成
第
十一章 目标代 码生成
第
十二章 并行编译基础
第
十二章 并行编译基础

12. 第一章 引论第一章 引论
1.1 1.1 什么
叫编译程序
什么
叫编译程序
1.2 1.2 编译过程
概述
编译过程
概述
1.3 1.3 编译程序的结构编译程序的结构
1.4 1.4 编译程序与程序设计环
境
编译程序与程序设计环
境
1.5 1.5 编译程序的
生成
编译程序的
生成

13. 知

识
结
构

14. 过程式语言 过程式语言 Fortran,Pascal,CFortran,Pascal,C
函
数式语言
函
数式语言
LispLisp
逻
辑式语言
逻
辑式语言
PrologProlog
对
象式语言
对
象式语言
C++C++
　　　　　　　　汇编语言　　　　　　　　汇编语言
　　　　　　　　机器语言　　　　　　　　机器语言
第一章 引论第一章 引论
1.1 1.1 什么
叫编译程序
什么
叫编译程序
１１. . 程序设计语言程序设计语言
程序设程序设
计语言 计语言



高级语言高级语言
低
级语言： 面向机器的语言
低
级语言： 面向机器的语言

15. 编译程序编译程序 ::是
指这样的程序， 它能够把某
是
指这样的程序， 它能够把某
种语言的程序
转换成另一种语言的程序
种语言的程序
转换成另一种语言的程序
，
而后者与前者在逻辑上是等 价的。如
，
而后者与前者在逻辑上是等 价的。如
果
源语言是诸如
果
源语言是诸如
FORTRANFORTRAN、、PascalPascal
、、CC、、AdaAda、、SmalltalkSmalltalk或或JavaJava这这
样
的“高级语言 ”，而目标语言如汇编语
样
的“高级语言 ”，而目标语言如汇编语
言
之类的“低级语言”这样的翻译程序则
言
之类的“低级语言”这样的翻译程序则
称之
为编译程序。
称之
为编译程序。

16. 22..在计算机上如
何执行一个高级
在计算机上如
何执行一个高级
语言程序？语言程序？
11）
把高级语言程序 翻译成机器语言程序；
）
把高级语言程序 翻译成机器语言程序；
22）
运行所得的机器语言程序 求得计算结果。
）
运行所得的机器语言程序 求得计算结果。
高级语言
源程序的执行通常分两个阶段
:
计算机只
能识别由
0和1组
成的二进制指令。

17. 源
程序
(高级语言 )
编译程序
计算机
目标程序
(机器语言 )
编译
阶段
初始
数据
目标程序
计算机
运
行系统
计算结果
运
行阶段

18. ２２. . 语言处理器语言处理器

编译器编译器

解
释器
解
释器

19. ２２. . 翻
译和解释程序
翻
译和解释程序
　　(1)(1)翻
译和编译程序
翻
译和编译程序
编译：如果一
个翻译程序的
源
语言
源
语言
是某种高级语言，其 目标语目标语
言言是
相对于某一计算机的汇编语言或机器语言， 则称这种翻译程
序为编译程序（或
称为编译器）。
翻
译
：是
指在计算机中 放置一个能由计算机直接执行的翻译程
序，
它以某一种程序设计语言（ 源语言）所编写的程序（
源
程
源
程
序序）作为
翻译或转换的对象，当计算机 执行翻译程序时， 就将它
转换
成与之等价的另一种语言（目标语言）的程序（
目标程序目标程序）。
输
入
输
出

20. (2) (2) 编译和解
释程序
编译和解
释程序
目标目标
程序程序
源源
程程
序序
编编
译译
程程
序序
初始
数据
初始
数据
计计
算算
结结
果果
源
程序
源
程序
解解
释释
程程
序序初始
数据
初始
数据
计计
算算
结结
果果

21. 功
能
功
能
工作结果工作结果 实现技术上实现技术上
解
释
解
释
程序程序
源
程序的一
源
程序的一
个个执
行
执
行
系统系统
源
程序的
源
程序的
执
行结果
执
行结果
执
行中间代码
执
行中间代码
编译编译
程序程序
源
程序的一
源
程序的一
个个转换转换系统系统
源
程序的
源
程序的
目标代
码
目标代
码
把
中间代码转
把
中间代码转
换
成目标程序
换
成目标程序
解
释程序和编译程序的 区别
解
释程序和编译程序的 区别
解
释程序和编译程序
的根
本区别
根
本区别
：
是
否生成目标代 码

22. 口
译
——解
释程序
笔译——编译程序
解
释程序和编译程序的 区别
解
释程序和编译程序的 区别
优
点：直观易懂，结构简 单，
易
于实现人机对话。
缺点：
效率低。
解
释程序的优缺点
解
释程序的优缺点

23. 
在
把用户输入映射为输出的过程中， 由一
在
把用户输入映射为输出的过程中， 由一
个
编译器产生的机器语言目标程序比一 个
个
编译器产生的机器语言目标程序比一 个
编译器
快的多。然而，解释器的错误诊断
编译器
快的多。然而，解释器的错误诊断
效
果比编译器好。
效
果比编译器好。

JavaJava语言处理语言处理 结
合了编译和解 释过程。一
结
合了编译和解 释过程。一
个个JavaJava源
程序首先被编译成为 字节码的中
源
程序首先被编译成为 字节码的中
间表
示形式。然后由虚拟机对得到的字节
间表
示形式。然后由虚拟机对得到的字节
码加以
解释执行。优点：在一台机器上编
码加以
解释执行。优点：在一台机器上编
译
得到的字节码可以在另一台机器上解 释
译
得到的字节码可以在另一台机器上解 释
执
行。
执
行。

24. 一
个语言处理系统
一
个语言处理系统

25. 编译程序的分
类
编译程序的分
类

诊断型
编译程序
诊断型
编译程序
::
用
于帮助程序开发和调试的编译程序。
用
于帮助程序开发和调试的编译程序。

优化型
编译程序：
优化型
编译程序：
着重于
提高目标代 码效率的编译程序。
着重于
提高目标代 码效率的编译程序。

交
叉型编译程序
交
叉型编译程序
一
些设备上的嵌入式应用软件一般是在另 外类型的计算机上设计和 开发，
一
些设备上的嵌入式应用软件一般是在另 外类型的计算机上设计和 开发，
经过编译、
运行、和测试后 再经过一次编译产生出在上述设 备上可以运行
经过编译、
运行、和测试后 再经过一次编译产生出在上述设 备上可以运行
的目标代
码。
的目标代
码。
这
类编译程序 称之为交叉型编译程序；
这
类编译程序 称之为交叉型编译程序；
能
产生不同于其宿主机的机器代 码的编译程序。
能
产生不同于其宿主机的机器代 码的编译程序。

26. 
可
变目标型编译程序
可
变目标型编译程序
不
需重写编译程序中与机器 无关的部分
不
需重写编译程序中与机器 无关的部分
就
能改变目标机的编译程序。
就
能改变目标机的编译程序。

27. 编译技术的发展编译技术的发展

第一
个编译程序出现在
第一
个编译程序出现在
2020世纪世纪5050年
代
年
代
早
期，主要是 将算术公式翻译成机器代 码
早
期，主要是 将算术公式翻译成机器代 码
。。

2020世纪世纪6060年
代起，出现自编译技术。
年
代起，出现自编译技术。

还
在不断发展之中，目前已经形成一套比
还
在不断发展之中，目前已经形成一套比
较成熟的系统
化的理论和方法。
较成熟的系统
化的理论和方法。

28. 编译程序的工作过程
指从输入源程序开
编译程序的工作过程
指从输入源程序开
始到输
出目标程序为 止的整个过程。一般可
始到输
出目标程序为 止的整个过程。一般可
划
分为五个阶段：词法分析、语法分析、语
划
分为五个阶段：词法分析、语法分析、语
义
分析和中间代 码生成、代码优化、目标代
义
分析和中间代 码生成、代码优化、目标代
码生
成。
码生
成。
1)1)词法分析词法分析
词法分析的
任务是输入源程序
词法分析的
任务是输入源程序
, , 对构成对构成
源
程序的字符串进行扫描和分解，识别出一
源
程序的字符串进行扫描和分解，识别出一
个个单
词符号
个个单
词符号
, , 并将
识别出的 单词用统一长
并将
识别出的 单词用统一长
度
的标准形式表 示。词法分析过程 就是将源
度
的标准形式表 示。词法分析过程 就是将源
程序中的程序中的 字符串字符串变换
成
变换
成
单
词串
单
词串
的过程。的过程。

29. 翻
译外文资料
翻
译外文资料
编译
源程序
编译
源程序
分析分析
识别
单词
识别
单词
分析
句子
分析
句子
初步翻
译句子的含意
初步翻
译句子的含意
词法分析词法分析
语法分析语法分析
语
义分析中间代 码生成
语
义分析中间代 码生成
综合综合
修辞加
工
修辞加
工
写
出译文
写
出译文
代
码优化
代
码优化
目标代
码生成
目标代
码生成
1.1.２

２

编译过程
概述
编译过程
概述
翻
译外文资料与编译 源程序进行类比

30. 在词法分析
阶段工作所依循的是语言的词法 规
则
。描述词法 规则的有效工具是正规式和有限自
动
机。
int fun()
{
int i,sum;
sum=0;
for(i=0;i<=100;i++)
sum+=i;
return sum;
}
•
关键字
：
关键字
：
int for returnint for return
•
标识
符：
标识
符：
i sumi sum
•
常
量：
常
量：
0 1000 100
•
运
算符：
运
算符：
= <= ++ +== <= ++ +=
•
界限符
：
界限符
：
; ( ) { } ,; ( ) { } ,

31. 2)语法分析
语法分析的
任务：在词法分析的基 础上，
根
据语言的语法 规则，把单词符号分解成各
类
语法单位（语法范畴），如“短语”、“句子”、

“子句”、“程序段”等。
语法
规则通常用上下文 无关文法描述。

32. int fun() ----函
数定义语句
{
int i,sum; ----变
量定义语句
sum=0; ----赋值
语句
for(i=0;i<=100;i++) ---- for语
句
sum+=i; ----赋值
语句
return sum; ----返回
语句
}

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

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

35. 5）目标代
码生成
这一
阶段的任务：把中间代码（或经优
化
处理后） 变换成特定机器上的 低级语言代
码
。它有赖于硬件系统结构和机器 指令含义。
如
何充分利用寄存器、合理选择指令
以生
成尽可能短且有效的目标代 码等都与目
标机器
硬件结构有 关。

36. 11）编译程序的
功能和组织结构
）编译程序的
功能和组织结构
表 处 理
词
法
分
析
器
源
程
序
目
标
程
序
错
误 处 理
语
法
分
析
器
语
义
分
析
目
标
代
码
生
成
前
端
后
端
代
码
优
化
器
中
间
代
码
生
成
1.3 编译程序的结构

37. 2）表
格与表格管理
用
于记录源程序的各种信息以及编译过
程中的
各种状况，以便后续阶段使 用。
与编译
前三阶段有关的表格有：
符号
表、常数表、标 号表、分程序入 口表、
中间代
码表等。
注
：在编译过程中， 随着源程序的不 断
被改
造，编译的 各阶段常常需 要不同的表
格
，编译过程的 绝大多数时间是花在 查表、
造表和
更新表格的事务上。在大多数的编
译程序中，表
格专门由表格管理程序来处
理。

38. 3）出
错处理
出
错处理程序的 任务包括 检查错误、报告
出
错信息、排 错、恢复编译工作。
错误类型 :
语法
错误
:在词法分析和语法分析
阶段检测
出
来。
语
义错误：一般在语 义分析阶段检测。

39. 编译程序的 前端前端：
与
源语言有关，而与目标机无关的编译程序
编译程序的 后
端
后
端
：
与目标机有
关，而与源语言无关的编译程序
遍
（趟）
遍
（趟）
：是对
源程序或源程序的中间结果 从头到
尾扫
描一遍，并作有关加工处理，生成新的中间结
果或目标程序。
宿
主机
宿
主机
：
运行编译程序的计算机 称为宿主机。
目标机目标机：
运行编译程序 所产生的目标代码的计算机
成为目标机。
44）
相关概念
）
相关概念

40. 1.4 1.4 编译程序与程序设计环编译程序与程序设计环
境境
编译程序
无疑是实现高级语言的一 个最重
编译程序
无疑是实现高级语言的一 个最重
要的工具。
但支持程序设计 人员进行程序设计
要的工具。
但支持程序设计 人员进行程序设计
开
发通常还需要其它一些工具：如编辑程序、
开
发通常还需要其它一些工具：如编辑程序、
连接
程序、调试程序等。编译程序与这 些程序
连接
程序、调试程序等。编译程序与这 些程序
设计工具一
起构成所谓的程序设计环 境。
设计工具一
起构成所谓的程序设计环 境。
在一
个程序设计环 境中，编译程序 起着中心
在一
个程序设计环 境中，编译程序 起着中心
的作用。
连接程序、调试程序、程序分析等工
的作用。
连接程序、调试程序、程序分析等工
具
直接依赖于 编译程序 所产生的结果， 而其它
具
直接依赖于 编译程序 所产生的结果， 而其它
工具的构造
也常常要用到编译的原理、方法和
工具的构造
也常常要用到编译的原理、方法和
技术。技术。

41. 图1.2 Ada程序设计环
境

42. 1.5 1.5 编译程序的
生成
编译程序的
生成
●●常
用的方法（ 根据语言来分）
常
用的方法（ 根据语言来分）
11）
直接用机器语言编 写编译程序
）
直接用机器语言编 写编译程序
22）用汇编语言编
写编译程序
）用汇编语言编
写编译程序
注
：编译程序核 心部分常用汇编语言编 写
注
：编译程序核 心部分常用汇编语言编 写
33）用高级语言编
写编译程序
）用高级语言编
写编译程序
注
：这是普遍采用的方法
注
：这是普遍采用的方法
◆◆常
用的方法（ 根据实现途径来分）
常
用的方法（ 根据实现途径来分）
11）自编译）自编译
22）编译工具）编译工具 :LEX(:LEX(词法分析词法分析 ))与与YACC(YACC(用
于自
用
于自
动产生动产生LALRLALR分析表分析表))
33）
移植（同种语言的编译程序在不同 类型的机
）
移植（同种语言的编译程序在不同 类型的机
器
之间移植）
器
之间移植）

43. 设计和实现一
个编译程序， 必须精通
设计和实现一
个编译程序， 必须精通
::

源
语 言
源
语 言

目标语言目标语言

编译方法编译方法
4 4 编译程序的编译程序的 设计实现设计实现

44. 5 5 经
典的编译程序
经
典的编译程序
Pascal编译程序
C编译程序
Fortran 编译程序

45. 谢
谢
谢
谢