编译原理chpt1概述

1、编译原理课程信息编译程序的用途和地位：编译程序的用途和地位：u计算机只直接认识0、1序列u怎么办？配翻译！u回顾回顾: 程序上机过程 高级语言书写的程序 编译程序低级语言程序u地位：计算机（系统及课程体系）的核心、基础。u目标：(1)理解编译程序是如何工作的； (2)对任何一个程序设计语言，如何实现它； (3)编译构造工具的实现及使用； (4)能将常用技术和算法应用于软件的设计和实现中。为什么学习编译？编译是与数据结构、OS等同样重要的基础性课程专业基础能力的四个方面：计算思维、算法设计、程序实现和系统开发在编译中都有较为充分的体现编译程序的构造原理和技术可以说是计算机科学技术中理论和实践相结

2、合的最好典范学习编译才能透彻理解、熟练运用程序设计语言日后科研工作中将长期受益，是优秀专业人员必修课图灵奖获得者Perlis教授的名言“To understand a program you must become both the machine and the program.”。编译有助于你达成这个愿望编写编译器的原理和技术具有十分普遍的意义，以至于在每一个计算机科学家的研究生涯中，它的原理和技术都回反复用到 。措施：作业、提问、上机、测验、讨论、计算思维是什么计算思维是什么n计算思维（计算思维（Computational Thinking）计算思维计算思维是运用计算机科学的基础概念去求

3、解问是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为，它包括了一系题、设计系统和理解人类的行为，它包括了一系列广泛的计算机科学的思维工具列广泛的计算机科学的思维工具 计算思维和阅读、写作和算术一样，是计算思维和阅读、写作和算术一样，是21世纪每世纪每个人的基本技能，而不仅仅属于计算机科学家个人的基本技能，而不仅仅属于计算机科学家计算思维在生物、物理、化学、经济学、统计学计算思维在生物、物理、化学、经济学、统计学等其他学科中的影响已经显现等其他学科中的影响已经显现 n计算思维包括一系列广泛的计算机科学的思计算思维包括一系列广泛的计算机科学的思维方法维方法递归递归抽象和问题分解抽象和

4、问题分解保护、冗余、容错、纠错和恢复保护、冗余、容错、纠错和恢复利用启发式推理来寻求解答利用启发式推理来寻求解答在不确定情况下的规划、学习和调度在不确定情况下的规划、学习和调度课程特点：1 理论和实践并重的课程2 记分方法： 上机(50)平时(20)期末笔试(30)教师联系信息教师联系信息王显荣：电话 4994019-？ 办公室 计算机楼210房间 教材及主要参考书n教材：编译原理（第2版），张素琴、吕映芝等，清华大学出版社 2004n参考书：Compilers: Principles, Technigues, and Tools(Second Edition) Alfred V.Aho, M

5、onica S.Lam, Ravi Sethi, Jeffrey D.Ullman, Addison-Wesley, 2007n参考书:编译原理，陈意云、张昱，高等教育出版社 2003教学内容简介1 编译程序概述 词法分析、语法分析、语义分析、中间代码生成、目标代码生成、代码优化、符号表管理和错误处理等成分。 编译成分的主要功能、编译阶段的逻辑关系？2 PL/0 编译程序剖析通过剖析一个用C语言实现的PL/0语言的编译程序以理解各编译成分的功能及手工实现方法。3 高级语言的认识 理解和定义程序设计语言是学习和构造编译程序的前提。 每个程序设计语言都包含语法和语义两个基本方面。 上下文无关文法给

6、出程序设计语言的精确的,易于理解的语法说明。流行的描述语义规则的方法属性文法。4 词法分析程序的自动构造 词法分析程序的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。 正则表达式和有穷状态自动机分别作为单词的描述工具和识别机制。5 语法分析程序的构造n自顶向下的语法分析。相当于从根开始，按前序生成结点，为输入串构造分析树的过程。讨论预测分析法，介绍对于LL(1)文法, 如何自动构造预测分析程序 n自底向上语法分析法：对输入符号串自左向右扫描，并将输入符依次移入栈中，边移进边分析，一旦栈顶形成可归约串，就将其替换为相应非终结符，重复此过程，直到栈中只剩文法的开始符时，成功结束。

