毕业设计（论文）-一门自定义编程语言的设计及其编译器的实现.doc

太原理工大学毕业设计(论文)用纸一门自定义编程语言的设计及其编译器的实现摘要编译程序是现代计算机必不可少的组成部分，它完成了将源程序转换为目标程序的全部过程。在我这次的毕业设计当中，定义和设计了一个类C的编程语言。由于我自身能力、时间和所学知识有限，设计出的这门语言十分简单，并没能提出一个准确有效的对现有编程语言的改进方案。当然，这个课题毕竟是一个很前沿的问题，作为大学毕业生的我只是对这个前沿问题进行了一些实践性的尝试。当然，我的毕业设计中最重要的部分就是实现了这门编程语言的编译器，它的主要功能包括了词法分析、语法分析、语义分析、中间代码生成（中间代码采用了四元式的结构），以及目标代码生成（目标代码采用了汇编语言），可以将符合语法的程序成功执行，并显示结果。由于技术所限，编译器没有进行进行代码优化和对错误的处理。但总体而言，这个编译器项目的功能性还是十分完备的。关键词： 编译器；程序设计语言；词法分析；语法分析全套设计加扣 3012250582A Design of Custom Programming Language and the Realization of its CompilerAbstractThe compiler is an essential part of the modern computer , it completed the source to the target program the whole process.In my current graduation designs, I definited and designed a similar C programming language . Because of my own ability , limited time and the knowledge , the language is very simple , and I did not able to present an accurate and effective for improvement program existing programming languages. Of course , this subject is after all a very cutting-edge issues , as university graduates on the cutting-edge issues , I just made some practical attempt.In addition , the most important part of my project is to realize this programming language compiler, its main features include lexical analysis , parsing, semantic analysis and code generation ( intermediate code using a quaternion type of structure ) , and target code generation ( object code using assembly language ) , in line with the syntax of the program can be executed successfully , and displays the results . Due to technical limitations, no compiler for code optimization and error handling . Overall, however, the functionality of this compiler project is still very completed.Keywords: complier;Programing Language; lexical analyzers; Syntax analysis42目录摘要iAbstractii第一章 绪论1一 论文主要内容1（一） 程序设计语言的设计1（二） 编译器的实现1（三） 在线编译思路的尝试1二 文献综述1（一） 前言1（二） 研究概述2三 研究编程语言的目的和意义3四 研究编译器的目的和意义3第二章 自定义语言的设计4一 程序设计语言概述4（一） 程序设计语言概念4（二） 程序设计语言分类4（三） 程序设计语言的实现4二 程序设计语言发展现状4三 程序设计语言的发展趋势5四 自定义语言的设计5（一） 词法的设计5（二） 语法的设计6（三） 中间代码的选择6第三章 编译器概述7一 编译器的基本概念7（一） 编译器概述7（二） 编译过程概述7二 研发编译器的意义8三 编译器的发展趋势8四 尝试在线编译器的意义8五 编译器的概要设计9（一） 系统总体结构9（二） 代码分析模块结构9（三） 类结构的设计10第四章 词法分析12一 词法分析概述12（一） 词法分析概念12（二） 常用的LEX程序12二 词法分析器设计12（一） 词法的设计步骤12（二） 正规式和DFA13（三） 利用有限自动机的词法分析13三 词法分析器的实现14（一） 数据结构定义14（二） 实现细则14第五章 语法分析16一 语法分析概述16二 语法分析器设计16三 语法分析器实现17（一） 上下文无关文法17（二） LR分析方法17第六章 语义分析及中间代码生成20一 语义分析及中间代码生成的概念20二 语义分析设计20三 中间代码的选取21第七章 目标代码生成22一 目标代码定义22（一）简介22（二）目标代码格式22二 目标代码生成概述23三 实现过程23第八章 系统的在线化尝试25一 为什么要进行编译器在线化25（一）现有系统的局限性25（二）编译器在线化的优势26（三）在线编译器的发展现状26二 在线化的设计思路26（一）开发技术概述26（二）正则表达式27（三）在线编译器功能的确立27（四）类与方法的建立27三 在线化的具体实现28（一）基础页面部分28（二） 逻辑部分29第九章 系统测试31一 测试方法概述31（一） 测试方法综述31（二） 本次选取的测试方法32二 在线版本测试用例及结果32（一） 基本运算32（二） 输出字符串33（三） 错误处理34三 本地版本测试用例34（一） 基本运算34（二） 输出字符串35（三） if语句36（四） for循环36四 测试结果37结论38致谢40外文原文41中文翻译68第一章 绪论一 论文主要内容（一） 程序设计语言的设计在这次的毕业设计中，为了更好的完成自己的编译器，我设计了一门自定义的编程语言，这门编程语言的设计初衷并非为了改善现有编程语言的不足或者是为了对编程语言进行某种探讨，而仅仅是为了更好的配合我的编译器的实现。不过，在设计过程中，我接触到了一些新的，有趣的知识，并在我的设计中进行了融合，并进行了一些小的尝试。之后我会用单独一章的篇幅来论述我的程序设计语言的理解和认识。（二） 编译器的实现编译器的实现是我的毕业设计的主要内容，因而本篇论文的大部分章节会按照软件工程的开发流程来详细论述我的开发历程以及对编译器本身的理解。在语言选择上，我放弃了灵活的C而选择了我更为熟练的Java，这个决定使得我的程序在生成四元式再转为汇编的过程中遇到了一定程度的麻烦，或者说一定程度上影响了我毕业设计的质量，当然，直到开发尾声我才意识到这个问题。底层实现上，我借助了一些网上大牛写好的代码段，并配合一定量自定义的批处理，反复利用cmd来生成一个exe文件，最终在执行这个exe文件得到程序的运行结果。（三） 在线编译思路的尝试 将编译器转为在线编译器是我从做编译器一开始就有的想法，并且在整个过程中都在不断的尝试。然而，由于我的实现方式所限，最终也没能捕获执行结果，以至于我的编译器虽然拥有B/S的执行方式，但却只能在服务器端执行，唯一可行的方式是将执行结果打包，在用户执行完程序后为其提供下载服务。但是这无疑会影响用户体验。二 文献综述（一） 前言随机计算机技术的不断发展与进步，如今从事于软件开发行业的人越来越多。而既然选择了从事软件开发行业，就自然会与程序设计语言以及编译器结下不解之缘。但不论是谁来开发软件，都一定离不开程序设计语言，也一定离不开编译器，因为它们是一切程序之源。既然想要开发软件就必须有编程语言和编译器，那么，编程语言和编译器本身又是如何产生的呢？本篇论文正是在探讨这个问题，在此之前，先需要介绍一些基本概念。程序设计语言，其实就是一组记号以及一些规则，跟句这些几号和规则组成的总体就称作计算机设计语言，它可以用来书写计算机程序。通常来讲，程序设计语言有三个要素，即语法、语义和语用。编译器，是一种基础的程序，它可以将用某种语言写成的源程序翻译成另一种编程语言，它可以将易于人类编写的高级语言翻译成复杂的低级语言，这种转换可以极大的提高人们编写程序的效率，降低程序编写的难度，所以从某种意义上说，编译程序的产生是一种历史的必然。由于编译技术历史较为久远，再加上编译器技术所涉及的技术内容十分宽泛，所以本篇论文所引用的参考文献内容也较为繁杂。论文所选用的文献涵盖了编译器技术的发展历程，各种编译器的开发背景，以及各种编程语言产生的目的和意义。同时，还有不少文献包涵了编译器的前端设计的简要介绍，同时阐述了编译所应该具有的功能以及其当前的发展现状，以及实现编译器所使用的工具甚至是参考资料。（二） 研究概述 上个世纪50年代，IBM的John Backus带领着一个研究小组对FORTRAN语言及其编译器进行了开发工作。但是因为当时人们对编译理论了解很少，使得开发工作变得既复杂又艰苦。与此同时，Noam Chomsk带着他的团队开始了他对自然语言结构的研究工作。他的发现最终使得后来的编译器的结构变得异常简单，甚至还带有了一些自动化的属性。Chomsky的研究成果导致了根据语言文法的难易程度以及识别它们所需要的算法来对语言进行分类。正如现如今所称的Chomsky架构（Chomsky Hierarchy），它包含了文法的四个层次：0型文法、1型文法、2型文法和3型文法，而且其中每一个都是其前者的特殊情况。2型文法（上下文无关文法）被证明是程序设计语言中最为有用的，而且今天它已开始代表着程序设计语言结构的标准方式。分析问题（parsing problem，用于上下文无关文法识别的有效算法）的研究是在60年代和70年代，它相当完善的解决了这个困难的问题。现在，它已是编译原理中的一个必备的标准部分。 有限状态自动机（Finite Automaton）以及正则表达式（Regular Expression）同上下文无关文法十分紧密相关，它们与Chomsky的3型文法所对应。对它们的研究与Chomsky的研究几乎是同时开始的，并且还引出了表示程序设计语言的单词的符号表达方式。 人们接着又去深化了生成有效的目标代码的方法，这就是最初的，最原始的编译器，它们被一直使用，直至今天。人们通常将把它称为优化技术（Optimization Technique），但因为它从来没有真正地得到过被优化了的目标代码，而仅仅是改进了它的有效性，因此实际上它应被称作代码改进技术（Code Improvement Technique）。 直到现代的新编译器，大量的项目都贯注于编译器其它部分的实现生成自动化，这其中就包括了代码的生成。这些尝试并没能取得什么成果，这大概是因为操作太过复杂而人们又对其不甚了解的原因。三 研究编程语言的目的和意义程序设计语言是一切软件开发活动的基础，程序设计语言的优劣直接决定了软件开发人员的开发效率，从而间接的影响到了软件的质量，因而程序设计语言的研究有着十分重要的意义。同时研究程序设计语言对于从事软件开发的人来说，也具有身份深远的意义，因为当软件开发人员开始研究和分析程序设计语言时，他就会进入一个更深层次的分析过程，这个过程将十分有利于他思考程序设计语言本身。这样的过程不仅仅可以软件开发人员更加了解程序设计语言，而且还可以使得新的程序开发软件更加的合理与高效。同时，软件开发的需求本来就是一直在进步的，程序设计语言一定会跟随着需求的变化而变化，所以，为了能更好的应对时代的需求，对编程语言的研究当然是无法避免的。四 研究编译器的目的和意义 编译器的设计涉及到了编译程序构造的一般原理、主要实现技术、基本设计方法和一些自动构造的工具。尽管“编译程序”是特指将高级程序设计语言翻译成低级语言的程序或者代码段，但编译程序构造的基本原理和相关技术也同样广泛应用于一般的设计和实现过程中，因此，这是一门对实践性要求较高的学问。目前，世界上有着数千种编程语言，既有Fortran和Pascal这样老牌的传统程序设计语言，也有各个计算机应用领域中新出现的专用语言。目标语言的种类也同样广泛，目标语言可以是另一种程序设计语言，也可以是从微处理机到计算机的任何种类的计算机的机器语言。不同的语言需要不同的编译器。根据编译器的构造方法的不同，或者它们要实现的功能的不同，编译器通常被分为一遍编译器、多遍编译器、装入并执行编译器、调试编译器、优化编译器等等多种类别。从表面上来看，编译器的种类似乎千变万化，多种多样，不可琢磨，实质上，任何编译器所要完成的基本任务其实都是相同的。通过理解这些编译任务，我们可以利用同样的基本技术和基本方法为各种各样的源语言和目标机器构建编译器。这将很有益处。第二章 自定义语言的设计一 程序设计语言概述（一）程序设计语言概念 程序设计语言通常是被设计成专门使用在计算机上的语言，但其实，它们也可以用来定义一些算法或者数据结构。正是因如此，程序员们才会试图通过改进使得程序代码更容易阅读。程序设计语言往往使程序员能够比使用机器语言更加准确的表达他们所想要表达的目的。对于那些从事计算机科学技术的人来说，懂得程序设计语言本身是十分重要的，因为，当今所有的计算都需要使用程序设计语言才能完成。（二）程序设计语言分类当今，有许多用于特殊用途的编程语言，它们只在特殊情况下使用。例如，PHP专门用来编辑网站服务器；而Perl则更适合文本处理；C语言却被广泛应用于操作系统和编译器等底层系统的开发。高级语言的出现使得现代的编程语言不再过度的倚赖某种特定的机器或者环境。这是因为高级语言在不同的平台上都会被编译成特定的机器语言，而不是直接就被机器执行。最早出现的编程语言之一FORTRAN的一个主要目标就是实现了平台的独立。（三）程序设计语言的实现虽然大多数的语言可以既可被编译又可被解释，但是，大多数语言仅在一种情况下能够良好的运行。在一些编译系统中，程序一般要经过几个阶段的编译，后阶段的编译往往更加接近机器语言。这种常用的使用技巧是编译程序先去编译一个叫做“0代码”的转换程序，然后再使用虚拟器，将程序转换到可以运行于机器上的底层代码。这种技巧后来又用于Pascal和P-code，以及Smalltalk和二进制码，在很多时候，中间过渡的代码往往是解释，而不是编译的。如果所使用的翻译机制是将所要翻译的程序代码作为一个整体去翻译，并且在之后运行内部的格式，那么这个翻译过程就被称为编译。因此，一个编译器是把一个人可阅读的程序文本作为输入的数据，然后输出可执行文件。所输出的可执行文件是机器语言，由计算机的中央处理器直接运行，也可以是某种模拟器的二进制代码。二 程序设计语言发展现状 目前通用的编程语言有两种形式：低级语言和高级语言。低级语言直接对硬件操作，其中汇编语言的指令采用了英文缩写的标识符，更容易识别和记忆。用汇编语言能完成的操作不是一般高级语言所能直接实现的，而且其源程序经汇编生成的可执行文件不仅体积比较小，而且执行速度非常快。而高级语言则是目前大多数编程者的选择。和汇编语言相比，它不但是将许多相关的机器指令合成为单条的指令，而且去掉了与具体操作有关但是与完成工作无关的细节，例如，使用堆栈、寄存器等等，这样就大大的简化了程序中使用的指令。于此同时，由于省略了很多细节，编程者也就不需要有太多的硬件知识。目前主流的高级语言有java、c、phython、javascript等等，这些语言的语法、命令格式都各不相同，但它们所编制的程序都不能直接被计算机识别，必须经过转换才能被执行，因而，制作一个编译器才显得尤为重要。三 程序设计语言的发展趋势 程序设计语言是软件的重要方面。它的发展趋势是模块化、简明性和形式化。一、模块化。不仅语言具有模块成分，程序由模块组成，而且语言本身的结构也是模块化的。二、简明性。涉及的基本概念不多，成分简单，结构清晰，易学易用。三、形式化。发展合适的形式体系，以描述语言的语法、语义、语用。四 自定义语言的设计（一）词法的设计1 保留字表 首先，需要定义全部的保留字，所以需要定义一个保留字表，如表2-1所示。表2-1 保留字表保留字用途null空for类c的for循环myprint输出语句br换行语句if条件语句break跳出循环whilewhile循环int定义整型double定义浮点型main程序入口2 标识符规则变量规则：要求以字母开头，可由字母数字组成。函数名称规则：要求全部使用字母组成。3 特殊符号表 与此同时，也必须在同时定义出全部的特殊符号，这里就涉及到了一张特殊符号表，这个表里面有全部的特殊符号，如表2-2所示。表2-2 特殊符号表符号用途+、-、*、/运算符=赋值(、)定义优先级=、=、比较+、-自增自减（二）语法的设计在简要的设计里，主要讲一下类型的推导，这里可不是Go语言那中没什么可靠性的:=赋值操作符，而是真正的类型推导，这就要跟C+的泛型lambda表达式、C#的linq语法糖，或者Haskell的函数一样，要可以自己计算出模板的类型参数的位置或者内容，才能全方位的实现什么类型都不写，都还能使用强类型并享受它带来的好处。这里，我们使用上下文无关文法。比如，G可以用一个四元组表示：G(V,T,P,S)。其中：V是文法的非终结符号集合，每个非终结符号都表示语言的一个语法变量；T是终结符号集，每个终结符号都表示语言的一个基本符号，即词汇；P是产生式集，文法使用产生式来定义每个非终结符号；S是V中的一个非终结符号，被称为开始符号。文法的每个产生式都由左、右两部分组成，左部是一个非终结符号，而右部是由零个或若干个终结符、非终结符组成的符号串。同时，使用自底向上的LR文法，可以有效的扫描输入流并进行规约。（三）中间代码的选择由于四元式结构十分利于转化为汇编语言，同时，也因为四元式本身有着清晰易懂，便于人类理解以及在开发过程中查找错误的优点，所以四元式变成了我在自己的编译器中选择并使用的中间代码。四元式的结构如表2-3。表2-3 四元式的结构第一部分第二部分第三部分第四部分运算符第一运算量第二运算量结果 第三章 编译器概述一 编译器的基本概念（一）编译器概述编译程序可以说是现代计算机系统的基本组成部分之一，而且在多数计算机系统中都含有不止一个高级语言的编译程序，对有些高级语言，甚至为其配置了几个不同性能的编译程序。从功能上来看，一个编译程序就是一个语言的翻译程序。它把一种称作源语言书写的程序翻译成另一种称作目标语言编写的等价的程序。比如汇编程序就是一个常见的翻译程序，它把汇编语言编写的程序翻译成机器语言写的程序。如果源语言是诸如JAVA，C+，或C那样的高级语言，而目标语言是像汇编语言或者机器语言那样的低级语言，则这种翻译程序被称作编译程序。（二）编译过程概述图3-1 常规的编译过程如图3-1所示，编译过程一般由编辑源代码，随后进行词法分析，对源程序进行扫描，分析出其中的单词，例如保留字，标识符等等。随后进行语法分析的工作，它在词法分析工作的基础上，把单词符号分解成各类语法单位。随后，进入语义分析阶段，在这个阶段，程序将会分析出各类语法范畴，并初步产生中间代码。随后，“翻译”的工作将正式展开，这里将会把语义分析的结构在中间代码生成的环节正式转换为我所使用的四元式。中间代码生成是非常重要的一步，它在进行了上述语法分析和语义分析工作之后，将源程序变成一种其内部使用的表示形式，这种内部表示形式被叫做中间代码。所谓“中间代码”，通常会是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，其主要的设计原则有两点：一是容易生成；二是容易将它翻译成为目标代码。在我的编译器中，采用了一种叫做“四元式”中间代码。最终，四元式等中间代码经由汇编等低级语言，得以实现在计算机上。二 研发编译器的意义编写编译器具有十分普遍的意义，因为在每一个计算机科学家或者说普通开发者的的职业生涯中，编译器是我们不可避免的程序。编译器的编写涉及到了程序设计语言、计算机组成原理、语言理论、算法和软件工程等诸多学科。研究编译程序是有意义在于：1）编译程序构造是计算机科学中的一个非常重要的分支，是大多数程序的基础，也是最早获得成功的学科分支之一；2）它与文件转换程序关系十分密切，而且编译器理论也不仅仅适用于编译程序；3）同时，编译器内部也包含着许多在实际应用中非常有用的算法。三 编译器的发展趋势由于近些年并行机及多处理机的飞速发展，时代对软件的并行处理技术提出了更新的要求。至于编译技术领域，并行编译技术的发展也很快，目前，实现并行编译技术有两种方法：第一种方法，是运用重构技术把已有的串行语言编写的程序进行相应的分析，将其分解成可并行处理的成分，再分配到多CPU或多处理机上运行。第二种方法，即在程序设计语言机制上就设置允许用户自己编写可并行的程序，这当然要比编写串行语言对编程人员提出更高的要求。即用户自己必须知道程序各模块之间的逻辑结构关系以及调用关系。这样才可以确定哪些模块可以并行执行。随着并行技术和并行语言理论的发展，处理并行语言的并行编译技术也正在深入的研究之中，而通过将串行程序转换成并行程序的更为高端的自动并行编译技术也正在深入的研究和讨论之中，过程如图3-2。源语言的定义编译程序编译程序自动生成软件机器语言的描述图3-2 自动编译技术四 尝试在线编译器的意义传统应用一般都仅能在PC上运行，只适合单用户进行操作，这些软件通常功能强大，但是只能应用在PC上，无法与人共享，具有较大的局限性，在使用这些软件之前，你必须进行繁琐的安装操作，并且还需要一定的存储空间。但是如果将这些应用换成Web应用，那么它所产生的硬件需求就少得多，而且更新方便，利于使用，你仅仅需要上网，就能使用，而且，随着web技术的不断发展，新技术越来越成熟，Web应用的用户体验完全不亚于传统的PC程序。所以，将的传统的PC端编译器转换成Web应用是合理的。五 编译器的概要设计（一） 系统总体结构一般的编译系统都在纵向上分为两层，即大家常说的编译器的前端和后台，在我的项目中，也采用了这种同行的模式，即前端处负责理数据显示，以及部分的业务逻辑，包括源代码的初步审查、中间代码生成、代码执行，而后台主要负责代码分析的业务逻辑，前端和后台通过Ajax与servelet来进行数据通讯。系统的框架如图3-3所示。图3-3 系统框架图（二） 代码分析模块结构编译器的代码分析模块主要是处理从前台传递过来的代码，功能包括对代码进行词法分析和语法分析，以及判断用户的代码的正确性，如果用户输入的代码存在错误，则应该能够识别出错误出现的位置，并且可以将错误信息返回给前台，其工作流程如图3-4所示。图3-4 代码分析工作流程（三） 类结构的设计在本次的类结构当中，代码的分析器基本是由词法的分析器以及语法的分析器所构成，它们的类图结构如图3-5所示。图3-5 类结构的设计由此在简单的梳理一下本次开发工作的具体需求。首先，必须要对用户的输入代码进行初步审查和判断，并且需要实时提示用户他是否成功的输入了关键字信息。同时，还必须要检查输入关键字的精确度，在用户选择编译本段程序之后必须迅速将这段代码编译，并且快速产生相对应的四元式。第四章 词法分析一 词法分析概述（一） 词法分析概念 词法分析，负责对源程序中的字符串即代码进行扫描和分析，根据既定的构词法将字符流转化成单词流。例如对于标准的C语句：x = y + z m * 10。其词法分析的结果：ID ASSIGN ID ADD ID SUB ID MUL NUM SEMI 。构词的规则就称作词法，例如，标识符可定义为以字母开头，后面跟零个或其他任意个字母或者数字序列。词法分析程序就根据词法的构造有限自动机理论来识别其中的每一个单词，最终将产生的单词交给语法分析程序。（二） 常用的LEX程序 LEX是一个常用的词法分析器的自动产生系统，它的结构示意如下：LEX源程序 LEX yylex输入串 yylex 单词符号串LEX的源程序是用一种面向问题的方式写成的。这个种模式的核心是正规表达式，用它来描述输入字符串的词法结构。在这个语言结构中，用户还可以来描述某一个词被识别出来时需要完成的动作，例如，在高级语言的词法分析器中，每当识别出一个关键字时，它都应该向语法分析器去返回该关键字的内部编码。LEX本身并不是一个完备的语言，它只是某种高级语言（通常称为LEX的宿主语言）的扩充，因此，LEX并没有为描述动作而去设计新的语言，而是去借助其宿主语言来描述动作。LEX可以自动地把表示输入串词法结构的正规式及相应动作转换成一个宿主语言程序，即所说的词法分析程序。二 词法分析器设计（一） 词法的设计步骤1、预留一部分关键字。2、丰富和完善运算类型。需要把括号、赋值、逗号等全部作为运算符进行处理。从而使得编程语言的运算类型获得极大的丰富。3、完善数据结构和类型。4、增加结构化的控制语句。（二） 正规式和DFA为了更加准确的识别出正规集，我们需要识别出输入串中的正规集，这里，就必然要设计和定义正规式。如编译原理一般所设，和分别代表了终结符结束与空集，则如常规意义所表示，代表所定义的全集全集。因而定义如下规则：和都是上的正规式，它们表示的正规集分别是和对于任何的a，a都是上的一个正规式，它所表示的正规集为a假设U和V都是上的正规式，则它们所表示的正规集分别记做L(U)和L(V)，那么(U|V)、(U.V)和(U)*也都是正规式，则它们所表示的正规集分别是L(U)L(V)、L(U)L(V)和(L(U)*。 规定为仅由有限次的使用上述三步骤而定义成的表达式才是上的正规式，仅由这些正规所表示的字符集才是上的正规集。正规式的定义可以有效地用来描述词法，从而确定的有限自动机(DFA)能快速准确地识别出正规集，进而执行词法分析的功能。（三） 利用有限自动机的词法分析词法分析是整个编译过程的第一个阶段，它可以将字符序列转化为单词序列。而识别单词的基本方法是根据词法定义去构造有限自动机，即需要一个描述语言结构特征的状态转换图。例如对于十进制整数正规定义：1-9+0-9*可以构造如图4-1所示的有限自动机。图 4-1 识别十进制整数的有限自动机其中，状态2称为接收态，若对于一个字符序列有限自动机最终可以达到状态2，那就说明已经识别出了一个整数。在这个地方，词法分析的器构造程序LEX就是使用这一原理进行了识别的工作。对于构造词法分析器，它的主要任务就是去设计词法的正规定义以及相关的动作。因此，在上面例子中的LEX程序段即：1-9+0-9return ICON;三 词法分析器的实现（一）数据结构定义1 关键字与系统标识符表 Ktab 用于存储关键字和标识符等信息，定义一个类KWORD，其中定义了一些属性如下： char name; int val;其中：name用于保存关键字，而val域则存储关键字的种类标识。val域即词法分析器传给语法分析器的终结符。2 关键字的具体定义以下为Ktab数组中存储的对象如下：break,BREAK ,char,TYPE,myprint,MYPRINT ,else,ELSE,for,FOR ,if,IF ,int,TYPE ,main,MAIN,br,BR ,while,WHILE ,double,DOUBLE ,string,STRING （二）实现细则1 注释处理选择支持两种风格的注释：/*.*/和/，对于发现注释内容出现到/* 和 / 后时，直接通过调用动作input跳过。2 常数处理词法分析器要求可以识别十进制、八进制和十六进制以及无符号整数和字符常数（例如A）。可以通过函数int sto(char str, int rad)将其转化成数值形式。3 标点处理此处可以选择直接返回其相应的标识。4 标识符处理在识别标识符之后，需要调用函数keyword去查找其相关属性值并返回。分为下述两种情况： 对于系统的保留字和关键字，要求函数keyword可以返回相应的标识。对于返回值相同的，可以通过yytxt进行区别。 对于用户自定义标识符，要求函数keyword返回其名称键值。在效能方面，为了提高查找关键字以及查找系统标识符表的速度，我在keword函数中优化了算法，基本采用了二分查找法来增加效率。第五章 语法分析一 语法分析概述在完成了词法分析之后，就要在词法分析的基础上，将单词组合成各类语法短语。而在这个环节里，要将一般语法短语规则表示成语法树。语法分析模块的主要任务，就是根据既定的文法规则去把已经得到的单词序列分解成为各类语法单位，进而识别出一个又一个的句子，例如，对第四章中所举例的的语句进行相应的语法分析便可得到如图5-1的分语法分析树。如果输入的单词无法构成下述的语法树，则直接说明了单词存在语法错误。常见的语法分析方法一般有自顶向下的分析和自底向上的分析两大类。在本编译器中，我采用了其中的一种，自底向上的方法，即LR方法。图5-1 语法分析树NUM项ID项*表达式IDID-项表达式+项表达式=变量赋值语句二 语法分析器设计（一） 注意事项1、特别留意语法限制的控制，拒绝赋予语言危险级别的操作。2、注意要拒绝程序允许直接访问物理地址，禁止进行位操作，避免其直接对硬件进行任何程度的操作。3、考虑设计可以使得生成目标代码质量好，程序执行效率高。4、同时，一定程度上提前考虑此语言写的程序可移植性要好。（二） 定义语法规则 =| = type 变量，变量； = 变量 = ； = 标识符运算符 标识符 ； = 变量 |常量 = + | - | * | / | = = =if(表达式) 循环语句 |条件语句 |赋值语句 =赋值语句 | 条件语句 | 循环语句 = while(表达式) 赋值语句|条件语句|循环语句 = myprint 表达式三 语法分析器实现（一）上下文无关文法 在实现语法分析的过程中，使用了上下文无关文法，定义文法G，使用一个常规的四元组进行表示：G(V,T,P,S)其中：V表示文法中的非终结符号集，其中每个非终结符号都表示一个语法变量；T表示终结符号集，每个终结符号都表示一个基本符号，即词汇；P表示产生式集，文法使用产生式来定义每个非终结符号；S表示V中的一个非终结符号，称做开始符号。正常情况下，文法的每一个产生式都会由左、右两部分组成。其中，左部分是非终结符；右部分则是由零个或者若干个终结符与非终结符组合而成的符号串。（二）LR分析方法LR分析方法全称是自底向上的语法分析，它的功能非常强，适用于多种上下文无关文法。其中，L指的是从左向右去扫描输入串，R是指按照最右推导的逆过程进行归约。此处列举LR分析法的一些优点：可以使用上下文无关的文法来描述程序设计的语言结构，都可以构造其LR分析器，然后进行识别。LR分析法具有一般性无回溯移进特性，是一种能被有效实现的规约文法。能使用LR分析器分析的文法类包含了能用LL(1)分析器去分析的全部文法。LR分析器在自左向右扫描输入串时，可以尽可能地发现语法错误。图5-2是一个LR分析器的结构示意图。其中，分析栈存放状态和移进、归约的文法符号： S0X1S1.Xm-1Sm-1S0其中，S表示状态，X表示符号，在实现过程中，文法符号不一定需要进分析栈。动作表中的项目ACTIONSm,ai的含义为当输入符号为ai、栈顶状态为Sm时，分析算法应该执行的动作；若ACTIONSm,aiSi，则表示移进，然后栈顶状态为i;rj时表示使用产生式j去归约；acc在这里表示接收输入串，err则表示语法错误。状态转换表中的项目GOTOSi,X用来表示归约出非终结符号X后，若当前栈顶状态为Si时，分析栈应该转换到下一状态上，即所谓栈顶的新状态，这一过程参见图5-2。图5-2 LR分析过程我所使用的LR分析算法具体为： 首先，要根据输入符号ai、栈顶状态Sm以及动作表项actionSm,ai的值，来决定当前分析应执行的动作，归约、移进、接收或出错，当移进或归约之后，要根据动作表或者状态转换表来设置分析栈的状态。 其实，可以把分析栈中的串和等待输入的终结符号看作两个分量，而这两个分量构成了如下形式的二元组： (S0X1S1X2S2.XmSm , aiai+1.an#)这个二元组的结构表示右句型 X1X2.Xmaiai+1.an#假设当前的分析栈栈顶为状态Sm，此时下一个输入符号为ai，而分析器的下一个动作由动作表项actionSm,ai决定。 如果actionSm,ai移进S，分析器执行移进操作，二元组变成： (S0X1S1X2S2.XmSmaiS , ai+1.an#) 即分析器把输入符号ai以及状态S移进栈中，于是，ai+1变成了下一个输入符号。 如果actionSm,ai归约A则分析器执行归约，二元组变成 (S0X1S1X2S2.Xm-rSm-rAS , ai+1.an#)其中，S由goto表示确定：S = gotoSm-r,ai，r=|，这是句柄号串的长度。当归约时，分析器从栈中弹出2r个元素：其中有r个状态和r个文法符号，于是，这时使得状态Sm-r出现在栈顶，然后，再把归约产生式的左部的非终结符A和由gotoSm-r,A式确定的状态S压入栈。在归约的过程中，不去改变输入符号。这里，对LR分析器来说，从栈中弹出文法符号串Xm-r+1.Xm总是去匹配归约产生式的右部的。 若actionSm,aiacc，则选择接收输入符号串，至此语法分析完成。若actionSm,aierr，则表示发现语法错误，开始调用错误处理程序。第六章 语义分析及中间代码生成一 语义分析及中间代码生成的概念这一阶段的任务可以概述为：对前一部分，即语法分析过程所识别出的各类语法范畴做出分析，得到其具体含义，并进行初步翻译。在这里，初步翻译将会产生中间代码，即我所选择的四元式。简言之，这一部分就是根据前一阶段所产生的语法树，按照语言所定义好的语义去进行翻译，随后产生规定好的四元式这类中间代码。由于中间代码自身的特性，它们可以非常方便地转换为目标代码。例如，前面的语法树所产生的四元式序列为： (*,_t1,10,m)(-,_t2,z,_t0)(+,_t1,y,_t1)(=,x,_t1)关于生成中间代码的原因，是因为中间代码全都非常接近于底层代码，所以中间代码的产生可以极大的简化生成目标代码的难度。同时，中间代码作为阶段性的成果出现，便于记录和标识，这也是必须的。二 语义分析设计从语义分析开始，就正式开始了编译器的最主要功能：翻译。在这个环节，编译器开始去理解程序代码的含义，而不仅仅是在分析代码的成分和结构。因而，在语义分析的环节，首先要明确语义分析的基本任务：1. 类型的确定：这里需要确定程序中的标识符所确定的数据类型。2. 类型的检查：在检查环节，需要按照语言的类型给则要求，对运算符进行响应的类型转换等等。3. 确认含义：更具语义的定义，需要去确认程序中个构造成分组合到一起的含义，并进行响应的语义处理。4. 其他语义检查：在语义分析过程中穿插一些静态的语义检查，这里包括了不允许从循环外部转到循环内部等等。关于符号表的组织方面的一些要求和定义，编译程序一般用符号表来跟踪关于名称的汇聚信息以及它们的作用域，当词法分析器识别出标识符后，编译程序就开始查找符号表，来看它是否还在符号表中，如果不在的话，会把这个新标识符填入符号表中。而在语义分析阶段和代码生成阶段，同样也要通过查找符号来获得标识符的属性信息。可见，在编译程序运行过程中的符号表的查、填等动作非常之频繁，因而，提高符号表的查填效率就成为了提高编译程序运行效率的一个关键因素，这也是对符号表设计的一个根本的要求。三 中间代码的选取由于中间代码本身对后续的代码优化以及目标代码生成有着密切的关系。同时，它的结构又和目标机器的体系结构存在一定程度的关联，所以，中间代码的选择对于编译器的效率以及质量有着很大的关系。中间代码十分接近于底层的语言，因而中间代码的选择将会直接影响转换的效率，以及最终转换成的底层代码的质量，所以，中间代码生成这一步才显得更加关键，中间代码要适应于自己的程序，这非常关键。相比较于复杂难懂的逆波兰式，四元式是一种更加接近于汇编语言的语言形式，而且四元式的结构非常易于理解，这也是我选择四元式的一个重要的原因。四元式实际上是一种所谓“三地址”语句的表示方式，它的成分是：算符op，第一和第二运算分量arg1、arg2，还有运算结果result。四元式形如：(op,arg1,arg2,result)此处特别留意了for循环的四元式转换过程。对于程序：for(i=1;i=100;i+)可将此语句展开，随后再化为四元式，即：(=,1,_,1)(=,I,100,T1)(BF,7,T1,_)(+,sum,i,sum)(+,i,1,i)(BR,2,_,_)第七章 目标代码生成一 目标代码定义（一） 简介通常来讲，在编译原理中的所谓目标代码（objectcode）都是在指计算机科学里编译器程序或者汇编器程序在处理源代码之后所生成的那种代码。它一般是由机器代码或者其他更加接近于机器语言的别的代码组成。说到目标代码，这里就不得不提到一个概念：目标文件（objectfile），它是指代存放目标代码的一种计算机文件，通常情况下，它被称作是二进制文件。在这里，目标文件中包含着全部的机器代码，这些机器代码可以直接被计算机里面的中央处理器拿来执行。同时，这个文件当中还包含了代码在运行时所使用的全部数据：例如重定位信息，又如用于链接或者用来调试代码的那些程序符号，比如变量还有函数的名字等等。除此之外，这个文件还包括了其他全部的调试信息。所以说，目标文件就是从源代码文件去产生程序文件这一重要过程的一个中间产物。而我们平时所遇到和使用到链接器，则正是通过把目标文件全部给链接在一起然后来生成可执行