编译原理
第一章 概述
第二章 PL/0编译系统
第三章词法分析程序的自动构造
第四章文法和语言
第五章自顶向下语法分析
LL( 1) 文法
第六章自底向上语法分析
LR分析程序及其自动构造
第七章 语法制导翻译和中间代码生成
第八章 运行时的存储组织和管理
第九章 代码优化
第十章 代码生成第一章 概述
1.1什麽是编译程序
1.2编译过程和编译程序的结构
1.3 编译技术的发展和应用
参考书什么是编译程序 (compiler)
编译程序是现代计算机系统的基本组成部分,
从功能上看,一个编译程序就是一个语言翻译程序,它把一种语言 (称作源语言 )书写的程序翻译成另一种语言 (称作目标语言 )的等价的程序,
1.1
功能术语编译程序的源语言
(源程序 )
编译程序的目标语言 (目标程序 )
编译程序的实现语言
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)
1.2 编译过程和编译程序的结构
编译逻辑过程
词法分析
语法分析
语义分析
中间代码生成
代码优化
目标代码生成词法分析
从左至右读字符流的源程序、识别 (拼 )单词例:
position,= initial + rate * 60;
词法分析
position,= initial + rate * 60;
单词类型 单词值标识符 1(id1) position
算符 (赋值 ),=
标识符 2(id2) initial
算符 (加 ) +
标识符 3(id3) rate
算符 (乘 ) *
整数 60
分号 ;
又如一个 C源程序片断,int a;
a = a + 2;
词法分析后可能返回,
单词类型 单词值保留字 int
标识符 (变量名 ) a
界符 ;
标识符 (变量名 ) a
算符 (赋值 ) =
标识符 (变量名 ) a
算符 (加 ) +
整数 2
界符 ;
有关术语
词法分析 (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)
语法分析
功能,层次分析,依据 源程序的 语法规则 把源程序的单词序列组成语法短语 (表示成语法树 ).
position,= initial + rate * 60 ;
规则
<赋值语句 >::=<标识符 >,:=” <表达式 >
<表达式 >::=<表达式 >,+” <表达式 >
<表达式 >::=<表达式 >,*” <表达式 >
<表达式 >::=,(” <表达式 >,)”
<表达式 >::=<标识符 >
<表达式 >::=<整数 >
<表达式 >::=<实数 >
赋值语句标识符 表达式表达式 +
表达式 表达式标识符 整数标识符
:=
表达式
*
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)
语义分析语义审查 (静态语义 )
– 上下文相关性
– 类型匹配
– 类型转换例,Program p();
Var rate:real;
procedure initial;

position,= initial + rate * 60
/* error */ /* error */ /* warning */;

又如,
int arr [2],abc;
abc = arr * 10;

Program p();
Var rate:real;
Var initial,real;
Var position,real ;

