毕业设计 (论文)文献综述.doc

《毕业设计 (论文)文献综述.doc》由会员分享，可在线阅读，更多相关《毕业设计 (论文)文献综述.doc（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流毕业设计 (论文)文献综述.精品文档.附1 成绩： 西安建筑科技大学毕业设计 (论文)文献综述院 （系）：信息与控制工程学院 专业班级： 计算机0801 毕 业 设 计论 文 方 向 ： 综述题目：基于Java的小型编译器前端的设计与开发文献综述学生姓名： 李轲 学 号： 080620111 指导教师： 叶娜 年 月 日基于Java的小型编译器前端的设计与开发文献综述摘要： 21世纪是电脑发展的时代，从事软件开发的人越来越多，使用的开发软件和开发环境也不尽相同，但是不论是哪种开发环境，都少不了使用编译器。包括常用的C语言。编译器（Compil

2、er），是一种电脑程式，它会将用某种编程语言写成的源代码（原始语言），转换成另一种编程语言（目标语言）。它主要的目的是将便于人编写，阅读，维护的高级计算机语言所写作的源代码程式，翻译为计算机能解读、运行的低阶机器语言的程序，也就是执行档。编译器将原始程序（Source program）作为输入，翻译产生使用目标语言（Target language）的等价程序一个现代编译器的主要工作流程：源代码 (source code) 预处理器 (preprocessor) 编译器 (compiler) 汇编程序 (assembler) 目标代码 (object code) 链接器 (Linker) 可执行

3、程序 (executables)。低阶机器语言是计算机能直接解读、运行的。编译器将源程序作为输入，翻译产生使用目标语言的等价程序。源代码一般为高级语言 ， 如Pascal、C、C+、C#、Java等，而目标语言则是汇编语言或目标机器的目标代码，有时也称作机器代码。论文首先论述编译器的发展历程开发背景和研究的目的与意义，然后对本次编译器前端设计进行简单介绍，同时阐述该编译器所具有的的功能，以及实现所用的工具和参考的资料关键词：编译器，源代码，目标代码1. 前言编译程序是现代计算机系统的基本组成部分之一。编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代

4、码优化程序、表格管理程序和出错处理程序等成分构成。在编译原理的教学过程中,语法和语义分析阶段关于算法的讲解都需要对算法进行详细的分析，包括算法条件的判断，文法分析表的构造过程，文法分析表的具体生成，针对文法的句子的分析过程等。这些过程往往需要占用大量时间来分析、制表等。2C语言编译器的发展历程C语言是在70年代初问世的。一九七八年由美国电话电报公司(AT&T)贝尔实验室正式发表了C语言。同时由B.W.Kernighan和D.M.Ritchit合著了著名的“THE C PROGRAMMING LANGUAGE”一书。通常简称为K&R，也有人称之为K&R标准。但是，在K&R中并没有定义一个完整的标

5、准C语言，后来由美国国家标准学会在此基础上制定了一个C 语言标准，于一九八三年发表。通常称之为ANSI CC语言是一种结构化语言。它层次清晰，便于按模块化方式组织程序，易于调试和维护。C语言的表现能力和处理能力极强。它不仅具有丰富的运算符和数据类型，便于实现各类复杂的数据结构。它还可以直接访问内存的物理地址，进行位(bit)一级的操作。由于C语言实现了对硬件的编程操作，因此C语言集高级语言和低级语言的功能于一体。既可用于系统软件的开发，也适合于应用软件的开发。此外，C语言还具有效率高，可移植性强等特点。因此广泛地移植到了各类各型计算机上，从而形成了多种版本的C语言 目前最流行的C语言编译器有以

6、下几种： GNU Compiler Collection 或称 GCC Microsoft C 或称 MS C Borland Turbo C 或称 Turbo C 这些C语言版本不仅实现了ANSI C标准，而且在此基础上各自作了一些扩充，使之更加方便、完美3本次设计实现目标本次论文要求设计与开发一个能够识别C语言子集的小型编译器前端系统，按照面向对象的思想与技术完成需求分析与系统设计，要求对给定的C语言子集能够进行词法分析、语法分析、语义分析及语法制导的中间代码的生成，中间代码以三地址码形式生成。语法分析树语法单元源程序三地址代码符号表语法分析器中间代码生成一个编译器前端的模型 图1词法分析

