编译原理教程 01绪论

1、第1章绪论第一章 绪论编编 译译 技技 术术江苏大学计算机学院计算机科学系江苏大学计算机学院计算机科学系主讲：年 轶第1章绪论第一章 引 论FTPFTP地址：地址：3用户名：用户名：nianyi密码：密码：123456上传文件夹：上传文件夹：up -“课程内容课程内容” -“班级班级”下载文件夹：下载文件夹：down -“课程内容课程内容”上传文件压缩包命名规则：班级上传文件压缩包命名规则：班级+学号（末学号（末2位）位）+姓名姓名 例如：例如：J计计080101许燕许燕，软件软件080101王鹏晓，网络王鹏晓，网络090101符丹符丹，嵌软，嵌软09010

2、1张巍张巍第1章绪论第一章 引 论学时与参考教材学时与参考教材学时学时：35+1035+10小时小时 参考教材参考教材1 1、Compilers：Principles,Techniques,andTools 龙书龙书 该书出的比较早，但里面讲解的该书出的比较早，但里面讲解的核心编译核心编译原理至今都没原理至今都没有变过，所以一直到今天，它的有变过，所以一直到今天，它的价值都非凡价值都非凡。 这本书最大的这本书最大的特点特点就是一开始就通过一个实际的小例子，就是一开始就通过一个实际的小例子，把编译原理的把编译原理的大致内容大致内容罗列出来，让很多编译原理的初学者罗列出来，让很多编译原理的初学者很

3、快心里有了个底很快心里有了个底,也知道为什么会有这些理论，怎么运用这也知道为什么会有这些理论，怎么运用这些理论。些理论。第1章绪论1977年，Alfred V. Aho和Jeffrey D. Ullman合作出版了Principles of Compiler Design，封面是一位骑士和一只龙，龙是绿色的，因此被称为龙书或绿龙书。第1章绪论1986，原来的两位作者，加上Ravi Sethi，升级了前一本书，书名为 Compilers：Principles, Techniques, andTools ，封面沿用骑士和龙，但龙是红色的，因此被称为龙书二或红龙书。第1章绪论2006年底，龙书升级了

4、。作者增加了Monica S. Lam，名字与龙书二相同，封面依然沿用骑士和龙，但龙是紫色的，因此被称为龙书三或紫龙书。第1章绪论第1章绪论2 2、Modern Compiler Design 中文名字叫做中文名字叫做现代编译程序设计现代编译程序设计，此书比较，此书比较关注的是编译原理的实践，书中给出了不少的实际程关注的是编译原理的实践，书中给出了不少的实际程序代码，还有很多实际的编译技术问题等等。序代码，还有很多实际的编译技术问题等等。 此书另外一个特点就是其此书另外一个特点就是其“现代现代”而字。在传统而字。在传统的编译原理教材中，你是很少能看到如同的编译原理教材中，你是很少能看到如同Ja

5、va中的中的“垃圾回收垃圾回收”等算法的。等算法的。 如果你如果你想想深入学习编译原理的理论知识，那么你肯深入学习编译原理的理论知识，那么你肯定得看前面那本定得看前面那本龙书龙书，如果你想自己动手做一个先进，如果你想自己动手做一个先进的编译器，那么你的编译器，那么你得看这本得看这本现代编译程序设计现代编译程序设计。第1章绪论第一章 引 论为什么要学习编译原理？ 一个一个高手高手的必经之路，可以说不懂编译原理就的必经之路，可以说不懂编译原理就写不出好程序来。写不出好程序来。 如果哪一个高手说他如果哪一个高手说他不会不会编译原理，你大可编译原理，你大可以认为他在以认为他在说谎说谎。 通过了解程序如

6、何从通过了解程序如何从源代码源代码经过一步步操作经过一步步操作最终到最终到目标代码目标代码，可以，可以帮助帮助我们更好的理解计算我们更好的理解计算机，有助于编写好自己的代码。机，有助于编写好自己的代码。 能能更深入更深入的了解编出来的代码是怎样被机器的了解编出来的代码是怎样被机器识别运行的，有助于你编程时的排查错误。识别运行的，有助于你编程时的排查错误。第1章绪论第一章 引 论 你可以把学习的你可以把学习的过程过程当作一种当作一种了解了解，或者当，或者当作一种对作一种对数据结构和算法数据结构和算法的应用。能够让你更加的应用。能够让你更加深入的理解程序在计算机中是如何运行，以及甚深入的理解程序在

