1
编译原理
田凤占
计算机与信息技术学院
tfz@computer.njtu.edu.cn
2
本课程的学习目的
? 编译程序是计算机系统中最重要的系统程序之一。
? 掌握设计和构造编译程序的基本原理和基本方法，其
中许多方法也适用于构造解释程序或汇编程序。
? 上述理论（如 Chomsky文法和自动机理论）可以直接
用于特定领域的应用，如机器翻译，自然语言处理等
人工智能领域。
? 有利于深入掌握不同的程序设计语言，甚至开发新的
语言。
? 某些院校的考研课程之一
? 先修课：数据结构、汇编语言,C语言等
3
教材和参考书
? 教材,
– 编译原理。蒋立源，康慕宁主编，西北工业大学出版社，
1999年，第二版。（ 95国家级重点教材）
? 参考书,
– 编译原理与技术。陈意云，中国科大出版社,2002，第二版。
（中科院指定考研参考书、科技大教材）
– 编译原理 。 吕英芝, 张素琴编著, 清华大学出版社, 2003年
8月 。 （ 清华教材 ）
–, 程序设计语言编译原理（第 3版）, 。陈火旺、刘春林等
著，国防工业出版社,2001年 2月。（南大教材）
– 编译程序设计原理。杜淑敏等编著，北京大学出版社。（北
大教材）
4
课程安排（共 48课时）
? 第一章 绪论 2课时
? 第二章 前后文无关文法和语言 6课时
? 第三章 词法分析 8课时
? 第四章 语法分析 12课时
? 复习和习题课 2课时
? 第五章 语法制导翻译及中间代码生成 10课时
5
课程安排（续）
? 第六章 符号表及出错处理 自学
? 第七章 存储组织与管理 2课时
? 第八章 代码优化 略
? 第九章 目标代码生成 4课时
? 第十章 查错与改错 自学
? 总复习 2课时
6
考核方式
? 课后作业 30分
? 期末考试 70分
? 认真听课能使你事半功倍！
? 独立完成作业对取得好成绩至关重要！
7
第一章 绪论
计算机的软硬件组成
中央处理机
输入 /输出处理机等
硬件部分 存储器
通信设备
编译程序, 解释程序, 汇编程序
数据库管理程序 （ DBMS）
系统软件 操作系统 （ OS）
装入, 链接, 编辑程序
软件部分 数据通信系统
应用软件
8
程序设计语言
? 低级语言,机器语言（二进制代码）、汇编语言（直
接操作寄存器、多种寻址方式）及其它面向机器的程
序设计语言；其特点对计算机的依赖性强、直观性差、
编写程序的工作量大，对程序设计人员要求较高。
? 机器语言 符号汇编语言 宏汇编语言
? 高级语言,具有很强的算法描述能力，其编写和调试
效率也比低级语言优越得多。现有上百种 高级语言,
常用的有 BASIC,FORTRAN,PASCAL,C,C++、
JAVA等。
9
编译技术的产生
? FORTRAN,ALGOL 和 COBOL
? FORTRAN(FORmulaTRANslation) 公式翻译
语言是五十年代初期产生第一个实用的高
级语言
1954-1959年 FORTRAN语言及编译系
统产生标志着编译技术开始形成
10
ALGOL和 COBOL
? ALGOL(ALGOkithmic Language)
国际代数语言
ALGOL58 ALGOL60
采用 BNF范式形式化的语言描述体系
促进了语法分析及理论的研究
语言格式影响程序设计语言的发展
? COBOL
引入了独立于机器的数据描述概念
导致了数据库管理系统的产生
11
PASCAL,PROLOG
? PASCAL
由 ALGOL60研究小组研制的用于教学与编写系统软
件的语言
继承了 ALGOL60的描述方法
对程序验证和结构化程序设计起重要作用
? PROLOG PROgramming in LOGic 法国马赛大学
? C++,Java
? IDE(Interactive Development Environment)
交互式开发环境
12
编译程序
? 高级语言与机器之间有一道“鸿沟”,机器不
能理解也不能直接执行高级语言 ！
? 使该语言能让计算机所理解：翻译或解释。
? 翻译：在计算机中放置一能由计算机直接执行
的翻译程序，它将某程序设计语言（ 源语言 ）
所编写的程序（ 源程序 ）作为加工对象，将其
翻译成为与之等价的另一种语言（ 目标语言 ）
的程序（ 目标程序 ）。
? 编译程序：源语言是高级语言，目标语言是汇
编或机器语言。
13
源程序与目标程序是逻辑等价的
翻译程序
高级语言 机器语言
汇编语言 编译程序
源程序
源语 言
目标程序
目标语 言
逻辑等价
14
执行高级语言程序
? 编译阶段,将源程序编译为目标程序。
? 运行阶段,执行目标程序。在执行时，一般
应有一些辅助子程序配合。如：数据格式转
换、标准函数计算、动态存储分配子程序等
等，由它们构成的子程序库称为 运行系统 。
? 编译系统 =编译程序 +运行系统
15
执行高级语言程序的过程
源程序 P
编
译
阶
段
运
行
阶
段
计算机 A
目标程序 P’
计算机 B
运行结果 S
编译程序
运行程序 数据
16
解释程序
? 高级语言程序 也可通过 解释程序 来执行。
? 解释程序,以源程序为输入，在执行过程中不再产生
目标程序，而是边解释边执行。如 Basic,Java等
? 解释程序 运行效率不高，但结构简单、占用内存少，
易于修改。
? 纯粹的 解释程序 不多见，通常是将编译和解释作某种
程度的结合。
– 翻译为中间语言形式，再解释执行
– 翻译时对频繁出现的结构产生目标代码
17
解释程序工作过程
计算机
解释程序 源程序 计算结果
初始数据
18
1.1 编译过程概述
? 翻译外文书刊与编译工作比较
翻译外文书刊 编译源程序
分析
阅读原文
识别单词
分析句子
输入并扫描源程序
词法分析
语法分析
综合 修辞加工 写出译文 代码优化 目标代码生成
编译程序的特有工作：中间代码生成，信息表的构
造与查询，运行时存储空间的分配，出错处理等
19
编译程序 的构成
? 编译程序主要由八个部分构成,
1.词法分析 程序（ 扫描器 scanner）
2.语法分析 程序（ 分析器 parser）
3.语义分析 程序
4.中间代码生成 程序
5.代码优化 程序
6.目标代码生成 程序
7.错误检查和处理 程序
8.各种信息表格的管理 程序
20
1.2 编译程序 的 逻辑结构
源
程
序
词
法
分
析
程
序
中
间
代
码
生
成
代
码
优
化
程
序
目
标
代
码
目
标
代
码
生
成
语
法
分
析
程
序
语
义
分
析
程
序
错误检查和处理程序
信息表管理程序
21
一个微型 PASCAL语言的定义
? 它只有如下四种语句,
1） PROGRAM语句；
2）说明语句；
3） BEGIN-END语句；
4）赋值语句；
? 每个 PASCAL/M语句 都
以 PROGRAM语句开头，
后跟说明语句，再跟以
一个 BEGIN-END语句，
在其内部可以有若干赋
值语句。
PROGRAM source;
{This little source program is
used to illustrate compiling
procedure }
VAR x,y,z:integer;
a:integer;
BEGIN
{ This program has only 4
statement }
x:=23+5;
z:=x DIV -3;
y:=z+18*3;
a:=x+(y-2) DIV 4;
END,
22
1.2.1 词法分析程序（ 扫描器 ）
? 词法分析程序 的任务是,
1）识别出源程序的各个基本语法单位（单词或语法符号）
2）删除无用的空白字符及其它与输入介质相关的非实质
性字符（空格、回车等）
3）删除注释
4）进行词法检查，报告所发现的错误
? 扫描器需要根据当前查看字符的种类，并参考扫描过程
中已得到的信息，判断该字符在源程序中所处位置,
1）正处理的注释中的一个字符； 2）无用字符； 3）下
一个单词的首字符； 4）正识别的单词中的一个字符； 5）
不合法的字符。
23
源程序 source的扫描器输出
PROGRAM source;
{This little source program is used
to illustrate compiling
procedure }
VAR x,y,z:integer;
a:integer;
BEGIN
{ This program has only 4
statement }
x:=23+5;
z:=x DIV -3;
y:=z+18*3;
a:=x+(y-2) DIV 4;
END,
? 输出以单词为单位的单词
流
? 例如，以特殊符号,#”分
隔的单词流,
# PROGRAM # source # ;
# VAR # x #,# y #,# z
#, # integer # ; # a #, #
integer # ; # BEGIN # x
#,= # 23 # + # 5 # ; # z
#,= # x # DIV # - # 3 # ; #
y #,= # z # + # 18 # * # 3
# ; # a #,= # x # + # ( # y
# - # 2 # ) # DIV # 4 # ; #
END #, #
24
单词流的 内部表示
? 注意,前面的单词流形式是为便于阅读而假定的形式。
? 为了让计算机能够方便地识别和使用,常用方法是将
单词在计算机内部表示为一个有序对 (Class,Value)。
? Class为一整型数，用于标识该单词的类别；
? Value用于存放单词的值。
? 例如对于 source程序，可将其单词分为四类：（ 1）保
留字（ 2）专用符号（ 3）标识符（ 4）整数 。这样，
source程序相应的单词流为,
(1,‘PAROGRAM’) (3,’source’) (2,’;’) (1,’VAR’)
(...) … … (2,’;’) (1,’END’) (2,‘.’)
25
1.2.2 语法分析程序（ 分析器 ）
? 语法分析程序 以词法分析程序输出的单词流
为输入，分析源程序的结构，判断它是否为
相应程序设计语言的合法程序。
? 方法,试图为源程序构造一棵完整的 语法树 。
若成功，则说明输入串合乎语法；否则说明
源程序中存在错误。
? 语法树：一个有标记的有序树形结构，叶子
上的标记是程序中的单词，内部节点上的标
记是语法范畴（语法变量名）。
26
1.2.2 语法分析程序（ 续 ）
? 语法分析工作是在相应程序设计语言的 语法
规则 指导下进行的。 语法规则描述了该语言
的各种语成份的组成结构 。
– 前后文无关文法（ CFG）,Backus-Naur范
式（ BNF）
27
1.2.3 语义分析程序
? 语法特征 描述 各语法成份的形式或结构 ；
? 语义特征 描述 各语法成份的 含义 与 功能, 即规定它们
的属性或在执行应进行的运算或操作。
? 只有进行了 语义分析, 才能 让计算机知道应进行何操
作或运算。
? 在进行 语义分析 时还应进行相应的 语义检查 （运算时
类型匹配、类型的矛盾说明、参数匹配等）。
? 语义处理尚无公认的方法来系统地描述。当前较通用
的方法是半机械化的,语法制导翻译,方法。
28
1.2.4 中间代码生成
? 为了处理方便和便于代码优化，
在语义分析后通常并不直接产生
目标代码，而是生成介于二者之
间的 中间代码 。
? 常见的 ~有,逆波兰式、三元式、
四元式及树形结构等 。
? 例如,source程序中的第四条赋
值语句相应的逆波兰式（算符的
后缀表示）可写成,a x y 2 - div +
:= (a,= x + (y-2) div 4)。
? source程序相应的四元式表示为,
(prologue,’source’)
(add,’23’,’5’,T)
(store,T,,’x’)
(div,’x’,’-3’,T)
(store,T,,’z’)
(mult,‘18’,’3’,T)
(add,’z’,T,T)
(store,T,,’y’)
(sub,’y’,’2’,T)
(div,T,’4’,T)
(add,’x’,T,T)
(store,T,,’a’)
(epilogue)
29
1.2.5 代码优化程序
? 代码优化 的 目的 是 生成质量较高的目标代码
? 衡量质量的标准,空间指标 和 时间指标
? 优化方法分类,
– 与机器有关和与机器无关
– 局部优化和全局优化
? 以增加编译程序本身的时空复杂度和可靠性
为代价
? 优化指标有时是相互矛盾的，应根据具体情
况进行取舍和侧重
30
source程序的优化结果
(prologue,’source’)
(add,’23’,’5’,T)
(store,T,,’x’)
(div,’x’,’-3’,T)
(store,T,,’z’)
(mult,‘18’,’3’,T)
(add,’z’,T,T)
(store,T,,’y’)
(sub,’y’,’2’,T)
(div,T,’4’,T)
(add,’x’,T,T)
(store,T,,’a’)
(epilogue)
(prologue,’source’)
(store,28,,’x’)
(div,’x’,’-3’,T)
(store,T,,’z’)
(add,’z’,54,T)
(store,T,,’y’)
(sub,’y’,’2’,T)
(div,T,’4’,T)
(add,’x’,T,T)
(store,T,,’a’)
(epilogue)
31
1.2.6 目标代码生成程序
? 任务,将中间代码翻译成为目标程序
? 目标代码生成程序的设计,
– 首先确定源语言各种语法成份的 目标代码结构，
即源语言或中间语言的每一结构所对应的机器
指令组或汇编语句组，称之为框架,其中包含
待定成分。
– 再根据需要制定中间代码到目标代码的 翻译策
略和算法,要求目标代码具有较高的执行效率。
? 生成尽可能短的目标代码
? 充分发挥计算机可用资源的效率，如寄存器和执
行速度快的指令
32
目标代码生成程序（续）
– 编写目标代码生成程序，对具体机器的依赖性很
强，需具体情况具体分析
? 通常，目标代码的三种形式,
（ 1）具有 绝对地址 的 机器指令代码，在内存中有固定
的存放位置，可立即运行 ；
（ 2） 汇编语言 形式的目标程序，须经汇编程序进行汇
编，以生成机器代码；
（ 3） 模块结构 的机器指令（浮动地址），须经连接程
序将它们和另外的运行子程序连接装配后才能运行。
? Source程序对应的 80386汇编程序见书中 P9
33
1.2.7 错误检查和处理程序
? 程序中出现错误是难免的 。一完善的编译程序应具有
强大的查错能力，并能准确地报告源程序中错误的种
类及位置。
? 除报错外，编译程序还可生成一些另外的 注释信息,
它有助于程序设计人员调试程序。
? 常见的辅助手段
– 输出,对照图,,Source程序的对照图，见 P10表 1-2
– 输出各变量的值
? 没有统一的方法系统的解决程序诊断的问题
– 在编译系统的各部分插入一些程序段落，段落的总体
组成了编译系统的错误检查和处理程序
34
1.2.8 信息表管理程序
? 编译过程中，需经常收集、记录或查询程序中所出现
的各种量的有关 属性 （信息）。
? 为此，编译程序需要建立一批不同用途的 表格 （常数
表、变量表、关键字表等）
? 除此之外，根据不同的分析方法，编译程序还保持一
些专用的表格（ LL分析表,LR分析表、状态矩阵等）
? 合理地组织各种表格，恰当地选用相应的造表和查表
算法是提高编译程序工作效率的有效途径
35
1.3 编译程序的组织
开始
语法分析
程序
整理目标程序
停机
目标程序
源程序
词法分析
程序
取单词
送单词
语义分析及
代码生成程序
语法构造
返回
单遍扫描的编译过程
36
多边扫描的编译过程
? 多遍扫描：编译程序划分为若干个相继执行
的模块，每一模块对前一模块的输出进行一
遍扫描，并将处理的结果提供给下一模块。
? 如何确定扫描的遍数，如何组织各遍扫描中
的工作取决于源程序的具体情况以及编译程
序运行的具体环境。
? 多遍扫描的优点
– 各遍扫描的功能相对独立，编译程序结构清晰
– 有利于进行细致、充分的代码优化处理
– 有利于采用覆盖技术，减少编译程序占用的内存
空间
37
本章内容结束
编译原理
田凤占
计算机与信息技术学院
tfz@computer.njtu.edu.cn
2
本课程的学习目的
? 编译程序是计算机系统中最重要的系统程序之一。
? 掌握设计和构造编译程序的基本原理和基本方法，其
中许多方法也适用于构造解释程序或汇编程序。
? 上述理论（如 Chomsky文法和自动机理论）可以直接
用于特定领域的应用，如机器翻译，自然语言处理等
人工智能领域。
? 有利于深入掌握不同的程序设计语言，甚至开发新的
语言。
? 某些院校的考研课程之一
? 先修课：数据结构、汇编语言,C语言等
3
教材和参考书
? 教材,
– 编译原理。蒋立源，康慕宁主编，西北工业大学出版社，
1999年，第二版。（ 95国家级重点教材）
? 参考书,
– 编译原理与技术。陈意云，中国科大出版社,2002，第二版。
（中科院指定考研参考书、科技大教材）
– 编译原理 。 吕英芝, 张素琴编著, 清华大学出版社, 2003年
8月 。 （ 清华教材 ）
–, 程序设计语言编译原理（第 3版）, 。陈火旺、刘春林等
著，国防工业出版社,2001年 2月。（南大教材）
– 编译程序设计原理。杜淑敏等编著，北京大学出版社。（北
大教材）
4
课程安排（共 48课时）
? 第一章 绪论 2课时
? 第二章 前后文无关文法和语言 6课时
? 第三章 词法分析 8课时
? 第四章 语法分析 12课时
? 复习和习题课 2课时
? 第五章 语法制导翻译及中间代码生成 10课时
5
课程安排（续）
? 第六章 符号表及出错处理 自学
? 第七章 存储组织与管理 2课时
? 第八章 代码优化 略
? 第九章 目标代码生成 4课时
? 第十章 查错与改错 自学
? 总复习 2课时
6
考核方式
? 课后作业 30分
? 期末考试 70分
? 认真听课能使你事半功倍！
? 独立完成作业对取得好成绩至关重要！
7
第一章 绪论
计算机的软硬件组成
中央处理机
输入 /输出处理机等
硬件部分 存储器
通信设备
编译程序, 解释程序, 汇编程序
数据库管理程序 （ DBMS）
系统软件 操作系统 （ OS）
装入, 链接, 编辑程序
软件部分 数据通信系统
应用软件
8
程序设计语言
? 低级语言,机器语言（二进制代码）、汇编语言（直
接操作寄存器、多种寻址方式）及其它面向机器的程
序设计语言；其特点对计算机的依赖性强、直观性差、
编写程序的工作量大，对程序设计人员要求较高。
? 机器语言 符号汇编语言 宏汇编语言
? 高级语言,具有很强的算法描述能力，其编写和调试
效率也比低级语言优越得多。现有上百种 高级语言,
常用的有 BASIC,FORTRAN,PASCAL,C,C++、
JAVA等。
9
编译技术的产生
? FORTRAN,ALGOL 和 COBOL
? FORTRAN(FORmulaTRANslation) 公式翻译
语言是五十年代初期产生第一个实用的高
级语言
1954-1959年 FORTRAN语言及编译系
统产生标志着编译技术开始形成
10
ALGOL和 COBOL
? ALGOL(ALGOkithmic Language)
国际代数语言
ALGOL58 ALGOL60
采用 BNF范式形式化的语言描述体系
促进了语法分析及理论的研究
语言格式影响程序设计语言的发展
? COBOL
引入了独立于机器的数据描述概念
导致了数据库管理系统的产生
11
PASCAL,PROLOG
? PASCAL
由 ALGOL60研究小组研制的用于教学与编写系统软
件的语言
继承了 ALGOL60的描述方法
对程序验证和结构化程序设计起重要作用
? PROLOG PROgramming in LOGic 法国马赛大学
? C++,Java
? IDE(Interactive Development Environment)
交互式开发环境
12
编译程序
? 高级语言与机器之间有一道“鸿沟”,机器不
能理解也不能直接执行高级语言 ！
? 使该语言能让计算机所理解：翻译或解释。
? 翻译：在计算机中放置一能由计算机直接执行
的翻译程序，它将某程序设计语言（ 源语言 ）
所编写的程序（ 源程序 ）作为加工对象，将其
翻译成为与之等价的另一种语言（ 目标语言 ）
的程序（ 目标程序 ）。
? 编译程序：源语言是高级语言，目标语言是汇
编或机器语言。
13
源程序与目标程序是逻辑等价的
翻译程序
高级语言 机器语言
汇编语言 编译程序
源程序
源语 言
目标程序
目标语 言
逻辑等价
14
执行高级语言程序
? 编译阶段,将源程序编译为目标程序。
? 运行阶段,执行目标程序。在执行时，一般
应有一些辅助子程序配合。如：数据格式转
换、标准函数计算、动态存储分配子程序等
等，由它们构成的子程序库称为 运行系统 。
? 编译系统 =编译程序 +运行系统
15
执行高级语言程序的过程
源程序 P
编
译
阶
段
运
行
阶
段
计算机 A
目标程序 P’
计算机 B
运行结果 S
编译程序
运行程序 数据
16
解释程序
? 高级语言程序 也可通过 解释程序 来执行。
? 解释程序,以源程序为输入，在执行过程中不再产生
目标程序，而是边解释边执行。如 Basic,Java等
? 解释程序 运行效率不高，但结构简单、占用内存少，
易于修改。
? 纯粹的 解释程序 不多见，通常是将编译和解释作某种
程度的结合。
– 翻译为中间语言形式，再解释执行
– 翻译时对频繁出现的结构产生目标代码
17
解释程序工作过程
计算机
解释程序 源程序 计算结果
初始数据
18
1.1 编译过程概述
? 翻译外文书刊与编译工作比较
翻译外文书刊 编译源程序
分析
阅读原文
识别单词
分析句子
输入并扫描源程序
词法分析
语法分析
综合 修辞加工 写出译文 代码优化 目标代码生成
编译程序的特有工作：中间代码生成，信息表的构
造与查询，运行时存储空间的分配，出错处理等
19
编译程序 的构成
? 编译程序主要由八个部分构成,
1.词法分析 程序（ 扫描器 scanner）
2.语法分析 程序（ 分析器 parser）
3.语义分析 程序
4.中间代码生成 程序
5.代码优化 程序
6.目标代码生成 程序
7.错误检查和处理 程序
8.各种信息表格的管理 程序
20
1.2 编译程序 的 逻辑结构
源
程
序
词
法
分
析
程
序
中
间
代
码
生
成
代
码
优
化
程
序
目
标
代
码
目
标
代
码
生
成
语
法
分
析
程
序
语
义
分
析
程
序
错误检查和处理程序
信息表管理程序
21
一个微型 PASCAL语言的定义
? 它只有如下四种语句,
1） PROGRAM语句；
2）说明语句；
3） BEGIN-END语句；
4）赋值语句；
? 每个 PASCAL/M语句 都
以 PROGRAM语句开头，
后跟说明语句，再跟以
一个 BEGIN-END语句，
在其内部可以有若干赋
值语句。
PROGRAM source;
{This little source program is
used to illustrate compiling
procedure }
VAR x,y,z:integer;
a:integer;
BEGIN
{ This program has only 4
statement }
x:=23+5;
z:=x DIV -3;
y:=z+18*3;
a:=x+(y-2) DIV 4;
END,
22
1.2.1 词法分析程序（ 扫描器 ）
? 词法分析程序 的任务是,
1）识别出源程序的各个基本语法单位（单词或语法符号）
2）删除无用的空白字符及其它与输入介质相关的非实质
性字符（空格、回车等）
3）删除注释
4）进行词法检查，报告所发现的错误
? 扫描器需要根据当前查看字符的种类，并参考扫描过程
中已得到的信息，判断该字符在源程序中所处位置,
1）正处理的注释中的一个字符； 2）无用字符； 3）下
一个单词的首字符； 4）正识别的单词中的一个字符； 5）
不合法的字符。
23
源程序 source的扫描器输出
PROGRAM source;
{This little source program is used
to illustrate compiling
procedure }
VAR x,y,z:integer;
a:integer;
BEGIN
{ This program has only 4
statement }
x:=23+5;
z:=x DIV -3;
y:=z+18*3;
a:=x+(y-2) DIV 4;
END,
? 输出以单词为单位的单词
流
? 例如，以特殊符号,#”分
隔的单词流,
# PROGRAM # source # ;
# VAR # x #,# y #,# z
#, # integer # ; # a #, #
integer # ; # BEGIN # x
#,= # 23 # + # 5 # ; # z
#,= # x # DIV # - # 3 # ; #
y #,= # z # + # 18 # * # 3
# ; # a #,= # x # + # ( # y
# - # 2 # ) # DIV # 4 # ; #
END #, #
24
单词流的 内部表示
? 注意,前面的单词流形式是为便于阅读而假定的形式。
? 为了让计算机能够方便地识别和使用,常用方法是将
单词在计算机内部表示为一个有序对 (Class,Value)。
? Class为一整型数，用于标识该单词的类别；
? Value用于存放单词的值。
? 例如对于 source程序，可将其单词分为四类：（ 1）保
留字（ 2）专用符号（ 3）标识符（ 4）整数 。这样，
source程序相应的单词流为,
(1,‘PAROGRAM’) (3,’source’) (2,’;’) (1,’VAR’)
(...) … … (2,’;’) (1,’END’) (2,‘.’)
25
1.2.2 语法分析程序（ 分析器 ）
? 语法分析程序 以词法分析程序输出的单词流
为输入，分析源程序的结构，判断它是否为
相应程序设计语言的合法程序。
? 方法,试图为源程序构造一棵完整的 语法树 。
若成功，则说明输入串合乎语法；否则说明
源程序中存在错误。
? 语法树：一个有标记的有序树形结构，叶子
上的标记是程序中的单词，内部节点上的标
记是语法范畴（语法变量名）。
26
1.2.2 语法分析程序（ 续 ）
? 语法分析工作是在相应程序设计语言的 语法
规则 指导下进行的。 语法规则描述了该语言
的各种语成份的组成结构 。
– 前后文无关文法（ CFG）,Backus-Naur范
式（ BNF）
27
1.2.3 语义分析程序
? 语法特征 描述 各语法成份的形式或结构 ；
? 语义特征 描述 各语法成份的 含义 与 功能, 即规定它们
的属性或在执行应进行的运算或操作。
? 只有进行了 语义分析, 才能 让计算机知道应进行何操
作或运算。
? 在进行 语义分析 时还应进行相应的 语义检查 （运算时
类型匹配、类型的矛盾说明、参数匹配等）。
? 语义处理尚无公认的方法来系统地描述。当前较通用
的方法是半机械化的,语法制导翻译,方法。
28
1.2.4 中间代码生成
? 为了处理方便和便于代码优化，
在语义分析后通常并不直接产生
目标代码，而是生成介于二者之
间的 中间代码 。
? 常见的 ~有,逆波兰式、三元式、
四元式及树形结构等 。
? 例如,source程序中的第四条赋
值语句相应的逆波兰式（算符的
后缀表示）可写成,a x y 2 - div +
:= (a,= x + (y-2) div 4)。
? source程序相应的四元式表示为,
(prologue,’source’)
(add,’23’,’5’,T)
(store,T,,’x’)
(div,’x’,’-3’,T)
(store,T,,’z’)
(mult,‘18’,’3’,T)
(add,’z’,T,T)
(store,T,,’y’)
(sub,’y’,’2’,T)
(div,T,’4’,T)
(add,’x’,T,T)
(store,T,,’a’)
(epilogue)
29
1.2.5 代码优化程序
? 代码优化 的 目的 是 生成质量较高的目标代码
? 衡量质量的标准,空间指标 和 时间指标
? 优化方法分类,
– 与机器有关和与机器无关
– 局部优化和全局优化
? 以增加编译程序本身的时空复杂度和可靠性
为代价
? 优化指标有时是相互矛盾的，应根据具体情
况进行取舍和侧重
30
source程序的优化结果
(prologue,’source’)
(add,’23’,’5’,T)
(store,T,,’x’)
(div,’x’,’-3’,T)
(store,T,,’z’)
(mult,‘18’,’3’,T)
(add,’z’,T,T)
(store,T,,’y’)
(sub,’y’,’2’,T)
(div,T,’4’,T)
(add,’x’,T,T)
(store,T,,’a’)
(epilogue)
(prologue,’source’)
(store,28,,’x’)
(div,’x’,’-3’,T)
(store,T,,’z’)
(add,’z’,54,T)
(store,T,,’y’)
(sub,’y’,’2’,T)
(div,T,’4’,T)
(add,’x’,T,T)
(store,T,,’a’)
(epilogue)
31
1.2.6 目标代码生成程序
? 任务,将中间代码翻译成为目标程序
? 目标代码生成程序的设计,
– 首先确定源语言各种语法成份的 目标代码结构，
即源语言或中间语言的每一结构所对应的机器
指令组或汇编语句组，称之为框架,其中包含
待定成分。
– 再根据需要制定中间代码到目标代码的 翻译策
略和算法,要求目标代码具有较高的执行效率。
? 生成尽可能短的目标代码
? 充分发挥计算机可用资源的效率，如寄存器和执
行速度快的指令
32
目标代码生成程序（续）
– 编写目标代码生成程序，对具体机器的依赖性很
强，需具体情况具体分析
? 通常，目标代码的三种形式,
（ 1）具有 绝对地址 的 机器指令代码，在内存中有固定
的存放位置，可立即运行 ；
（ 2） 汇编语言 形式的目标程序，须经汇编程序进行汇
编，以生成机器代码；
（ 3） 模块结构 的机器指令（浮动地址），须经连接程
序将它们和另外的运行子程序连接装配后才能运行。
? Source程序对应的 80386汇编程序见书中 P9
33
1.2.7 错误检查和处理程序
? 程序中出现错误是难免的 。一完善的编译程序应具有
强大的查错能力，并能准确地报告源程序中错误的种
类及位置。
? 除报错外，编译程序还可生成一些另外的 注释信息,
它有助于程序设计人员调试程序。
? 常见的辅助手段
– 输出,对照图,,Source程序的对照图，见 P10表 1-2
– 输出各变量的值
? 没有统一的方法系统的解决程序诊断的问题
– 在编译系统的各部分插入一些程序段落，段落的总体
组成了编译系统的错误检查和处理程序
34
1.2.8 信息表管理程序
? 编译过程中，需经常收集、记录或查询程序中所出现
的各种量的有关 属性 （信息）。
? 为此，编译程序需要建立一批不同用途的 表格 （常数
表、变量表、关键字表等）
? 除此之外，根据不同的分析方法，编译程序还保持一
些专用的表格（ LL分析表,LR分析表、状态矩阵等）
? 合理地组织各种表格，恰当地选用相应的造表和查表
算法是提高编译程序工作效率的有效途径
35
1.3 编译程序的组织
开始
语法分析
程序
整理目标程序
停机
目标程序
源程序
词法分析
程序
取单词
送单词
语义分析及
代码生成程序
语法构造
返回
单遍扫描的编译过程
36
多边扫描的编译过程
? 多遍扫描：编译程序划分为若干个相继执行
的模块，每一模块对前一模块的输出进行一
遍扫描，并将处理的结果提供给下一模块。
? 如何确定扫描的遍数，如何组织各遍扫描中
的工作取决于源程序的具体情况以及编译程
序运行的具体环境。
? 多遍扫描的优点
– 各遍扫描的功能相对独立，编译程序结构清晰
– 有利于进行细致、充分的代码优化处理
– 有利于采用覆盖技术，减少编译程序占用的内存
空间
37
本章内容结束