7、器编译器前端主要负责解析（parse）输入的源代码，由语法分析器和语意分析器协同工作。语法分析器负责把源代码中的单词（Token）找出来，语义分析器把这些分散的单词按预先定义好的语法组装成有意义的表达式，语句 ，函数等等。 例如“a = b + c;”前端语法分析器看到的是“a， =， b ， +， c;”，语意分析器按定义的语法，先把他们组装成表达式“b + c”，再组装成“a = b + c”的语句。 前端还负责语义（semantic checking）的检查，例如检测参与运算的变量是否是同一类型的，简单的错误处理。最终的结果常常是一个抽象的语法树（abstract syntax tree

8、，或 AST），最后通过中间代码生成器将语法分析树，转化为三地址代码，这样后端可以在此基础上进一步优化，处理。编译器翻译程序步骤编译器内部包括了许多步骤或称为阶段（phase），它们执行不同的逻辑操作。将这些阶段设想为编译器中一个个单独的片断是很有用的，尽管在应用中它们是经常组合在一起的，但它们确实是作为单独的代码操作来编写的。图1 - 1是编译器中的阶段和与以下阶段（文字表、符号表和错误处理器）或其中的一部分交互的3个辅助部件。这里只是简要地描述一下每个阶段，今后大家还会更详细地学到它们（文字表和符号表在1 . 4节中，错误处理器在1 . 5节）。(1) 扫描程序（scanner）在这个阶段

9、编译器实际阅读源程序（通常以字符流的形式表示）。扫描程序执行词法分析（Lexical analysis）：它将字符序列收集到称作记号（token）的有意义单元中，记号同自然语言，如英语中的字词相似。因此可以认为扫描程序执行与拼写相似的任务。例如在下面的代码行（它可以是C程序的一部分）中：a index = 4 + 2这个代码包括了1 2个非空字符，但只有8个记号：a 标识符 左括号i n d e x 标识符 右括号= 赋值4 数字+ 加号2 数字每一个记号均由一个或多个字符组成，在进一步处理之前它已被收集在一个单元中。扫描程序还可完成与识别记号一起执行的其他操作。例如，它可将标识符输入到符号表

10、中，将文字（literal）输入到文字表中（文字包括诸如3.14159265 35的数字常量，以及诸如“ Hello ,world!”的引用字符串）。(2) 语法分析程序（parser）语法分析程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析（syntax analysis），这与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。通常将语法分析的结果表示为分析树（ parse tree）或语法树（syntax tree）。例如，还是那行C代码，它表示一个称为表达式的结构元素，该表达式是一个由左边为下标表达式、右边为整型表达式的赋值表达式组成。这个结构可按下面

11、的形式表示为一个分析树：图2请注意，分析树的内部节点均由其表示的结构名标示出，而分析树的叶子则表示输入中的记号序列（结构名以不同字体表示以示与记号的区别）。分析树对于显示程序的语法或程序元素很有帮助，但是对于表示该结构却显得力不从心了。分析程序更趋向于生成语法树，语法树是分析树中所含信息的浓缩（有时因为语法树表示从分析树中的进一步抽取，所以也被称为抽象的语法树（ abstract syntax tree）。下面是一个C赋值语句的抽象语法树的例子：图3请注意，在语法树中，许多节点（包括记号节点在内）已经消失。例如，如果知道表达式是一个下标运算，则不再需要用括号“ ”和“”来表示该操作是在原始输入

12、中。(3) 语义分析程序（semantic analyzer）程序的语义就是它的“意思”，它与语法或结构不同。程序的语义确定程序的运行，但是大多数的程序设计语言都具有在执行之前被确定而不易由语法表示和由分析程序分析的特征。这些特征被称作静态语义（ static semantic），而语义分析程序的任务就是分析这样的语义（程序的“动态”语义具有只有在程序执行时才能确定的特性，由于编译器不能执行程序，所以它不能由编译器来确定）。一般的程序设计语言的典型静态语义包括声明和类型检查。由语义分析程序计算的额外信息（诸如数据类型）被称为属性（attribute），它们通常是作为注释或“装饰”增加到树中（还

13、可将属性添加到符号表中）。在正运行的C表达式a index = 4 + 2中，该行分析之前收集的典型类型信息可能是： a是一个整型值的数组，它带有来自整型子范围的下标；index则是一个整型变量。接着，语义分析程序将用所有的子表达式类型来标注语法树，并检查赋值是否使这些类型有意义了，如若没有，则声明一个类型匹配错误。在上例中，所有的类型均有意义，有关语法树的语义分析结果可用以下注释了的树来表示：图4(4) 源代码优化程序（source code optimizer）编译器通常包括许多代码改进或优化步骤。绝大多数最早的优化步骤是在语义分析之后完成的，而此时代码改进可能只依赖于源代码。这种可能性是

