《编译原理第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 OI 高级语言书写的程序 编译程序低级语言程序S TI 什么是编译程序什么是编译程序分类软件系统软件语言处理系统操作系统编译系统裸机分类分类软件：计算机系统中的程序及其文档系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。软件语言：用于书写软件
3、的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言。 预处理器编译器汇编器装配连接编辑骨架程序 源程序 目标汇编程序 可重定位机器代码 绝对机器码可重定位目标文件库语言处理过程语言处理过程什么是编译程序什么是编译程序语言转(变）换系统C+编译器C+CJavaBytecodeJava编译器术语术语编译程序(compiler)编译程序的源语言(源程序) (source language)(source program)编译程序的目标语言(目标程序) (object or target language)(object or target program) 编译程序的实
4、现语言(implementation language)语言处理程序(language processor)语言转（变）换(language transformation)1.2 编译过程和编译程序的结构编译过程和编译程序的结构编译逻辑过程词法分析语法分析语义分析中间代码生成代码优化目标代码生成词法分析词法分析从左至右读字符流的源程序、识别(拼)单词例： position := initial + rate * 60;position := initial + rate * 60;单词类型单词类型单词值单词值 标识符1(id1) position 算符(赋值) := 标识符2(id2) ini
5、tial 算符(加) + 标识符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
6、into tokens,which are sequences of characters that have a collective meaning.单词-token保留字-reserved word标识符 -identifier(user-defined name)功能:层次分析.依据依据源程序的语法规则语法规则把源程序的单词序列组成语法短语(表示成语法树).position := initial + rate * 60 ;规则规则 :=“:=” :=“+” :=“*” :=“(”“)” := := := 赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*id1:=id
7、2+id3*N:=+N 60*id1 Positionid2 initialid3 rate术语术语语法分析(syntax analysis 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 co
8、nstruct 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:
9、real; Var initial :real; Var position :real ; position := initial + rate * 60语义分析语义分析60:=+*Id1 positionId2 initialId3 rateinttoreal术语术语语义分析(semantic analysis) The parsed program is further analyzed to determine whether it conforms to the source languages contextual constraints:scope rules, type rule
10、se.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration. 中间代码生成中间代码生成源程序的内部(中间)表示三元式、四元式、P-Code、C-Code、U-Code、bytecode( * id3t1t2)t2 = id3 * t1t2 := id3 * t1id1:= id2 + id3 * 60(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1)中间代码生
11、成中间代码生成(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
12、 code or 4- tuple code.代码优化代码优化id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 变换变换 （1） ( *id360.0t1) ( 2）（ + id2 t1id1)代码优化代码优化t1 = b* c t1 = b* c t2 = t1+ 0 t2 = t1 + t1t3 = b* c a = t2t4 = t2 + t3a = t4代码优化代码优化(code optimization)Intermediate code optimizationThe
13、 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目标代码生成目标代码生成(*,id360
14、.0t1)(+,id2t1id1)movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id1符号表管理符号表管理记录源程序中使用的名字收集每个名字的各种属性信息类型、作用域、分配存储信息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 inf
15、ormation relevant to contextual analysis,and is obtained from the identifiers 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-tim
16、e 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)词法分析程序语法分析程
17、序语义分析程序中间代码生成程序代码优化程序目标代码生成程序符号表管理程序出错处理程序出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理编译阶段的组合编译阶段的组合分析，综合(synthesis)源程序的分析线性分析层次分析语义分析目标程序的综合编译的前端（front end）编译的后端（back end）遍（趟）遍（趟）从头到尾扫描源程序（各种形式）一遍遍(pass)高级语言解释系统高级语言解释系统(interpreter)功能 让计算机执行高级语言（basic,lisp,prolog)与编译程序的不同 1）不生成目标代码 2）能支持交互环境 （同
18、增量式编译系统） 源 程 序 初始数据 解释程序计算结果 解释系统解释系统直接对源程序中的语句进行分析，执行其隐含的操作。如： b := 2 ; a := b+2 ; 编译程序 write a ; 解释程序直接将4的值输出（显示）Int 2St bLd badd 2St a生成代码 编译阶段和运行阶段存储结构编译阶段和运行阶段存储结构 编译时 运行时 名字表目标代码缓冲区编译用源程序中间表示各种表格目标代码区数据区源程序缓冲区解释系统存储结构解释系统存储结构解释系统源程序工作单元名字表标号表缓冲区(输入输出)栈区1.3 编译技术的发展和应用编译技术的发展和应用功能：程序 集成环境实现方式手工机
19、器语言汇编系统程序设计语言自动构造工具lex yacc gccS OI 编译程序的发展编译程序的发展Human-orientedlanguageComputer-orientedlanguage计算模式，语言范式语言应用领域编译程序万诺曼机体系结构并行体系结构嵌入系统 编译程序的发展编译程序的发展语言范型(paradigms)命令式(imperative language)应用式(applicative)基于规则的（rule-based）面向对象的（object-oriented）编译程序执行环境批处理交互环境嵌入系统环境 语言范型（支持的计算模式）语言范型（支持的计算模式） 命令式：程序特点
20、： 语言执行的解释： 编译技术发展快：语句1； 改变机器状态 系统语言语句2； 内存 自动化生成技术语句3； 各种寄存器 的内容 外存 与万诺曼机的 体系结构一般 应用式（函数式）：程序特点： Function n(funetion2(funetion1(data)程序执行： 执行一个个函数施用在数据上的变换最终得到的结果编译： 语法分析容易； 语义处理复杂； 基于规则的语言（prolog,yacc)：程序特点： 使能条件1 动作1 使能条件2 动作2 使能条件3 动作3 面向对象语言： 抽象数据类型，继承机制编译： 动态绑定； 执行环境执行环境批处理环境：将源程序作为整体处理 排除程序错误不
21、能依靠用户的外部帮助交互环境：解释 增量式编译嵌入式系统环境：交叉编译分布并行环境：并行编译程序创建和测试环境： 独立编译 编译和调试同时设计考虑 编译技术的发展和应用编译技术的发展和应用结构化编译器程序分析工具 静态分析 动态分析 度量工具 结构度量 模块接口复杂度 c分析工具(source insight) 广泛的语言领域 数据库系统查询 脚本语言 置标语言(SGML.HTML.XML)研究领域研究领域并行编译技术交叉编译技术硬件描述语言及其编译技术 并行化编译技术并行化编译技术目的：提高并行计算机体系结构的性能。超大规模计算的日益增长的需求 高性能计算机 并行软件并行体系结构单机速度 并
22、行体系结构途径1途径2 并行体系结构 编译技术支持 串行程序并行化编译技术支持 并行程序设计语言编译 依赖于目标机的优化（低层） 性能发挥 并行算法复杂，难掌握，难编程 开发并行 软件的困难 并行程序的不确定行为，难调试，验证设计新的并行算法 修改已有串行程序尽量（直接用并行程序 并行化（研究算法和设计语言和并行程 应用的人同时工作）序库实现。).HPF.Occom. PVM 途径12嵌入式嵌入式交叉编译器交叉编译器由于目标机指令系统与宿主机的指令系统不同，编译由于目标机指令系统与宿主机的指令系统不同，编译时将应用程序的源程序在宿主机上生成目标机代码，时将应用程序的源程序在宿主机上生成目标机代
23、码，称为交叉编译。称为交叉编译。SOIOAB硬件描述语言及其编译技术硬件描述语言及其编译技术电路设计依据 验证结果 如：VHDL 第第1章章 小结小结内容1 什么是编译程序2 编译过程和编译程序的结构3 为什么要学习编译程序本章没有难以理解的内容,重点对编译程序的功能和结构做一综述,要说难点的话可能是:了解编译程序各个成分在编译阶段的逻辑关系以及他们怎样作为一个整体完成编译任务的。 参考书参考书ALFRED V. AHO, RAVISETHI, JEFFREY D. ULLMAN, Compilers Principles, Techniques and Tools ADDISSON-WESL
24、EY 1986这是最经典的一本编译参考书，不要嫌它老！Tomas Pittmn, The art of Compiler Design theory and Practice, Prentice-Hall 1992陈火旺 刘春林等 程序设计语言编译原理 国防工业出版社 2000David 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 1996Bennett, J.P.,Introduction to Compiling techniques: a first course using ANSI C,LEX and YACC.-2nd ed- , The McGRAW-HILL Publishing Company 1996David A. Watt, Programming Language Syntax and Semantics,Prentice Hall 1991