position,= initial + rate * 60
语义分析
60
:=
+
*
Id1
positionId2
initial
Id3
rate
inttoreal
术语
语义分析 (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 )
中间代码生成 (intermediate code generation)
This is where the intermediate
representation of the source program is
created.We want this representation to
be easy to generate,and easy to
translate into the target program.The
representation can have a variety of
forms,but a common one is called three-
address code or 4- tuple code.
代码优化
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 )
代码优化
t1 = b* c t1 = b* c
t2 = t1+ 0 t2 = t1 + t1
t3 = b* c a = t2
t4 = t2 + t3
a = t4
代码优化 (code optimization)
Intermediate code optimization
The optimizer accepts input in the intermediate
representation and output a version still in the
intermediate representation,In this phase,the
compiler attempts to produce the
smallest,fastest and most efficient running
result by applying various techniques.
Object code optimization
目标代码生成
(*,id3 60.0 t1 )
(+,id2 t1 id1 )
movf id3,R2
mulf #60.0,R2
movf id2,R1
addf R2,R1
movf R1,id1
符号表管理
记录源程序中使用的名字
收集每个名字的各种属性信息
– 类型、作用域、分配存储信息
Const1 常量 值,35
Var1 变量 类型:实 层次,2
符号表 (symbol table)
Symbol table is a data structure which is
employed to associate identifiers with
their attributes,
An identifier’s attribute consists of
information relevant to contextual
analysis,and is obtained from the
identifier’s declaration.
出错处理
检查错误、报告出错信息、排错、恢复编译工作出错处理 (error handling)(error
reporting and error recovery)
The compiler should report the location of
each error,together with some explanation,
The major categories of compile-time error,
syntax error,scope error,type error.
After detecting and reporting an error,the
compiler should attempt error recovery,means
that the compiler should try to get itself into a
state where analysis of the source program
can continue as normally as possible.
编译程序结构 (components)
词法分析程序
语法分析程序
语义分析程序
中间代码生成程序
代码优化程序
目标代码生成程序
符号表管理程序
出错处理程序出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理编译阶段的组合
分析,综合 (synthesis)
– 源程序的分析
线性分析
层次分析
语义分析
– 目标程序的综合
编译的前端( front end)
编译的后端( back end)
遍(趟) 从头到尾扫描源程序(各种形式)一 遍 (pass)
高级语言解释系统 (interpreter)
功能 让计算机执行高级语言( basic,lisp,prolog)
与编译程序的不同 1)不生成目标代码
2)能支持交互环境
(同增量式编译系统)
源 程 序
初始数据解释程序 计算结果解释系统
直接对源程序中的语句进行分析,执行其隐含的操作。
如,… …
b,= 2 ;
a,= b+2 ; 编译程序
write a ;
… …
解释程序直接将 4的值输出(显示)
Int 2
St b
Ld b
add 2
St a
生成代码编译阶段和运行阶段存储结构
编译时 运行时名字表目标代码缓冲区编译用源程序中间表示各种表格目标代码区数据区源程序缓冲区解释系统存储结构解释系统源程序工作单元名字表标号表缓冲区
(输入输出 )
栈区
1.3 编译技术的发展和应用
功能:程序 集成环境
实现方式
– 手工
机器语言
汇编
系统程序设计语言
– 自动构造工具 lex yacc gcc
S O
I
编译程序的发展
Human-
oriented
language
Computer-
oriented
language
计算模式,语言 范式语言应用领域编译程序万诺曼机体系结构并行体系结构嵌入系统编译程序的发展
语言范型 (paradigms)
– 命令式 (imperative language)
– 应用式 (applicative)
– 基于规则的( rule-based)
– 面向对象的( object-oriented)
编译程序执行环境
– 批处理
– 交互环境
– 嵌入系统环境语言范型(支持的计算模式)
命令式:
程序特点,语言执行的解释,编译技术发展快:
语句 1; 改变机器状态 系统语言
语句 2; 内存 自动化生成技术
语句 3; 各种寄存器 的内容
… … 外存与万诺曼机的体系结构一般应用式(函数式):
程序特点:
Function n(…funetion2(funetion1(data))…)
程序执行:
执行一个个函数施用在数据上的变换最终得到的结果编译:
语法分析容易;
语义处理复杂;
基于规则的语言( prolog,yacc):
程序特点:
使能条件 1? 动作 1
使能条件 2? 动作 2
使能条件 3? 动作 3
面向对象语言:
抽象数据类型,继承机制编译:
动态绑定;
执行环境
批处理环境:将源程序作为整体处理
排除程序错误不能依靠用户的外部帮助
交互环境:解释
增量式编译
嵌入式系统环境:交叉编译
分布并行环境:并行编译
程序创建和测试环境,独立编译
编译和调试同时设计考虑编译技术的发展和应用
结构化编译器
程序分析工具 静态分析
动态分析
度量工具 结构度量
模块接口复杂度
c分析工具 (source insight)
广泛的语言领域 数据库系统查询
脚本语言
置标语言 (SGML.HTML.XML)
研究领域
并行编译技术
交叉编译技术
硬件描述语言及其编译技术并行化编译技术
目的:提高并行计算机体系结构的性能。
超大规模计算的日益增长的需求 高性能计算机
并行软件并行体系结构 单机速度 并行体系结构途径
1
途径
2
并行体系结构编译技术支持串行程序并行化编译技术支持 并行程序设计语言编译依赖于目标机的优化(低层)
性能发挥并行算法复杂,难掌握,难编程开发并行软件的困难并行程序的不确定行为,难调试,验证设计新的并行算法 修改已有串行程序尽量
(直接用并行程序 并行化(研究算法和设计语言和并行程 应用的人同时工作)
序库实现。 ).
HPF.Occom,PVM
途径
1 2
– 嵌入式嵌入式操作系统宿主机操作系统及支撑环境编辑器连接器交叉调试 器仿真器下载器交叉编译 器代码优化 器嵌入式应用交叉编译器由于目标机指令系统与宿主机的指令系统不同,编译时将应用程序的源程序在宿主机上生成目标机代码,
称为交叉编译。
S O
I OA B
硬件描述语言及其编译技术
电路设计依据
验证结果如,VHDL
第一章 小结
内容
1 什么是编译程序
2 编译过程和编译程序的结构
3 为 什么要学习编译程序
本章没有难以理解的内容,重点对编译程序的功能和结构做一综述,要说难点的话可能是,了解编译程序各个成分在编译阶段的逻辑关系以及他们怎样作为一个整体完成编译任务的。
参考书
Tomas Pittmn,The art of Compiler Design
theory and Practice,Prentice-Hall 1992
ALFRED V,AHO,RAVISETHI,JEFFREY D,
ULLMAN,Compilers Principles,Techniques and
Tools ADDISSON-WESLEY 1986
陈火旺 刘春林等 程序设计语言编译原理 国防工业出版社 2000
David A Watt & Deryck F Brown Programming
language processors in java (in c,in c++)
compilers and interpreters,Prentice-Hall 2000
参考书
Terrence W.Pratt,Marvin V.Zelkowitz
Programming Languages Design and
Implementation,Prentice-Hall 1996
Bennett,J.P.,Introduction to Compiling
techniques,a first course using ANSI C,LEX
and YACC.-2nd ed-,The McGRAW-HILL
Publishing Company 1996
David A,Watt,Programming Language
Syntax and Semantics,Prentice Hall 1991