编译原理 教学课件 ppt 作者 康慕宁 林奕 讲稿_1

《编译原理 教学课件 ppt 作者 康慕宁 林奕 讲稿_1》由会员分享，可在线阅读，更多相关《编译原理 教学课件 ppt 作者 康慕宁 林奕 讲稿_1（55页珍藏版）》请在金锄头文库上搜索。

1、1,第一章 绪论,2,内容,汇编语言和高级程序设计语言 编译器基本构造 编译技术 编译器工作过程,3,1.1 汇编语言和高级语言,汇编语言、机器语言的特点 面向机器，CPU可直接执行 每个操作仅完成简单功能 缺少高层抽象元素的表示方法，直接访问内存地址 难以在不同机器间移植 程序编写复杂困难,4,汇编语言和高级语言,高级语言 面向程序员，机器不能直接执行，必须经过编译或解释才能执行 支持复杂的计算组合和流程控制 支持抽象的数据类型，通过名字访问变量、对象、类、函数等抽象元素 容易在不同机器间移植 编写复杂程序更为方便直观,1.1 汇编语言和高级语言,5,C语言程序 x=a+b+c+d 对应的汇

2、编程序 mov eax,dword ptr ebp-8 add eax,dword ptr ebp-0Ch add eax,dword ptr ebp-10h add eax,dword ptr ebp-14h mov dword ptr ebp-4,eax,1.1 汇编语言和高级语言,6,1.1 汇编语言和高级语言,7,1.2 编译器的基本概念,狭义的编译器 将高级语言编写程序翻译为汇编或二进制代码的软件系统 主要功能： 判断程序的合法性 程序被等价翻译为低级语言 程序错误的识别与提示,8,狭义的编译器,源程序,编译器 判断程序的合法性 程序被等价翻译为低级语言 程序错误的识别与提示,汇编或

3、二进制可执行程序,语义等价,1.2 编译器的基本概念,9,广义的编译器,广义的编译器 将一种语言编写的程序，翻译为具有相同功能的另一种语言的程序的软件,1.2 编译器的基本概念,10,广义的编译器,C+源码,编译器 判断程序的合法性 程序被等价翻译为其他语言 程序错误的识别与提示,C源码,语义等价,1.2 编译器的基本概念,11,编译器和解释器,编译器将一种语言编写的程序，翻译为另一种语言表示的程序 C+程序可执行程序 C语言源程序 汇编程序 但这些程序本身并不能执行，而只是保存在磁盘或其他介质上的符号的集合,1.2 编译器的基本概念,12,谁执行程序？,1、计算机 2、解释器 3、虚拟机,1

4、.2 编译器的基本概念,13,计算机执行程序,1.2 编译器的基本概念,14,解释器的基本概念,解释器是运行在某个硬件平台上的一种软件。该软件负责读取输入的程序代码，并对其进行相应的计算或执行相应的功能,1.2 编译器的基本概念,15,解释器的用途,浏览器内的HTML解释器,HTML网页源文件,浏览器内显示的网页,CAD等设计图源文件,CAD内的文件格式解释器,CAD设计图的图形显示,Matlab/TCL/Dos批处理等解释性程序,Matlab/TCL/Dos批处理解释器,程序执行的交互序列与计算结果,1.2 编译器的基本概念,16,编译器与虚拟机,编译器只把程序翻译为另一种语言的程序，而并不

5、负责对翻译结果进行执行 CPU和解释器才是对翻译结果的执行者 解释器的两种类型： 1、高级语言解释器 2、低级语言解释器（虚拟机）,1.2 编译器的基本概念,17,高级语言解释器 输入的是具有复杂语法、语义结构的源程序，如Basic语言，TCL/Tk语言，Matlab的m语言等编写的源程序，Dos批处理程序、Linux的Shell脚本程序 直接执行该程序的各种计算与交互任务 高级语言解释器的特点 结构复杂，执行效率低,1.2 编译器的基本概念,18,虚拟机,高级语言的优点 面向程序员，与底层硬件无关 编译与执行分离，执行效率高 可移植性好 高级语言的不足 移植时需要重新编译 不同平台虽然差别不