7、计算机中是如何运行，以及甚至加深对硬件体系的认识。至加深对硬件体系的认识。 可以进一步加深对可以进一步加深对相关语言相关语言的理解，以及运的理解，以及运用。用。知道知道为什么要有这样那样的限制或者为什么为什么要有这样那样的限制或者为什么语言本身这么来设计。语言本身这么来设计。 当你看到一个当你看到一个开发环境开发环境，比如，比如Visual Studio正正在编译执行你的在编译执行你的VC+源代码时，你知道它是如何源代码时，你知道它是如何处理的。处理的。 第1章绪论 在解决在解决其他复杂其他复杂的问题时，可以借鉴编译原理的的问题时，可以借鉴编译原理的思想思想，不，不一定是编译程序具体的一定是编

8、译程序具体的实现模式实现模式，而是解决编译问题时的思考，而是解决编译问题时的思考方法。方法。 在在20世纪世纪50年代，编译器的编写一直被认为是年代，编译器的编写一直被认为是十分困难十分困难的的事情，第一事情，第一Fortran的编译器据说花了的编译器据说花了18年的时间才完成。年的时间才完成。 在人们尝试编写编译器的同时，诞生了在人们尝试编写编译器的同时，诞生了许多跟编译相关的许多跟编译相关的理论和技术理论和技术，而这些理论和技术比一个实际的编译器本身价值，而这些理论和技术比一个实际的编译器本身价值更大更大。 就犹如数学家们在解决著名的哥德巴赫猜想一样，虽然没就犹如数学家们在解决著名的哥德巴

9、赫猜想一样，虽然没有最终解决问题，但是其间诞生不少名著的相关数论。有最终解决问题，但是其间诞生不少名著的相关数论。第1章绪论1.1 程序设计语言和编译程序程序设计语言和编译程序 1.2 编译程序的历史及发展编译程序的历史及发展 1.3 编译过程与编译程序结构编译过程与编译程序结构1.4 编译程序的开发编译程序的开发 1.5 构造编译程序所应具备的知识内容构造编译程序所应具备的知识内容 第1章绪论第1章绪论计算机语言计算机语言低级语言低级语言面向机器面向机器 主要包括：主要包括：机器机器语言、语言、汇编汇编语言语言 特点特点：与特定的机器有关，功效高，但使用复杂、繁：与特定的机器有关，功效高，但

10、使用复杂、繁琐、费时、易出错。琐、费时、易出错。 高级语言高级语言 面向用户面向用户 如：如： Fortran、Pascal、C 、Java语言等语言等 特点：特点：不依赖具体机器，移植性好、对用户要求低、不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。易使用、易维护等。 1.1 程序设计语言和编译程序程序设计语言和编译程序第1章绪论高级语言程序的执行方式高级语言程序的执行方式 编译编译 解释解释计算机系统的组成：计算机系统的组成： 裸机，系统程序裸机，系统程序(操作系统、操作系统、编译程序编译程序、解释程序解释程序、程序设计程序设计语言、连接装配程序、系统实用程序等语言、连接装配程

11、序、系统实用程序等)，应用程序。，应用程序。 第1章绪论 编译程序编译程序就是指这样一种程序，通过它能够将用高级语就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在言编写的源程序转换成与之在逻辑上逻辑上等价的低级语言形式的等价的低级语言形式的目标程序，见图目标程序，见图11。图图1-1 编译程序的功能编译程序的功能第1章绪论一个高级语言程序的执行通常分为两个阶段：一个高级语言程序的执行通常分为两个阶段： 编译阶段编译阶段和和运行运行阶段。阶段。 编译阶段编译阶段将源程序变换成目标程序。将源程序变换成目标程序。 运行阶段运行阶段则由所生成的目标程序连同则由所生成的目标程序连同运行

12、系统运行系统(数据空间分数据空间分配子程序、标准函数程序等配子程序、标准函数程序等)接受程序的初始数据作为输入，运接受程序的初始数据作为输入，运行后输出计算结果。行后输出计算结果。图图1-2 源程序的编译和运行阶段源程序的编译和运行阶段第1章绪论如果编译生成的目标程序是如果编译生成的目标程序是汇编语言汇编语言形式的，那么在编译形式的，那么在编译与运行阶段之间还要添加一个汇编阶段，它将编译生成的汇编与运行阶段之间还要添加一个汇编阶段，它将编译生成的汇编语言目标程序再经过汇编程序变换成机器语言目标程序，如图语言目标程序再经过汇编程序变换成机器语言目标程序，如图13所示。所示。图图1-3源程序的编译

