一种简单的编译器的设计

一种简单的编译器的设计 摘要：基于编译理论与虚拟机技术，经过词法分析、语法分析、语义分析等过程，设计一个简单的编译器，将某一种源程序编译成目标程序，以验证结果的正确性。 关键词：编译器；词法分析；语法分析；语义分析 中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)33-1508-03 The Design of a Simple Compiler CHENG Hua (Jiangsu Food Science College, Huaian 223003, China) Abstract: Based on compile theory and Virtual Machine technology,to transfer source program into destination program by Lexical analyse, Parse, Semantic analyse, and to test and verify the results. Key words: compiler; lexical analyse; parse; semantic analyse 1 设计背景 目前，计算机无纸化考试系统的应用越来越广，选择题、判断题的自动评分基本完善，但对程序修改题、编程题等考题来说，运用简单地看结果或指定行、段等办法评分，不能从根本上达到客观、公正地评阅考生答案。要想让计算机评分具有智能化，就必须让计算机具备“思想”，即让评分系统能“看懂”考生答案，能“感受”设计成果的优越之处与不足所在，能给“过程分”及“设计创新分”，而绝不单纯依赖“运行结果”。本文以此为切入点，基于编译理论与虚拟机技术，自主设计有限元编译系统，分课程、分模块，能自行分析、编译考生答案（如程序代码），进而判断其正确性、合理性及优越性。 2 编译程序的一般结构 编译程序结构框图如图1。 3 编译器的设计 3.1 建立符号表及其管理程序 建立符号表，收录某种语言（C、PASCAL等）的所有字符集，允许在编译的各个阶段插入或查找名字的相关信息，并且能够反映出名字所在的位置，编制相应的程序来实现对字符表的各种操作，主要操作有：查找操作、插入操作、定位操作、重定位操作。 3.2 建立一个词法分析器 图1 核心技术是处理单词符号的种类及内部的编码（需要设计翻译表）、行计数器等，把词法分析器作为语法分析器调用的函数，词法分析器以二进制的形式输出单词符号的类别编码和属性值。词法分析器依据源语言的构词规则对源语言进行分析,依次读入原程序中的每个字符，对构成原程序的字符串进行分解，识别出每个具有独立意义的字符串（相对记号叫做单词），为其构造记号，形成记号流，如果符号表中没有各记号对应的单词，则把单词添加到符号表中，添加时为记号增加一个属性值即一个指针，指向符号表中该记号对应的单词。在词法分析中，还进行词法检查。如果词法分析器从源程序读入不合法的字符要做错误处理，显示或打印错误信息，并跳过这个字符，继续识别和分析下一个字符。 3.3 建立一个语法分析器 先要消除文法中的左递规，从而采用预测分析的方法实现一个语法分析器。把语法分析器设计成层次结构，它把记号流按语言的语法结构层次分组，以形成语法短语，源程序的语法短语用分析树表示。然后根据源语言的语法规则进行语法分析，从源程序记号序列中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成做准备。在分析过程中，分析器采用自顶向下的方法为词法分析器生成的记号序列建立分析树，验证这个记号序列是不是该语言的一个句子，若是，则输出该句子的分析树，若不是，则表明输入的记号序列中存在错误，需要报告错误的性质和位置。 3.4 建立一个语义分析器 该部分要对语句的意义进行检查，以保证程序各部分能够有机的结合在一起，并为以后生成目标代码收集必要的信息。语义分析使用语法分析确定的层次结构来表示各语法成分（比如表达式和语句等），依据源语言的语义规则进行工作。其中一个重要的任务是类型检查，按照语言的类型检查规则检查每个运算符相关的运算对象，看其类型是否一致、合法，如果类型不一致则进行类型转换，可以做显示或隐式转换。 3.5 中间代码生成及优化 经过词法、语法、语义分析（这三个阶段为分析阶段）后，进入综合阶段。这个阶段的任务是根据所制定的源语言到目标语言的对应关系，对分析阶段所产生的中间形式进行综合加工，从而得到与源程序等价的目标程序。经过语法分析和语义分析后将源程序生成一种中间表示形式，也就是中间代码，然后对该中间代码进行优化，使之占用内存少、运行快，从优化的中间代码生成优化的目标代码。 3.6 错误处理 在编译的各个阶段都可能检测到源程序中的错误，发现错误则要向用户报告，并做适当的处理，使编译继续下去，以便对源程序中可能存在的其它错误进行检查。 4 编译程序的实现 本文仅以词法分析为例，给出词法分析程序的设计过程。 4.1 待分析的简单语言的词法 1) 关键字：为了简单起见，仅取5个关键字 begin、if、while、do、end，所以的关键字均为小写。 2) 运算符和界符：: = + - * /= = ; ( ) # 3) 其他单词是标识符（ID）和整型常数（NUM），通过以下正规式定义： ID=letter(letter|digit)* NUM=digitdigit* 4) 空格由空白、制表符和换行符组成，一般用来分隔ID、NUM、运算符和关键字，词法分析阶段通常被忽略。 4.2 为上述各种单词和符号设置对应的种别码 4.3 词法分析程序的功能 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。其中，syn为单词种别码，token为存放的单词自身字符串。 4.4 词法分析程序的算法思想 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。部分源代码如下： #include stdio.h #include string.h char prog80,token8; int typenn6=1,2,3,4,5,6; char ch; int syn,p=0,m=0,n=0,sum=0; char *rwtab6=begin,if,then,while,do,end; scaner() for (n=0;n8;n+)tokenn=0; ch=progp+; while (ch=) ch=progp+; m=0; if (ch=z&ch=a|ch=Z&ch=A) while (ch=z&ch=a|ch=Z&ch=A|ch=0&ch=9) tokenm+=ch;ch=progp+; m-;tokenm=0; p-; syn=10; for(n=0;n6;n+) if (strcmp(token,rwtabn)=0) syn=typennn; break; else if (ch=0&ch=9) while (ch=0&ch=9) sum=sum*10+ch-0;ch=progp+; p-; syn=11; else switch(ch) case : m=0; tokenm+=ch; ch=progp+; if (ch=) syn=21; tokenm+=ch; else if (ch=) syn=22; tokenm+=ch; else syn=20; p-; break; case +: syn=13; token0=ch; break; case -: syn=14; token0=ch; break; case *: syn=15; token0=ch; break; case /: syn=16; token0=ch; break; case #: syn=0; token0=ch; break; default:syn=-1; main() p=0; printf(n please input string:n); while (ch=getchar()!=#)progp+=ch; p=0; do scaner(); switch(syn) case 11:printf(%d,%dn,sum,syn);break; case -1:printf(error!n);break; default: printf(%s,%dn,token,syn); while (syn!=0); 5 结束语 本文说明了一种简单的编译器的设计及实现方法，特别是对词法分析程序进行了较深入的剖析。利用此思想及方法，生成了C语言的编译器，对PASCAL、BASIC等语言编译器的设计，也具有一定的借鉴作用。 参考文献： 1 Wilhelm R, Maurer D. Compiler DesignM. Addison-Wesley Pub.Co., 1