6、大，但即使微小的差别也可能引起移植时巨大的麻烦,1.2 编译器的基本概念,19,虚拟机（续）,虚拟机 专门设计的具有通用性虚拟计算机 包括专门的指令集（通常称为字节码） 包括特定的内存管理体制 支持标准的数据表示格式（如IEEE浮点格式） 支持线程、锁等复杂模型,1.2 编译器的基本概念,20,虚拟机的实现,软件实现的虚拟机 如Java虚拟机，可用来解释执行编译后的字节码程序 硬件实现的“虚拟机” 实际上，硬件实现的应该是真实的机器。但由于其指令集和体系结构是符合某种虚拟机规范的，因此也可认为是“虚拟机” 例如，直接实现Java虚拟机的硬件Java机器,1.2 编译器的基本概念,21,1.2

7、编译器的基本概念,CPU,操作系统,进程,进程,Java 虚拟机,字节码程序 字节码指令 字节码指令 字节码指令 ,读取指令,读/写数据,用软件执行诸如加、减、乘、除等计算,虚拟机内存,22,1.3 编译技术的基本构造与工作原理,编译器和语言的规格说明 语言手册与规范 程序员手册与编程书籍 以上两种只有编译器设计者人工阅读，并将其转换为软件设计方案。存在二义性，无法保证不同编译器设计者的理解是完全相同的。 形式化的规格说明 精确的数学化的说明，可对其完善性进行数学验证，并根据规格说明自动生成编译器设计框架。,23,编译器的内部工作原理,人工翻译过程,1.3 编译技术的基本构造与工作原理,24,

8、int a;int add(int d1,int d2)return d1+d2;int main(void)a=5;a=add(a, 6);return 0; 自动翻译过程 1、线性扫描过程：自左向右，逐个字母 2、识别单词（关键字，标识符，注释，各种数字等） 3、复杂程序结构的识别不是简单线性的 识别过程不能通过简单的线性扫描完成 需要考虑当前已经识别到什么程度了,1.3 编译技术的基本构造与工作原理,25,当扫描到”;”时，可以判定当前识别到的是一个变量定义。 当扫描到int d1后面的”,”时，可以确定遇到的是一个变量定义，但该变量却是函数add的形式参数。 虽然int a和int d

9、1在构成上是一样的，但由于处于程序中的不同位置，因此对其理解却有着很大的不同。 编译器应当能够处理这些复杂的情况。,int a;int add(int d1,int d2),1.3 编译技术的基本构造与工作原理,26,1.4 程序设计语言的编译技术,词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成 程序信息管理和错误检查与处理,27,词法分析,以字符为单位，从源程序的字符流中提取能够构成单个语言单位的单词 常见的单词： 关键字 标识符 各种计算或其他符号 各种格式的数字 注释 空白符号：空格，Tab键，回车等,28,单词间的分隔： 绝大部分现代程序设计语言的不同单词之间，都可

10、以用空白符号、各种算符（如+-*/）等进行区分。 这方便了单词的识别，降低了词法分析的复杂成都。 Fortran中的空格不用于分隔单词，属于早期语言的“不良”特点。,29,语法分析,以单词为单位，分析这些单词出现的位置、顺序、次数等，是否符合被编译语言的格式要求（语法规格说明） 不处理除格式正确性的语义问题,int func(void) int x, y; float x, z; /x重复定义，不符合C程序的定义 ,30,语法分析的过程不是简单线性的,if (ab) /语法分析器从识别出关键词if开始识别本语句 x=5; else if(u= =v) v=9; else /语法分析器在识别到这

11、个“”后才能完成 /对本if语句的识别。此前需要先识别诸多其他内容。,31,语义分析,语义分析可采用与语法分析一起进行的方式进行，即所谓的语法制导的语义分析。 也可采用在语法制导阶段生成适当的中间表示，而后针对中间表示进行更为深入的语义分析的方式。,32,常见的语义分析任务包括 识别变量是数组、指针、简单变量、结构体（struct）或共用体（union），并识别其类型和作用域。为每个变量建立“档案”以供后面的处理来检索和查阅； 识别函数定义并记录函数的信息，包括函数的返回值类型、函数名以及每个参数的信息和作用域等； 对变量、函数的每次访问是否合法进行检查，如变量类型是否匹配、函数参数个数是否正