13、、汇编和运行阶段源程序的编译、汇编和运行阶段第1章绪论用高级语言编写的程序也可通过用高级语言编写的程序也可通过解释程序解释程序来执行。解释程来执行。解释程序也是一种翻译程序，它将源程序作为输入，序也是一种翻译程序，它将源程序作为输入，一条一条语句语句一条一条语语句地读入并解释执行。句地读入并解释执行。 解释程序与编译程序的解释程序与编译程序的主要区别主要区别是：编译程序将源程序翻是：编译程序将源程序翻译成目标程序后再执行该目标程序；而解释程序则逐条译成目标程序后再执行该目标程序；而解释程序则逐条读出读出源源程序中的语句程序中的语句并并解释执行，即在解释程序的解释执行，即在解释程序的执行过程执行

14、过程中中并不产并不产生目标程序生目标程序。典型的解释型高级语言是。典型的解释型高级语言是BASIC语言。语言。图图1-4 解释程序的解释执行过程解释程序的解释执行过程第1章绪论1.3 编译过程和编译程序结构编译过程和编译程序结构编译程序的工作过程：编译程序的工作过程：1.词法分析阶段词法分析阶段2.语法分析阶段语法分析阶段3.语义分析和中间代码生成阶段语义分析和中间代码生成阶段4.优化阶段优化阶段5.目标代码生成阶段目标代码生成阶段第1章绪论1词法分析词法分析词法分析的词法分析的任务任务是输入源程序，对构成源程序的字符串是输入源程序，对构成源程序的字符串进行扫描和分解，识别出进行扫描和分解，识

15、别出一个个单词一个个单词符号，如符号，如基本字基本字(if、for、begin等等)、标识符标识符、常数常数、运算符运算符和和界符界符(如如“(”、“)”、“=”、“；”)等，等， 将将所识别出的单词所识别出的单词用统一长度的用统一长度的标准形式标准形式(也称内部码也称内部码)来表来表示，以便于后继语法工作的进行。示，以便于后继语法工作的进行。 因此，词法分析因此，词法分析工作工作是将源程序中的是将源程序中的字符串字符串变换成变换成单词符单词符号流号流的过程。的过程。 词法分析所词法分析所遵循遵循的是语言的的是语言的构词构词规则（词法规则）规则（词法规则） 。第1章绪论2语法分析语法分析语法分

16、析的语法分析的任务任务是在是在词法分析的基础上词法分析的基础上，根据语言的，根据语言的语法语法规则规则(文法规则文法规则)把单词符号流分解成各类语法单位把单词符号流分解成各类语法单位(语法范畴语法范畴)，如如“短语短语”、“子句子句”、“句子句子(语句语句)”、“表达式表达式”、“程序程序段段”和和“程序程序”等。等。 通过通过语法分析语法分析可以确定整个输入串是否构成一个可以确定整个输入串是否构成一个语法上正语法上正确的确的“程序程序”。 语法分析所遵循的是语言的语法分析所遵循的是语言的语法规则语法规则，语法规则，语法规则通常通常用用上上下文无关文法下文无关文法描述。描述。第1章绪论形式语言

17、学（形式语言学（代数语言学） 运用形式模型（抽象符号系统）对语言(包括人工语言和自然语言)进行理论上的分析和描写。 描述语言有三种途径:1穷举 2文法 3自动机。 文法是指的产生过程,而自动机是指的识别过程。 一种语言,如果存在对它的识别过程,就一定存在对它的产生过程,反之亦然。 现行的形式语法系统是Chomsky于1956年为了描述自然语言而提出的一种理论模型。第1章绪论上下文无关文法上下文无关文法 文法文法描述语言的语法结构的形式规则（即语法规则）。 上下文无关文法上下文无关文法它是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。举例： 程序语言中，当碰

18、到一个算术表达式时，对它“就事论事”进行处理，不必考虑它所处的上下文。 自然语言中，一个句子，一个词，它们的语法性质和所处的上下文往往有密切的关系。第1章绪论3语义分析和中间代码生成语义分析和中间代码生成这一阶段的这一阶段的任务任务是对各类不同是对各类不同语法范畴语法范畴按按语言的语义语言的语义进行进行初初步翻译步翻译，包含两个方面的工作：，包含两个方面的工作： 一是对每种语法范畴进行一是对每种语法范畴进行静态语义检查静态语义检查，如变量是否定义、类，如变量是否定义、类型是否正确等；型是否正确等； 二是在二是在语义检查正确语义检查正确的情况下进行中间代码的翻译。的情况下进行中间代码的翻译。 中

