《编译原理 第1章(清华大学)》由会员分享，可在线阅读，更多相关《编译原理 第1章(清华大学)（60页珍藏版）》请在金锄头文库上搜索。
1、编 译 原 理 清华大学计算机系列教材 吕映芝 张素琴 蒋维杜 编著第1章 概述 第2章 PL/0编译系统 第3章词法分析程序的自动构造 第4章文法和语言 第5章自顶向下语法分析LL（1）文法目 录第6章自底向上语法分析、LR分析程序及其自动 构造 第7章 语法制导翻译和中间代码生成 第8章 运行时的存储组织和管理 第9章 代码优化 第10章 代码生成第1章 概 述1.1什么是编译程序 1.2编译过程和编译程序的结构 1.3 编译技术的发展和应用参考书什么是编译程序(compiler)编译程序是现代计算机系统的基本组成部 分.从功能上看，一个编译程序就是一个语言 翻译程序,它把一种语言(称作源
2、语言)书 写的程序翻译成另一种语言(称作目标语 言)的等价的程序. 1.1功能术语编译程序的源语言( 源程序)编译程序的目标语 言(目标程序)编译程序的实现语 言S O I高级语言书写的程序编译程序低级语言程序S T I什么是编译程序分类 软件 系统软件 语言处理系统操作系统编译系 统裸机分类软件：计算机系统中的 程序及其文档 系统软件：居于计算机 系统中最靠近硬件的一 层，其他软件一般都通 过系统软件发挥作用。 他和具体的应用领域无 关，如编译系统和操作 系统等。语言处理系统：把软件 语言书写的各种程序处 理成可在计算机上执行 的程序。 软件语言：用于书写软 件的语言。它主要包括 需求定义语
3、言，功能性 语言，设计性语言，程 序设计语言以及文档语 言。预处理器编译器汇编器装配连接编辑骨架程序源程序 目标汇编程序 可重定位机器代码 绝对机器码可重定位目标文件库语言处理过程什么是编译程序语言转(变）换系统C+编译器C+CJavaBytecodeJava编译器术语编译程序(compiler) 编译程序的源语言(源程序) (source language)(source program) 编译程序的目标语言(目标程序) (object or target language)(object or target program) 编译程序的实现语言(implementation languag
4、e) 语言处理程序(language processor) 语言转（变）换(language transformation)1.2 编译过程和编译程序的结构编译逻辑过程 词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成词法分析从左至右读字符流的源程序、识别(拼)单词例：position := initial + rate * 60;position := initial + rate * 60;单词类型单词值标识符1(id1) position算符(赋值) :=标识符2(id2) initial算符(加) +标识符3(id3) rate算符(乘) *整数 60分号 ；又如一个
5、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
6、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 analys
7、is or parsing) The purpose of syntax analysis is to determine the source programs phrase structure.This process is also called parsing.The source program is parsed to check whether it conforms to the source languages syntax,and to construct a suitable representation of its phrase structure.语法树(推导树)(
8、parse tree or derivationtree)语义分析语义审查(静态语义) 上下文相关性 类型匹配 类型转换例: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 +
9、rate * 60语义分析60:=+*Id1 positionId2 initial Id3 rateinttoreal术语语义分析(semantic analysis)The parsed program is further analyzed to determine whether it conforms to the source languages contextual constraints:scope rules, type rules e.g. To relate each applied occurrence of an identifier in the source pr
10、ogram to the corresponding declaration. 中间代码生成源程序的内部(中间)表示 三元式、四元式、P-Code、C-Code、U -Code、bytecode( * id3t1t2)t2 = id3 * t1 t2 := id3 * t1id1:= id2 + id3 * 60(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1)中间代码生成(intermediate code generation)This is where the intermediate representation
11、 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)(inttoreal60-t1)(2)( * id3t1t2)
12、(3)( +id2t2t3)(4)( :=t3-id1)变换 （1） ( *id360.0t1)( 2）（ + id2 t1id1)代码优化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
13、 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目标代码生成(*,id360.0t1)(+,id2t1id1)movfid3,R2 mulf#60.0,R2 movfid2,R1 addfR2,R1 movfR1,id1符号表管理记录源程序中使用的名字 收集每个名字的各种
14、属性信息 类型、作用域、分配存储信息Const1常量值：35Var1变量类型：实层次：2符号表(symbol table)Symbol table is a data structure which is employed to associate identifiers with their attributes . An identifiers attribute consists of information relevant to contextual analysis,and is obtained from the identifiers declaration.出错处理检查错误、
15、报告出错信息、排错、恢复编 译工作出错处理(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 rec