7、n介绍LR分析法，LR分析表的构造原理。6 语义分析和中间代码生成引入属性文法和语法制导翻译的概念，介绍中间代码，针对一些语法成分讨论相应语义处理工作的描述。7 符号表介绍符号表的一般组织和使用方法，讨论分程序结构语言的名字作用域分析及符号表设计方案。8 运行时的存储组织和管理生成目标程序之前，编译程序必须对目标程序运行时的数据空间进行组织和安排。主要讨论栈式存储分配。9 代码优化和目标代码生成介绍优化技术，优化分类以及优化工作的基础控制流和数据流分析问题。将讨论目标代码生成程序设计的一般问题，包括指令选择，寄存器分配和计算顺序选择。目录n第一章 引论n第二章 PL/0编译系统n第三章 词法分

8、析程序及其自动构造n第四章 文法和语言n第五章 预测分析、算符优先分析n第六章 LR分析程序及其自动构造n第七章 语法制导翻译和中间代码n第八章 代码优化n第九章 其它编译技术第1章 概述1.1 编译程序及其结构1.2 程序设计语言的实现途径1.3 编译程序的实现方式1.4 编译技术的应用-处理源程序的软件工具1.5 编译技术的发展一、编译程序的作用u计算机只直接认识0、1序列u它如何处理各种高级语言程序？配翻译！（正如不懂英语的人可通过翻译与说英语的人交谈一样）u回顾回顾: 程序上机过程1.1 编译程序及其结构(compiler) 高级语言书写的程序 编译程序低级语言程序 目标程序汇编语言（

9、符号化的指令系统）、机器语言 源程序pascal、c、易学、易用、易读、易改、易移植n语言转(变)换系统n编译系统的结构、工作流程、设计原理和基本实现技术？C+编译器C+CJavaBytecodeJava编译器操作系统编译系统裸机术语n编译程序(compiler)n编译程序的源语言(源程序) (source language)(source program)n编译程序的目标语言(目标程序) (object or target language)(object or target program) n编译程序的实现语言(implementation language)n语言处理程序(langua

10、ge processor)n语言转（变）换(language transformation)二、编译逻辑过程n词法分析n语法分析n语义分析n中间代码生成n代码优化n目标代码生成从左至右扫描字符流的源程序、分解构成源程序的字符串，拼出一个个的单词 单词符号是语言中具有独立意义的最基本结构。多数程序语言中，单词符号一般包括 各类型的常数、保留字、标识符、运算符、界符等等。n单词-tokenn保留字-reserved wordn标识符 -identifier(user-defined name)词法分析(lexical analysis or scanning) -The stream of cha

11、racters 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. （字母组成的有集体含义的最小成分）语言的单词符号是由词法规则所确定的。词法规则规定了啥样的字符串是一个单词符号position := initial + rate * 60;单词类型单词类型单词值单词值 标识符1(id1) position 算符(赋值) := 标识符2(id2) initial

12、 算符(加) + 标识符3(id3) rate 算符(乘) * 整数 60 分号 ；语法分析(Syntax Analysis or parsing)n功能：层次分析，依据依据源程序的语法规则语法规则把源程序的单词序列组成语法短语(表示成语法树). n结构上的合法性Structural validationThis line is a longer sentence语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位：表达式、语句、子程序等）nposition:=initial + rate * 60 ;结构描述结构描述 :=“:=” :=“+” :=“*” :=“(”“)” := :=