14、通过将这一操作提供为编译过程中的单独阶段指出的。每个编译器不论在已完成的优化种类方面还是在优化阶段的定位中都有很大的差异。在上例中，我们包括了一个源代码层次的优化机会，也就是：表达式4 + 2可由编译器计算先得到结果6（这种优化称为常量合并（constant folding）。当然，还会有更复杂的情况。还是在上例中，通过将根节点右面的子树合并为它的常量值，这个优化就可以直接在（注释）语法树上完成：图5尽管许多优化可以直接在树上完成，但是在很多情况下，优化接近于汇编代码线性化形式的树更为简便。这样节点的变形有许多，但是三元式代码（ three-address code）（之所以这样称呼是因为它在

15、存储器中包含了3个（或3个以上）位置的地址）却是标准选择。另一个常见的选择是P -代码（P - cod e），它常用于Pascal编译器中。在前面的例子中，原先的C表达式的三元式代码应是：t = 4 + 2a index = t（请注意，这里利用了一个额外的临时变量t 存放加法的中间值）。这样，优化程序就将这个代码改进为两步。首先计算加法的结果：t = 6a index = t接着，将t替换为该值以得到三元语句a index = 6图1 - 1已经指出源代码优化程序可能通过将其输出称为中间代码（ intermediate code）来使用三元式代码。中间代码一直是指一种位于源代码和目标代码（例

16、如三元式代码或类似的线性表示）之间的代码表示形式。但是，我们可以更概括地认为它是编译器使用的源代码的任何一个内部表示。此时，也可将语法树称作中间代码，源代码优化程序则确实能继续在其输出中使用这个表示。有时，这个中间代码也称作中间表示（ intermediate representation, I R）。(5) 代码生成器（code generator）代码生成器得到中间代码（ I R），并生成目标机器的代码。尽管大多数编译器直接生成目标代码，但是为了便于理解，本书用汇编语言来编写目标代码。正是在编译的这个阶段中，目标机器的特性成为了主要因素。当它存在于目标机器时，使用指令不仅是必须的而且数据的

17、形式表示也起着重要的作用。例如，整型数据类型的变量和浮点数据类型的变量在存储器中所占的字节数或字数也很重要。在上面的示例中，现在必须决定怎样存储整型数来为数组索引生成代码。例如，下面是所给表达式的一个可能的样本代码序列（在假设的汇编语言中）：MOV R0, index ; value of index - R0MUL R0, 2 ; double value in R0MOV R1, &a ; address of a - R1ADD R1, R0 ; add R0 to R1MOV *R1, 6 ; constant 6 - address in R1在以上代码中，为编址模式使用了一个类似C

18、的协定，因此& a是a的地址（也就是数组的基地址），* R 1则意味着间接寄存器地址（因此最后一条指令将值6存放在R 1包含的地址中）。这个代码还假设机器执行字节编址，并且整型数占据存储器的两个字节（所以在第2条指令中用2作为乘数）。(6) 目标代码优化程序（target code optimizer）在这个阶段中，编译器尝试着改进由代码生成器生成的目标代码。这种改进包括选择编址模式以提高性能、将速度慢的指令更换成速度快的，以及删除多余的操作。在上面给出的样本目标代码中，还可以做许多更改：在第2条指令中，利用移位指令替代乘法（通常地，乘法很费时间），还可以使用更有效的编址模式（例如用索引地址来

19、执行数组存储）。使用了这两种优化后，目标代码就变成：MOV R0, index ; value of index - R0SHL R0 ; double value in R0MOV &aR0, 6 ; constant 6 - address a + R0到这里，对编译器阶段的简要描述就结束了，但我们还应特别强调这些讲述仅仅是示意性的，也无需表示出正在工作中的编译器的实际结构。编译器在其结构细节上确实差别很大，然而，上面讲到的阶段总会出现在几乎所有的编译器的某个形式上。我们还谈到了用于维持每一个阶段所需信息的数据结构，例如语法树、中间代码（假设它们并不相同）、文字表和符号表。下一节是编译器中

