河北工业大学城市学院本科毕业设计（论文）前期报告
河北工业大学城市学院本科毕业设计（论文）前期报告
毕业设计（论文）题目：高级语言编译系统前端程序的开发
专业：计算机科学与技术
学生信息：学号：075851姓名：柏少乾班级：网络C072班
指导教师信息：姓名：吴清职称：教授
报告提交日期：2011年03月17日
1、课题意义
对源程序的词法分析开始到中间代码生成，编译程序所完成的处理工作只依赖于源语言，而与运行目标程序的计算机（或目标语言）无关，通常将这些环节统称为编译程序的前端（Front End）。代码优化和目标代码生成，一般只依赖于目标语言，通常将它称为编译程序的后端（Back End）。
如果能将编译程序严格划分为前端和后端两个相对独立的部分，并以中间代码作为其间信息交流的载体这样的模式来构造编译程序，将会给编译程序的开发和维护带来许多好处。例如在构建支持不同硬件平台的编译程序时，只需以编译前端生成的中间代码为接口开发不同硬件平台下的编译后端，以实现代码最大程度的复用。
本次课题主要提供的是一个适合于教学的编译器前端系统的软件雏形和演示程序。要完成具有词法扫描、语法和语义分析、符号表管理等模块的编译器前端的编程工作，即将字符串形式的源程序翻译成四元式形式的中间代码。
2、国内外研究现状
上世纪50年代，Noam Chomsky开始了他对自然语言结构的研究。他的发现最终使得编译器的结构异常简单，甚至还带有了一些自动化。Chomsky的研究导致了根据语言文法的难易程度以及识别它们所需要的算法来对语言分类。正如现在所称的Chomsky架构（Chomsky Hierarchy），它包括了文法的四个层次：0型文法、1型文法、2型文法和3型文法，且其中的每一个都是其前者的特殊情况。2型文法（或上下文无关文法）被证明是程序设计语言中最有用的，而且今天它已代表着程序设计语言结构的标准方式。分析问题（parsing problem，用于上下文无关文法识别的有效算法）的研究是在60年代和70年代，它相当完善的解决了这个问题。现在它已是编译原理中的一个标准部分。
有限状态自动机（Finite Automaton）和正则表达式（Regular Expreion）同上下文无关文法紧密相关，它们与Chomsky的3型文法相对应。对它们的研究与Chomsky的研究几乎同时开始，并且引出了表示程序设计语言的单词的符号方式。
当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编译器自动构造。这些程序最初被称为编译器的编译器（Compiler-compiler），但更确切地应称为分析程序生成器（Parser Generator），这是因为它们仅仅能够自动处理编译的一部分。这些程序中最著名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年为Unix系统编写的。类似的，有限状态自动机的研究也发展了一种称为扫描程序生成器（Scanner Generator）的工具，Lex（与Yacc同时，由Mike Lesk为Unix系统开发）是这其中的佼佼者。
3、课题研究的内容及重点解决的问题
（1）词法分析程序
编译程序的整个工作过程，是从接受字符串形式的源程序文件作为输入，并对此输
入进行词法分析开始的。词法分析的任务就在于依次扫视输入串中的各个字符，并从其中识别出一系列具有独立意义的基本语法单位——单词（token，也称为记号）。作为词法分析的结果，通常是把从源程序中所识别出的各个单词的词文（lexeme）转换为某种内部表示，并依次进行输出。而此种内部编码形式的单词串，将作为语法分析程序的输入和编译程序后续相关工作阶段的处理对象。
解决的问题有两方面，其一是如何描述一个语言中各种单词的结构，另一个是通过
什么途径来识别源程序中的各个单词。
（2）语法分析程序
语法分析是编译过程的一个逻辑阶段。
语法分析程序以词法分析程序所输出的用内部编码格式表示的单词序列作为输入，其任务是分析源程序的结构，判别它是否为相应程序设计语言中的一个合法程序。为了完成这种分析，一般的途径是由语法分析程序试着为其构造一棵完整的语法树。如果这种尝试成功，就表明该输入串在结构上的确是一个合乎语法的程序，否则，源程序中就必然存在语法错误。
产生语法树的方法，可大致分为两大类：自顶向下和自底向上。
（3）语义分析程序
语义分析是编译过程的一个逻辑阶段。
语义分析规定各语法成分的含义和用途，以及应进行的运算和操作。在进行语义分
析的过程中，还应进行相应的语义检查，以保证源程序在语义上的正确性。在其过程中，语义分析程序也需要进行频繁的造表和查表工作。
由于对程序语言的语义至今还没有找到一种公认的方法来系统地描述它们。在多数
情况下，人们不得不采用一种半机械化的方法来解决语义分析方面的问题。当前比较流行的是一种所谓“语法制导翻译”的方法，这种方法把编译程序的语法分析和语义分析有机地组织起来，穿插地进行。
（4）中间代码生成
为了处理上的方便，特别是为了便于代码的优化处理，通常在语义分析后不直接产
生机器语言或汇编语言形式的目标代码，而是生成一种介于源语言和目标语言之间的中间语言代码。目前常见的中间代码形式有逆波兰表示、三元式、四元式及树形结构等等。
中间代码的产生是与语义分析紧密相连的。但由于迄今对于程序语言的语义描述还
没有一个公认的形式化系统，因此，对编译程序中间代码生成部分的设计，在一定程度上仍凭借经验来完成。对于采用语法制导翻译的编译程序，通常的做法是将产生中间代码的工作交给语义过程来完成。即每当一个语义过程被调用而对相应的语法结构进行语义分析时，它就根据此语法结构的语义，并结合在分析时所获得的语义信息，产生相应的中间代码，再把后者放到中间代码的序列中去。
（5）符号表管理
在编译程序的过程中，符号表建立并保持一批表格，其中的每一登记项，将填入名
字标识符以及与该名字相关联的一些信息。这些信息，将全面地反映各个符号的属性及它们在编译过程中的特征，诸如名字的种属(常数、变量、数组、标号等)、名字的类型(整型、实型、逻辑型、字符型等)、特征(当前是定义性出现还是使用性出现等)、给该名字分配的存储单元地址以及与该名字的语义有关的其它信息等等。根据对编译程序工作阶段的划分，名字表中的各种信息将在编译程序工作过程中的适当时候填入。
符号表的建立分为分程序结构语言符号表的建立和非分程序结构语言符号表的建
立。
4、课题研究的思路和方案
编译系统前端可以划分为四个组成部分：词法分析程序，语法分析程序，语义分析程序
和中间代码生成。为了适合于教学用途，使整个编译程序的结构比较清晰，这里采用多遍扫描的编译程序结构，将整个编译程序划分为若干个相继执行的模块，每一模块都对它前一模块的输出扫描一遍，完成相应的工作，然后将工作的结果供下一模块加工。
当构造词法分析器时, 根据单词的正规式定义首先构造与正规式等价的NFA, 之后用子集法将NFA转换成DFA, 并用此DFA进行词法分析。对词法分析器生成器的设计算法进行了研究, 即构造等价于给定正规式非确定有限自动机。
LR分析法是编译程序语法分析中最常用且有效的自下而上的分析方法，理论较完善，适用于大多数上下文无关语言的分析。
5、工作计划安排
（1）前期掌握编译系统的原理，并通过文献和书籍了解国内外编译原理的研究现状和最新发展；（2）然后参考已有的程序设计语言定义一种语言，这种语言力求简单，容易用具有代表性的算法实现编译过程；（3）根据这种语言的文法，设计一个小型编译器的前端系统，完成编译器中用到的若干典型词法扫描、语法分析和语义分析以及中间代码生成算法；（4）具体实现编译前端系统，提供一个适合于教学的编译器前端系统的软件雏形和演示程序；（5）自行编写若干个典型的微源程序作为测试用例，对生成的系统进行测试和调试工作；（6）编写齐全的文档。
6、参考文献
[1] 蒋立源，康慕宁．编译原理．3版．西安：西北工业大学出版社，2005．1：42-268
[2] 李垒，陈平．词法分析器生成器的设计与实现．河南：河南工业职业技术学院，2008.09
[3] 胡慧，张海，余玛俐．类C语言词法分析器的设计与实现．九江：九江学院，2006
[4] 杨超，王一宾．一种改进的词法分析程序及其类C语言实现．安庆：安庆师范学院计算机与信息学院，2009
[5] 许秀林．C语言表达式的语法分析．南通：南通职业大学，2000
[6] 温敬和．LL(1)文法及分析表的自动构造．上海：上海第二工业大学，2001
[7] 付争方，张海娟．LR语法分析器构造方法初探．中国科技信息，2005
[8] 张艳红，康月兵．LS MPP编译系统中间代码的设计与实现．西安：第二炮兵工
程学院，2002
[9] 袁彩虹，薛光，张连堂．语义分析和中间代码产生教学过程研究．河南：河南大学计算机与信息工程学院，2009
[10] R.Gregory Taylor．LL parsing,LR parsing,complexity,and automata．New
York：ACM，2002