19、间代码中间代码是是介于介于高级语言的语句和低级语言的指令之间的一高级语言的语句和低级语言的指令之间的一种独立于具体硬件的记号系统，它既有一定程度的抽象，又与低种独立于具体硬件的记号系统，它既有一定程度的抽象，又与低级语言的指令十分接近，因此转换为目标代码比较容易。级语言的指令十分接近，因此转换为目标代码比较容易。 把语法范畴翻译成中间代码把语法范畴翻译成中间代码所遵循所遵循的是的是语言的语义规则语言的语义规则，常见，常见的中间代码有的中间代码有四元式、三元式、间接三元式和逆波兰记号四元式、三元式、间接三元式和逆波兰记号等。等。第1章绪论4优化优化优化的任务是对前阶段产生的中间代码进行等价变换或

20、改优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得造，以期获得更为高效更为高效(节省时间和空间节省时间和空间)的目标代码。的目标代码。 常用的常用的优化措施优化措施有删除冗余运算、删除无用赋值、合并已知有删除冗余运算、删除无用赋值、合并已知量、循环优化等。量、循环优化等。 例如，其值例如，其值并不随循环并不随循环而发生变化的运算可提到进入循环前而发生变化的运算可提到进入循环前计算一次，而不必在循环中每次循环都进行计算。优化所遵循计算一次，而不必在循环中每次循环都进行计算。优化所遵循的原则是程序的等价变换规则。的原则是程序的等价变换规则。第1章绪论5目标代码生成目标代码生成这一阶段

21、的任务是把中间代码这一阶段的任务是把中间代码(或经优化处理之后或经优化处理之后)变换成变换成特特定机器上定机器上的的机器语言程序或汇编语言程序机器语言程序或汇编语言程序，实现最终的翻译工作。，实现最终的翻译工作。 此工作因为此工作因为目标语言目标语言的关系而十分的关系而十分依赖硬件系统依赖硬件系统，即如何充，即如何充分利用机器现有的寄存器，合理地选择指令，生成尽可能短且有分利用机器现有的寄存器，合理地选择指令，生成尽可能短且有效的目标代码，这些都与目标机器的硬件结构有关。效的目标代码，这些都与目标机器的硬件结构有关。上述编译过程的五个阶段是编译程序工作时的动态特征，编上述编译过程的五个阶段是编

22、译程序工作时的动态特征，编译程序的结构可以按照这五个阶段的任务分模块进行设计。译程序的结构可以按照这五个阶段的任务分模块进行设计。第1章绪论图图15 编译程序结构示意编译程序结构示意 第1章绪论编译过程中源程序的编译过程中源程序的各种信息各种信息被保留在不同的表格里，编被保留在不同的表格里，编译各阶段的工作都译各阶段的工作都涉及涉及到构造、查找或更新有关的到构造、查找或更新有关的表格表格，编译，编译过程的过程的绝大部分时间都绝大部分时间都用在造表、查表和更新表格的事务上，用在造表、查表和更新表格的事务上，因此，编译程序中还应包括一个因此，编译程序中还应包括一个表格管理程序表格管理程序。出错处理

23、出错处理与编译的各个阶段都有联系，与前三个阶段的联与编译的各个阶段都有联系，与前三个阶段的联系尤为密切。系尤为密切。出错处理程序应在出错处理程序应在发现错误后，将错误的有关信发现错误后，将错误的有关信息如错误类型、出错地点等向用户报告。此外，为了尽可能多息如错误类型、出错地点等向用户报告。此外，为了尽可能多地发现错误，应在发现错误后还能继续编译下去，以便发现更地发现错误，应在发现错误后还能继续编译下去，以便发现更多的错误。多的错误。第1章绪论1.4 编译程序的开发编译程序的开发编译程序的开发常常采用编译程序的开发常常采用自编译自编译、交叉编译交叉编译、自展和移植等自展和移植等技术实现。技术实现

24、。1自编译自编译用某种高级语言书写自己的编译程序称为自编译。用某种高级语言书写自己的编译程序称为自编译。 例如，假定例如，假定A机器上已有一个机器上已有一个PASCAL语言可以运行，则语言可以运行，则可以可以用用PASCAL语言语言编写编写出一个功能出一个功能更强的更强的PASCAL语言编译程序语言编译程序，然后借助于原有的然后借助于原有的PASCAL编译程序对新编写的编译程序对新编写的PASCAL编译程编译程序进行编译，从而在编译后即得到一个能在序进行编译，从而在编译后即得到一个能在A机器上运行的功能机器上运行的功能更强的更强的PASCAL编译程序。编译程序。第1章绪论2交叉编译交叉编译交叉

