《东北大学秦皇岛分校编译原理课件 第一章》由会员分享，可在线阅读，更多相关《东北大学秦皇岛分校编译原理课件 第一章（76页珍藏版）》请在金锄头文库上搜索。
1、编译原理n课时：授课课时48+实验课时8n课程性质：必修/考试n考试方式：闭卷考试n主讲：敬茂华 jing_n先修课程：离散数学、组成原理、汇编语言、数据结构、C+或其他程序设计语言第0章 预备知识n本门课程的目的和意义 n程序设计语言与程序的翻译n程序设计语言的语法描述 为什么要学习编译原理？n n例例 intint fact() fact() static static intint i=5; i=5; if(i=0)if(i=0) return(i);return(i); elseelse i=i-1;i=i-1; return(i+abs(1)*fact(); /*return(i+a
2、bs(1)*fact(); /*第第9 9行行, ,函数函数abs( ):abs( ):求绝对值求绝对值.*/.*/ main()main() printf(“factorprintf(“factor of 5=%d/n”,fact(); of 5=%d/n”,fact(); 上程序的运行结果是上程序的运行结果是120120。但是，如果把第。但是，如果把第9 9行的行的 abs(1)abs(1)改成改成1 1的话，该程序结果是的话，该程序结果是1 1。分析分析n ni i 是静态变量，所有地方对是静态变量，所有地方对 i i 的操作都是对同一地址空间的操作，所以每次递归的操作都是对同一地址空间
3、的操作，所以每次递归进入进入factfact函数后，上一层对函数后，上一层对 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次递归时，所求值为次递归时，所求值为4*4*factfact，第第3 3次递归时，所求值为次递归时，所求值为3*3*factfact，第第4 4次递归时，所求值为
4、次递归时，所求值为2*2*factfact，第第5 5次递归时，所求值为次递归时，所求值为1*fact1*fact，而此时而此时factfact为为1 1。这样，程序相当于是求一个阶乘函数。这样，程序相当于是求一个阶乘函数5*4*3*2*15*4*3*2*1，所以，结果为，所以，结果为120120。n n程序改动后结果变化，主要是和编译时代码生成策略有关。对于表达式程序改动后结果变化，主要是和编译时代码生成策略有关。对于表达式 ( (i+abs(1)*fact()i+abs(1)*fact()，因两个子表达式都有函数调用，因此，编译器先产生左子表达因两个子表达式都有函数调用，因此，编译器先产生
5、左子表达式代码，后产生右子表达式代码。当式代码，后产生右子表达式代码。当abs(1)abs(1)改为改为1 1后，左子表达式就没有函数调后，左子表达式就没有函数调用了，于是，编译器会先产生右子表达式代码，这样一来，每次递归调用时，用了，于是，编译器会先产生右子表达式代码，这样一来，每次递归调用时， ( (i+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)
6、*fact()，第第5 5次递归时，所求值为次递归时，所求值为( (i+1)*fact()i+1)*fact()，而此时而此时factfact为为1 1，i i为为0 0，即实际上每次递归调用所求的实际都是，即实际上每次递归调用所求的实际都是1*1*factfact，最后结果最后结果还是还是1 1。编译原理课程关注的内容n面向机器的语言 计算机的硬件只能识别由0、1字符串组成的机器指令序列，即 机器指令程序。特点：不易理解，编写程序既困难又容易出错 。 用容易记忆的符号来代替0、字符串。用符号表示的指令被 称为汇编指令，汇编指令的集合被称为汇编语言，由汇编语言 编写的指令序列被称为汇编语言程序
7、。n面向人类的语言通用程序设计语言，如，Java，C#；数据查 询语言，如；形式化描述语言，如EBNF、。n其他面向特定应用领域的语言面向互联网应用的HTML、XML；面向计算机辅助设计的MATLAB；面向集成电路设计的VHDL、Verilog；面向虚拟现实的VRML；n语言之间的翻译 高级语言之间的翻译，一般被称为高级语言之间的翻译，一般被称为转换转换，如，如FORTRANFORTRAN到到AdaAda的转的转换等，或者被称为换等，或者被称为预处理预处理，如，如SQLSQL到到C/C+C/C+的预处理。的预处理。 高级语言可以直接翻译成机器语言，也可以翻译成汇编语言，这两高级语言可以直接翻译
8、成机器语言，也可以翻译成汇编语言，这两个翻译过程是将个翻译过程是将高级语言的源程序高级语言的源程序翻译成翻译成低级语言的目标程序低级语言的目标程序，这，这种翻译被称为种翻译被称为编译编译。 将一个汇编语言汇编为可在将一个汇编语言汇编为可在另一平台另一平台上运行的机器指令，则称为上运行的机器指令，则称为交交叉汇编叉汇编，而建立在交叉汇编基础之上的编译模式称为，而建立在交叉汇编基础之上的编译模式称为交叉编译交叉编译。 把机器语言翻译成汇编语言，或者把汇编语言翻译成高级语言，分把机器语言翻译成汇编语言，或者把汇编语言翻译成高级语言，分别称它们为别称它们为反汇编反汇编和和反编译反编译。n n上述语言之
9、间的翻译虽然各不相同，但上述语言之间的翻译虽然各不相同，但基本方法基本方法，特别是对，特别是对源语言的源语言的分析方法分析方法是相同的。是相同的。编译原理与编译技术编译原理与编译技术n n编译原理与编译技术是两类不同的过程。编译原理与编译技术是两类不同的过程。n n编译原理研究的就是语言翻译方法中所用到的基本原编译原理研究的就是语言翻译方法中所用到的基本原理，关注的是产生编译器的理论和原理。一般并不深理，关注的是产生编译器的理论和原理。一般并不深入讨论某一具体的编译器的实现和工作机制。入讨论某一具体的编译器的实现和工作机制。n n编译技术更关注编写（实现）编译器过程中所用到的编译技术更关注编写
10、（实现）编译器过程中所用到的技术。技术。n n编译原理是学习编译技术以及深入掌握利用高级语言编译原理是学习编译技术以及深入掌握利用高级语言进行编程的基础。进行编程的基础。通用程序设计语言的主要成份通用程序设计语言的典型特征之一是通用程序设计语言的典型特征之一是抽象抽象，其抽象程度是以程，其抽象程度是以程序设计语言所支持的序设计语言所支持的基本结构基本结构为特征的。可以大致划分为三种形式为特征的。可以大致划分为三种形式：过程过程、模块模块（抽象数据类型，（抽象数据类型，ADTADT）和）和类类。以以过程过程为基本结构的程序设计语言的典型代表有为基本结构的程序设计语言的典型代表有C C、Pasca
11、lPascal等；等；以以ADTADT为基本结构的程序设计语言的典型代表是为基本结构的程序设计语言的典型代表是Ada83Ada83；而以；而以类类为基为基本结构的程序设计语言包括当前流行的本结构的程序设计语言包括当前流行的C+C+、JavaJava和和Ada95Ada95等。这三等。这三种形式经过了一个演变过程，每一次演变都使得程序设计语言的抽象种形式经过了一个演变过程，每一次演变都使得程序设计语言的抽象程度得到一次提高，同时也为这些程序设计语言的编译器提出了新的程度得到一次提高，同时也为这些程序设计语言的编译器提出了新的要求。要求。类概念的引入，为利用程序设计语言构造类型提供了真正的支持，也
12、是面向对象程序设计（OOP）语言的重要特征之一。程序设计语言提供的机制与程序设计的风格有着密切关系，以过程为基本抽象的程序设计语言支持的是过 程式的程序设计范型（paradigm），以类为基本抽象的程序设计语言支持的是面向对象的程序设计范型，以 ADT为基本抽象的程序设计语言介于二者之间，一般被认为是面向过程的语言，但也被认为是基于对象的语言 。有些面向对象的程序设计语言是由过程式的语言发展 而来的，如C+、Ada95等，它们实质上是支持多范型的程序设计语言。n本课程以PL/0（面向过程的语言）编译器为例，讨论 把高级语言中应用最广的通用程序设计语言翻译成汇 编语言程序所涉及的基本原理、技术和
13、方法。这些原 理、技术和方法也同样适用于其他各类翻译器的构造 ，同时有些技术和方法也可以被用于其他软件设计。n内容上以最简单的、以过程为基本结构的程序设计语 言为背景进行讨论。因为无论何种形式的程序设计语 言，均是由声明声明和操作操作这样两个基本元素构成的， 所不同的是声明和操作的范围和复杂程度不同。n以过程为基本结构的程序设计语言的特征是把整个程 序作为一个过程。过程的定义由两类语句组成：声明 性语句和操作性语句。一般来讲，声明性语句提供所 操作对象的性质，如数据类型、值、作用域等。而操 作性语句确定操作的计算次序，完成实际操作。n本门课程的目的和意义 计算机问题求解的基本途径 :对问题进行
14、抽象和形式化表示，然后进行处理。掌握形式语言与自动机理论。掌握编译原理及方法。了解编译程序的实现原理和技术。培养形式化描述和抽象思维能力。利用从本课程学到的知识，增强编写和调试程序的能力。编译原理及技术在其他方面的应用编译原理及技术在其他方面的应用n正文查找n正文处理n指令识别等n程序设计语言与程序的翻译一般的程序设计语言的定义都涉及语法、语义和语用三个方面 。由符号（单词）构成语法成分的规则称为一般语法规则 。由基本符号构成的符号（单词）书写规则特称为词法规则 。n程序设计语言的语法描述 v语法图 vBNF范式 ：；:=语法成分的定义；| 表示“或者”v扩充的BNF范式 ：增加了三个符号 x
15、表示x可以出现0到多次。x表示x可能出现，也可能不出现。（x|y） 表示x和y二者取一。 v文法v口语 第一章 概述n1.1 什么是编译程序 n1.2 编译的基本过程 n1.3 编译程序的逻辑 结构 n1.4 决定编译阶段组合的因素 n1.5 与编译器相关的程序 n1.6 编译器的翻译步骤 n1.7 编译器中的主要数据结构 n1.8 编译器结构的其他观点 直观印象：两数之和的程序n8086/8088 机器语言的程 序： 1010 0000 0000 0001 0000 0000 1000 1010 0010 0110 0000 0010 0000 0000 0000 0000 1110 000
16、0 1010 0010 0000 0011 0000 0000 1111 0100nIBM PC汇编语言的 程序： START: MOV AX,DSEG MOV DS,AX MOV AL,DATA1 MOV AH,DATA2 ADD AL,AH MOV RLT,AL HLTnC语言的 程序： a=b+c; 1.1什么是编译程序(compiler)n编译程序是现代计算机系统的基本组成 部分。n从功能上看，一个编译程序就是一个语 言翻译程序,它把一种语言(称作源语言) 书写的程序翻译成另一种语言(称作目标 语言)的等价的程序。功能等价功能等价什么是编译程序n语言转(变）换系统C+编译器C+CJavaBytecodeJava编译器1.1.1 编译程序的功能 重
