,编译原理,课程信息
教学目的与要求：
编译程序是现代计算机系统的基本组成部分之一。本课程重点讲述编译程序的设计原理和常用实现技术。通过课程的学习和实验的完成,应该 清楚的理解一个编译程序是如何工作的；如果在以后遇到了任何一个程序设计语言,应该 知道如何实现这个语言的多数机制； 应 具有一定的使用编译构造工具开发编译程序的经验； 会 将所学的常用技术和算法应用于类似的软件的设计和实现中。
课程架构：
1 理论和实践并重的课程
2 理论部分的题目出现于书面练习，课堂小测和期末考试
3 实践题目（ Project）
– Project1,用高级语言（ C或 Pascal）实现扩充的 PL/0编译程序
– Project2,使用编译构造工具实现面向对象语言 Tool的编译程序
– Project3,使用编译构造工具实现扩充的 PL0编译程序
– Project4,用 GCC裁制一个编译器（任选）
4 各部分权重
– 书面练习抽查
– 课堂小测（两次） 10%
– 实践 20%或 35% （必做,Project1占 10%； 选做,Project2占
25%,Project3占 10% ；任选,Project4待定）
– 期末考试 70%或 55%
教材及主要参考书
教材：,编译原理,（第 2版），张素琴、
吕映芝、蒋维杜、戴桂兰，清华大学出版社
2004
参考书：,Compilers,Principles,
Technigues,and Tools,Alfred V.Aho,
Ravi Sethi,Jeffrey D.Ullman,Addison-
Wesley,1986,影印版：人民邮电出版社，
2001
参考书,,程序设计语言 编译原理,（第 3
版），陈火旺、刘春林等，国防工业出版社
2000
教学内容
1 编译程序概述编译程序是现代计算机系统的基本组成部分之一,编译程序一般由词法分析程序，语法分析程序，语义分析程序，中间代码生成程序，目标代码生成程序，代码优化程序，符号表管理程序和错误处理程序等成分构成。本章概要介绍编译成分的主要功能以及编译阶段的逻辑关系。
2 PL/0 编译程序剖析给出一个简单的类 Pascal语言，其编译程序用高级语言（ C和 Pascal）实现。通过剖析该高级语言程序以理解各编译成分的功能及手工实现方法。
教学内容
3 高级语言的认识要学习和构造编译程序，理解和定义程序设计语言是必不可少的。每个程序设计语言都有一定的规则用以规定合适程序的语法结构，也需要有对一个程序的含义的描述。上下文无关文法给出程序设计语言的精确的,易于理解的语法说明。尚没有公认的形式系统描述程序含义，但也有流行的描述语义规则的方法 —
属性文法。
4 词法分析程序的自动构造词法分析程序是编译程序的一个构成部分，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。正则表达式和有穷状态自动机分别作为单词的描述工具和识别机制，成为词法分析程序的自动构造原理，学习 Lex（ Flex）工具的使用方法。
教学内容
5 语法分析程序的构造
自顶向下的语法分析。可以看作是为一个输入串寻找一个最左推导的过程,也等价于从根开始,按前序生成结点，为输入串构造分析树的过程。讨论一种有效的无回溯的自顶向下分析程序,这种分析程序称为预测分析程序。介绍对于一个文法类,LL（ 1）文法,如何自动的构造预测分析程序。
自底向上（自下而上）语法分析方法，也称移进 -归约分析法。它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移进边分析，一旦栈顶符号串形成可归约串，就用相应非终结符代替可归约串，这称为一步归约，重复这一过程，直到归约到栈中只剩文法的开始符号时，则为分析成功，并确认输入串是文法的句子。本章介绍
LR分析法，分析过程中归约的是当前句型的句柄，
称为规范归约。重点讲解 LR类（ LR（ 0）,SLR
（ 1）,LALR（ 1）,LR（ 1））文法的分析表的构造原理。
教学内容
6 语义分析和中间代码生成在词法分析和语法分析之后，编译程序下一个逻辑阶段的任务是语义分析和生成中间代码。引入属性文法和语法制导的翻译的概念，
介绍中间代码的形式，针对一些语法成分讨论相应语义处理工作的描述。
7 符号表介绍符号表的一般组织和使用方法，讨论分程序结构语言的名字作用域分析及符号表设计方案。
教学内容
8 运行时的存储组织和管理编译的最终目标是生成目标程序。在目标代码生成前，编译程序必须对目标程序运行时的数据空间进行组织和安排,介绍目标程序运行时的数据空间的存储分配策略，说明程序设计语言本身关于名称的作用域和生存期的规则与存储分配策略的关系，重点讨论栈式动态存储方案,
教学内容
9 代码优化和目标代码生成代码优化是对代码作一些等价变换，以使得最后生成的目标代码更为高效。介绍优化技术，优化分类以及优化工作的基础－控制流和数据流分析问题。
编译的最后一个逻辑阶段是目标代码生成。
目标代码生成程序的设计细节要考虑目标语言和操作系统的特点。讨论目标代码生成程序设计的一般问题，包括指令选择，寄存器分配和计算顺序选择。
教师联系信息张素琴 电话 62785601
办公室 东主楼 10-207
zsq-dcs@tsinghua.edu.cn
董渊 电话 62794240
办公室 东主楼 10-209
dongyuan@tsinghua.edu.cn
王生原 电话 62794240
办公室 东主楼 10-209
wwssyy@tsinghua.edu.cn
课程相关资料相关资料放在 ftp://166.111.68.86，帐号和密码都是 compiler05。
第 1章 概述
1.1 什么是编译程序
1.2 程序设计语言的实现
1.3 处理源程序的软件工具
1.4 编译技术的发展
1.1什么是编译程序 (compiler)
编译程序是现代计算机系统的基本组成部分,
从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言 (称作源语言 )书写的程序翻译成另一种语言 (称作目标语言 )的等价的程序,
什么是编译程序功能术语编译程序的源语言 (源程序 )
编译程序的目标语言
(目标程序 )
编译程序的实现语言
S O
I
高级语言书写的程序编译程序 低级语言程序
S T
I
什么是编译程序
分类
– 软件
– 系统软件
– 语言处理系统操作系统编译系统裸机分类
软件：计算机系统中的程序及其文档
系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。
语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。
软件语言：用于书写软件的语言。它主要包括需求定义语言，
功能性语言，设计性语言，程序设计语言以及文档语言。
什么是编译程序
语言转 (变）换系统
C++编译器C++ C
Java BytecodeJava编译器术语
编译程序 (compiler)
编译程序的源语言 (源程序 ) (source
language)(source program)
编译程序的目标语言 (目标程序 ) (object or
target language)(object or target program)
编译程序的实现语言 (implementation
language)
语言处理程序 (language processor)
语言转（变）换 (language transformation)
编译逻辑过程
词法分析
语法分析
语义分析
中间代码生成
代码优化
目标代码生成词法分析 — 第一步识别单词英文句子由单词构成
This line is a longer sentence.
（字母组成的有集体含义的最小成分）
句子开头的单词第一个字母要大写
空格是单词分隔符
句点是句子结尾
ist his linealo gerse nte nce.
词法分析从左至右扫描字符流的源程序、分解构成源程序的字符串，识别出 (拼 )一个个的单词（符号）
单词符号是语言中具有独立意义的最基本结构。多数程序语言中，单词符号一般包括 — 各类型的常数、保留字、标识符、运算符、界符等等。
例如
double f = sqrt(-1);
词法分析
double f = sqrt(-1);
TDOUBLE (“double”)
TIDENT (“f”)
TOP (“=“)
TIDENT (“sqrt”)
TLPAREN (“(“)
TOP (“-”)
TINTCONSTANT (“1”)
TRPAREN (“)”)
TSEP (“;”)
词法分析
词法分析 (lexical analysis or scanning)
--The stream of characters making up
a source program is read from left to
right and grouped into tokens,which
are sequences of characters that
have a collective meaning.
单词 ---token
保留字 ---reserved word
标识符 ---identifier(user-defined name)
例
程序文本 If x = y then z,= 1 else z,= 2;
经词法分析，变成一个个单词
if,x,=,y,then,z,
,=,1,else,z,:=,2,;
语言的单词符号是由词法规则所确定的。
词法规则规定了字母表中哪样的字符串是一个单词符号。
词法分析
position,= initial + rate * 60;
单词类型 单词值标识符 1(id1) position
算符 (赋值 ),=
标识符 2(id2) initial
算符 (加 ) +
标识符 3(id3) rate
算符 (乘 ) *
整数 60
分号 ；
语 法分析 Syntax Analysis
功能,层次分析,依据 源程序的 语法规则 把源程序的单词序列组成语法短语 (表示成语法树 ).
也 称为 ―parsing‖
使用 context-free grammars
结构 上的合法性 Structural validation
（可生成语法树或推导 Creates parse tree
or derivation）
This line is a longer sentencep r o n o u n n o u n v e r b a r t i c l e a d j e c t i v e
s u b j e c t
n o u n
o b j e c t
s e n t e n c e
T h i s l i n e i s
a l o n g e r
s e n t e n c e
分析程序成分 G
t h e n - s t m t
a s s i g n a d j e c t i v e
p r e d i c a t e e l s e - s t m t
I f - t h e n - e l s e
x =
y Z 1 2Z
double f = sqrt(-1);
―sqrt(-1)‖的 推导
Expression
FuncCall
TIDENT TLPAREN Expression TRPAREN
TIDENT TLPAREN UnaryExpression TRPAREN
TIDENT TLPAREN TOP Expression TRPAREN
TIDENT TLPAREN TOP TINTCONSTANT TRPAREN
规则
Expression -> UnaryExpression
Expression -> FuncCall
Expression -> TINTCONSTANT
UnaryExpression -> TOP Expression
FuncCall -> TIDENT TLPAREN Expression TRPAREN
double f = sqrt(-1);
的 Parsing？
语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位）
语法分析
又例：
position,= initial + rate * 60 ;
（ Pascal）规则
<赋值语句 >::=<标识符 >,:=” <表达式 >
<表达式 >::=<表达式 >,+” <表达式 >
<表达式 >::=<表达式 >,*” <表达式 >
<表达式 >::=,(” <表达式 >,)”
<表达式 >::=<标识符 >
<表达式 >::=<整数 >
<表达式 >::=<实数 >
赋值语句标识符 表达式表达式 +
表达式 表达式标识符 整数标识符
:=
表达式
*
id1:=id2+id3*N
:=
+
N
60
*
id1
Positionid2
initial
id3
rate
语法分析
语法分析 (syntax analysis or parsing)
The purpose of syntax analysis is to determine
the source program’s phrase structure.This
process is also called parsing.The source
program is parsed to check whether it
conforms to the source language’s syntax,and
to construct a suitable representation of its
phrase structure.
语法树 (推导树 )(parse tree or derivation
tree)
语义分析
句子的结构理解了，扑捉它的“含义”
如：杰克说杰瑞把他的作业落在了家里。
“他的”是谁的？
又：杰克说杰克把他的作业落在了家里。
几个杰克？
语义分析
杰克把她的作业落在了家里。
（杰克是男生）“杰克”和“她的”不一致。
“杰克”和“他的”才匹配程序设计语言靠严格的约束规则解决二义。
{
int jack=3;
{
int jack=4;
cout << jack;
}
}
语义分析进一步分析语法结构正确的程序是否符合源程序的上下文约束、运算相容性等规定 。
审查静态语义
– 使用的变量声明了吗？
– 允许操作的运算对象吗？
– 类型正确吗？
– …
例,Program p();
Var rate:real;
procedure initial;
…
position,= initial + rate * 60
/* error */ /* error */ /* warning */;
…
Program p();
Var rate:real;
Var initial,real;
Var position,real ;
…
position,= initial + rate * 60
/*warning*/
语义分析 (处理）
60
:=
+
*
Id1
positionId2
initial
Id3
rate
inttoreal
语义分析（语言的规定和实现）
int arr[2],c;
c = arr * 10;
语义分析
语义分析 (semantic analysis)
The parsed program is further analyzed
to determine whether it conforms to the
source language’s contextual
constraints:scope rules,type rules
e.g,To relate each applied occurrence of
an identifier in the source program to
the corresponding declaration,
中间代码（中间表示）生成 (翻译）
源程序的内部 (中间 )表示三元式、四元式,P-Code,C-Code、
U-Code,bytecode
( * id3 t1 t2 )
t2 = id3 * t1
t2,= id3 * t1
id1:= id2 + id3 * 60
(1) (inttoreal,60 - t1 )
(2) (*,id3 t1 t2 )
(3) (+,id2 t2 t3 )
(4) (:=,t3 - id1 )
翻译 为中间代码
Three-address codej = 2 * i + 1;if (j >= n)
j = 2 * i + 3;
return a[j]; t1 = 2 * i
t2 = t1 + 1
j = t2
t3 = j < n
if t3 goto L0
t4 = 2 * i
t5 = t4 + 3
j = t5
L0,t6 = a[j]
return t6
中间代码 (intermediate code)
Intermediate code is a intermediate
representation of the source program,
We want this representation （ intermediate
representation） to be easy to generate,and
easy to translate into the target program.
The representation can have a variety of forms,
a common one is called three-address code
or 4- tuple code.
不同层次的中间代码源语言
（高级语言）
中间代码
（高级）
中间代码
（中级）
中间代码
（低级）
float a[10][20];
a[i][j+2];
t1 = a[i,j+2] t1 = j + 2
t2 = i * 20
t3 = t1 + t2
t4 = 4 * t3
t5 = addr a
t6 = t5 + t4
t7 = *t6
r1 = [fp - 4]
r2 = [r1 + 2]
r3 = [fp - 8]
r4 = r3 * 20
r5 = r4 + r2
r6 = 4 * r5
r7 = fp – 216
f1 = [r7 + r6]
代码 优化 Code Optimization应用 一些技术对代码进行变换以使得编译产生的目标代码高效 。
Example（ 中间代码一级）
t1 = 2 * i
t2 = t1 + 1
j = t2
t3 = j < n
if t3 goto L0
t4 = 2 * i
t5 = t4 + 3
j = t5
L0,t6 = a[j]
return t6
t1 = 2 * i
j = t1 + 1
t3 = j < n
if t3 goto L0
j = t1 + 3
L0,t6 = a[j]
return t6
代码优化
id1:= id2 + id3 * 60
(1) (inttoreal 60 - t1 )
(2) ( * id3 t1 t2 )
(3) ( + id2 t2 t3 )
(4) (,= t3 - id1 )
变换?
（ 1） ( * id3 60.0 t1 )
( 2）（ + id2 t1 id1 )
目标 代码生成 Object code generation 生成目标机汇编和机器指令
Example,a in R0,i in R1,n in R2
t1 = 2 * i
j = t1 + 1
t3 = j < n
if t3 goto L0
j = t1 + 3
L0,t6 = a[j]
return t6
sll R1,1,R1
add R1,1,J
cmp J,R2
blt,LL3
add R1,3,J
.LL3,ld [R0+J],Rt
retr
目标代码生成
(*,id3 60.0 t1 )
(+,id2 t1 id1 )
movf id3,R2
mulf #60.0,R2
movf id2,R1
addf R2,R1
movf R1,id1
编译程序的工作
分析 (analysis)和综合 (synthesis)
– 源程序的分析
线性分析
层次分析
语义分析
– 目标程序的综合
编译阶段的划分 前端 （ front end） 和 后端
（ back end） －
— 编译的前端与源语言有关但与目标机无关的那些部分组成
— 编译的后端与目标机有关的那些部分组成
遍（趟） 从头到尾扫描源程序（各种形式）一 遍 (pass)
编译程序结构 (components)
词法分析程序
语法分析程序
语义分析程序
中间代码生成程序
代码优化程序
目标代码生成程序
符号表管理程序
出错处理程序出错处理程序语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理程序符号表
记录源程序中使用的名字
收集每个名字的各种属性信息
– 类型、作用域、分配存储信息
name,I
kind：常量 value,35
name:object
kind：变量 type：实 level,2 add,dx
符号表管理 (登录，查找）
symbol table management
出错处理 (error handling ）
检查错误、报告出错信息、排错、恢复编译工作
(error reporting and error recovery)
1.2程序设计语言的实现有些语言基本通过解释程序 Java的 Bytecode
有些环境同时提供编译程序和解释系统 Lisp
主要的途径有两个,通过编译程序和解释程序编译程序 低级语言程序高级语言程序高级语言程序 解释程序 计算结果编译程序和解释系统如对源程序,… …
b,= 2 ;
a,= b+2 ; 编译程序
write a ;
… …
解释程序直接将 4的值输出（显示）
（ 直接对源程序中的语句进行分析，执行其隐含的操作。）
Int 2
St b
Ld b
add 2
St a
生成代码
J A V A
S O U R C E
(,j a v a )
C L A S S L O A D E R
B Y T E C O D E
V E R I F I R
J A V A
B Y T E
C O D E
(,c l a s s )
J A V A
C L A S S
L I B R A R I E S
H A R D W A R E
C O M P I L E - T I M E
E N V I R O N M E N T
J A V A B Y T E
C O D E S M O V E
L O C A L L Y O R
T H R O U G H
N E T W O R K
编 译 程 序编 译 程 序解 释 程 序
J A V A V I R T U A L M A C H I N E
R U N T I M E E N V O R O N G M E N T
( J A V A P L A T F O R M )
编译程序和解释程序编译程序是一个语言处理程序,它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序,这个二进制代码程序在机器上运行以生成结果,因此通过编译程序使得我们可以先准备好一个在该机器上运行的程序,然后这个程序便会以机器的速度运行,但是在不把整个程序全部都翻译结束之后,这个程序是不能开始运行,也不能产生任何结果的,编译和运行是两个独立分开的阶段,
但在一个交互环境中,不需要将这两个阶段分隔开,编译就不如解释的方法更方便,另一种语言处理程序,解释程序,它不需要在运行前先把源程序翻译成目标代码,也可以让我们实现在某台机器上运行程序并生成结果,
解释程序
是这样一个程序,它接受某个语言的程序并立即运行这个源程序,它的工作模式是一个个的获取,分析并执行源程序语句,一旦第一个语句分析结束,源程序便开始运行并且生成结果,它特别适合程序员交互方式的工作情况,即希望在获取下一个语句之前了解每个语句的执行结果,允许执行时修改程序,
著名的解释程序有 Basic语言解释程序,Lisp语言解释程序,UNIX命令语言解释程序 (shell),数据库查询语言 SQL 解释程序以及 bytecode解释程序,
高级语言解释系统 (interpreter)
功能 让计算机执行高级语言（ basic,lisp,prolog)
与编译程序的不同 1）不生成目标代码
2）能支持交互环境
（同增量式编译系统）
源 程 序初始数据解释程序 计算结果编译程序和解释程序的存储组织也有很大不同
编译程序处理时,在源语言程序被 编译阶段,存储区中要为源程序 (中间形式 )和目标代码开辟空间,要存放编译用的各种各样表格,比如符号表,在 目标代码运行阶段,存储区中主要是目标代码和数据,编译所用的任何信息都不再需要,
解释程序一般是把源程序一个语句一个语句的进行语法分析,转换为一种内部表示形式,存放在源程序区,
比如 BASIC解释程序,将 LET和 GOTO这样的关键字表示为一个字节的操作码,标识符用其在符号表的入口位置表示,因为 解释程序 允许在执行用户程序时修改用户程序,这就要求 源程序,符号表等内容始终存放在存储区中,并且存放格式要设计的易于使用和修改,
编译阶段和运行阶段存储结构编译时 运行时名字表目标代码缓冲区编译用源程序中间表示各种表格目标代码区数据区源程序缓冲区解释系统存储结构解释系统源程序临时工作单元名字表标号表缓冲区
(输入输出 )
栈区语言处理过程
C程序
# include <stdio.h>
# include <stdlib.h>
# define MAX_LINES 75
Enum booleans (FALSE,TRUE);
Main (int argc,char *argv[]*)
…
预处理器编译器汇编器装配连接编辑骨架程序源程序目标汇编程序可重定位机器代码绝对机器码可重定位目标文件库语言处理过程
1.3 处理源程序的软件工具
（ 编译技术的应用）
结构化编缉器
程序分析工具 静态分析动态分析度量工具 结构度量模块接口复杂度
c分析工具 (source insight)
广泛的语言领域 数据库系统查询（ SQL）
脚本语言置标语言 (SGML.HTML.XML)
1.3处理源程序的软件工具
1.语言的结构化编辑器
2.语言程序的调试工具
3.程序格式化工具
4.语言程序测试工具
5.程序理解工具
6.高级语言之间的转换工具
1.语言的结构化编辑器用户可使用该编辑器在语言的语法制导下编制出所需的源程序。
结构化编辑器不仅具有通常的正文编辑器的正文编辑和修改功能，而且还能像编译程序那样对源程序正文进行分析。因此，
结构化编辑器能够执行一些对编制程序有用的附加的任务。例 如，它能够检查用户的输入是否正确，能够自动地提供关键字,
当用户敲入 if后，编辑器立即显示 then并将这两个关键字之间必须出现的条件留给用户输入，并能检查 begin或左括号与 end
或右括号是否相匹配等等。由于结构化编辑器具有上述功能，
既可保证编出的源程序无语法错误，并有统一的可读性好的程 序格式，这无疑将会提高程序的开发效率和质量。
商用产品很多如 Turbo-Edit,Editplus和 Ultraedit等等,很多集成开发环境中里也都包含这种类似的工具,如 Jbuild中就有 JAVA
程序的结构化编辑器,
2.语言程序的调试工具调试是软件开发过程中一个重要环节，结构化编辑器只能解决语法错误的问题，而对一个已通过编译的程序来说，需进一步了解的是程序执行的结果与编程人员的意图是否一致，程序的执行是否实现预计的算法和功能。这种对算法的错误或程序没能反映算法的功能等错误就需用调试器来协助解决。有一种调试 器允许用户使用源程序正文和它的符号来调试,即一行一行的跟踪程序,查看变量和数据结构的变化以进行调试工作,当然,这些符号的信息必须由编译程序提供,调试器的实现可以有很多途径,
其中一种是写一个解释器,以交互的方式翻译和执行每一行,它必须维护其所有的运行时的资源以保证在程序执行期间很容易的 查询不同变量的当前值,如果不想通过解释程序允许编译了的代码调试,编译程序必须在目标代码 (汇编 )生成时同时生成特定的调试信息,比如,关联标识符和它表示的地址的信息,用于无歧义的引用一个声明了多次的标识符的信息等等,调试功能愈强，实现愈复杂，它涉及源程序的语法分析和语义处理技术。
3.程序格式化工具 程序格式化工具分析源程序并以使程序结构变得清晰可读的形式打印出来。例如，注释可以以一种专门的字形出现，且语句的嵌套层次结构可以用缩排方式（齿形结构）表示出来。
4.语言程序测试工具 语言程序的测试工具有两种：静态分析器和动态测试器。
静态分析器 是在不运行程序的情况下对源程序进行静态地分析，
以发现程序中潜在的错误或异常,它对源程序进行语法分析并制定相应表格，检查变量定值与引用的关系。如某变量未被赋值就被引用，或定值后未被引用，或多余的源代码等一些编译程序的语法分析发现不了的错误。
动态测试工具 也是首先对源程序进行分析，在分析基础上将用于记录和显示程序执行轨迹的语句或函数插入到源程序的适当位置,并用测试用例记录和显示程序运行时的实际路径,将运行结果与期望的结果进行比较分析，帮助编程人员查找问题。
5.程序理解工具 对程序进行分析，确定模块间的调用关系，记录程序数据的静态属性和结构属性，并画出控制流程图，帮助用户 理解程序。
6,高级语言之间的转换工具 由于计算机硬件的不断更新换代，更新更好的程序设计语言的推出为提高计算机的使用效率提供了良好条件，然而一些已有的非常成熟的软件如何在新机器新语言情 况下使用呢?为了减少重新编制程序所耗费的人力和时间，就要解决如何把一种高级语言转换成另一种高级语言，乃至汇编语言转换成高级语言的问题。这种转换工作要对被转换的语言进行词法和语法分析，只不过生成的目标语言是另一种高级语言而已。 这与实现一个完整的编译程序相比工作量要少些。
比如,C,PASCAL,FORTRAN到 Ada的翻译器
IBM 4700汇编到 C的转换器
COBOL 到 Java 的编译器
Human-
oriented
language
Computer-
oriented
language
计算模式，语言 范式语言应用领域编译程序万诺曼机体系结构并行体系结构嵌入系统
1.4 编译技术的发展
S O
I
高级程序语言
不同的应用侧重,
数值计算 -- Fortran 系统程序设计 ---C
事务处理 --Ｃ obol VLSI设计 ---VHDL
人工智能 ---Ｐ rolog 其它 ---
大型嵌入式实时处理 ---Ａ da
符号处理 ---Ｓ nobol
语言范型,
强制式语言 ---C,Fortran,Pascal
应用式 (函数式 ） 语言 ---ML,Lisp
基于规则 (逻辑 ） 的语言 ---Prolog,Yacc
面向对象语言 ---Ada,C++,Java
强制式语言（ Imperative Language） 也称过程式语言。
其特点是命令驱动，面向语句，一个强制式语言程序由一系列的语句组成，每个语句的执行引起若干存储单元中的值的改变，这种语言的语法形式通常具有如下形式；
语句 1；
语句 2；
语句 3；
语言执行的解释与万诺曼机的体系结构对应：改变机器状态（内存，各种寄存器和外存的内容）
应用式（函数式）：
应用式语言 （ Applicative Language） 更注重程序所表示的功能,而不是一个语句接一个语句地执行 。 程序的开发过程是从前面已有的函数出发构造出更复杂的函数,对初始数据集进行操作直至最终的函数可以用于从初始数据计算出最终的结果 。
程序执行：
执行一个个函数施用在数据上的变换最终得到的结果
Example,解决八皇后问题 的一段 Haskell98程序：
queen 0 = [[]]
queen (n+1) = [ x,y | y <- queen n,x <- [1..8],safe 1 x y]
safe n x [] = True
safe n x (z,y) = and [x/=z,x/=z +n,x/=z -n,safe (n+1) x y]
--------------------------------------------------------------------------
test = queen 8
len = length test --92 right answer!
基于规则的语言 ( Rule-based Language)这类语言的语法形式通常为：
条件 1? 动作 1
条件 2? 动作 2
条件 3? 动作 3
程序的执行过程是：检查一定的条件，当它满足值，则执行适当的动作。它也称逻辑程序设计语言，因为它的基本允许条件是谓词逻辑表达式。
Example,一个简单的 Prolog程序：
father(a,b);
father(b,c);
grandfather(X,Y):-father(X,Z),father(Z,Y);
grandfather(a,c).
Yes
grandfather(X,c).
X=a
grandfather(X,Y).
X=a,Y=c
面向对象语言：
抽象数据类型支持封装性，继承性和多态性编译技术与体系结构的发展密切相关
CISC （ Complex Instruction Set Computing）
– 传统的编译技术与之伴随
RISC （ Reduced Instruction Set Computing）
– 编译技术与体系结构设计的协同
– 软硬件协同设计
EPIC （ Explicitly Parallel Instruction Computing）
– 现代编译技术的发展推动体系结构的进步
– IA-64 处理器产品系列（ IPF）的上市现代编译技术必须面对应用需求和目标体系结构的多样化
高性能计算（ High Performance Computing）
– 指令级并行（ Instruction Level Parallelism）
– 线程级并行（ Thread Level Parallelism）
– 处理机级并行（ Processor Level Parallelism）
– 系统级并行（ Thread Level Parallelism）
嵌入式计算（ Embedded Computing）
– 需求多样性（实时、资源限制、功耗、多目标）
其它
– 多媒体计算 （ Multimedia Computing）
– 网络计算 （ Network Computing）
– ……
编译技术重要方向
并行编译技术 – 面向高性能计算
交叉编译技术 – 面向嵌入式计算并行编译系统已成为现代高性能计算机系统中一个重要的部分
并行编译系统处理并行程序设计语言实现串行程序并行化,
针对并行体系结构的程序优化
– 针对向量机的向量语言处理、串行程序向量化
– 针对并行多处理机的并行语言处理，串行程序并行化
– 针对流水线，超长指令字、指令延迟槽等硬件结构的指令调度优化，针对分布存储器多处理机的通信优化等并行处理语句举例
Ｃ＝Ａ＊Ｂ
或者
Ｃ （ １：Ｎ ） ＝Ａ （ １：Ｎ ） ＊Ｂ （ １：Ｎ ）
它们等价于循环：
do Ｉ＝Ｉ,Ｎ
Ｃ （ Ｉ ） ＝Ａ （ Ｉ ） ＊Ｂ （ Ｉ ）
Enddo
Parallel
do Ｉ＝Ｉ,T
Ｃ （ Ｉ ） ＝Ａ （ Ｉ ） ＊Ｂ （ Ｉ ）
Enddo
do Ｉ＝ T,Ｎ
Ｃ （ Ｉ ） ＝Ａ （ Ｉ ） ＊Ｂ （ Ｉ ）
Enddo
Endparallel
if ( a>b && c>d && e>f )
s1;
else
s2;
1:a>b
2:c>d
4:s1 5:s2
3:e>f
例：并行比较例：针对体系结构的优化
如 针对 IA-64,将如下语句
if (a>b) then c = c+1 else d = d*e + f
通过编译的优化，可以消除条件语句中的转移指令，
把它转化成预测执行：
pT,pF = CMP (a>b)
if (pT) c = c+1
if (pF) d = d*e + f
成功地消除了转移。此外，还可以利用 IA-64 的
EPIC 特性，把上述后两条指令调度成并行执行。
并行编译系统的程序分析，程序优化和并行代码生成三个部分程序分析－各种并行优化的基础 。
数据依赖关系分析控制依赖并系分析数据流分析,
程序分析的级别对超标量机 ——一般的数据流分析 。
对于提供指令级并行的超长指令字机器,向量机或并行机数据依赖关系分析和控制依赖关系分析分析的范围 ——与并行粒度有关循环级并行 ——分析的对象是循环子程序并行 ——分析子程序之间的关系程序优化
尽可能利用并行硬件能力为目的的各种程序转换 。
减少指令长度和存储访问次数利用向量流水线的向量化,
利用多处理机结构的并行化,
减少流水部件或存储器访问延迟的指令调度并行代码生成包括程序中的并行语法,语义的分析处理,也包括与体系结构相关的目标代码生成 。
与并行语言有关与计算机结构有关向量处理机 ----向量语句组织成向量循环共享存储器多处理机 ---并行循环的迭代划分,以及处理机调度与同步库子程序调用的插入分布存储器大规模并行机 ---数据与计算的分布,
分布数组的地址计算,通信所需的消息传递库子程序调用的插入等 。
计算机提供的并行性越高体系结构越复杂，
编译面临的任务就越多，越困难，这种困难性主要在于针对并行体系结构的向量化，并行化和各种优化中的许多问题都是ＮＰ一完全的问题嵌入式操作系统宿主机操作系统及支撑环境编辑器连接器交叉调试 器仿真器下载器交叉编译 器代码优化 器嵌入式应用嵌入式系统开发环境由于目标机指令系统与宿主机的指令系统不同，
编译程序在宿主机 A上运行，将应用程序的源程序生成目标机 B的代码，这种编译称为交叉编译。
S O
I OA B
交叉编译程序
– 手工
机器语言
汇编
系统程序设计语言
– 自展，交叉编译
– 自动构造工具，如 lex yacc
– 编译基础设施（多源语言多目标机体系结构的编译程序构造和编译技术研究平台）
编译程序的实现方式一些编译基础设施
编译基础设施（ Compiler Infrastructure）
– NCI (National Compiler Infrastructure) project
SUIF (Stanford University)
Zephyr (Virginia University and Princeton University )
– Trimaran compiler infrastructure
IMPACT (UIUC )
CAR (Hewlett Packard Laboratories)
ReaCT-ILP (NYU and GIT)
– GCC
GNU project,everyone can get and maintain freely
A compiler researcher’s view of
Trimaran infrastructure
源语言 1
语法树源语言 n
机器描述文件
m a c h i n e,m d
目标机描述宏文件 t m,h
R T L 表示汇编语言代码语法分析器 1
R T L 生成器语法分析器 n
优化器代码生成机器描述文件
m a c h i n e,m d
目标机描述宏文件 t m,h
…
…
GCC 结构现代编译技术的一些研究领域
一些编译优化相关的研究领域依然为 Hot
topics,如
– Profiling 技术
– 软件流水（ Software Piplines）技术
– 指令调度（ Instruction Scheduling）技术
– 预测（ predication）技术
– 猜测（ suspecting）技术
兴起一些新的 Hot topics,如
– 动态编译（ Dynamic compiling）技术
– 面向嵌入式计算的编译技术
如,Power-ware,Resource-ware 等技术
– 面向安全计算的编译技术技术
如,Certifying Compilation 技术
Thank You
The End of Ch.1,
教学目的与要求：
编译程序是现代计算机系统的基本组成部分之一。本课程重点讲述编译程序的设计原理和常用实现技术。通过课程的学习和实验的完成,应该 清楚的理解一个编译程序是如何工作的；如果在以后遇到了任何一个程序设计语言,应该 知道如何实现这个语言的多数机制； 应 具有一定的使用编译构造工具开发编译程序的经验； 会 将所学的常用技术和算法应用于类似的软件的设计和实现中。
课程架构：
1 理论和实践并重的课程
2 理论部分的题目出现于书面练习，课堂小测和期末考试
3 实践题目（ Project）
– Project1,用高级语言（ C或 Pascal）实现扩充的 PL/0编译程序
– Project2,使用编译构造工具实现面向对象语言 Tool的编译程序
– Project3,使用编译构造工具实现扩充的 PL0编译程序
– Project4,用 GCC裁制一个编译器（任选）
4 各部分权重
– 书面练习抽查
– 课堂小测（两次） 10%
– 实践 20%或 35% （必做,Project1占 10%； 选做,Project2占
25%,Project3占 10% ；任选,Project4待定）
– 期末考试 70%或 55%
教材及主要参考书
教材：,编译原理,（第 2版），张素琴、
吕映芝、蒋维杜、戴桂兰，清华大学出版社
2004
参考书：,Compilers,Principles,
Technigues,and Tools,Alfred V.Aho,
Ravi Sethi,Jeffrey D.Ullman,Addison-
Wesley,1986,影印版：人民邮电出版社，
2001
参考书,,程序设计语言 编译原理,（第 3
版），陈火旺、刘春林等，国防工业出版社
2000
教学内容
1 编译程序概述编译程序是现代计算机系统的基本组成部分之一,编译程序一般由词法分析程序，语法分析程序，语义分析程序，中间代码生成程序，目标代码生成程序，代码优化程序，符号表管理程序和错误处理程序等成分构成。本章概要介绍编译成分的主要功能以及编译阶段的逻辑关系。
2 PL/0 编译程序剖析给出一个简单的类 Pascal语言，其编译程序用高级语言（ C和 Pascal）实现。通过剖析该高级语言程序以理解各编译成分的功能及手工实现方法。
教学内容
3 高级语言的认识要学习和构造编译程序，理解和定义程序设计语言是必不可少的。每个程序设计语言都有一定的规则用以规定合适程序的语法结构，也需要有对一个程序的含义的描述。上下文无关文法给出程序设计语言的精确的,易于理解的语法说明。尚没有公认的形式系统描述程序含义，但也有流行的描述语义规则的方法 —
属性文法。
4 词法分析程序的自动构造词法分析程序是编译程序的一个构成部分，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。正则表达式和有穷状态自动机分别作为单词的描述工具和识别机制，成为词法分析程序的自动构造原理，学习 Lex（ Flex）工具的使用方法。
教学内容
5 语法分析程序的构造
自顶向下的语法分析。可以看作是为一个输入串寻找一个最左推导的过程,也等价于从根开始,按前序生成结点，为输入串构造分析树的过程。讨论一种有效的无回溯的自顶向下分析程序,这种分析程序称为预测分析程序。介绍对于一个文法类,LL（ 1）文法,如何自动的构造预测分析程序。
自底向上（自下而上）语法分析方法，也称移进 -归约分析法。它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移进边分析，一旦栈顶符号串形成可归约串，就用相应非终结符代替可归约串，这称为一步归约，重复这一过程，直到归约到栈中只剩文法的开始符号时，则为分析成功，并确认输入串是文法的句子。本章介绍
LR分析法，分析过程中归约的是当前句型的句柄，
称为规范归约。重点讲解 LR类（ LR（ 0）,SLR
（ 1）,LALR（ 1）,LR（ 1））文法的分析表的构造原理。
教学内容
6 语义分析和中间代码生成在词法分析和语法分析之后，编译程序下一个逻辑阶段的任务是语义分析和生成中间代码。引入属性文法和语法制导的翻译的概念，
介绍中间代码的形式，针对一些语法成分讨论相应语义处理工作的描述。
7 符号表介绍符号表的一般组织和使用方法，讨论分程序结构语言的名字作用域分析及符号表设计方案。
教学内容
8 运行时的存储组织和管理编译的最终目标是生成目标程序。在目标代码生成前，编译程序必须对目标程序运行时的数据空间进行组织和安排,介绍目标程序运行时的数据空间的存储分配策略，说明程序设计语言本身关于名称的作用域和生存期的规则与存储分配策略的关系，重点讨论栈式动态存储方案,
教学内容
9 代码优化和目标代码生成代码优化是对代码作一些等价变换，以使得最后生成的目标代码更为高效。介绍优化技术，优化分类以及优化工作的基础－控制流和数据流分析问题。
编译的最后一个逻辑阶段是目标代码生成。
目标代码生成程序的设计细节要考虑目标语言和操作系统的特点。讨论目标代码生成程序设计的一般问题，包括指令选择，寄存器分配和计算顺序选择。
教师联系信息张素琴 电话 62785601
办公室 东主楼 10-207
zsq-dcs@tsinghua.edu.cn
董渊 电话 62794240
办公室 东主楼 10-209
dongyuan@tsinghua.edu.cn
王生原 电话 62794240
办公室 东主楼 10-209
wwssyy@tsinghua.edu.cn
课程相关资料相关资料放在 ftp://166.111.68.86，帐号和密码都是 compiler05。
第 1章 概述
1.1 什么是编译程序
1.2 程序设计语言的实现
1.3 处理源程序的软件工具
1.4 编译技术的发展
1.1什么是编译程序 (compiler)
编译程序是现代计算机系统的基本组成部分,
从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言 (称作源语言 )书写的程序翻译成另一种语言 (称作目标语言 )的等价的程序,
什么是编译程序功能术语编译程序的源语言 (源程序 )
编译程序的目标语言
(目标程序 )
编译程序的实现语言
S O
I
高级语言书写的程序编译程序 低级语言程序
S T
I
什么是编译程序
分类
– 软件
– 系统软件
– 语言处理系统操作系统编译系统裸机分类
软件：计算机系统中的程序及其文档
系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。
语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。
软件语言：用于书写软件的语言。它主要包括需求定义语言，
功能性语言，设计性语言，程序设计语言以及文档语言。
什么是编译程序
语言转 (变）换系统
C++编译器C++ C
Java BytecodeJava编译器术语
编译程序 (compiler)
编译程序的源语言 (源程序 ) (source
language)(source program)
编译程序的目标语言 (目标程序 ) (object or
target language)(object or target program)
编译程序的实现语言 (implementation
language)
语言处理程序 (language processor)
语言转（变）换 (language transformation)
编译逻辑过程
词法分析
语法分析
语义分析
中间代码生成
代码优化
目标代码生成词法分析 — 第一步识别单词英文句子由单词构成
This line is a longer sentence.
（字母组成的有集体含义的最小成分）
句子开头的单词第一个字母要大写
空格是单词分隔符
句点是句子结尾
ist his linealo gerse nte nce.
词法分析从左至右扫描字符流的源程序、分解构成源程序的字符串，识别出 (拼 )一个个的单词（符号）
单词符号是语言中具有独立意义的最基本结构。多数程序语言中，单词符号一般包括 — 各类型的常数、保留字、标识符、运算符、界符等等。
例如
double f = sqrt(-1);
词法分析
double f = sqrt(-1);
TDOUBLE (“double”)
TIDENT (“f”)
TOP (“=“)
TIDENT (“sqrt”)
TLPAREN (“(“)
TOP (“-”)
TINTCONSTANT (“1”)
TRPAREN (“)”)
TSEP (“;”)
词法分析
词法分析 (lexical analysis or scanning)
--The stream of characters making up
a source program is read from left to
right and grouped into tokens,which
are sequences of characters that
have a collective meaning.
单词 ---token
保留字 ---reserved word
标识符 ---identifier(user-defined name)
例
程序文本 If x = y then z,= 1 else z,= 2;
经词法分析，变成一个个单词
if,x,=,y,then,z,
,=,1,else,z,:=,2,;
语言的单词符号是由词法规则所确定的。
词法规则规定了字母表中哪样的字符串是一个单词符号。
词法分析
position,= initial + rate * 60;
单词类型 单词值标识符 1(id1) position
算符 (赋值 ),=
标识符 2(id2) initial
算符 (加 ) +
标识符 3(id3) rate
算符 (乘 ) *
整数 60
分号 ；
语 法分析 Syntax Analysis
功能,层次分析,依据 源程序的 语法规则 把源程序的单词序列组成语法短语 (表示成语法树 ).
也 称为 ―parsing‖
使用 context-free grammars
结构 上的合法性 Structural validation
（可生成语法树或推导 Creates parse tree
or derivation）
This line is a longer sentencep r o n o u n n o u n v e r b a r t i c l e a d j e c t i v e
s u b j e c t
n o u n
o b j e c t
s e n t e n c e
T h i s l i n e i s
a l o n g e r
s e n t e n c e
分析程序成分 G
t h e n - s t m t
a s s i g n a d j e c t i v e
p r e d i c a t e e l s e - s t m t
I f - t h e n - e l s e
x =
y Z 1 2Z
double f = sqrt(-1);
―sqrt(-1)‖的 推导
Expression
FuncCall
TIDENT TLPAREN Expression TRPAREN
TIDENT TLPAREN UnaryExpression TRPAREN
TIDENT TLPAREN TOP Expression TRPAREN
TIDENT TLPAREN TOP TINTCONSTANT TRPAREN
规则
Expression -> UnaryExpression
Expression -> FuncCall
Expression -> TINTCONSTANT
UnaryExpression -> TOP Expression
FuncCall -> TIDENT TLPAREN Expression TRPAREN
double f = sqrt(-1);
的 Parsing？
语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位）
语法分析
又例：
position,= initial + rate * 60 ;
（ Pascal）规则
<赋值语句 >::=<标识符 >,:=” <表达式 >
<表达式 >::=<表达式 >,+” <表达式 >
<表达式 >::=<表达式 >,*” <表达式 >
<表达式 >::=,(” <表达式 >,)”
<表达式 >::=<标识符 >
<表达式 >::=<整数 >
<表达式 >::=<实数 >
赋值语句标识符 表达式表达式 +
表达式 表达式标识符 整数标识符
:=
表达式
*
id1:=id2+id3*N
:=
+
N
60
*
id1
Positionid2
initial
id3
rate
语法分析
语法分析 (syntax analysis or parsing)
The purpose of syntax analysis is to determine
the source program’s phrase structure.This
process is also called parsing.The source
program is parsed to check whether it
conforms to the source language’s syntax,and
to construct a suitable representation of its
phrase structure.
语法树 (推导树 )(parse tree or derivation
tree)
语义分析
句子的结构理解了，扑捉它的“含义”
如：杰克说杰瑞把他的作业落在了家里。
“他的”是谁的？
又：杰克说杰克把他的作业落在了家里。
几个杰克？
语义分析
杰克把她的作业落在了家里。
（杰克是男生）“杰克”和“她的”不一致。
“杰克”和“他的”才匹配程序设计语言靠严格的约束规则解决二义。
{
int jack=3;
{
int jack=4;
cout << jack;
}
}
语义分析进一步分析语法结构正确的程序是否符合源程序的上下文约束、运算相容性等规定 。
审查静态语义
– 使用的变量声明了吗？
– 允许操作的运算对象吗？
– 类型正确吗？
– …
例,Program p();
Var rate:real;
procedure initial;
…
position,= initial + rate * 60
/* error */ /* error */ /* warning */;
…
Program p();
Var rate:real;
Var initial,real;
Var position,real ;
…
position,= initial + rate * 60
/*warning*/
语义分析 (处理）
60
:=
+
*
Id1
positionId2
initial
Id3
rate
inttoreal
语义分析（语言的规定和实现）
int arr[2],c;
c = arr * 10;
语义分析
语义分析 (semantic analysis)
The parsed program is further analyzed
to determine whether it conforms to the
source language’s contextual
constraints:scope rules,type rules
e.g,To relate each applied occurrence of
an identifier in the source program to
the corresponding declaration,
中间代码（中间表示）生成 (翻译）
源程序的内部 (中间 )表示三元式、四元式,P-Code,C-Code、
U-Code,bytecode
( * id3 t1 t2 )
t2 = id3 * t1
t2,= id3 * t1
id1:= id2 + id3 * 60
(1) (inttoreal,60 - t1 )
(2) (*,id3 t1 t2 )
(3) (+,id2 t2 t3 )
(4) (:=,t3 - id1 )
翻译 为中间代码
Three-address codej = 2 * i + 1;if (j >= n)
j = 2 * i + 3;
return a[j]; t1 = 2 * i
t2 = t1 + 1
j = t2
t3 = j < n
if t3 goto L0
t4 = 2 * i
t5 = t4 + 3
j = t5
L0,t6 = a[j]
return t6
中间代码 (intermediate code)
Intermediate code is a intermediate
representation of the source program,
We want this representation （ intermediate
representation） to be easy to generate,and
easy to translate into the target program.
The representation can have a variety of forms,
a common one is called three-address code
or 4- tuple code.
不同层次的中间代码源语言
（高级语言）
中间代码
（高级）
中间代码
（中级）
中间代码
（低级）
float a[10][20];
a[i][j+2];
t1 = a[i,j+2] t1 = j + 2
t2 = i * 20
t3 = t1 + t2
t4 = 4 * t3
t5 = addr a
t6 = t5 + t4
t7 = *t6
r1 = [fp - 4]
r2 = [r1 + 2]
r3 = [fp - 8]
r4 = r3 * 20
r5 = r4 + r2
r6 = 4 * r5
r7 = fp – 216
f1 = [r7 + r6]
代码 优化 Code Optimization应用 一些技术对代码进行变换以使得编译产生的目标代码高效 。
Example（ 中间代码一级）
t1 = 2 * i
t2 = t1 + 1
j = t2
t3 = j < n
if t3 goto L0
t4 = 2 * i
t5 = t4 + 3
j = t5
L0,t6 = a[j]
return t6
t1 = 2 * i
j = t1 + 1
t3 = j < n
if t3 goto L0
j = t1 + 3
L0,t6 = a[j]
return t6
代码优化
id1:= id2 + id3 * 60
(1) (inttoreal 60 - t1 )
(2) ( * id3 t1 t2 )
(3) ( + id2 t2 t3 )
(4) (,= t3 - id1 )
变换?
（ 1） ( * id3 60.0 t1 )
( 2）（ + id2 t1 id1 )
目标 代码生成 Object code generation 生成目标机汇编和机器指令
Example,a in R0,i in R1,n in R2
t1 = 2 * i
j = t1 + 1
t3 = j < n
if t3 goto L0
j = t1 + 3
L0,t6 = a[j]
return t6
sll R1,1,R1
add R1,1,J
cmp J,R2
blt,LL3
add R1,3,J
.LL3,ld [R0+J],Rt
retr
目标代码生成
(*,id3 60.0 t1 )
(+,id2 t1 id1 )
movf id3,R2
mulf #60.0,R2
movf id2,R1
addf R2,R1
movf R1,id1
编译程序的工作
分析 (analysis)和综合 (synthesis)
– 源程序的分析
线性分析
层次分析
语义分析
– 目标程序的综合
编译阶段的划分 前端 （ front end） 和 后端
（ back end） －
— 编译的前端与源语言有关但与目标机无关的那些部分组成
— 编译的后端与目标机有关的那些部分组成
遍（趟） 从头到尾扫描源程序（各种形式）一 遍 (pass)
编译程序结构 (components)
词法分析程序
语法分析程序
语义分析程序
中间代码生成程序
代码优化程序
目标代码生成程序
符号表管理程序
出错处理程序出错处理程序语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理程序符号表
记录源程序中使用的名字
收集每个名字的各种属性信息
– 类型、作用域、分配存储信息
name,I
kind：常量 value,35
name:object
kind：变量 type：实 level,2 add,dx
符号表管理 (登录，查找）
symbol table management
出错处理 (error handling ）
检查错误、报告出错信息、排错、恢复编译工作
(error reporting and error recovery)
1.2程序设计语言的实现有些语言基本通过解释程序 Java的 Bytecode
有些环境同时提供编译程序和解释系统 Lisp
主要的途径有两个,通过编译程序和解释程序编译程序 低级语言程序高级语言程序高级语言程序 解释程序 计算结果编译程序和解释系统如对源程序,… …
b,= 2 ;
a,= b+2 ; 编译程序
write a ;
… …
解释程序直接将 4的值输出（显示）
（ 直接对源程序中的语句进行分析，执行其隐含的操作。）
Int 2
St b
Ld b
add 2
St a
生成代码
J A V A
S O U R C E
(,j a v a )
C L A S S L O A D E R
B Y T E C O D E
V E R I F I R
J A V A
B Y T E
C O D E
(,c l a s s )
J A V A
C L A S S
L I B R A R I E S
H A R D W A R E
C O M P I L E - T I M E
E N V I R O N M E N T
J A V A B Y T E
C O D E S M O V E
L O C A L L Y O R
T H R O U G H
N E T W O R K
编 译 程 序编 译 程 序解 释 程 序
J A V A V I R T U A L M A C H I N E
R U N T I M E E N V O R O N G M E N T
( J A V A P L A T F O R M )
编译程序和解释程序编译程序是一个语言处理程序,它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序,这个二进制代码程序在机器上运行以生成结果,因此通过编译程序使得我们可以先准备好一个在该机器上运行的程序,然后这个程序便会以机器的速度运行,但是在不把整个程序全部都翻译结束之后,这个程序是不能开始运行,也不能产生任何结果的,编译和运行是两个独立分开的阶段,
但在一个交互环境中,不需要将这两个阶段分隔开,编译就不如解释的方法更方便,另一种语言处理程序,解释程序,它不需要在运行前先把源程序翻译成目标代码,也可以让我们实现在某台机器上运行程序并生成结果,
解释程序
是这样一个程序,它接受某个语言的程序并立即运行这个源程序,它的工作模式是一个个的获取,分析并执行源程序语句,一旦第一个语句分析结束,源程序便开始运行并且生成结果,它特别适合程序员交互方式的工作情况,即希望在获取下一个语句之前了解每个语句的执行结果,允许执行时修改程序,
著名的解释程序有 Basic语言解释程序,Lisp语言解释程序,UNIX命令语言解释程序 (shell),数据库查询语言 SQL 解释程序以及 bytecode解释程序,
高级语言解释系统 (interpreter)
功能 让计算机执行高级语言（ basic,lisp,prolog)
与编译程序的不同 1）不生成目标代码
2）能支持交互环境
（同增量式编译系统）
源 程 序初始数据解释程序 计算结果编译程序和解释程序的存储组织也有很大不同
编译程序处理时,在源语言程序被 编译阶段,存储区中要为源程序 (中间形式 )和目标代码开辟空间,要存放编译用的各种各样表格,比如符号表,在 目标代码运行阶段,存储区中主要是目标代码和数据,编译所用的任何信息都不再需要,
解释程序一般是把源程序一个语句一个语句的进行语法分析,转换为一种内部表示形式,存放在源程序区,
比如 BASIC解释程序,将 LET和 GOTO这样的关键字表示为一个字节的操作码,标识符用其在符号表的入口位置表示,因为 解释程序 允许在执行用户程序时修改用户程序,这就要求 源程序,符号表等内容始终存放在存储区中,并且存放格式要设计的易于使用和修改,
编译阶段和运行阶段存储结构编译时 运行时名字表目标代码缓冲区编译用源程序中间表示各种表格目标代码区数据区源程序缓冲区解释系统存储结构解释系统源程序临时工作单元名字表标号表缓冲区
(输入输出 )
栈区语言处理过程
C程序
# include <stdio.h>
# include <stdlib.h>
# define MAX_LINES 75
Enum booleans (FALSE,TRUE);
Main (int argc,char *argv[]*)
…
预处理器编译器汇编器装配连接编辑骨架程序源程序目标汇编程序可重定位机器代码绝对机器码可重定位目标文件库语言处理过程
1.3 处理源程序的软件工具
（ 编译技术的应用）
结构化编缉器
程序分析工具 静态分析动态分析度量工具 结构度量模块接口复杂度
c分析工具 (source insight)
广泛的语言领域 数据库系统查询（ SQL）
脚本语言置标语言 (SGML.HTML.XML)
1.3处理源程序的软件工具
1.语言的结构化编辑器
2.语言程序的调试工具
3.程序格式化工具
4.语言程序测试工具
5.程序理解工具
6.高级语言之间的转换工具
1.语言的结构化编辑器用户可使用该编辑器在语言的语法制导下编制出所需的源程序。
结构化编辑器不仅具有通常的正文编辑器的正文编辑和修改功能，而且还能像编译程序那样对源程序正文进行分析。因此，
结构化编辑器能够执行一些对编制程序有用的附加的任务。例 如，它能够检查用户的输入是否正确，能够自动地提供关键字,
当用户敲入 if后，编辑器立即显示 then并将这两个关键字之间必须出现的条件留给用户输入，并能检查 begin或左括号与 end
或右括号是否相匹配等等。由于结构化编辑器具有上述功能，
既可保证编出的源程序无语法错误，并有统一的可读性好的程 序格式，这无疑将会提高程序的开发效率和质量。
商用产品很多如 Turbo-Edit,Editplus和 Ultraedit等等,很多集成开发环境中里也都包含这种类似的工具,如 Jbuild中就有 JAVA
程序的结构化编辑器,
2.语言程序的调试工具调试是软件开发过程中一个重要环节，结构化编辑器只能解决语法错误的问题，而对一个已通过编译的程序来说，需进一步了解的是程序执行的结果与编程人员的意图是否一致，程序的执行是否实现预计的算法和功能。这种对算法的错误或程序没能反映算法的功能等错误就需用调试器来协助解决。有一种调试 器允许用户使用源程序正文和它的符号来调试,即一行一行的跟踪程序,查看变量和数据结构的变化以进行调试工作,当然,这些符号的信息必须由编译程序提供,调试器的实现可以有很多途径,
其中一种是写一个解释器,以交互的方式翻译和执行每一行,它必须维护其所有的运行时的资源以保证在程序执行期间很容易的 查询不同变量的当前值,如果不想通过解释程序允许编译了的代码调试,编译程序必须在目标代码 (汇编 )生成时同时生成特定的调试信息,比如,关联标识符和它表示的地址的信息,用于无歧义的引用一个声明了多次的标识符的信息等等,调试功能愈强，实现愈复杂，它涉及源程序的语法分析和语义处理技术。
3.程序格式化工具 程序格式化工具分析源程序并以使程序结构变得清晰可读的形式打印出来。例如，注释可以以一种专门的字形出现，且语句的嵌套层次结构可以用缩排方式（齿形结构）表示出来。
4.语言程序测试工具 语言程序的测试工具有两种：静态分析器和动态测试器。
静态分析器 是在不运行程序的情况下对源程序进行静态地分析，
以发现程序中潜在的错误或异常,它对源程序进行语法分析并制定相应表格，检查变量定值与引用的关系。如某变量未被赋值就被引用，或定值后未被引用，或多余的源代码等一些编译程序的语法分析发现不了的错误。
动态测试工具 也是首先对源程序进行分析，在分析基础上将用于记录和显示程序执行轨迹的语句或函数插入到源程序的适当位置,并用测试用例记录和显示程序运行时的实际路径,将运行结果与期望的结果进行比较分析，帮助编程人员查找问题。
5.程序理解工具 对程序进行分析，确定模块间的调用关系，记录程序数据的静态属性和结构属性，并画出控制流程图，帮助用户 理解程序。
6,高级语言之间的转换工具 由于计算机硬件的不断更新换代，更新更好的程序设计语言的推出为提高计算机的使用效率提供了良好条件，然而一些已有的非常成熟的软件如何在新机器新语言情 况下使用呢?为了减少重新编制程序所耗费的人力和时间，就要解决如何把一种高级语言转换成另一种高级语言，乃至汇编语言转换成高级语言的问题。这种转换工作要对被转换的语言进行词法和语法分析，只不过生成的目标语言是另一种高级语言而已。 这与实现一个完整的编译程序相比工作量要少些。
比如,C,PASCAL,FORTRAN到 Ada的翻译器
IBM 4700汇编到 C的转换器
COBOL 到 Java 的编译器
Human-
oriented
language
Computer-
oriented
language
计算模式，语言 范式语言应用领域编译程序万诺曼机体系结构并行体系结构嵌入系统
1.4 编译技术的发展
S O
I
高级程序语言
不同的应用侧重,
数值计算 -- Fortran 系统程序设计 ---C
事务处理 --Ｃ obol VLSI设计 ---VHDL
人工智能 ---Ｐ rolog 其它 ---
大型嵌入式实时处理 ---Ａ da
符号处理 ---Ｓ nobol
语言范型,
强制式语言 ---C,Fortran,Pascal
应用式 (函数式 ） 语言 ---ML,Lisp
基于规则 (逻辑 ） 的语言 ---Prolog,Yacc
面向对象语言 ---Ada,C++,Java
强制式语言（ Imperative Language） 也称过程式语言。
其特点是命令驱动，面向语句，一个强制式语言程序由一系列的语句组成，每个语句的执行引起若干存储单元中的值的改变，这种语言的语法形式通常具有如下形式；
语句 1；
语句 2；
语句 3；
语言执行的解释与万诺曼机的体系结构对应：改变机器状态（内存，各种寄存器和外存的内容）
应用式（函数式）：
应用式语言 （ Applicative Language） 更注重程序所表示的功能,而不是一个语句接一个语句地执行 。 程序的开发过程是从前面已有的函数出发构造出更复杂的函数,对初始数据集进行操作直至最终的函数可以用于从初始数据计算出最终的结果 。
程序执行：
执行一个个函数施用在数据上的变换最终得到的结果
Example,解决八皇后问题 的一段 Haskell98程序：
queen 0 = [[]]
queen (n+1) = [ x,y | y <- queen n,x <- [1..8],safe 1 x y]
safe n x [] = True
safe n x (z,y) = and [x/=z,x/=z +n,x/=z -n,safe (n+1) x y]
--------------------------------------------------------------------------
test = queen 8
len = length test --92 right answer!
基于规则的语言 ( Rule-based Language)这类语言的语法形式通常为：
条件 1? 动作 1
条件 2? 动作 2
条件 3? 动作 3
程序的执行过程是：检查一定的条件，当它满足值，则执行适当的动作。它也称逻辑程序设计语言，因为它的基本允许条件是谓词逻辑表达式。
Example,一个简单的 Prolog程序：
father(a,b);
father(b,c);
grandfather(X,Y):-father(X,Z),father(Z,Y);
grandfather(a,c).
Yes
grandfather(X,c).
X=a
grandfather(X,Y).
X=a,Y=c
面向对象语言：
抽象数据类型支持封装性，继承性和多态性编译技术与体系结构的发展密切相关
CISC （ Complex Instruction Set Computing）
– 传统的编译技术与之伴随
RISC （ Reduced Instruction Set Computing）
– 编译技术与体系结构设计的协同
– 软硬件协同设计
EPIC （ Explicitly Parallel Instruction Computing）
– 现代编译技术的发展推动体系结构的进步
– IA-64 处理器产品系列（ IPF）的上市现代编译技术必须面对应用需求和目标体系结构的多样化
高性能计算（ High Performance Computing）
– 指令级并行（ Instruction Level Parallelism）
– 线程级并行（ Thread Level Parallelism）
– 处理机级并行（ Processor Level Parallelism）
– 系统级并行（ Thread Level Parallelism）
嵌入式计算（ Embedded Computing）
– 需求多样性（实时、资源限制、功耗、多目标）
其它
– 多媒体计算 （ Multimedia Computing）
– 网络计算 （ Network Computing）
– ……
编译技术重要方向
并行编译技术 – 面向高性能计算
交叉编译技术 – 面向嵌入式计算并行编译系统已成为现代高性能计算机系统中一个重要的部分
并行编译系统处理并行程序设计语言实现串行程序并行化,
针对并行体系结构的程序优化
– 针对向量机的向量语言处理、串行程序向量化
– 针对并行多处理机的并行语言处理，串行程序并行化
– 针对流水线，超长指令字、指令延迟槽等硬件结构的指令调度优化，针对分布存储器多处理机的通信优化等并行处理语句举例
Ｃ＝Ａ＊Ｂ
或者
Ｃ （ １：Ｎ ） ＝Ａ （ １：Ｎ ） ＊Ｂ （ １：Ｎ ）
它们等价于循环：
do Ｉ＝Ｉ,Ｎ
Ｃ （ Ｉ ） ＝Ａ （ Ｉ ） ＊Ｂ （ Ｉ ）
Enddo
Parallel
do Ｉ＝Ｉ,T
Ｃ （ Ｉ ） ＝Ａ （ Ｉ ） ＊Ｂ （ Ｉ ）
Enddo
do Ｉ＝ T,Ｎ
Ｃ （ Ｉ ） ＝Ａ （ Ｉ ） ＊Ｂ （ Ｉ ）
Enddo
Endparallel
if ( a>b && c>d && e>f )
s1;
else
s2;
1:a>b
2:c>d
4:s1 5:s2
3:e>f
例：并行比较例：针对体系结构的优化
如 针对 IA-64,将如下语句
if (a>b) then c = c+1 else d = d*e + f
通过编译的优化，可以消除条件语句中的转移指令，
把它转化成预测执行：
pT,pF = CMP (a>b)
if (pT) c = c+1
if (pF) d = d*e + f
成功地消除了转移。此外，还可以利用 IA-64 的
EPIC 特性，把上述后两条指令调度成并行执行。
并行编译系统的程序分析，程序优化和并行代码生成三个部分程序分析－各种并行优化的基础 。
数据依赖关系分析控制依赖并系分析数据流分析,
程序分析的级别对超标量机 ——一般的数据流分析 。
对于提供指令级并行的超长指令字机器,向量机或并行机数据依赖关系分析和控制依赖关系分析分析的范围 ——与并行粒度有关循环级并行 ——分析的对象是循环子程序并行 ——分析子程序之间的关系程序优化
尽可能利用并行硬件能力为目的的各种程序转换 。
减少指令长度和存储访问次数利用向量流水线的向量化,
利用多处理机结构的并行化,
减少流水部件或存储器访问延迟的指令调度并行代码生成包括程序中的并行语法,语义的分析处理,也包括与体系结构相关的目标代码生成 。
与并行语言有关与计算机结构有关向量处理机 ----向量语句组织成向量循环共享存储器多处理机 ---并行循环的迭代划分,以及处理机调度与同步库子程序调用的插入分布存储器大规模并行机 ---数据与计算的分布,
分布数组的地址计算,通信所需的消息传递库子程序调用的插入等 。
计算机提供的并行性越高体系结构越复杂，
编译面临的任务就越多，越困难，这种困难性主要在于针对并行体系结构的向量化，并行化和各种优化中的许多问题都是ＮＰ一完全的问题嵌入式操作系统宿主机操作系统及支撑环境编辑器连接器交叉调试 器仿真器下载器交叉编译 器代码优化 器嵌入式应用嵌入式系统开发环境由于目标机指令系统与宿主机的指令系统不同，
编译程序在宿主机 A上运行，将应用程序的源程序生成目标机 B的代码，这种编译称为交叉编译。
S O
I OA B
交叉编译程序
– 手工
机器语言
汇编
系统程序设计语言
– 自展，交叉编译
– 自动构造工具，如 lex yacc
– 编译基础设施（多源语言多目标机体系结构的编译程序构造和编译技术研究平台）
编译程序的实现方式一些编译基础设施
编译基础设施（ Compiler Infrastructure）
– NCI (National Compiler Infrastructure) project
SUIF (Stanford University)
Zephyr (Virginia University and Princeton University )
– Trimaran compiler infrastructure
IMPACT (UIUC )
CAR (Hewlett Packard Laboratories)
ReaCT-ILP (NYU and GIT)
– GCC
GNU project,everyone can get and maintain freely
A compiler researcher’s view of
Trimaran infrastructure
源语言 1
语法树源语言 n
机器描述文件
m a c h i n e,m d
目标机描述宏文件 t m,h
R T L 表示汇编语言代码语法分析器 1
R T L 生成器语法分析器 n
优化器代码生成机器描述文件
m a c h i n e,m d
目标机描述宏文件 t m,h
…
…
GCC 结构现代编译技术的一些研究领域
一些编译优化相关的研究领域依然为 Hot
topics,如
– Profiling 技术
– 软件流水（ Software Piplines）技术
– 指令调度（ Instruction Scheduling）技术
– 预测（ predication）技术
– 猜测（ suspecting）技术
兴起一些新的 Hot topics,如
– 动态编译（ Dynamic compiling）技术
– 面向嵌入式计算的编译技术
如,Power-ware,Resource-ware 等技术
– 面向安全计算的编译技术技术
如,Certifying Compilation 技术
Thank You
The End of Ch.1,
