东北大学秦皇岛分校编译原理课件 第一章(精品).ppt

《东北大学秦皇岛分校编译原理课件 第一章(精品).ppt》由会员分享，可在线阅读，更多相关《东北大学秦皇岛分校编译原理课件 第一章(精品).ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理编译原理n课时：授课课时课时：授课课时48+48+实验课时实验课时8 8n课程性质：课程性质：必修/考试考试n考试方式：闭卷考试考试方式：闭卷考试n主讲：敬茂华主讲：敬茂华 jing_jing_n先修课程：离散数学、组成原理、汇编语言、先修课程：离散数学、组成原理、汇编语言、数据结构、数据结构、C+C+或其他程序设计语言或其他程序设计语言第第0章章 预备知识预备知识n本门课程的目的和意义本门课程的目的和意义 n程序设计语言与程序的翻译程序设计语言与程序的翻译n程序设计语言的语法描述程序设计语言的语法描述 为什么要学习编译原理？为什么要学习编译原理？n n例例例例intint fact(

2、)fact()static static intint i=5;i=5;if(i=0)if(i=0)return(i);return(i);elseelsei=i-1;i=i-1;return(i+abs(1)*fact();/*return(i+abs(1)*fact();/*第第第第9 9行行行行,函数函数函数函数abs():abs():求绝对值求绝对值求绝对值求绝对值.*/.*/main()main()printf(“factorprintf(“factor of 5=%d/n”,fact();of 5=%d/n”,fact();上程序的运行结果是上程序的运行结果是上程序的运行结果是上程

3、序的运行结果是120120。但是，如果把第。但是，如果把第。但是，如果把第。但是，如果把第9 9行的行的行的行的abs(1)abs(1)改成改成改成改成1 1的话，该程序结果是的话，该程序结果是的话，该程序结果是的话，该程序结果是1 1。分析分析分析分析n n i i 是静态变量，所有地方对是静态变量，所有地方对是静态变量，所有地方对是静态变量，所有地方对 i i 的操作都是对同一地址空间的操作，所以每次递归的操作都是对同一地址空间的操作，所以每次递归的操作都是对同一地址空间的操作，所以每次递归的操作都是对同一地址空间的操作，所以每次递归进入进入进入进入factfact函数后，上一层对函数后，

4、上一层对函数后，上一层对函数后，上一层对 i i 的赋值仍然有效。由于的赋值仍然有效。由于的赋值仍然有效。由于的赋值仍然有效。由于C C语言的编译机制，每次调用语言的编译机制，每次调用语言的编译机制，每次调用语言的编译机制，每次调用时，时，时，时，(i+abs(1)*fact()i+abs(1)*fact()中中中中(i+abs(1)i+abs(1)的值都先于的值都先于的值都先于的值都先于factfact算出。所以，第算出。所以，第算出。所以，第算出。所以，第1 1次递归时，次递归时，次递归时，次递归时，所求值为所求值为所求值为所求值为5*5*factfact，第第第第2 2次递归时，所求值为

5、次递归时，所求值为次递归时，所求值为次递归时，所求值为4*4*factfact，第第第第3 3次递归时，所求值为次递归时，所求值为次递归时，所求值为次递归时，所求值为3*3*factfact，第第第第4 4次递归时，所求值为次递归时，所求值为次递归时，所求值为次递归时，所求值为2*2*factfact，第第第第5 5次递归时，所求值为次递归时，所求值为次递归时，所求值为次递归时，所求值为1*fact1*fact，而此时而此时而此时而此时factfact为为为为1 1。这样，程序相当于是求一个阶乘函数。这样，程序相当于是求一个阶乘函数。这样，程序相当于是求一个阶乘函数。这样，程序相当于是求一个阶

6、乘函数5*4*3*2*15*4*3*2*1，所以，结果为，所以，结果为，所以，结果为，所以，结果为120120。n n程序改动后结果变化，主要是和编译时代码生成策略有关。对于表达式程序改动后结果变化，主要是和编译时代码生成策略有关。对于表达式程序改动后结果变化，主要是和编译时代码生成策略有关。对于表达式程序改动后结果变化，主要是和编译时代码生成策略有关。对于表达式(i+abs(1)*facti+abs(1)*fact()()，因两个子表达式都有函数调用，因此，编译器先产生左子表达式代码，后产因两个子表达式都有函数调用，因此，编译器先产生左子表达式代码，后产因两个子表达式都有函数调用，因此，编译

7、器先产生左子表达式代码，后产因两个子表达式都有函数调用，因此，编译器先产生左子表达式代码，后产生右子表达式代码。当生右子表达式代码。当生右子表达式代码。当生右子表达式代码。当abs(1)abs(1)改为改为改为改为1 1后，左子表达式就没有函数调用了，于是，后，左子表达式就没有函数调用了，于是，后，左子表达式就没有函数调用了，于是，后，左子表达式就没有函数调用了，于是，编译器会先产生右子表达式代码，这样一来，每次递归调用时，编译器会先产生右子表达式代码，这样一来，每次递归调用时，编译器会先产生右子表达式代码，这样一来，每次递归调用时，编译器会先产生右子表达式代码，这样一来，每次递归调用时，(i

8、+1)*fact()i+1)*fact()中中中中(i+1)i+1)的值后于的值后于的值后于的值后于factfact算出。第算出。第算出。第算出。第1 1次递归时，所求值为次递归时，所求值为次递归时，所求值为次递归时，所求值为(i+1)*fact()i+1)*fact()，第第第第2 2次递归时，次递归时，次递归时，次递归时，所求值为所求值为所求值为所求值为(i+1)*fact()i+1)*fact()，第第第第5 5次递归时，所求值为次递归时，所求值为次递归时，所求值为次递归时，所求值为(i+1)*fact()i+1)*fact()，而此时而此时而此时而此时factfact为为为为1 1，i

9、 i为为为为0 0，即实际上每次递归调用所求的实际都是，即实际上每次递归调用所求的实际都是，即实际上每次递归调用所求的实际都是，即实际上每次递归调用所求的实际都是1*1*factfact，最后结果还是最后结果还是最后结果还是最后结果还是1 1。编译原理课程关注的内容n面向机器的语言面向机器的语言计算机的硬件只能识别由计算机的硬件只能识别由0、1字符串组成的机器指令序列，即字符串组成的机器指令序列，即机器指令程序。特点：不易理解，编写程序既困难又容易出错。机器指令程序。特点：不易理解，编写程序既困难又容易出错。用容易记忆的符号来代替用容易记忆的符号来代替0、字符串。用符号表示的指令被、字符串。用

10、符号表示的指令被称为汇编指令，汇编指令的集合被称为汇编语言，由汇编语言称为汇编指令，汇编指令的集合被称为汇编语言，由汇编语言编写的指令序列被称为汇编语言程序。编写的指令序列被称为汇编语言程序。n面向人类的语言面向人类的语言通用程序设计语言，如，通用程序设计语言，如，Java，C#；数据查；数据查询语言，如；形式化描述语言，如询语言，如；形式化描述语言，如EBNF、。、。n其他面向特定应用领域的语言其他面向特定应用领域的语言面向互联网应用的面向互联网应用的HTML、XML；面向计算机辅助设计的；面向计算机辅助设计的MATLAB；面向集成电路设计的；面向集成电路设计的VHDL、Verilog；面向

11、虚拟现；面向虚拟现实的实的VRML；n语言之间的翻译语言之间的翻译 高级语言之间的翻译，一般被称为高级语言之间的翻译，一般被称为高级语言之间的翻译，一般被称为高级语言之间的翻译，一般被称为转换转换转换转换，如，如，如，如FORTRANFORTRAN到到到到AdaAda的转的转的转的转换等，或者被称为换等，或者被称为换等，或者被称为换等，或者被称为预处理预处理预处理预处理，如，如，如，如SQLSQL到到到到C/C+C/C+的预处理。的预处理。的预处理。的预处理。高级语言可以直接翻译成机器语言，也可以翻译成汇编语言，这两高级语言可以直接翻译成机器语言，也可以翻译成汇编语言，这两高级语言可以直接翻译

12、成机器语言，也可以翻译成汇编语言，这两高级语言可以直接翻译成机器语言，也可以翻译成汇编语言，这两个翻译过程是将个翻译过程是将个翻译过程是将个翻译过程是将高级语言的源程序高级语言的源程序高级语言的源程序高级语言的源程序翻译成翻译成翻译成翻译成低级语言的目标程序低级语言的目标程序低级语言的目标程序低级语言的目标程序，这，这，这，这种翻译被称为种翻译被称为种翻译被称为种翻译被称为编译编译编译编译。将一个汇编语言汇编为可在将一个汇编语言汇编为可在将一个汇编语言汇编为可在将一个汇编语言汇编为可在另一平台另一平台另一平台另一平台上运行的机器指令，则称为上运行的机器指令，则称为上运行的机器指令，则称为上运行

13、的机器指令，则称为交交交交叉汇编叉汇编叉汇编叉汇编，而建立在交叉汇编基础之上的编译模式称为，而建立在交叉汇编基础之上的编译模式称为，而建立在交叉汇编基础之上的编译模式称为，而建立在交叉汇编基础之上的编译模式称为交叉编译交叉编译交叉编译交叉编译。把机器语言翻译成汇编语言，或者把汇编语言翻译成高级语言，分把机器语言翻译成汇编语言，或者把汇编语言翻译成高级语言，分把机器语言翻译成汇编语言，或者把汇编语言翻译成高级语言，分把机器语言翻译成汇编语言，或者把汇编语言翻译成高级语言，分别称它们为别称它们为别称它们为别称它们为反汇编反汇编反汇编反汇编和和和和反编译反编译反编译反编译。n n上述语言之间的翻译虽

14、然各不相同，但上述语言之间的翻译虽然各不相同，但上述语言之间的翻译虽然各不相同，但上述语言之间的翻译虽然各不相同，但基本方法基本方法基本方法基本方法，特别是对，特别是对，特别是对，特别是对源语言的源语言的源语言的源语言的分析方法分析方法分析方法分析方法是相同的。是相同的。是相同的。是相同的。编译原理与编译技术编译原理与编译技术n n编译原理与编译技术是两类不同的过程。编译原理与编译技术是两类不同的过程。编译原理与编译技术是两类不同的过程。编译原理与编译技术是两类不同的过程。n n编译原理研究的就是语言翻译方法中所用到的基本原编译原理研究的就是语言翻译方法中所用到的基本原编译原理研究的就是语言翻

15、译方法中所用到的基本原编译原理研究的就是语言翻译方法中所用到的基本原理，关注的是产生编译器的理论和原理。一般并不深理，关注的是产生编译器的理论和原理。一般并不深理，关注的是产生编译器的理论和原理。一般并不深理，关注的是产生编译器的理论和原理。一般并不深入讨论某一具体的编译器的实现和工作机制。入讨论某一具体的编译器的实现和工作机制。入讨论某一具体的编译器的实现和工作机制。入讨论某一具体的编译器的实现和工作机制。n n编译技术更关注编写（实现）编译器过程中所用到的编译技术更关注编写（实现）编译器过程中所用到的编译技术更关注编写（实现）编译器过程中所用到的编译技术更关注编写（实现）编译器过程中所用到

16、的技术。技术。技术。技术。n n编译原理是学习编译技术以及深入掌握利用高级语言编译原理是学习编译技术以及深入掌握利用高级语言编译原理是学习编译技术以及深入掌握利用高级语言编译原理是学习编译技术以及深入掌握利用高级语言进行编程的基础。进行编程的基础。进行编程的基础。进行编程的基础。通用程序设计语言的主要成份通用程序设计语言的主要成份通用程序设计语言的典型特征之一是通用程序设计语言的典型特征之一是通用程序设计语言的典型特征之一是通用程序设计语言的典型特征之一是抽象抽象抽象抽象，其抽象程度是以程，其抽象程度是以程，其抽象程度是以程，其抽象程度是以程序设计语言所支持的序设计语言所支持的序设计语言所支持

17、的序设计语言所支持的基本结构基本结构基本结构基本结构为特征的。可以大致划分为三种形式：为特征的。可以大致划分为三种形式：为特征的。可以大致划分为三种形式：为特征的。可以大致划分为三种形式：过程过程过程过程、模块模块模块模块（抽象数据类型，（抽象数据类型，（抽象数据类型，（抽象数据类型，ADTADT）和）和）和）和类类类类。以以以以过程过程过程过程为基本结构的程序设计语言的典型代表有为基本结构的程序设计语言的典型代表有为基本结构的程序设计语言的典型代表有为基本结构的程序设计语言的典型代表有C C、PascalPascal等；等；等；等；以以以以ADTADT为基本结构的程序设计语言的典型代表是为基

18、本结构的程序设计语言的典型代表是为基本结构的程序设计语言的典型代表是为基本结构的程序设计语言的典型代表是Ada83Ada83；而以；而以；而以；而以类类类类为基为基为基为基本结构的程序设计语言包括当前流行的本结构的程序设计语言包括当前流行的本结构的程序设计语言包括当前流行的本结构的程序设计语言包括当前流行的C+C+、JavaJava和和和和Ada95Ada95等。这三等。这三等。这三等。这三种形式经过了一个演变过程，每一次演变都使得程序设计语言的抽象种形式经过了一个演变过程，每一次演变都使得程序设计语言的抽象种形式经过了一个演变过程，每一次演变都使得程序设计语言的抽象种形式经过了一个演变过程，

19、每一次演变都使得程序设计语言的抽象程度得到一次提高，同时也为这些程序设计语言的编译器提出了新的程度得到一次提高，同时也为这些程序设计语言的编译器提出了新的程度得到一次提高，同时也为这些程序设计语言的编译器提出了新的程度得到一次提高，同时也为这些程序设计语言的编译器提出了新的要求。要求。要求。要求。类概念的引入，为利用程序设计语言构造类型提供类概念的引入，为利用程序设计语言构造类型提供了真正的支持，也是了真正的支持，也是面向对象程序设计（面向对象程序设计（OOP）语语言的重要特征之一。言的重要特征之一。程序设计语言提供的机制与程序设计的风格有着密程序设计语言提供的机制与程序设计的风格有着密切关系

20、，以过程为基本抽象的程序设计语言支持的是切关系，以过程为基本抽象的程序设计语言支持的是过过程式程式的程序设计范型（的程序设计范型（paradigm），以类为基本抽象的），以类为基本抽象的程序设计语言支持的是程序设计语言支持的是面向对象面向对象的程序设计范型，以的程序设计范型，以ADT为基本抽象的程序设计语言介于二者之间，一般被为基本抽象的程序设计语言介于二者之间，一般被认为是认为是面向过程面向过程的语言，但也被认为是的语言，但也被认为是基于对象基于对象的语言。的语言。有些面向对象的程序设计语言是由过程式的语言发展而有些面向对象的程序设计语言是由过程式的语言发展而来的，如来的，如C+、Ada95

21、等，它们实质上是支持多范型的等，它们实质上是支持多范型的程序设计语言。程序设计语言。n本课程以本课程以PL/0（面向过程的语言）编译器为例，讨论（面向过程的语言）编译器为例，讨论把高级语言中应用最广的把高级语言中应用最广的通用程序设计语言通用程序设计语言翻译成翻译成汇汇编语言编语言程序所涉及的基本原理、技术和方法。这些原程序所涉及的基本原理、技术和方法。这些原理、技术和方法也同样适用于其他各类翻译器的构造，理、技术和方法也同样适用于其他各类翻译器的构造，同时有些技术和方法也可以被用于其他软件设计。同时有些技术和方法也可以被用于其他软件设计。n内容上以最简单的、以过程为基本结构的程序设计语内容上

22、以最简单的、以过程为基本结构的程序设计语言为背景进行讨论。因为无论何种形式的程序设计语言为背景进行讨论。因为无论何种形式的程序设计语言，均是由言，均是由声明声明和和操作操作这样两个基本元素构成的，这样两个基本元素构成的，所不同的是声明和操作的范围和复杂程度不同。所不同的是声明和操作的范围和复杂程度不同。n以过程为基本结构的程序设计语言的特征是把整个程以过程为基本结构的程序设计语言的特征是把整个程序作为一个过程。过程的定义由两类语句组成：声明序作为一个过程。过程的定义由两类语句组成：声明性语句和操作性语句。一般来讲，性语句和操作性语句。一般来讲，声明性语句提供所声明性语句提供所操作对象的性质操作

23、对象的性质，如数据类型、值、作用域等。而，如数据类型、值、作用域等。而操操作性语句确定操作的计算次序作性语句确定操作的计算次序，完成实际操作。，完成实际操作。n本门课程的目的和意义本门课程的目的和意义 计算机问题求解的基本途径计算机问题求解的基本途径:对问题进行抽象和形式化表示，对问题进行抽象和形式化表示，然后进行处理。然后进行处理。掌握形式语言与自动机理论。掌握形式语言与自动机理论。掌握编译原理及方法。掌握编译原理及方法。了解编译程序的实现原理和技术。了解编译程序的实现原理和技术。培养形式化描述和抽象思维能力。培养形式化描述和抽象思维能力。利用从本课程学到的知识，增强编写和调试程序的能力。利

24、用从本课程学到的知识，增强编写和调试程序的能力。编译原理及技术在其他方面的应用编译原理及技术在其他方面的应用n正文查找n正文处理n指令识别等n程序设计语言与程序的翻译程序设计语言与程序的翻译一般的程序设计语言的定义都涉及一般的程序设计语言的定义都涉及语法语法、语义语义和和语用语用三个方面三个方面。由符号（单词）构成语法成分的规则称为由符号（单词）构成语法成分的规则称为一般一般语法规则语法规则。由基本符号构成的符号（单词）书写规则由基本符号构成的符号（单词）书写规则特称为特称为词法规则词法规则。n程序设计语言的语法描述程序设计语言的语法描述 v语法图语法图 vBNF范式范式：；:=语法成分的定义

25、；语法成分的定义；|表示表示“或者或者”v扩充的扩充的BNF范式范式：增加了三个符号增加了三个符号 x表示表示x可以出现可以出现0到多次。到多次。x表示表示x可能出现，也可能不出现。可能出现，也可能不出现。（x|y）表示表示x和和y二者取一。二者取一。v文法文法v口语口语 第一章第一章 概述概述n1.1 1.1 什么是编译程序什么是编译程序 n1.2 1.2 编译的基本过程编译的基本过程 n1.3 1.3 编译程序的逻辑编译程序的逻辑结构结构 n1.4 决定编译阶段组决定编译阶段组合的因素合的因素 n1.5 与编译器相关的程序与编译器相关的程序 n1.6 编译器的翻译步骤编译器的翻译步骤 n1

26、.7 编译器中的主要数编译器中的主要数据结构据结构 n1.8 编译器结构的其他观编译器结构的其他观点点 直观印象：两数之和的程序直观印象：两数之和的程序n8086/8088机器语言的机器语言的程序：程序：1010 00000000 00010000 00001000 10100010 01100000 00100000 00000000 00001110 00001010 00100000 00110000 00001111 0100nIBM PC汇编语言的汇编语言的程序：程序：START:MOV AX,DSEGMOV DS,AXMOV AL,DATA1MOV AH,DATA2ADD AL,A

27、HMOV RLT,ALHLTnC语言的语言的程序：程序：a=b+c;1.1什么是编译程序什么是编译程序(compiler)n编译程序是现代计算机系统的基本组成编译程序是现代计算机系统的基本组成部分。部分。n从功能上看，一个编译程序就是一个语从功能上看，一个编译程序就是一个语言翻译程序言翻译程序,它把一种语言它把一种语言(称作源语言称作源语言)书写的程序翻译成另一种语言书写的程序翻译成另一种语言(称作目标称作目标语言语言)的的等价等价的程序。的程序。功能等价功能等价什么是编译程序什么是编译程序n语言转语言转(变）换系统变）换系统C+编译器编译器C+CJavaBytecodeJava编译器编译器1

28、.1.1 编译程序的功能编译程序的功能 重要性：编译程序使得程序员不必重要性：编译程序使得程序员不必去考虑那些与机器硬件相关的细节，去考虑那些与机器硬件相关的细节，而专注于自己的程序设计工作。而专注于自己的程序设计工作。高级语言程序高级语言程序（源程序）（源程序）低级语言程序低级语言程序（目标程序）（目标程序）编译程序编译程序1.1.2 翻译程序的种类翻译程序的种类v汇编程序汇编程序：用于特定计算机上的汇编语言的翻用于特定计算机上的汇编语言的翻 译程序。译程序。v编译程序：编译程序：将高级语言翻译成低级语言的翻译将高级语言翻译成低级语言的翻译 程序程序v解释程序：解释程序：将会话式语言翻译成目

29、标指令的翻将会话式语言翻译成目标指令的翻 译程序译程序编译程序与解释程序的根本区别编译程序与解释程序的根本区别 源程序源程序编译程序编译程序目标程序目标程序执行源程序源程序解释程序解释程序调用相应指令并执行调用相应指令并执行执行从翻译的角度来讲，两种方式所涉及的基本原理、方法与从翻译的角度来讲，两种方式所涉及的基本原理、方法与技术是相似的。技术是相似的。1.1.3 编译程序生成的目标程序的形式编译程序生成的目标程序的形式v 可立即执行的机器语言代码可立即执行的机器语言代码v 汇编语言程序汇编语言程序v 待装配的机器语言代码模块待装配的机器语言代码模块1.1.4 什么叫机器语言什么叫机器语言计算

30、机提供的基本操作称为指令。计算机提供的基本操作称为指令。指令的全体称为指令系统。指令的全体称为指令系统。指令系统也称为机器语言。指令系统也称为机器语言。指令的基本形式：指令的基本形式：操作码操作码操作地址操作地址 1.1.5 什么是编译系统什么是编译系统操作系统编译系统裸机编译系统编译系统编译程序编译程序连接程序连接程序系统库系统库源程序编辑程序源程序编辑程序辅助开发的各种软件辅助开发的各种软件NYN开始开始编辑编辑编译编译连接连接执行执行源程序源程序目标程序目标程序系统库与系统库与其他目标程序其他目标程序可执行程序可执行程序结果结果是否有错是否有错结果对否结果对否Y高级语言程序的处理、执行过

31、程高级语言程序的处理、执行过程 n 语言处理过程语言处理过程预处理器编译器汇编器装配连接编辑骨架程序 源程序 目标汇编程序 可重定位机器代码 绝对机器码可重定位目标文件库1.1.6 编译理论和编译器的发展史编译理论和编译器的发展史 机器语言机器语言汇编语言汇编语言文法文法高级语言高级语言编译器编译器编译器编译器自动构自动构造工具造工具 自动机自动机语言文法语言文法：语言结构的规则语言结构的规则 有穷自动机（有穷自动机（Finite Automata）：一种识别装置一种识别装置 正则表达式（正则表达式（Regular Expression）：）：是是3 3型文法的一种等价表示型文法的一种等价表示

32、 0型文法型文法1型文法型文法2型文法型文法3型文法型文法 1.2 编译的基本过程源程序源程序词法分析词法分析语法分析语法分析语义分析语义分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成目标程序目标程序表表格格管管理理出出错错处处理理编译的基本过程编译的基本过程词法分析n从左至右读字符流的源程序、识别从左至右读字符流的源程序、识别(拼拼)单词单词例：例：position :=initial +rate *60;词法分析词法分析position :=initial +rate *60;单词类型单词类型单词值单词值 标识符标识符1(id1)position 算符算符(赋值赋值)

33、:=标识符标识符2(id2)initial 算符算符(加加)+标识符标识符3(id3)rate 算符算符(乘乘)*整数整数 60 分号分号 ；语法分析语法分析n功能功能:层次分析。层次分析。依据依据源程序的源程序的语法规则语法规则把源把源程序的单词序列组成语法短语程序的单词序列组成语法短语(表示成语法树表示成语法树)。position :=initial +rate *60 ;规则规则:=“:=”:=“+”:=“*”:=“(”“)”:=:=:=赋值语句赋值语句标识符标识符表达式表达式表达式表达式+表达式表达式表达式表达式标识符标识符整数整数标识符标识符:=表达式表达式*id1:=id2+id3

34、*N:=+N 60*id1 Positionid2 initialid3 rate语义分析语义分析语义审查语义审查(静态语义静态语义)上下文相关性上下文相关性类型匹配类型匹配类型转换类型转换例例:Program p();Var rate:real;procedure initial;position:=initial +rate*60/*error*/*error*/*warning*/;语义分析60:=+*Id1 positionId2 initialId3 rateinttoreal中间代码生成中间代码生成源程序的内部源程序的内部(中间中间)表示表示三元式、四元式、三元式、四元式、P-Co

35、de、C-Code、U-Code、bytecode(*id3t1t2)t2=id3*t1t2:=id3*t1中间代码生成中间代码生成id1:=id2+id3*60(1)(inttoreal,60-t1)(2)(*,id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1)代码优化代码优化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*

36、c a=t2t4=t2+t3a=t4目标代码生成目标代码生成(*,id360.0t1)(+,id2t1id1)movfid3,R2mulf#60.0,R2movfid2,R1addfR2,R1movfR1,id1符号表管理符号表管理n记录源程序中使用的名字记录源程序中使用的名字n收集每个名字的各种属性信息收集每个名字的各种属性信息类型、作用域、分配存储信息类型、作用域、分配存储信息Const1常量常量值：值：35Var1变量变量类型：实类型：实层次：层次：2出错处理出错处理n检查错误、报告出错信息、排错、恢复检查错误、报告出错信息、排错、恢复编译工作编译工作1.3编译程序的逻辑结构编译程序的逻

37、辑结构(components)n词法分析程序n语法分析程序n语义分析程序n中间代码生成程序n代码优化程序n目标代码生成程序n符号表管理程序n出错处理程序出出错错处处理理语法分析程序语法分析程序语义分析程序语义分析程序目标代码生成程序目标代码生成程序词法分析程序词法分析程序中间代码生成程序中间代码生成程序代码优化程序代码优化程序表表格格管管理理1.4 决定编译阶段组合的因素决定编译阶段组合的因素 n分析，综合分析，综合(synthesis)源程序的分析源程序的分析线性分析线性分析层次分析层次分析语义分析语义分析目标程序的综合目标程序的综合n编译的前端（编译的前端（front end）n编译的后端

38、（编译的后端（back end）n遍（趟）从头到尾扫描源程序（各种形遍（趟）从头到尾扫描源程序（各种形式）一遍式）一遍(pass)。1.5 与编译器相关的程序与编译器相关的程序 n翻译程序翻译程序 n编译程序（编译程序（compliercomplier）n解释程序（解释程序（interpretorinterpretor）n汇编程序（汇编程序（assemblerassembler）n连接程序（连接程序（linkerlinker）n装入程序（装入程序（loaderloader）n预处理程序（预处理程序（preprocessorpreprocessor）n编辑器（编辑器（editoreditor）n

39、调试程序（调试程序（debuggerdebugger）n描述器（描述器（profilerprofiler）n项目管理程序（项目管理程序（project managerproject manager）1.6 编译器的翻译步骤编译器的翻译步骤 n例：a index=4+2 一、一、扫描程序（扫描程序（Scanner）8个记号（或：单词）（个记号（或：单词）（Token）：）：a标识符标识符左括号左括号index标识符标识符右括号右括号4数字数字+加号加号2数字数字二、语法分析程序（二、语法分析程序（Parser）expressionassign-expressionexpressionexpres

40、sionsubscript-expressionadditive-expressionexpressionexpressionexpressionexpressionidentifieraidentifierindexnumber4number2=+代码行代码行a index=4+2的分析树的分析树assign-expressionsubscript-expressionadditive-expressionidentifieraidentifierindexnumber4number2代码行代码行a index=4+2的语法树的语法树三、语义分析程序（三、语义分析程序（Semantic An

41、alyzer）assign-expressionsubscript-expressionintegeradditive-expressionintegeridentifieraarray of integeridentifierindexintegernumber4integernumber2integer代码行代码行a index=4+2的带注释语法树的带注释语法树四、源代码优化程序（四、源代码优化程序（Source Code Optimizer）assign-expressionsubscript-expressionintegeridentifieraarray of integerid

42、entifierindexintegernumber6integer代码行a index=4+2的带注释语法树五、代码生成器（五、代码生成器（Code Generator）六、目标代码优化程序（六、目标代码优化程序（Target Code Optimizer）1.7 编译器中的主要数据结构编译器中的主要数据结构 n记号（记号（Token）（也叫单词）n语法树（语法树（Syntax Tree）n符号表（符号表（Symbol Table）n常数表（常数表（Literal Table）n中间代码（中间代码（Intermediate Code）n临时文件（临时文件（Temporary File）补充知

43、识高级语言解释系统高级语言解释系统(interpreter)n功能功能 让计算机执行高级语言（让计算机执行高级语言（basic,lisp,prolog)n与编译程序的不同与编译程序的不同 1）不生成目标代码）不生成目标代码n 2）能支持交互环境）能支持交互环境n （同增量式编译系统）（同增量式编译系统）n源源 程程 序序 n n初始数据初始数据 解释程序解释程序计算结果计算结果 解释系统解释系统n直接对源程序中的语句进行分析，执行其隐含的操作。直接对源程序中的语句进行分析，执行其隐含的操作。n如：如：n b:=2 ;n a:=b+2 ;编译程序编译程序n write a ;n n解释程序直接将

44、解释程序直接将4的值输出（显示）的值输出（显示）Int 2St bLd badd 2St a生成代码生成代码 编译阶段和运行阶段存储结构编译阶段和运行阶段存储结构 n 编译时编译时 运行时运行时 名字表名字表目标代码缓冲区目标代码缓冲区编译用源程序中编译用源程序中间表示各种表格间表示各种表格目标代码区目标代码区数据区数据区源程序缓冲区源程序缓冲区解释系统存储结构解释系统解释系统源程序源程序工作单元工作单元名字表名字表标号表标号表缓冲区缓冲区(输入输出输入输出)栈区栈区1.3 编译技术的发展和应用n功能：程序功能：程序 集成环境集成环境n实现方式实现方式手工手工机器语言机器语言汇编汇编系统程序设

45、计语言系统程序设计语言自动构造工具自动构造工具lex yacc gccS OI 编译程序的发展Human-orientedlanguageComputer-orientedlanguage计算模式，语计算模式，语言言范式范式语言应用领域语言应用领域编译程序冯冯诺伊曼机诺伊曼机体系结构体系结构并行体系结构并行体系结构嵌入系统嵌入系统 编译程序的发展n语言范型语言范型(paradigms)命令式命令式(imperative language)应用式应用式(applicative)基于规则的（基于规则的（rule-based）面向对象的（面向对象的（object-oriented）n编译程序执行环境

46、编译程序执行环境批处理批处理交互环境交互环境嵌入系统环境嵌入系统环境 语言范型（支持的计算模式）语言范型（支持的计算模式）n 命令式：命令式：n程序特点：程序特点：语言执行的解释：语言执行的解释：编译技术发展快：编译技术发展快：n语句语句1；改变机器状态改变机器状态 系统语言系统语言n语句语句2；内存内存 自动化生成技术自动化生成技术n语句语句3；各种寄存器各种寄存器 的内容的内容 n 外存外存 与与冯冯诺伊曼诺伊曼机的机的 体系结构一般体系结构一般 应用式（函数式）：应用式（函数式）：程序特点：程序特点：Function n(funetion2(funetion1(data)程序执行：程序执

47、行：执行一个个函数施用在数据上的变换最终得到的结果执行一个个函数施用在数据上的变换最终得到的结果编译：编译：语法分析容易；语法分析容易；语义处理复杂；语义处理复杂；基于规则的语言（基于规则的语言（prolog,yacc)：程序特点：程序特点：使能条件使能条件1 动作动作1 使能条件使能条件2 动作动作2 使能条件使能条件3 动作动作3 面向对象语言：面向对象语言：抽象数据类型，继承机制抽象数据类型，继承机制编译：编译：动态绑定；动态绑定；执行环境n批处理环境：将源程序作为整体处理批处理环境：将源程序作为整体处理 排除程序错误不能依靠用户的外部帮助排除程序错误不能依靠用户的外部帮助n交互环境：解

48、释交互环境：解释 增量式编译增量式编译n嵌入式系统环境：交叉编译嵌入式系统环境：交叉编译n分布并行环境：并行编译分布并行环境：并行编译n程序创建和测试环境：程序创建和测试环境：独立编译独立编译 编译和调试同时设计考虑编译和调试同时设计考虑 编译技术的发展和应用n结构化编译器结构化编译器n程序分析工具程序分析工具 静态分析静态分析n 动态分析动态分析n 度量工具度量工具 结构度量结构度量n 模块接口复杂度模块接口复杂度n c分析工具分析工具(source insight)n广泛的语言领域广泛的语言领域 数据库系统查询数据库系统查询n 脚本语言脚本语言n 置标语言置标语言(SGML.HTML.XM

49、L)研究领域n并行编译技术并行编译技术n交叉编译技术交叉编译技术n硬件描述语言及其编译技术硬件描述语言及其编译技术 并行化编译技术n目的：提高并行计算机体系结构的性能。目的：提高并行计算机体系结构的性能。n超大规模计算的日益增长的需求超大规模计算的日益增长的需求 高性能计算机高性能计算机n 并行软件并行软件并行体系结构并行体系结构单机速度单机速度 并行体系结构并行体系结构途径1途径2 并行体系结构并行体系结构 编译技术支持编译技术支持 串行程序并行化串行程序并行化编译技术支持编译技术支持 并行程序设计语言编译并行程序设计语言编译 依赖于目标机的优化（低层）依赖于目标机的优化（低层）性能发挥 并

50、行算法复杂，难掌握，难编程并行算法复杂，难掌握，难编程 开发并行开发并行 软件的困难软件的困难 并行程序的不确定行为，难调并行程序的不确定行为，难调试，验证试，验证设计新的并行算法设计新的并行算法 修改已有串行程序尽量修改已有串行程序尽量（直接用并行程序（直接用并行程序 并行化（研究算法和并行化（研究算法和设计语言和并行程设计语言和并行程 应用的人同时工作）应用的人同时工作）序库实现。序库实现。).HPF.Occom.PVM 途径12嵌入式交叉编译器由于目标机指令系统与宿主机的指令系统不同，编译由于目标机指令系统与宿主机的指令系统不同，编译时将应用程序的源程序在宿主机上生成目标机代码，时将应用