《课程说明 - East China Normal University》由会员分享，可在线阅读，更多相关《课程说明 - East China Normal University（49页珍藏版）》请在金锄头文库上搜索。
1、1.课程说明及引论,编译原理实践,序言,编译原理的课程实践一般有两种安排： 配合编译课程教学，安排多次小型实践，分别支持编译程序的各个阶段 针对某一规模适中的语言来设计和实现一个相对完整、独立的编译器。 编译原理实践作为编译原理课程的延伸，目的是让大家动手设计和实现某一规模适中的语言的编译器 涉及编译程序的各个阶段 强调了编译的总体设计、各个阶段的接口安排等等 学会运用所学技术解决实际问题,课程目标,回顾编译相关的文法和形式语言基本理论 以PL/0语言为例，介绍一个编译程序从语法定义、词法分析、语法分析、出错处理、代码生成到解释执行的全过程。使学生了解什么是编译，并懂得怎样从语言的定义出发，系
2、统地去开发一个语言的编译程序 介绍Lex（词法分析程序的生成系统） ,在1954年至1957年期间，IBM的John Backus带领的一个研究小组对FORTRAN语言及其编译器的开发 Noam Chomsky开始了他的自然语言结构的研究。他的发现最终使得编译器结构异常简单，甚至还带有了一些自动化 Chomsky的研究导致了根据语言文法(grammar)的难易程度以及识别它们所需的算法来为语言分类,乔姆斯基分类结构( Chomsky hierarchy)-文法的4个层次：0型、1型、2型和3型文法，且其中的每一个都是其前者的专门化 2型(或上下文无关文法(context-free gramma
3、r)被证明是程序设计语言中最有用的，而且今天它已代表着程序设计语言结构的标准方式,2. 编译程序的组成,编译过程,1.词法分析 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个具有独立意义的最小语法单位“单词 (token) ” 单词：是语言的基本语法单位，一般语言有四大类单词： 关键字或保留字(如BEGIN、END、IF) 标识符 常数 分界符(运算符)，如+、-、*、/、；、(、),举例： 1)a:=10+c*20 2)while x0 do x:=x-1 词法分析是一种线性分析,2.语法分析 在词法分析的基础上，根据语言的语法定义规则，识别出构成单词符号串的各类语法单位。 通
4、过语法分析，确定整个输入符号串是否构成语法上正确的“程序” 举例： a:=10+c*20 语法分析是一种层次分析,3.语义分析与中间代码产生 对识别出的各种语法成份进行语义分析，并产生相应的中间代码 中间代码：一种介于源语言和目标语言之间的中间语言形式 生成中间代码的目的： 便于做优化处理 便于编译程序的移植,中间代码的形式：编译程序设计者可以自己设计，常见的中间代码有：三元式、间接三元式、四元式、逆波兰表示、树形表示、 P-Code、C-Code、U-Code、bytecode等 中间代码具有易于产生，易于翻译成目标程序的特点，可以看成是一种抽象机的指令代码 中间代码的设计在相当大的程度上是
5、一种技巧，而不是科学 中间代码设计方案数可能两倍于编译器套件种类数！,举例： a:=10+c*20 由语法分析识别出为赋值语句，语义分析首先要分析语义上的正确性，例如要检查表达式中和赋值号两边的类型是否一致 根据赋值语句的语义，生成中间代码。即用一种语言形式来代替另一种语言形式，这是翻译的关键步骤。,4.代码优化 经过语义分析后，编译程序将源程序生成中间代码，这时的中间代码往往有些重复和冗余。对代码进行优化的目的是提高目标程序的执行效率 代码优化首先在中间代码上进行。在局部范围可能做的优化有常数表达式的计算或根据操作符的某些性质如可结合性、可交换性和分配性以及检测公共子表达式进行优化 不同的编
6、译器所作的代码优化工作量相差很大,5.目标代码生成 编译的最后一步是将中间代码生成特定机器上的低级语言代码 这部分与机器类型有关，对程序中的每个变量指定存贮单元，把中间代码的指令翻译成等价的某种类型机器的机器指令代码或汇编指令代码,目标代码的形式可以是绝对指令代码、可重定位的机器指令代码或汇编指令代码 如果目标是绝对指令代码，则可立即执行 如果是汇编指令代码，还需经汇编程序翻译后才能运行 现在多数编译程序产生的是可重定位的机器指令代码，这种目标代码在运行前必须借助于一个连接装配程序把各个目标模块（包括系统提供的库模块）连接在一起，确定程序中的变量在内存中的位置，装入内存中指定起始地址，使之成为
7、一个可以运行的绝对指令代码程序,什么是链接器（Linker） 链接器的功能是，将一个或多个由编译器生成的目标文件及库链接为一个可执行文件。,注意！,上述编译过程的5个阶段是一种典型的分法，并非所有的编译程序都分成5个阶段 本书中PL/0语言的编译程序省略了优化阶段；同时省去了最后的目标代码生成阶段，取而代之的是增加一个解释程序，由解释程序来解释执行中间代码程序，同样可以得到最终结果,编译和解释,解释程序：在解释程序的执行过程中不产生目标代码。每读一条源程序代码，就将它解释成等价的若干条机器代码，并执行之。一些规模较小的语言，如BASIC，常采用此方式。 通常把编译和解释作某种程度的结合。如Ja
8、va，先将源程序由java编译器(javac)编译生成字节码(bytecode)文件，然后由一个虚拟机对得到的字节码加以解释执行(java)。 注：字节码文件是与平台无关的二进制码。 PL/0编译程序也采用了编译和解释相结合的方式,6.符号表管理 编译过程中要记录源程序中出现的标识符，并收集每个标识符的各种属性信息。为此需要建立一个符号表记录有关标识符的各种信息。 符号表是由若干记录组成的数据结构，每个标识符在表中有一条记录，每条记录有多个域，每个域记载标识符的一个属性。 符号表的设计在很大程度上说它是一种艺术比说它是科学原理更合适：符号表的属性随语言的不同而变化，全局符号表最重要的是接口和性
9、能，等等,7.出错处理 编译的各个阶段都可能发现源程序中的错误。发现错误后如果立即停止编译，往往会降低调试程序的效率，所以应对出现的错误做适当的处理，从而使编译能继续进行。 词法分析可以检测出源程序中的非法符号，就好比自然语言语句中的出现的错字、错词。语法分析能够发现程序语句中的各种语法错误，如括号不匹配等等。语义分析能判断运算对象的类型是否匹配、变量是否重复声明或没声明就使用等错误。 任意时刻发现错误，都应该报告错误信息，包括错误出现的位置、错误性质等，为程序员调试程序提供方便。由此可见，错误检测和恢复也是编译程序中的一项重要工作。,3. 编译程序的结构,在设计和实现编译程序时，要考虑编译程
10、序分“遍”的问题。 所谓一“遍”是指在编译时把源程序或者中间形式从头到尾扫描一遍，并作相关处理，生成新的中间形式或目标代码 采用不同的分遍方式，编译程序的结构也有所不同,单遍编译程序,单遍编译程序只对源程序进行一遍扫描，就完成编译的各项任务，产生目标代码。在单遍编译程序中，往往以语法分析程序为中心，词法分析和语义分析作为语法分析的子程序。其工作过程如下： 当语法分析需要读进一个新单词时，就调用词法分析子程序。词法分析子程序则从源程序中依次读入字符，组合成单词符号，并将单词符号返回给语法分析程序。 当语法分析程序识别出一个语法成分时，就调用语义分析子程序进行语义分析，并生成目标程序。 当源程序处
11、理完后，进行善后处理，优化目标程序。,O.P.,单遍编译程序,多遍编译程序,有的编译程序把编译程序的五项任务分几遍来进行，每遍只完成部分任务， 多遍编译程序的工作过程如下： 调用词法分析程序将高级语言源程序转换成用单词符号表示的程序，即将字符串程序转换成单词符号串源程序。 调用语法分析程序对符号串源程序进行语法归类检查。 调用语义分析程序进行语义检查，并生成中间的代码程序。 调用代码优化程序对中间代码程序进行优化。 调用目标生成程序将优化后的中间代码程序转换成目标代码程序。,多遍编译程序结构,实际上，根据语言的不同，编译器可以是一遍(one pass)所有的阶段由一遍完成，其结果是编译得很好，
12、但(通常)代码却不太有效。 大多数带有优化的编译器都需要超过一遍：典型的安排是将一遍用于扫描和分析，将另一遍用于语义分析和源代码层优化，第3遍用于代码生成和目标层的优化。 更深层的优化则可能需要更多的遍： 5遍、6遍、甚至8遍都是可能的。,试问世界上第一个编译程序是用什么语言书写的？ 用高级语言书写？ *没有编译器，如何编译？ 因此世界上第一个编译器只能是用机器语言开发的,编译程序的自展技术,直接用目标机器上的机器语言书写源语言的编译程序工作量太大 用目标机器上的机器语言书写源语言的一个子集的编译程序，然后再用这个子集作为书写语言，实现源语言的编译程序。,如果把这个过程根据情况分为若干步，像滚
13、雪球一样直到生成预计源语言的编译程序为止，我们把这样的实现方式称为自展技术 简要来说就是：用被编译的语言来书写该语言自身的编译程序,4.程序设计语言的发展历程,按语言的代分类 第一代：机器语言 第二代：汇编语言 第三代：高级程序设计语言，如Fortran,Cobol,Lisp,C,C+,C#,Java 第四代：为特定应用设计的语言，如用于数据库查询的SQL，用于文字排版的Postscript 第五代：基于逻辑和约束的语言，如Prolog和OPS5,按程序中指名如何完成一个计算任务来分类 命令式语言：用命令式程序设计语言编写程序，就是描述解题过程中每一步的过程，程序的运行过程就是问题的求解过程，
14、因此也称为过程式语言。如C,C+,C#和Java等 声明式语言：描述目标性质，让计算机明白目标，而非流程。声明式编程通常被看做是形式逻辑的理论，把计算看做推导。如ML,Haskell,Prolog,HTML,CSS,正则表达式等 还有些语言是混合式的，既有声明式，也有动作处理,对编译器的影响,程序设计语言的发展对编译器设计提出了新的要求，编译器也推动了这些高级语言的使用 编译器必须能够正确翻译源语言书写的所有程序，这样的程序的集合通常是无穷的。为一个源程序生成最佳目标代码的问题一般来说是不可判定的 有关编译器的研究也是关于如何使用理论来解决实践问题的研究,构建一个编译器的相关科学,编译器的设计
15、中，有很多通过数学方法抽象出问题本质从而解决现实世界中复杂问题的完美例子 对编译器的研究主要是如何设计正确的数学模型和选择正确算法的研究 需要考虑到对通用性及功能的要求与简单性及有效性之间的平衡,最基本的数学模型是有穷状态自动机和正则表达式：用于描述词法单位以及描述被编译器用来识别这些单位的算法 上下文无关文法：用于描述程序设计语言的语法结构 树形结构：表示程序结构以及程序到目标代码的翻译方法的重要模型,编译技术的应用,懂得编译有助于深刻理解和正确使用程序设计语言，有助于加深对整个计算机系统的理解 虽然只有少数人从事构造或维护编译器的工作，但是大部分系统软件和应用程序的开发，通常要用到编译原理和技术 例如，设计词法分析器的串匹配技术已用于正文编辑器、信息检索和模式识别程序。上下文无关文法和语法制导定义已用于创建诸如排版、绘图系统和语言结构化编辑器，等等。,
