编译原理教程.ppt

21世纪高等院校规划教材第一章编译程序概论本章学习目标1.1程序设计语言机器语言本身是有由0和1组成的，符合计算机的硬件特性，因此能够直接执行。但用机器语言编写程序很不方便且容易出错，因此就用助记符代替机器语言，产生了汇编语言。汇编语言比机器语言在可读性方面有了进步，但是其依赖具体机器的特性无法改变，给程序设计语言增添了难度。高级语言不能直接在机器上运行，它不是面向机器，而是面向应用的，因此，要想让高级语言运行必须有编译程序。编译程序就是这样的一种程序，它能将高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序。高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段，源程序的运行过程如图1-1所示。编译阶段将源程序变换成目标程序；运行阶段则由所生成的目标程序连同运行系统（数据空间分配子程序、标准函数程序等）接受程序的初始数据作为输入，运行后输出计算结果。如果目标程序是汇编语言的形式，则需要在编译阶段和运行阶段之间加一个汇编阶段。源程序高级语言编写的程序除了可以通过编译方式外，还可以通过解释程序执行。所谓解释程序是一种语言翻译程序，读入一条语句，解释一条语句，执行一条语句，边读入边执行。解释程序与编译程序的主要区别是：编译程序将源程序翻译成目标程序后再执行目标程序，而解释程序是逐条读出源程序中的语句并执行，即在解释程序的执行过程中并不产生目标程序。1.2编译程序的编译过程和结构一般来说，整个编译过程可以划分成五个阶段：词法分析阶段、语法分析阶段、语义分析和中间代码生成阶段、中间代码的优化和目标代码的生成。1.词法分析阶段在高级语言中，所谓单词，就是指逻辑上紧密相连的一组字符，这些字符具有集体含义。单词是语言中最小的语义单位，如语言中的关键字、标识符、运算符和界限符。词法分析的依据是词的构造。单词的构造规则在高级语言中有明确的规定，比如哪些为保留字、变量如何定义、常量如何构造、分界符有哪些等。例如，用C语言编写的程序段如下：main(){floatx=2,y=3,s;s=x+y*5;}识别出的单词序列为表1-1所示表1-1词法分析程序2.词法分析3．语义分析和中间代码的生成中间代码的表示形式有很多种，常见的有四元式、三元式、间接三元式和逆波兰式。其中四元式的形式为（运算符，运算对象1，运算对象2，结果）4.中间代码优化5．目标代码的生成编译过程可以划分成五个阶段，这种划分是编译程序的逻辑组织形式。实际上，编译过程往往分成前端和后端。前端包括词法分析、语法分析、语义分析、中间代码生成和中间代码优化，主要依赖于源程序；后端包括目标代码生成，依赖于计算机硬件系统和机器指令系统。这种组织方式，便于编译程序的移植，若要将编译程序移植到不同类型的机器，只需要修改编译程序的后端即可。编译程序还采用“分遍”的形式，即编译过程可以由一遍或多遍编译程序来完成。对于源程序或中间代码，从头到尾扫描一次并完成所规定的工作称为一遍。在一遍中，可以完成一个或相连几个逻辑步骤的工作。例如可以把词法分析作为第一遍；语法分析和语义分析作为第二遍；代码优化和存储分配作为第三遍；代码生成作为第四遍；从而构成一个四遍扫描的编译程序。词法分析器1.3编译程序的设计技术1．高级语言的自编译技术用某种该高级语言书写自己的编译程序称为自编译。2.交叉编译交叉编译是指用A机器上的编译程序来产生可在B机器上运行的目标代码。例如，若A机器上已有C程序可以运行，则可以在A机器上的C程序书写一个编译程序，它的源程序是C语言程序，而产生的目标程序则是基于B机器上的，即能够在B机器上执行的低级语言程序。3．编译程序的自展技术Ln=L…L1L0图1-4编译系统的自展过程自展的方法是：首先确定一个非常简单的核心语言L0，然后用机器语言或汇编语言书写它的编译程序T0；再把语言L0扩充到L1,此时有L0属于L1，并用L0编写出L1的编译程序T1，然后再把语言L1扩充为L2，此时，L1属于L2，并用L1编写L2的编译程序T2,……这样不断的扩展下去，直到完成所要求的编译程序为止。自展技术的使用如图1-4所示。4．编译程序的移植技术编译程序可以通过移植得到，即可以将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序移植到另一个机器（目标机）上。5．编译程序的自动化在编译程序的自动化开发过程中，开发较早的是词法分析程序生成器和语法分析程序生成器。使用的工具是在UNIX操作系统下的软件工具LEX和YACC。1.4形式语言和编译实现技术形式语言理论采用数学那样的符号形式表示，数学那样的严格推理。采用形式语言方式讨论程序设计语言及其编译程序的构造，可以使我们不仅了解一些编译实现技术如何应用，而且还可以理解如此做的原因。对编译程序的设计中所采用的技术，不但要知其然，而且还要知道所以然。从理论高