13、 := 赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*id1:=id2+id3*N:=+N 60*id1 Positionid2 initialid3 rate语法分析n语法分析(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 con

14、forms to the source languages syntax,and to construct a suitable representation of its phrase structure.n语法树(推导树)(parse tree or derivation tree)语义分析进一步分析语法结构正确的程序是否符合源程序的上下文约束、运算相容性等规定。审查静态语义 使用的变量声明了吗？ 允许操作的运算对象吗？ 类型正确吗？ 例:Program p();Var rate:real;procedure initial;position := initial + rate * 60

15、/* error */ /* error */ /* warning */; int arr2, c; c = arr * 10;60:=+*Id1 positionId2 initialId3 rateinttorealProgram p(); Var rate:real; Var initial :real; Var position :real ; position := initial + rate * 60 /*warning*/语义分析n语义分析(semantic analysis) The parsed program is further analyzed to determi

16、ne whether it conforms to the source languages contextual constraints:scope rules, type rulese.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration. 中间代码（中间表示）生成(翻译）源程序的中间表示：三元式、四元式、P-Code、bytecode、id1:= id2 + id3 * 60(1)(inttoreal,60-t1)(2)(*,

17、id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1)翻译为中间代码 Three-address codej = 2 * i + 1;if (j = n) j = 2 * i + 3;return aj;t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto L0t4 = 2 * it5 = t4 + 3j = t5L0: t6 = ajreturn t6中间代码(intermediate code) Intermediate code is a intermediate representation of the source progr

18、am . 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.代码优化（Code Optimization）应用一些技术对代码进行变换以使得编译产生的目标代码高效。nExample

19、（中间代码一级）t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto L0t4 = 2 * it5 = t4 + 3j = t5L0: t6 = ajreturn t6t1 = 2 * ij = t1 + 1t3 = j nif t3 goto L0 j = t1 + 3L0: t6 = ajreturn t6id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 变换变换 （1） ( *id360.0t1) ( 2）（ + id2 t1id1)目

20、标代码生成Object code generation 生成目标机汇编或机器指令nExample: a in R0, i in R1, n in R2t1 = 2 * ij = t1 + 1t3 = j 机器语言n编译程序：高级语言-汇编语言或机器语言-笔译n解释程序：边翻译边解释，并不产生目标程序-口译编译程序和解释系统(interpreter)如对源程序： b := 2 ; a := b+2 ; 编译程序编译程序 write a ; 解释程序解释程序 直接将4的值输出（显示）（直接对源程序中的语句进行分析，执行其隐含的操作。）n解释系统 1）不生成目标代码 2）能支持交互环境Int 2St

21、 bLd badd 2St a生成代码编译程序和解释程序n编译程序把一个高级语言程序翻译成某个机器的汇编或二进制代码程序, 这个二进制代码程序在机器上运行以生成结果. 编译和运行是两个独立分开的阶段。n但在一个交互环境中,不需要将这两个阶段分隔开,解释程序是这样一个程序,它接受某个语言的程序并立即运行这个源程序.它的工作模式是一个个的获取,分析并执行源程序语句.n著名的解释程序有Basic语言解释程序 ,Lisp语言解释程序,UNIX命令语言解释程序(shell),数据库查询语言SQL 解释程序以及bytecode解释程序.解释程序计算结果源 程 序初始数据编译程序和解释程序的存储组织有很大不

22、同 编译时 运行时 名字表目标代码缓冲区编译用源程序中间表示各种表格目标代码区数据区源程序缓冲区编译阶段和运行阶段存储结构解释系统存储结构解释系统源程序临时工作单元名字表标号表缓冲区(输入输出)栈区语言处理过程语言处理过程C语言程序： #include #include #define MAX_LINES 75enum booleans (FALSE,TRUE);main (int argc,char *argv*) 预处理器编译器汇编器装配连接编辑骨架程序 源程序 目标汇编程序 可重定位机器代码 绝对机器码可重定位目标文件库语言处理过程语言处理过程手工：工作量大，可靠性差机器语言汇编系统程序

23、设计语言：C、PASCAL等，BASIC、FORTRAN等不是自展，交叉编译，移植自动构造工具，如 lex yacc编译基础设施（多源语言多目标机体系结构的编译程序构造和编译技术研究平台） 1.3 编译程序的实现方式先进的开发方式缩短了开发周期，提高了开发效率，大大增加了可靠性、可移植性、可维护性和可扩展性。u自编译：用某一高级语言书写另一种语言的编译程序用语言L1写的语言L2的编译程序comp.L2 同一机器上的语言L2的编译程序comp.L2 语言L1的编译程序comp.L1u自展：滚雪球式 L0-L1-L2-Li-1 -L（Li由Li-1实现） 弱小- 强大用机器或汇编语言实现u移植：将

24、A机上的某高级语言的编译程序稍加修改得到B机上的编译程序。 在 A机上用LA编写能生成B机代码的LB的编译程序LA的编译程序A机代码的LB的编译程序LA源程序B机上目标程序B机LB的编译程序u交叉编译：LA（A机语言L）=LB（B机语言L）交叉编译程序为另一系统配同一语言：由于目标机指令系统与宿主机的指令系统不同，编译程序在宿主机A上运行，将应用程序的源程序生成目标机B的代码，这种编译称为交叉编译。A机与B机的指令系统不同编译程序的自动生成问题:只告诉做什么,而不用告诉怎么做源语言的定义机器语言的描述编译程序自动生成工具编译程序编译程序复杂、庞大，手工编制时间长 开发过程自动化LEX / YA

25、CC、Antlr一些编译基础设施n编译基础设施（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

26、 , everyone can get and maintain freely1.4 编译技术的应用-处理源程序的软件工具处理源程序的软件工具n结构化编缉器n程序分析工具 静态分析 动态分析 度量工具 结构度量 模块接口复杂度 c分析工具(source insight) n广泛的语言领域 数据库系统查询（SQL） 脚本语言 置标语言(SGML.HTML.XML)处理源程序的软件工具：处理源程序的软件工具：语言的结构化编辑器、语言程序的调试工具、程序格式化工具、语言程序测试工具、程序理解工具、高级语言之间的转换工具。1.语言的结构化编辑器语言的结构化编辑器 结构化编辑器不仅具有通常的正文编辑器的

27、正文编辑和修改功能，而且还能执行一些对编制程序有用的附加的任务。例如，当用户敲入if后，编辑器立即显示then并将这两个关键字之间必须出现的条件留给用户输入，并能检查括号是否相匹配等等。这样，既可保证编出的源程序无语法错误，并有统一的可读性好的程序格式，这无疑将会提高程序的开发效率和质量。 Editplus、Ultraedit、，很多集成开发环境中的编辑器都是结构化编辑器.2. 语言程序的调试工具语言程序的调试工具结构化编辑器只能解决语法错误的问题，而对一个已通过编译的程序来说，需进一步了解的是程序执行的结果与编程人员的意图是否一致，程序的执行是否实现预计的算法和功能。这种对算法的错误或程序没

28、能反映算法的功能等错误就需用调试器来协助解决。源程序级调试器允许逐行跟踪源程序的执行,查看变量和数据结构的变化。当然,它们的信息须由编译程序提供。调试器的实现有很多途径。其中一种是写一个解释器,以交互的方式翻译和执行每一行。解释器必须维护程序运行时的所有资源以便实时查询它们的当前值；另一种调试途径是编译程序在目标代码生成时同时生成特定的调试信息,如变量名与它的地址的对应关系等。3.程序格式化工具程序格式化工具分析源程序，使之以清晰可读的结构形式进行显示。例如，注释可以以一种专门的字形出现，且语句的嵌套层次结构可以用齿形结构体现出来。 4.语言程序测试工具语言程序测试工具：静态分析器和动态测试器

29、 静态分析器静态分析器是在不运行程序的情况下对源程序进行静态分析，以发现其中潜在的错误或异常。它检查变量定值与引用的关系。如某变量未被赋值就被引用、定值后未被引用、多余的源代码等非语法错误。动态测试器动态测试器是在对源程序进行分析的同时将用于记录和显示程序执行轨迹的语句或函数插入到源程序的适当位置，并用测试用例记录和显示程序运行时的实际路径，将运行结果与期望的结果进行比较分析，帮助编程人员查找问题。5.程序理解工具程序理解工具分析程序，确定模块间的调用关系，记录程序数据的静态属性和结构属性，画出控制流程图，以帮助用户理解程序。6. 高级语言之间的转换工具高级语言之间的转换工具 Human-or

30、ientedlanguageComputer-orientedlanguage计算模式，语言范式语言应用领域编译程序万诺曼机体系结构并行体系结构嵌入系统1.5 编译技术的发展S OI高级程序语言v不同的应用侧重:数值计算- Fortran 系统程序设计-C事务处理-Cobol VLSI设计-VHDL人工智能-Prolog 其它-大型嵌入式实时处理-Ada 符号处理-Snobolv语言范型:强制式语言-C,Fortran,Pascal应用式(函数式）语言-ML，Lisp基于规则(逻辑）的语言-Prolog,Yacc面向对象语言-Ada,C+,Java强制式语言(Imperative Langua

31、ge)也称过程式语言其特点是命令驱动，面向语句，一个强制式语言程序由一系列的语句组成，每个语句的执行引起若干存储单元中的值的改变.语言执行的解释与万诺曼机的体系结构对应：改变机器状态（内存，各种寄存器和外存的内容）面向对象语言：支持封装性，继承性和多态性 基于规则的语言( Rule-based Language) ： 条件1 动作1 条件2 动作2 条件3 动作3程序的执行过程是：检查一定的条件，当它满足值，则执行适当的动作。它也称逻辑程序设计语言。 Example: 一个简单的Prolog程序：father(a,b);father(b,c);grandfather(X,Y):-father(

32、X,Z),father(Z,Y);?grandfather(a,c).Yes?grandfather(X,c).X=a?grandfather(X,Y).X=a,Y=c编译技术与体系结构的发展密切相关n CISC （Complex Instruction Set Computing） 传统的编译技术与之伴随n RISC （Reduced Instruction Set Computing） 编译技术与体系结构设计的协同 软硬件协同设计n EPIC （Explicitly Parallel Instruction Computing） 现代编译技术的发展推动体系结构的进步 IA-64 处理器产品系列（IPF）的上市现代编译技术必须面对应用需求和目标体系结构的多样化n 高性能计算（High Performance Computing） 指令级并行（Instruction Level Parallelism） 线程级并行（Thread Level