25、编译交叉编译是指用是指用A机器上的编译程序来产生可在机器上的编译程序来产生可在B机器上运机器上运行的目标代码。行的目标代码。 例如，若例如，若A机器上已有机器上已有C语言语言可以运行，则可用可以运行，则可用A机器中的机器中的C语言书写一个编译程序，它的源程序是语言书写一个编译程序，它的源程序是C语言程序，而产生的语言程序，而产生的目标程序则是基于目标程序则是基于B机器的，即机器的，即能够在能够在B机器上机器上执行的低级语言执行的低级语言程序。程序。以上两种方法都以上两种方法都假定假定已经有了一个系统程序设计语言可以已经有了一个系统程序设计语言可以使用。使用。第1章绪论3自展自展自展的方法是：自

26、展的方法是：首先首先确定一个非常简单的核心语言确定一个非常简单的核心语言L0，然后，然后用用机器语言或汇编语言机器语言或汇编语言书写出它的编译程序书写出它的编译程序T0；再把语言；再把语言L0扩充扩充到到L1，此时有，此时有L0L1，并用，并用L0编写编写L1的编译程序的编译程序T1(即自编译即自编译)；然后再把语言然后再把语言L1扩充为扩充为L2，此时有，此时有L1L2，并用，并用L1编写编写L2的编的编译程序译程序T2这样不断扩展下去，直到完成所要求的编译程序这样不断扩展下去，直到完成所要求的编译程序为止。为止。第1章绪论4移植移植移植移植是指是指A机器上的某种高级语言的编译程序机器上的某

27、种高级语言的编译程序稍加稍加改动后能改动后能够在够在B机器上运行。一个程序若能较容易地从机器上运行。一个程序若能较容易地从A机器上搬到机器上搬到B机器机器上运行，则称该程序是可移植的。移植具有一定的局限性。上运行，则称该程序是可移植的。移植具有一定的局限性。用系统程序设计语言来书写用系统程序设计语言来书写编译程序编译程序虽然缩短了开发周期并虽然缩短了开发周期并提高了编译程序的质量，但提高了编译程序的质量，但实现的自动化实现的自动化程度不高。实现编译程程度不高。实现编译程序的序的最高境界最高境界是能够有一个自动生成编译程序的软件工具，只要是能够有一个自动生成编译程序的软件工具，只要把把源程序的定

28、义源程序的定义以及机器语言的以及机器语言的描述描述输入到该软件中，就能自动输入到该软件中，就能自动生成这个语言的编译程序，如图生成这个语言的编译程序，如图16所示。所示。第1章绪论图16 编译程序自动生成示意第1章绪论1.5 构造编译程序所应具备的知识内容构造编译程序所应具备的知识内容对被编译的对被编译的源语言源语言(如如C、PASCAL等等)，要，要深刻理解深刻理解其结其结构构(语法语法)和含义。和含义。对目标机器的对目标机器的硬件和指令系统硬件和指令系统有深刻的了解。有深刻的了解。熟练掌握熟练掌握编译方法编译方法。第1章绪论(1) 对被编译的对被编译的源语言源语言(如如C、PASCAL等等

29、)，要，要深刻理解深刻理解其其结构结构(语法语法)和含义。例如，下面的和含义。例如，下面的for循环语句：循环语句： for(i=1;i=10+i;i+) x=x+1; 就存在对就存在对循环终值循环终值的理解问题。的理解问题。 一种一种理解理解是以是以第一次第一次进入进入for循环的循环的i值计算出值计算出循环终值循环终值，此，此循环终值在循环中不再改变，也即循环终值为循环终值在循环中不再改变，也即循环终值为11； 另一种另一种理解理解则是循环终值表达式则是循环终值表达式10+i中的中的i值随循环在不断值随循环在不断地改变，此时地改变，此时for语句将出现死循环。语句将出现死循环。 如如TUR

30、BO PASCAL就是按第一种语义进行翻译的，而就是按第一种语义进行翻译的，而TURBO C则是按第二种语义翻译的。此外，如果出了循环后则是按第二种语义翻译的。此外，如果出了循环后还要引用还要引用i值，那么这个值，那么这个i值究竟是值究竟是循环终值循环终值还是还是循环终值加循环终值加1？因此，对语义的不同理解可以得到不同的编译程序。因此，对语义的不同理解可以得到不同的编译程序。第1章绪论(2) 必须对目标机器的必须对目标机器的硬件和指令系统硬件和指令系统有深刻的了解。有深刻的了解。 例如，产生两个数相加的指令在例如，产生两个数相加的指令在8086/8088汇编中假定用下面汇编中假定用下面两种两种指令实现：指令实现：ADD AX，06或或ADD BX，06 粗略看来，这两条加法指令除了粗略看来，这两条加法指令除了寄存器寄存器不同外没有本质上的差不同外没有