20、的主要数据结构的概览。编译器中的主要数据结构当然，由编译器的阶段使用的算法与支持这些阶段的数据结构之间的交互是非常强大的。编译器的编写者尽可能有效实施这些方法且不引起复杂性。理想的情况是：与程序大小成线性比例的时间内编译器，换言之就是，在0 ( n）时间内， n是程序大小的度量（通常是字符数）。本节将讲述一些主要的数据结构，它们是其操作部分阶段所需要的，并用来在阶段中交流信息。(1) 记号（t o k e n）当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号；这也就是说，作为一个枚举数据类型的值来表示源程序的记号集。有时还必须保留字符串本身或由此派生出的其他信息（例如：与标识符记

21、号相关的名字或数字记号值）。在大多数语言中，扫描程序一次只需要生成一个记号（这称为单符号先行（ single symbol lookahead）。在这种情况下，可以用全程变量放置记号信息；而在别的情况（最为明显的是F O RT R A N）下，则可能会需要一个记号数组。(2) 语法树（syntax tre e）如果分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时动态分配该结构，则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是一个记录，它的域表示由分析程序和之后的语义分析程序收集的信息。例如，一个表达式的数据类型可作为表达式的语法树节点中的域。有时为了节

22、省空间，这些域也是动态分配或存放在诸如符号表的其他数据结构中，这样就可以有选择地进行分配和释放。实际上，根据它所表示的语言结构的类型（例如：表达式节点对于语句节点或声明节点都有不同的要求），每一个语法树节点本身都可能要求存储不同的属性。在这种情况下，可由不同的记录表示语法树中的每个节点，每个节点类型只包含与本身相关的信息。(3) 符号表（symbol table）这个数据结构中的信息与标识符有关：函数、变量、常量以及数据类型。符号表几乎与编译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语义分析程序；语义分析程序将增加数据类型和其他信息；优化阶段和代码生成阶段也将利用由符号表提供

23、的信息选出恰当的代码。因为对符号表的访问如此频繁，所以插入、删除和访问操作都必须比常规操作更有效。尽管可以使用各种树的结构，但杂凑表却是达到这一要求的标准数据结构。有时在一个列表或栈中可使用若干个表格。(4) 常数表（literal table）常数表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常数表中也十分重要。但是，在其中却无需删除，这是因为它的数据全程应用于程序而且常量或字符串在该表中只出现一次。通过允许重复使用常量和字符串，常数表对于缩小程序在存储器中的大小显得非常重要。在代码生成器中也需要常数表来构造用于常数和在目标代码文件中输入数据定义的符号地址。(5) 中间代码（

24、intermediate code）根据中间代码的类型（例如三元式代码和P -代码）和优化的类型，该代码可以是文本串的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器，应特别注意选择允许简单重组的表示。(6) 临时文件（t e m p o r a ry file）计算机过去一直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临时文件来保存翻译时中间步骤的结果或通过“匆忙地”编译（也就是只保留源程序早期部分的足够信息用以处理翻译）解决了。存储器的限制现在也只是一个小问题了，现在可以将整个编译单元放在存储器之中，特别是在可以分别编译的语言中时。但是偶尔还是会发现需要在某些

25、运行步骤中生成中间文件。其中典型的是代码生成时需要反填（ b a c k p a t c h）地址。例如，当翻译如下的条件语句时if x = 0 then . else .在知道e l s e部分代码的位置之前必须由文本跳到e l s e部分：CMP X, 0JNE NEXT ; location of NEXT not yet knownN E X T :通常，必须为N E X T的值留出一个空格，一旦知道该值后就会将该空格填上，利用临时文件可以很容易地做到这一点。4概要设计及基本功能本系统使用java语言开发，主要能读取识别c语言代码，因此，并能对给定的C语言子集能够进行词法分析、语法分析

26、、语义分析及语法制导的中间代码的生成，并用图形显示语法分析树，中间代码以三地址码形式生成。基本功能：1.识别C语言子集 2.对给定的C语言子集能够进行词法分析 3.对给定的C语言子集能够进行语法分析 4.对给定的C语言子集能够进行语义分析及语法制导的中间代码的生成，中间代码以三地址码形式生成5. 总结编译原理作为计算机专业及其重要的组成部分，理论上需要掌握有关形式语言和自动机的抽象概念，技术上又要能够熟练地利用各种数据结构进行编程。本文通过一个实际的可视编译器开发实例，描述了编译器前端的实现方法。希望通过词法分析和语法分析的可视化过程使得编译原理直观化和可视化。参考文献1谭浩强. C程序设计（第4版）M.清华大学出版社，20102颜志军，栾媛媛.Java程序设计实践教程M. 清华大学出版社，20113Alfred V. Aho著，赵建华等译.编译原理（第2版 本科教学版）M. 机械工业出版社，20094567 89Louden Kenneth C编译原理与实践M北京：机械工业出版社，2002