12、确、被访问的变量和函数是否在有效作用域内、被访问的结构体变量的分量是否在结构体中已经定义等。,33,中间代码生成,中间代码 是一种和汇编或机器指令非常类似的“虚拟低级语言”，但独立于具体的硬件平台。 一般的中间代码是为了方便编译程序进行优化而设计的。这与字节码为了提高虚拟机执行效率的目的不同。 在中间代码级别进行优化，既可以避免直接生成低级语言目标代码时带来的平台依赖问题，也使优化算法能够更加直接对存储器分配（如分配临时变量）、指令合并等问题进行检查和处理,34,常见的中间代码 逆波兰，三元式，四元式，P代码等 常见的中间表示 抽象语法树（Abstract Syntax Tree，AST） 中

13、间代码通常为线性结构，与汇编非常类似，缺少结构化的信息。AST更好地保留了源程序的结构信息，对优化等更为有利。,35,代码优化,针对机器的体系结构特点，对中间代码和目标代码进行优化。 优化目标： 可执行程序指令多少和动态存储空间的多少 可执行程序的速度 执行时的能耗（对于嵌入式系统来时非常重要）,36,目标代码生成,以优化后的中间代码为输入 根据中间代码、机器所支持的指令集和硬件资源情况，生成最终的可执行代码或汇编代码 两种方式： 固定地址方式。不允许按模块编译和动态加载。 浮动地址方式。允许按模块编译、链接甚至动态加载。,37,程序信息管理和错误检查与处理,程序信息管理 符号表 带信息的其他

14、数据结构（如抽象语法树） 错误检查与处理 识别出程序中的词法、语法和语义错误 为程序员提供尽可能多的错误信息，以帮助进行错误类型、位置判断和改正,38,1.5 编译程序的工作过程,以语法为中心的典型编译器工作过程,图1.4 语法分析为中心的编译过程,39,编译器后端的各个阶段（优化，代码生成等），是依次执行的。 编译器前端的各个模块，则以语法分析算法为核心组织在一起。,40,1.6 文法及其分类 1.6.1 文法,文法的定义 【定义2-1】一个文法被定义为一四元组（，N，P，S），其中， 有限、非空集合，称为终结符集、字母表、或符号集； N 有限、非空集合，且 N=，称为非终结符（或语法变量）

15、集； P 有限、非空集合，称为产生式集； S （N）称为开始符号或目标符号。,41,字母表与字符串 字母表中的元素称为字母，或称为终结符。字母是构成语言中句子的基本符号。 字母的有限序列称为字符串。 当字符串中的字母的个数为0时，称为空串，记为。 *表示由字母表中的字母构成的所有字符串之集合。一般来说，上定义的程序设计语言是*的子集。,42,非终结符与产生式 非终结符集N中的元素用于描述或代表*的一个子集中所有字符串。特别地，开始符号S恰好代表了一语言的所有字符串。非终结符也被称为语法范畴或文法变量。 产生式集P也称为重写规则集，它由两个字符串构成的有序对组成，中间用一箭头分隔。箭头两侧的字符

16、串可由终结符及非终结符组成，且在形式上符合文法的一些限制。最简单的语言可由最简单的（即限制最多的）文法定义，越复杂的语言对文法的限制越少。,43,【例2-1】假设我们要定义的语言L由字母表a,b,c中两个字符组成，即L=aa, ab, ac, ba, bb, bc, ca, cb, cc，则语言L可由下面的文法定义： G1=(a,b,c,A,B,AaB,AbB,AcB,Ba,Bb,Bc,A),44,推导（Derivation） 将一个字符串中的某个非终结符，用其某个产生式的右部符号串替换，称为一步推导。 例如，对于文法GA AaB,AbB,AcB,Ba,Bb,Bc 则存在一个从A开始的推导序列 AcBca 当然，从A开始还能推导出其他序列。 如果一个符号串可从A经过若干步推导得到，则称是GA的一个句型。如果仅包含终结符，则称为GA的一