编译原理 第一章 概述

编译原理主讲：欧阳俊林联系方式：手机：[phone]E_Mail：[e-mail]：8069195课程成绩：平时：20%实验：20%期末：60%提交作业方式：电子版（默认）/手写均可邮件标题：作业-班号-姓名-作业号例如：软件专061班张三同学第1章作业邮件标题为：作业-软件专071-张三-1每次作业用1个文件上交。如果需要多个文档，则使用winrar压缩成1个文件后上交。文件名同邮件标题。课程要求讲课进度较快，平时不复习并加深理解，后面可能听不懂。作业较多，要求独立完成。上机实验，要求给予足够重视。一、学习编译原理的意义对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用。从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中。大多数程序员同时是简单语言的设计者，有助于提高对这些语言的设计水平。在软件逆向工程、程序理解和软件安全等方面有着广泛的应用。要求先学习以下课程1.程序设计语言2.算法与数据结构：栈分配、堆分配、静态分配等各种存储分配方式。线性表、二叉查找树、哈希表等多种数据结构。3.离散数学：集合论与数理逻辑是进一步学习形式语言与自动机理论的数学基础。最好学习过或同时学习以下课程1.软件工程：掌握大型程序设计以及工程化的软件生产方法。2.形式语言与自动机：相当于本课程中词法分析与语法分析的理论基础。学好离散数学、数据结构、操作系统、编译原理这四门计算机专业的主干课，对自己的可持续发展是至关重要的，可惜这样的体会在工作中才得出(离散、DS、算法、编译、组成原理、DBS原理)。教材及参考书教材：编译技术(第二版)参考书：1、Compilers:Principles,Techniques,andTools(龙书)作者：AlfredV.Aho,RaviSethi,JeffreyD.Ullman2、ModernCompilerImplementationinC/JAVA(虎书)作者：AndrewW.Appel,withJensPalsberg3、AdvancedCompilerDesignandImplementation(鲸书)作者：AndrewW.Appel4、程序设计语言编译原理作者：陈火旺5、编译原理作者：陈意云6、编译原理作者：吕映芝CH1概论1．1程序设计语言及编译程序机器语言：能够被计算机的硬件系统直接执行的指令程序。汇编语言：将硬件指令用一些助记符表示。如ADD表示加法操作，SUB表示减法操作等等。称为符号化的机器语言。高级语言：使用便于理解的自然语言。这类语言完全摆脱了机器指令的约束，用它编写的程序接近自然语言和习惯上对算法的描述，故称为面向用户的语言。后来，又相继出现许多专门用于某个应用领域问题的专业语言，例如用于数据库操作的SQL语言，这类语言称为面向问题的语言。翻译程序：将源程序转换为目标程序的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。“翻译程序”将高级语言编制程序翻译成与之等价的汇编语言或机器语言程序，这种“翻译程序”就称为“编译程序”（或编译器）。“翻译程序”将汇编语言编制的程序翻译成机器语言程序，这种“翻译程序”称为“汇编程序”。“翻译程序”将源程序按动态顺序逐句进行分析解释翻译，边解释边执行，不产生目标程序，这种“翻译程序”称为“解释程序”。对某种语言来说，其编译程序再加上一些相应的支持用户程序运行的子程序构成的运行系统合称为该语言的编译系统。编译系统是计算机的重要组成部分。源程序、翻译程序、目标程序三者关系：源程序翻译程序目标程序SOURCEPROGRAMTRANSLATEROBJECTPROGRAM即源程序是翻译程序的输入，目标程序是翻译程序的输出源程序目标程序(*.C/*.PAS)(*.OBJ/*.EXE)解释程序源程序输入数据计算结果(*.bas/dos-shell)A语言转换程序编译程序B语言1．2编译过程和编译程序结构编译程序的主要功能是将一种高级语言程序翻译为等价的机器语言或汇编语言程序，实现的是语言的翻译，那么我们可以和英文的翻译过程类比。尽管编译过程和英文翻译的过程比较类似，但编译程序所翻译的毕竟不是自然语言，所以有自身特有的工作。比如中间代码的生成，编译过程中信息表的构造与查询以及运行时存储空间的分配，对语法和语义错误的处理等。翻译英文编译程序分析阅读原文识别单词分析句子输入并扫描源程序词法分析语法分析综合修辞加工写出译文代码优化目标代码生成1．词法分析程序词法分析程序又称扫描器。词法分析的主要任务是从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位“单词”，并指出其属性是标识符、分界符、数等等。其功能还包括删除无用字符和注释及进行词法检查。词法分析输出的单词常用形如(Class，Value)的二元组表示。表示单词属性的类别码Class可采用整数码或有意义的记号来表示。Value则是单词的值。例如，表达式y:=z+18*3经词法分析其结果如右图所示。词法分析就好比在自然语言中挑出句子中的各种单词并给出词性。如猴子吃香蕉，分析结果为：猴子（名词）、吃（动词）、香蕉（名词）。而在编译程序的词法分析中，同样是识别各种单词，只是单词的词性用某种记号或整数码来表示。ClassValueID‘y’:=‘:=’ID‘z’+‘+’NUM‘18’*‘*’NUM‘3’词法分析结果2．语法分析程序语法分析的功能是根据程序设计语言的语法规则分析源程序的结构，从词法分析的结果“单词序列”中识别出各种语法成分，如“程序”、“语句”、“表达式”等，并判别它是否为合法程序，检查出语法错误。语法分析与分析句子成分相类似，根据句子由主语、谓语组成，谓语由动词、宾语组成等语言规则，可对句子“猴子吃香蕉”的进行分析，如右图所示。可见，语法分析的一般途径就是试着为输入串构造一棵语法树。句子谓语主语宾语动词(吃)名词(猴子)名词(香蕉)句子“猴子吃香蕉”的语法分析树在编译程序的语法分析中，也按同样的方式依据程序设计语言的语法规则进行语法归类。如表达式y:=z+18*3，经词法分析可得出y为标识符、18为整数等等，其语法树如下图所示。如果在分析过程中，无法将某个单词符号进行语法归类，则表示该表达式有语法错误。表达式y:=z+18*3的语法树NUM（3）表达式:=ID（y）项+表达式项表达式NUM（18）ID（z）因子*因子因子项3．语义分析程序任何程序设计语言都具有语法特征和语义特征。前者用来定义语言各语法成分的形式或结构，后者则用来规定各语法成分的含义和功能。因此，编译过程也需要对源程序进行语义分析。语义分析的功能是确定源程序的语义是否正确，确定各语法成分的含义和用途以及应进行的运算和操作。句子“猴子吃香蕉”语义正确，而写成“香蕉吃猴子”语义就错了。语义检查十分复杂，主要审查的有上下文相关性，类型匹配，类型转换等。例如分析表达式a+b时，当分析到+操作时，语义分析程序就要分析a、b是否已经声明、是否具有兼容的类型、是否已经有值。为了识别出这些语义错误，语义分析要进行频繁的造表和查表工作。由于程序设计语言的语义至今没有系统的描述方法,不得不采用半机械化的方法”语法制导翻译”,即把编译程序的语法分析和语义分析有机的组织起来穿插进行。为了便于代码的优化处理，语义分析之后通常生成一种中间代码形式。常用的中间代码有逆波兰表示、三元式、四元式及树形结构等。中间代码具有易于产生、易于翻译成目标程序的特点，可看成是一种抽象机的指令代码。例如表达式a:=x+(y-2)DIV4用逆波兰表示为：‘a’‘x’‘y’‘2’‘-’‘4’‘DIV’‘+’‘:=’例如表达式(a+b)*(c+d)用四元式表示为：(add,‘a’,‘b’,T1)(add,‘c’,‘d’,T2)(mult,T1,T2,T3)4．中间代码生成5．代码优化经过语义分析后编译程序将源程序生成中间代码，这时的中间代码往往有些重复和冗余。代码优化的目的就是提高目标程序的质量(时空指标)。代码优化可分为局部优化和全局优化。在局部范围可做的优化有常数表达式的计算或根据操作符的某些性质如可结合性、可交换性和分配性以及检测公共子表达式进行优化。例如四元式中间代码如下：(*,3.14,2,T1)(=,T1,_,x)(*,2,5,T2)(*,T2,a,T3)(=,T3,_,y)(+,x,1,T4)(=,T4,_,z)而优化后的代码如下：(=,6.28,_,x)(*,10,a,y)(=,7.28,_,z)代码优化是以增加编译程序本身的时空复杂度和可靠性为代价的，它不是编译程序的必要组成部分，不同的编译程序所进行的代码优化程度差别很大，能够完成代码优化的编译程序称为“优化编译程序”。6．目标代码生成编译的最后一步是将优化后的中间代码生成特定机器上的低级语言代码。这部分与机器类型有关，对程序中的每个变量指定存贮单元，把中间代码的指令翻译成等价的某种类型机器的机器指令代码或汇编指令代码。目标代码有三种形式：绝对指令代码：内存中有固定的存放位置，可立即执行。可重定位的机器指令代码：目标程序一般具有浮动地址，在运行前必须借助于一个连接装配程序把各个目标模块(包括系统提供的运行子程序)连接在一起，确定程序中的变量在内存中的位置，装入内存中指定起始地址，使之成为一个可以运行的绝对指令代码程序。现在多数编译程序产生的是可重定位的机器指令代码。汇编指令代码：须经汇编程序翻译后才能运行。7．错误处理程序编译的各个阶段都可能发现源程序中的错误。发现错误后如果立即停止编译，往往会降低调试程序的效率，所以应对出现的错误做适当的处理，从而使编译能继续进行。词法分析可以检测出源程序中的非法符号，就好比自然语言语句中的出现的错字、错词。语法分析能够发现程序语句中的各种语法错误，如括号不匹配等。语义分析能判断运算对象的类型是否匹配、变量是否重复声明或没声明就使用等错误。任意时刻发现错误，都应该报告错误信息，包括错误出现的位置、错误性质等，为程序员调试程序提供方便。由此可见，错误检测和恢复也是编译程序中的一项重要工作。除报错外，编译程序还可生成辅助性的注释信息，如根据请求打印“对照表”和卸出各变量的值。8．信息表管理程序编译过程中要记录源程序中出现的标识符，并收集每个标识符的各种属性信息。在词法分析中，对所有标识符都用一个统一的符号表示，那么这个符号代表的标识符是变量名、函数名还是其它对象名称呢？如果是变量名，那么变量的类型是什么？如果是函数名，那么编译程序怎么知道参数的个数、类型及返回值的类型等信息呢？为此需要建立一个符号表记录有关标识符的各种信息。符号表是由若干记录组成的数据结构，每个标识符在表中有一条记录，每条记录有多个域，每个域记载标识符的一个属性。例如下面一条记录说明标识符x是整型变量及分配的内存地址。标识符名标识符类型类型地址x1（表示变量）1（表示整型）0001标识符的各种属性是在编译的不同阶段填入符号表的。词法分析阶段只能分析出标识符名，语法分析阶段只能判断标识符在语句中出现是否合法，只有到了语义分析阶段，才能将标识符的各种属性填入符号表并使用这些属性生成中间代码。所以，信息表管理程序被分别安插在编译程序的有关部分，完成造表和查表的工作。前端后端把编译程序分为前端和后端的优点是便于编译程序的构造、移植。例如当需要改动源语言时(如源语言版本升级)，只须修改编译程序前端。当需要变更一种语言的目标计算机时(即移植编译程序)，只须重新开发相应的后端。又比如有M种高级语言、N种目标机器，如果不分前端和后端，就需要建立M*N套编译程序，而分成前端和后端，可先建立M套前端编译程序将M种高级语言翻译成相同的中间语言，再建立N套后端翻译程序将中间语言翻译成N种机器的目标语言，这样只需要建立M套前端编译程序和N套编译程序后端编译程序，不仅程序个数减少，而且每端只包含编译程序的部分任务，更加易于实现。所谓一“遍”是指编译程