《编译原理基础》PPT课件.ppt

,中原工学院软件学院,SoftwareCollege,ZhongyuanUniversityofTechnology,计算机技术概论IntroductiontoComputerTechnologies,第6章编译原理基础PrinciplesofCompilation,中原工学院软件学院韩玉民,编译程序是高级语言的支撑基础，是计算机系统中重要的系统软件之一。,第6章编译原理,6.1程序设计语言的编译与解释6.2形式语言6.3第一阶段词法分析6.4第二阶段语法分析6.5第三阶段语义分析与中间代码生成6.6第四阶段代码优化6.7符号表管理和错误处理6.8第五阶段目标代码生成,第6章编译原理,程序设计语言分成两大类:低级语言:包括机器语言和汇编语言，主要是面向机器的。高级语言:高级语言则是面向应用的，分成很多种，如FORTRAN、Pascal、C、C#、VB、Java等。,6.1程序设计语言的编译与解释,6.1.1程序设计语言,机器语言本身是有由0和1组成的，符合计算机的硬件特性，因此能够直接执行。但用机器语言编写程序很不方便且容易出错，因此就用助记符代替机器语言，产生了汇编语言。汇编语言比机器语言在可读性方面有了进步，但是其依赖具体机器的特性无法改变，给程序设计语言增添了难度。,6.1.2程序的编译与解释,6.1程序设计语言的编译与解释,高级语言不能直接在机器上运行，它不是面向机器，而是面向应用的，因此，要想让高级语言运行必须有编译程序。编译程序就是这样的一种程序，它能将高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序。,1.编译方式,6.1程序设计语言的编译与解释,高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段，源程序的运行过程如图1-1所示。,程序的编译,程序的执行,6.1程序设计语言的编译与解释,编译阶段将源程序变换成目标程序；运行阶段则由所生成的目标程序连同运行系统（数据空间分配子程序、标准函数程序等）接受程序的初始数据作为输入，运行后输出计算结果。如果目标程序是汇编语言的形式，则需要在编译阶段和运行阶段之间加一个汇编阶段。,6.1程序设计语言的编译与解释,高级语言编写的程序除了可以通过编译方式外，还可以通过解释程序执行。所谓解释程序是一种语言翻译程序，按动态顺序，读入一条语句，解释一条语句，执行一条语句，即边翻译边执行。,2.解释方式,6.1程序设计语言的编译与解释,高级语言源程序经编译程序编译的经过目标代码还可以是待装配的目标代码（相对目标代码），这种形式的目标程序通常由多个目标模块组成，各目标模块由相应的源程序模块经编译生成，必须将相关的多个目标模块组装成到一个可执行目标程序中，才能运行。完成集成工作的程序称为连接程序。连接程序还连接目标程序和用于标准库函数的代码，以及连接目标程序和由计算机的操作系统提供的资源（例如，存储分配程序及输入与输出设备）。,3.连接程序（linker）,6.1程序设计语言的编译与解释,解释程序与编译程序的主要区别是：编译程序将源程序翻译成目标程序后再执行目标程序.解释程序是逐条读出源程序中的语句并执行，即在解释程序的执行过程中并不产生目标程序。,6.1程序设计语言的编译与解释,6.1.3编译程序的编译过程和编译程序的结构,编译程序的功能是将用高级语言编写的源程序翻译成等价的低级语言（汇编语言或机器语言）目标程序。编译的过程就是一个不同语言翻译的过程，所以其过程类似于自然语言的翻译。,6.1.3编译程序的编译过程和编译程序的结构,自然语言的翻译,6.1.3编译程序的编译过程和编译程序的结构,编译过程可以划分成五个阶段,1.编译过程,编译程序的功能是把高级语言源程序翻译成等价的低级语言目标程序。源程序是由一些基本符号构成的，我们在运行这个程序时，先编译，若某处有错误，就报错，无错误就运行。编译程序在编译时，先将程序中的单词一个个分离出来，登记在一个表中，这叫词法分析，然后检查语句格式，叫做语法分析。然后检查类型是否一致，计算表达式的值叫语义分析。这些功能都是由编译程序相应的程序完成的。,6.1.3编译程序的编译过程和编译程序的结构,一般来说，整个编译过程可以划分成五个阶段：词法分析阶段语法分析阶段语义分析和中间代码生成阶段中间代码的优化目标代码的生成。,6.1.3编译程序的编译过程和编译程序的结构,1.编译过程,6.1.3编译程序的编译过程和编译程序的结构,2.一遍与多遍编译,编译程序还采用“分遍”的形式，即编译过程可通过一遍或多遍编译来完成。所谓编译的“一遍”（pass）是指下述过程：对于源程序或中间代码，从头到尾扫描一遍，并完成规定的处理任务，生成新的源程序的中间代码代码或目标代码。在单遍编译中，编译程序包括了编译程序的各个阶段的任务，所有的阶段由一遍完成，其结果是编译得很好，但通常代码效率差。,6.1.3编译程序的编译过程和编译程序的结构,2.一遍与多遍编译,在多遍扫描的编译程序中，每一遍完成一个或几个相关逻辑的工作，一个阶段的工作也可以分多遍来完成。例如，将词法分析作为第一编，语法分析和语义分析作为第二遍等。,6.2形式语言程序设计语言的语法描述,程序和自然语言一样，也有其语法规则，要对程序进行语法分析，就要先了解程序的语法规则。程序的语法规则称为文法，即文法是描述语言的形式规则（语法规则）。用一组数学符号和规则来描述的语言称为形式语言。目前程序设计语言都是用形式语言来描述，形式语言是编译原理的理论基础。,1.什么是形式语言?,6.2形式语言程序设计语言的语法描述,程序和自然语言一样，也有其语法规则，要对程序进行语法分析，就要先了解程序的语法规则。程序的语法规则称为文法，即文法是描述语言的形式规则（语法规则）。这种规则要能够描述程序语言各种不同的结构，同时还要使程序能够易于分析和翻译，最好能够根据其语法规则自动生成有效的语法分析程序。目前程序设计语言都是用形式语言来描述，形式语言是编译原理的理论基础。,6.2形式语言程序设计语言的语法描述,2.字母表和符号串,任何一种语言，都是由该语言的基本符号所组成的符号串的集合。例如，英语文章是由句子和标点符号构成的，句子是由单词构成的，而单词则是由字母构成的。,6.2形式语言程序设计语言的语法描述,2.字母表和符号串,（1）字母表字母表是符号的非空有穷集合，字母表中的元素称为符号。因此字母表也称为符号表。不同的语言有不同的字母表，例如英语的字母表是26个英文字母、数字和一些特殊符号。汉语的字母表是汉字、数字和专用符号等。而C语言的字母表包括关键字、字母、数字和一些专用符号。（2）符号串字母表中的符号所组成的任何有穷序列称为该字母表上的符号串。例如语句“if(x=8)thena=5elsea=9”可以看作是定义在C语言字母表上的一个符号串。,6.2形式语言程序设计语言的语法描述,3.什么是文法?,文法是描述语言语法结构的形式规则。我们以自然语言为例来说明。在描述一种语言时，就是要说明这种语言包含哪些句子。例如汉语，但汉语的句子有无穷多个，无法全部写出来。这就要制定有限条语法规则，用这些语法规则来产生汉语的全部句子。这些规则就是所谓的文法。,6.2形式语言程序设计语言的语法描述,3.什么是文法?,语法规则例如，定义如下语法规则：,语法规则例如，定义如下语法规则：=|=我|你|他|她=李翔|韩方|计算机|大学生|教师|C语言=是|学习=,由语法规则推导句子,6.2形式语言程序设计语言的语法描述,如用EBNF来描述文法的定义：=+|-=0|1|2|3|4|5|5|6|7|8|9,6.2形式语言程序设计语言的语法描述,=|=|=_|=a|b|c|d|e|f|g|h|i|j|z=A|B|C|D|E|F|G|H|I|J|Z=|8|9=0|1|2|3|4|5|6|7,C语言的“标识符”用BNF描述为：,词法分析是编译过程的基础，其任务是扫描源程序，根据语言的词法规则，分解和识别出每个单词，并把单词翻译成相应的机内表示。当然，词法分析在识别单词的过程中，同时也做了词法检查。,6.3第一阶段-词法分析,在高级语言中，所谓单词，就是指逻辑上紧密相连的一组字符，这些字符具有集体含义。单词是语言中最小的语义单位，如语言中的关键字、标识符、运算符和界限符。词法分析的依据是词的构造。单词的构造规则在高级语言中有明确的规定，比如哪些为保留字、变量如何定义、常量如何构造、分界符有哪些等。,6.3第一阶段-词法分析,词法分析的主要内容包括：（1）分析并识别单词及其属性；（2）跳过空格、回车、制表符等分隔符；（3）滤掉注释；（4）进行词法检查，报告发现的错误；（5）还要根据需要创建符号表、常量表等。,6.3第一阶段-词法分析,main()floatx=2,y=3,s;s=x+y*5;,例如，用C语言编写的程序段如下：,识别出的单词序列为表所示,6.3第一阶段-词法分析,表1词法分析程序,6.3第一阶段-词法分析,作为第二阶段的输入,语法分析是在词法分析的基础上进行的，是编译过程的第二个阶段。语法分析的任务是根据语言的语法规则，把单词符号串分解成各类语法单位，如表达式、语句等。并在分析过程中，对单词串组成的源程序进行语法正确性检查。通过语法分析，可以确定整个输入符号串是否构成一个正确的程序。,6.4第二阶段-语法分析,6.4第二阶段-语法分析,语法分析的结果是无语法错误的语法成分，有多种输出形式。,6.5第三阶段-语义分析和中间代码的生成,一个源程序通过词法分析和语法分析后，可以确定该源程序在单词拼写和语法上是正确的，但并没有分析其语句的逻辑含义，即要执行什么操作？词法和语法的正确并不能保证语义的正确正如一篇单词拼写正确、语法正确的文章，人们在阅读时首先是要能读通，然后是要理解每句话及整篇文章的含义或思想。这就是对文章的语义分析。,语义分析的任务是对各种不同语句进行翻译，包括两方面的工作：一是对每种语法范畴进行语义检查，如变量是否定义、类型是否正确等；二是在语义检查正确的情况下，进行中间代码的翻译。,程序的语义分析就是对程序的逻辑含义进行分析，是编译过程中最实质性的工作。,Why?,6.5第三阶段-语义分析和中间代码的生成,1.语义分析,中间代码是介于高级语言语句和低级语言语句之间的一种独立于具体硬件的记号系统，它即有一定程度的抽象，又和低级语言十分接近，因此，转换成目标代码很容易。,Why?,6.5第三阶段-语义分析和中间代码的生成,2.中间代码的生成,中间代码的表示形式有很多种，常见的有:四元式三元式间接三元式逆波兰式等。其中四元式的形式为:（运算符，运算对象1，运算对象2，结果）,6.5第三阶段-语义分析和中间代码的生成,6.6第四阶段中间代码优化,代码优化就是为提高目标代码质量而进行的加工和处理工作，使得目标代码在执行时效率更高，即执行时间更短，同时占用内存空间更小。一般优化工作阶段是在中间代码生成之后或目标代码生成之后，实际上，编译程序通常包括许多代码改进或优化步骤。,中间代码优化通过调整和改变中间代码中某些操作次序，以最终产生更加高效的目标代码。优化的主要手段有:删除冗余运算删除无用赋值合并已知量循环优化等。,6.6第四阶段中间代码优化,6.6第四阶段中间代码优化,这一阶段的任务是对前一阶段的中间代码变换成特定机器上的机器语言或汇编语言程序，实现机器的最终翻译。最后阶段的工作因为目标语言的关系而十分依赖机器的硬件系统，即如何充分利用机器现存的寄存器，合理的选择指令，生成尽可能短的目标代码，这与机器的硬件有关。,6.7第五阶段目标代码的生成,目标代码生成程序生成的目标代码有不同的形式，一般有以下三种形式。（1）能够立即执行的机器语言代码这种代码所有地址已定位，编译后可以立即执行。（2）待装配的机器语言代码模块需要执行时，必须经由连接装配程序将它们与另外一些运行子程序（如语言的系统函数库）连接装配起来，构成可以执行的机器代码。（3）汇编语言代码必须经过汇编程序将其汇编成可执行的机器语言代码。,6.7第五阶段目标代码的生成,6.7第五阶段目标代码的生成,6.8符号表管理和错误处理,6.8符号表管理和错误处理,在编译的各个阶段常常要收集和使用源程序的各种信息，为了方便，通常把这些信息保存在一些表中，如关键字表、常量表、数组信息表、标识符表等等，这些表称为符号表。这样，对源程序各种信息的记录、使用和管理，实际上就是对这些符号表的存储、访问和管理。,1.符号表,6.8符号表管理和错误处理,1.符号表,6.8符号表管理和错误处理,2.错误处理,尽管现在许多集成开发环境都提供了多种方法来保证源程序的正确性，如VisualStudio的关键字及其属性和方法的逐步提示等，但源程序往往含有各种各样的错误，包括不符合词法规则、语法规则、语义规则等规定产生的错误，以及数组维数太大等违反语言环境限制的错误等。例如编程时经常出现的关键字拼写错误、变量未声明、语句缺少成分不符合语法规则、运算的操作数类型不匹配等等。,6.8符号表管理和错误处理,2.错误处理,对于有错误的源程序，编译程序要具有查错和改错的功能。查错是指在编译过程中应该能够准确、及时地检查出错误，并以简明的形式报告错误的性质和出错位置，使程序员能够方便地修改源程序。改错是指在编译时不能一发现有错误就终止编译工作，发现错误时要对错误做适当的处理，从而使编译工作能够继续下去。,小结,