基于gui的交互式编译系统之中间代码生成器的设计与实现

基于GUI的交互式编译系统之中间代码生成器的设计与实现基于GUI的交互式编译系统之中间代码生成器的设计与实现摘要本设计实现了一个编译器前端，它将一个用C语言的子语言编写的源程序翻译成中间代码。词法分析器、语法分析器、中间代码生成器均是采用C++语言手动书写完成，未采用自动生成器，GUI采用Win32API实现以保证轻快的运行速度及良好的系统性能，编辑控件采用Scintilla。词法分析器采用确定有限自动机实现，语法分析器是一个递归下降分析器，中间代码生成器输出的中间代码以四元式形式表示。本设计实现的编译器前端，运行在Windows平台下，Windows系统版本为WindowsXP、Windows7或更高版本。本设计提供了一个可工作的界面友好的编译器前端，可以用来理解编译原理及解释怎样用一种语言如C++实现编译器前端，以供学习和教学所用。关键词：编译器前端；GUI；C++

Design&ImplementationofIntermediateCodeGeneratorofInteractiveCompilationSystemBasedGUIAbstractThisfinalprojectimplementsacompilerfront-end,ittranslatessourceprogramswritteninasubsetoftheClanguageintointermediatecode.Thelexer、parserandintermediatecodegeneratorareallhand-writteninC++,noautolexerorparserareused,GUIisimplementedinWin32APIforfastrunningspeedandhighperformance,andeditcontrolusesScintilla.ThelexerisimplementedinDeterministicfiniteautomata,theparserisarecursive-descentparser,theintermediatecodesarerepresentedinquadruple。Thecompilerfront-endrunsontheWindowsplatform,WindowssystemversionisWindowsXP,Windows7orlater.Thisprojectprovideaworkinganduserinterfacefriendlycompilerfront-end,whichcanbeusedtodemonstratecompilerprincipleandhowcompilerscanbeimplementedinalanguagesuchasC++,forlearningandteaching.Keywords:compilerfront-end;GUI;C++

目录1绪论 绪论很少有人去自己编写或修改编译器，那么为什么要去实现编译器前端呢？很重要的一点就是，理解计算机程序怎样被编译以及执行，可以帮助任何程序员理解他们写的代码是怎样驱动计算机的，从而帮助他们写出更快、更高效的程序。编译原理经过多年发展已日趋成熟，然而现代很多跟编译原理相关的教材，内容陈旧落后，比如以Fortran或Pascal等过时语言为例进行分析讲解，或者全书充满晦涩难懂的定理公式，不能以直观的方式进行阐述，致使学生望而生畏。本设计用C++语言实现了一个编译器前端，它将一个用C子语言编写的源程序翻译成中间代码，拥有友好直观的交互式图形界面，有助于对编译原理的理解，可用于学习及教学。在一段程序可以执行之前，首先需要把它翻译成一种其能够被计算机接受的形式，完成这项翻译工作的程序称为编译器（compiler）[1]。简单而言，编译器是一个程序，它将使用源语言编写的程序转换成另一种目标语言。在转换阶段很重要的一部分是报告用户当前源程序的错误。为了将源程序从一种语言翻译成另一种语言，编译器必须首先把程序的各种成分拆开，并搞清其结构和含义，然后再把这些成分组合成有意义的计算机能识别的语言。编译器的前端进行词法分析、语法分析和语义分析，并且产生中间代码，即进行分析。编译器的后端对中间代码进行优化并将中间代码翻译成机器语言，即进行组合。词法分析的任务是：对源程序进行从左到右逐个字符地扫描，产生一个个独立的单词符号（token）。词法分析是编译的基础。语法分析的任务是：在词法分析识别出一系列单词符号的基础上，分析并判定源程序的结构是否符合语法规则。语法分析可以粗略地分为两类，一类是自顶向下，一类是自底向上[2]。对于本设计，采用的是自顶向下进行分析。语法分析得到语法树，尽管可以直接将语法树转换成目标机器代码，但这样做不利于可移植性和模块化设计。假设需要这样一个编译器：它可以编译N种不同的源语言，然后为M台不同的目标机生成代码。理论上，这是N*M个编译器，如图1.1(a)，但实现这么多的编译器是需要花费大量的人力物力。中间代码（intermediatecode,IC）是一种抽象机器语言，它可以表示目标机的操作而不需太多涉及与机器相关的细节，而且，它也独立于源语言的细节[3]。一个可移植的编译器如图1.1(b)所示，它先将源语言转换成中间代码，然后再将中间代码转化成目标机器语言，这样便只需要实现N个前端和M个后端。这种实现要更容易合理些。即使在只需实现一个前端和一个后端的情况下，好的中间代码也利于将系统模块化，使得编译器前端不会因机器相关的细节而复杂化，编译器后端不会因源语言的特殊信息而干扰。编译器可以使用的中间代码有多种形式，对于本设计，采用简单的四元式。ICIC(a)(b)图1.1面向5种语言并支持4种目标机的编译器：（a）没有IC，（b）有IC编译器的每个阶段都可能遇到错误，如果编译器在遇到第一个错误时就停止运行，对于修正程序肯定起不到多大帮助作用。词法分析阶段可以检测出来自输入的字符串不能形成语言的任何单词符号（token）。语法分析阶段可以检测出违反语言语法的单词符号串。本设计可以报告出错误是什么及错误在源程序的行号和列号。

2基本原理一个编译器是一个计算机程序，它可以把用某种高级语言写的源代码转换成另一种形式，典型的形式是机器码。机器码是计算机可以执行的一系列指令[4]。intmax(inta,intb){ if(a>b) returna; returnb;}一个编译器由有两部分组成，如图2.1所示。（1）源代码分析器：它将输入的源代码看作是一个字符串，然后将其翻译成有意义的符号（变量，值，操作符等）。（2）目标代码生成器：它将源代码分析器的结果转换成可执行代码。t1=-ct2=b*t1t3=t1+t2t1=-ct2=b*t1t3=t1+t2t4=t3目标代码源代码目标代码生成器源代码分析器目标代码生成器源代码分析器图2.1编译器结构源代码分析器不依赖于机器，然而目标代码生成器需要针对不同的机器类型生成不同的代码，因此是依赖于机器的。源代码分析器经常被称作编译器的前端，目标代码生成器被称作后端。本设计要实现的正是编译器的前端。编译器的前端又分为三个阶段，如图2.2所示。t1=-ct2=b*t1t1=-ct2=b*t1t3=t1+t2t4=t3前端源代码中间代码生成器语法分析器词法分析器源代码中间代码生成器语法分析器词法分析器图2.2编译器前端

2.1词法分析词法分析器以字符流作为输入，删除单词之间的空白符和注释（程序中每一部分都有可能出现空白和注释）并生成一系列的名字、关键字和标点符号。如果让语法分析器来处理它们就会使得语法分析过于复杂，结构也不清晰，这便是将词法分析成为一个独立阶段，从语法分析中分离出去的主要原因[5]。在词法分析器中，词法单元（token）通常包含以下几种类型：标识符保留字（如：“if”，“while”等）数值常量（如：整数，实数等）字符串常量简单符号（运算符如：“+”，“-”等，分隔符如：“；”，“，”等）多重符号（运算符如“+=”，“++”等）这些词法单元将用于下一阶段语法分析。2.1.1词法分析结果对于下面一段程序：intmatch(char*str) //findazero{ if(!strncmp(str,“0”,1)) return0;}词法分析器将产生如下tokens：INT ID(match) LPAREN CHAR STAR ID(str) RPARENLBRACEIF LPAREN BANG ID(strncmp) LPARENID(str)COMMASTRING(0)COMMA NUM(1) RPAREN RPARENRETURN REAL(0) SEMIRBRACEOF2.1.2确定有限自动机确定有限自动机可用来实现词法分析器。有限自动机包括一个有限状态集合和一些从一个状态通往另一状态的边，每条边上标有一个符号；其中一个状态是初态，某些状态是终态[6]。图2.3给出了几个有限自动机的例子。ifif312312IFa-za-z0-90-910-921210-92120-90-9ID NUM图2.3词法单词的有限自动机在确定有限自动机中，不会有从同一状态发出的两条边标记有相同的符号，确定有限自动机以如下方式接受或拒绝一个字符串：从初始状态出发，对于输入串中的每个字符，自动机都将沿着一条确定的边到达另一状态，这条边必须是标有输入字符的边，对n个字符的字符串进行了n次状态转换后，如果自动机到达了一个终态，自动机将接受该字符串，若到达的不是终态，或者找不到与输入字符相匹配的边，那么自动机将拒绝接受该字符串[7]。2.2语法分析语法分析是分析如何根据一个文法生成一个终结符号串的过程。一种语言的识别器是一个程序，它把输入看作一个字符串x，如果x是该语言的一个句子，则回答是，否则回答否。大多数分析方法都可以归为以下两类：自顶向下方法和自底向上方法。在自顶向下语法分析器中，构造过程从根结点开始，逐步向叶子节点方向进行，直至推出句子。自顶向下方法可以较容易地手工构造出高效的语法分析器。在自底向上语法分析器中，逐步对输入串进行归约，直至文法的开始符号，即从叶子节点开始，逐步向上归约，直至语法树的根节点。LL(1)文法表示对输入串从左到右扫描，进行最左推导，分析时每步向前查看一个字符。LL(1)分析法需要消除左递归和克服回溯。LR分析法表示对输入串从左到右扫描，构造最右推导的逆过程。LR分析法若采取手工构造，工作量非常大。本设计语法分析采用递归下降分析法。2.2.1递归下降分析法递归下降分析方法是一种不带回溯的自顶向下语法分析方法，它使用一组递归过程来处理输入。为文法的每个非终结符都创建一个相应的过程。递归下降分析法的一种简单形式是预测分析法。在预测分析法中，各个非终结符号对应的过程中的控制流可以由向前看符号无二义性地确定，在分析输入串时出现的过程调用序列隐式地定义了该输入串的一棵语法树[8]。假设用预测分析法分析以下文法(黑体字符序列被视为一个单元，也就是单个终结符号)：stmt expr; | if(expr)stmt | for(optExpr;optExpr;optExpr)stmt | otheroptExpr ε | expr则预测分析器如下所示：voidstmt(){ switch(curToken){ caseexpr: accept(expr);accept(‘;’); break; caseif: accept(if);accept(‘(’);accept(expr);accept(‘)’);stmt(); break; casefor: accept(for);accept(‘(’); optExpr();accept(‘;’);optExpr();accept(‘;’)optExpr(); accept(‘)’);stmt();break; caseother: accept(other);break; default: report(“syntaxerror”); }}voidoptExpr(){ if(curToken==expr) accept(expr);}voidaccept(terminalt){ if(curToken==t) curToken=nextTerminal; else report(“syntaxerror”);}该预测分析器中包含了两个过程stmt()和optExpr()，分别对应于文法中非终结符号stmt和optExpr。该分析器中还包括一个额外的过程accept。这个额外的过程用来简化stmt和optExpr()的代码。过程accept(t)将它的参数t和向前看符号比较，如果匹配就前进到下一个输入终结符号。因此，accept改变了全局变量curToken的值，该变量存储了当前正被扫描的输入终结符号。在分析过程的开始，首先调用文法的开始非终结符号stmt对应的过程，根据相应的语法规则，调用相应的处理过程。例如在处理“for(expr;expr;expr)other”输入时，curToken被初始化为第一个终结符号for。每个非终结符都产生一个对相应过程的调用：accept(for);accept(‘(’);optExpr();accept(‘;’);optExpr();accept(‘;’);optExpr();accept(‘)’);stmt();2.2.2运算符的优先级考虑表达式5+2*3。该表达式可有两种不同的翻译，即（5+２）*3或5+(2*3)。因此当多种运算符出现时，需要给出一些规则来确定运算符之间的相对优先关系。先考虑“+-*/”这四个常用运算符之间的优先级关系：左结合：+-左结合：*/创建两个非终结符expr和term，expr对应于“左结合：+-”，term对应于“左结合：*/”，并使用另一个非终结符号factor来表示表达式中的基本单元。当前，表达式中基本单元是数字位和带括号的表达式。factor digit|(expr)现在考虑具有最高优先级的二目运算符*和/。由于这些运算符是左结合的，因此其产生式和左结合列表的产生式类似：term term*factor| term/factor| factor类似的，expr生成由加减运算符分隔的term列表：expr expr+term | expr–term| term因此最终得到的文法是：expr expr+term|expr–term|termterm term*factor|term/factor|factorfactor digit|(expr)2.3中间代码生成目标代码目标代码1目标代码分析器目标代码分析器1中间代码目标代码分析器2中间代码目标代码分析器2目标代码目标代码2图2.4中间代码经常会有这种情况，编译器需要为几个目标机器生成机器码或汇编程序。中间代码是跟目标机器无关的，所以相同的中间代码可以在目标语言之间共享（如图2.4）。那么为一台新的机器开发编译器时就可以减少工作量。另外，很容易对中间代码进行优化，优化也是与机器无关的[9]。中间代码生成阶段将语法树翻译成中间语言表示形式。中间代码是机器无关的，但是它们接近机器指令。源程序通过中间代码生成器翻译成等价的中间语言。中间代码可以是不同的语言，它由编译器的设计者决定。语法树可以作为中间语言，后缀表达式可以作为中间语言，三地址代码（四元式）也可以作为中间语言。在后缀表达式中，任何语句表示都可以不使用括号，如：a*(9+d)=>a9d+*后缀表达式计算可以通过栈来实现。然而使用后缀表达式有很多不利的地方，如后缀表达式生成的汇编代码包含冗余的操作；这些操作只能在汇编代码中进行优化，而不是在中间代码中；优化需要针对特定的目标机器。因此需要一种接近汇编语言的中间代码，它支持机器无关级的优化。所以本设计采用四元式。2.3.1四元式在四元式中，所有的操作都可以归约为一元或二元操作。这种中间代码可以看成是一系列的执行步骤，每步的执行结果存储在临时变量中[10]。四元式由如下成分组成：操作符操作数，即两个操作数结果，存储运算结果（operator,arg1,arg2,result）一个简单的表达式可以用一个四元式表示：b+c=>(+,b,c,tmp1)稍微复杂的表达式可以由一个四元式集合表示，临时变量存储中间结果。a*(5+d)=>(+,5,d,tmp1) (*,a,tmp1,tmp2)2.3.2四元式的常见结构算术运算和布尔表达式a+b =>(+,a,b,tmp1)a*(b+c) =>(+,b,c,tmp1),(*,a,tmp1,tmp2)按照运算顺序，先计算括号中的表达式“b+c”，运算结果保存在临时变量tmp1中，然后计算a*tmp1。a<b =>(<,a,b,tmp)一元运算-a=>(-,a,_,tmp)下划线表示空。赋值a=a+b =>(+,a,b,tmp),(=,tmp,_,a)本设计的赋值运算只支持简单赋值，不支持连续赋值，如a=b=0。声明inta,b =>无inta=5 =>(=,5,_,a)声明时可以进行初始化。数组引用a=x[i]=>(=,x[i],_,a)x[i]=a=>(=,a,_,x[i])无条件跳转(jmp,jump_address,_,_)jump_address表示跳转目标地址，在本设计中是一个目标标号。条件跳转(<,i,5,tmp1) //条件(jtrue,jump_address,tmp1,_) //表示如果tmp1为真则跳转。注：是条件调转还是无条件调转，由arg2决定。for循环for(i=0;i<3;i++) body=>(=, 0, _, i) //初始化(label_0:,_, _, _)(<,i,3,temp_0) //条件(jtrue,label_1,temp_0,_)(jmp, label_3,_, _)(label_1:,_, _,_)bodyofloop...(label_2:,_,_,_)(+,i,1,i) //迭代(jmp,label_0,_,_)(label_3:,_,_,_)每个for语句会产生四个标号，一个表示类似“i=0”的初始化，一个表示类似“i<３”的条件判断，一个表示body,一个表示类似“i++”的表达式。if-else语句if(a<b)c=a;elsec=b;=>(<, a, b,temp_0)(jtrue, label_1, temp_0,_)(jmp, label_0, _,_)(label_1:,_, _,_)(=, a, _,c)(jmp, label_2,_,_)(label_0:,_, _,_)(=, b, _,c)(label_2:,_, _,_)一个if-else语句会产生3个标号，一个表示条件为真时的执行语句，一个表示条件为假的执行语句，一个表示跳出if-else语句。while语句while(a<b) a=a+1;=>(label_0:,_, _, _)(<, a, b,temp_0)(jtrue, label_1,temp_0,_)(jmp, label_2,_,_)(label_1:,_, _,_)(+, a,1,temp_1)(=, temp_1,_,a)(jmp, label_0,_,_)(label_2:,_,_,_)每个while语句产生3个标号，一个表示类似“a=0”的初始化，一个表示类似“a<b”的条件判断，一个表示body。switch语句switch(i){ case1: a=a+1;break; default: a=a+2;}=>(jmp,label_0,_,_)(label_3:,_,_,_)(+,a,1,temp_0)(=,temp_0,_,a)(jmp,label_2,_,_)(label_1:,_,_,_)(+,a,2,temp_1)(=,temp_1,_,a)(jmp,label_2,_,_)(label_0:,_,_,_)(==,i,1,temp_2)(jtrue,label_3,temp_2,_)(jmp,label_1,_,_)(label_2:,_,_,_)每个switch语句会针对相应的case和default产生标号，同时，还会产生跳出switch的标号。函数调用intadd(inta,intb){ returna+b;}voidmain(){ inta=1,b=1,c; c=add(a,b);}=>(add:,_,_,_)(enter,16,_,_)(+,a,b,temp_0)(return,temp_0,_,_)(return,_,_,_)(main:,_,_,_)(enter,16,_,_)(=,1,_,a)(=,1,_,b)(param,b,_,_)(param,a,_,_)(call,add,_,temp_1)(incStackPtr,8,_,_)(=,temp_1,_,c)(return,_,_,_)每个函数调用会针对主调函数和被调函数产生相应的标号。以上只是列举了一些简单情况下的示例，对于复杂的源程序，翻译成的四元式集是以上常见四元式结构组合的结果。2.4符号表符号表是一种供编译器用于保存有关源程序构造的各种信息的数据结构，这些信息在编译器的分析阶段被逐步收集并放入符号表[11]。编译器用符号表跟踪作用域及名字绑定的相关信息。在源程序中每次遇到名字都会去搜索符号表。如果新的名字出现或关于一个已存在名字新的信息出新，要对符号表进行更新。符号表条目可在词法分析阶段、语法分析阶段和语义分析阶段创建（如图2.5）。在本设计中，由语法分析器来创建这些条目。因为相对于词法分析器而言，语法分析器知道一个程序的语法结构，它可以更好地区分一个词法单元的实际意义，因此常更适合创建符号表条目。前端前端词法分析器中间代码生成器语法分析器词法分析器中间代码生成器语法分析器符号表符号表图2.5符号表符号表通常用哈希表实现。KEY：词素（lexeme），VALUE：符号（symbol）。2.4.1作用域在静态类型编程语言中，变量在使用之前必须声明，声明提供了变量的类型。如：inta;charc;通常，声明只在它的作用域内有效。函数作用域：每个变量在函数内部定义。块作用域：变量只在代码块内有效。floatfoo(inta,floatb){intc; //c为局部作用域中变量。{ intb=100; //块作用域中定义的b将参数b覆盖。c=a+b; //将参数a的值与新定义的b值之和赋值给c。}returnfloat(c)/b //此处的b为参数b。}为防止引用变量产生冲突，须为每个作用域设置一个符号表。2.4.2局部变量名的存储布局从变量类型可以知道该变量在运行时刻需要的内存数量。在编译时刻，可以使用这些数量为每个名字分配一个相对地址。名字的类型和相对地址信息保存在相应的符号表条目中[12]。数据对象的存储布局受目标机器的寻址约束的影响。比如，将整数相加的指令往往希望整数能够对齐（aligned），也就是说，希望它们被放在内存中特定的位置上，比如地址能够被4整除的位置上。类型的宽度（width）是指该类型的一个对象所需的存储单元的数量。一般情况下，字符类型（char）占用一个字节，整型（int）占用4个字节。可以使用一个变量，比如offset，来跟踪下一个可用的相对地址。在考虑第一个声明之前，offset被设置为0。每处理一个变量x时，x被加入符号表，它的相对地址被设置为offset的当前值，随后，x类型的宽度被加到offset上。

3设计与实现3.1C子语言本设计将一个用C子语言编写的源程序翻译成中间代码，该Ｃ子语言描述如下：3.1.1数据类型该子语言支持两种数据类型：int：32位有符号整型。char:8位无符号整型。只支持静态数组。如果传递一个数组给函数，数组将会以指针形式传递，所以对于数组的任何更改，将会影响调用函数传递的数组。另外，如果超过了数组的长度，调用函数的栈结构将会被破坏。每个作用域中的局部变量应该在该作用域块的开始即任何其他语句之前进行声明，就像以前的C98标准那样。3.1.2字面值整型，如：2343，-123字符串，如：“Hi，mynameisXiKangjie\n”字符，如：’a’,‘\n’3.1.3表达式表达式中只支持以下运算符：+，-，后缀++和--，*，/，%，<，<=，>，>=，==，||，&&布尔表达式中不支持短路代码。在短路代码中，布尔运算符&&、||和！被翻译成跳转指令。运算符本身不出现在代码中，布尔表达式的值是通过代码序列中的位置来表示的。3.1.4语句if-else语句switch语句while语句do-while语句for语句break和continue语句3.1.5函数有几个内建的函数用来基本的输入输出，它们是：-printStr(charstr[]);printStr("string");在标准输出中打印一个以null结尾的字符串。-printChar(charc);-printInt(intn);-readStr(charbuffer[],intbufferSize);-readInt(intn)这些函数会调用标准C输入输出函数，如printf和scanf，另外，这些函数名被视为关键字，所以它们是该语言语法的一部分。可以自定义函数。但是，需要知道这里不支持函数的前向声明：intf(intx);所以应该注意定义函数的顺序，当定义了很多相互调用的函数，会使程序变得复杂。另外，本子语言尽可能合理地去实现作用域，局部变量的作用域和生存周期就像C语言那样，但是没有全局作用域，也就是说不能定义全局变量。可是，在函数内部，可以自由嵌套作用域。比如：voidfoo() { intx,y; //嵌套块，产生一个新的内部作用域。 { intx;//嵌套作用域中的定义的x,它会将外部作用域中x覆盖。 if(true) { intx;//if块中定义的变量x,它会将外部作用域中x覆盖。 } } }在这个子语言中有很多的限制，比如没有类型检测，只有少量的语义分析等等。所以在此不是创建一种新的语言，而是以此子语言为例编写一个编译器前端。3.2符号表一个符号表必须允许添加新项，查找已存在项，支持在编译期间动态增长符号表。符号表可以实现为线性表和哈希表，线性表虽然容易实现，但表很大时性能会很差，所以本设计采用哈希表。本设计的符号表由类SymbolTable实现，其内部存储结构由哈希表实现（这里使用标准容器unordered_map），KEY代表词素（lexeme），VALUE代表与该词素对应的符号（Symbol）。符号由类Symbol实现。由于作用域可以嵌套，同时又要为每个作用域创建一个符号表，所以在类SymbolTable中，容器inner_scopes_存储嵌套的内部作用域，容器中的每个元素为指向内部作用域符号表的指针。指针outer_scope_指向外部作用域符号表。在创建一个符号表时，要为其传递外部作用域符号表参数，若当前创建的符号表为根符号表，则默认为其传递参数NULL。在符号表中插入新项有两种方式。一是插入Symbol，二是插入词素和词法单元标记。通过词素获取相应的符号，由重载运算符[]实现。classSymbolTable{public: SymbolTable(SymbolTable*prev=NULL):outer_scope_(prev){} ~SymbolTable(); boolInsert(Symbol*symbol); boolInsert(conststd::string&lexeme,TokenTagtag); boolIsInCurrentScope(conststd::string&lexeme)const; //重载了运算符[]，可以直接通过symboltable[key]来获取value。Symbol*operator[](conststd::string&key); std::vector<SymbolTable*>inner_scopes_; //内部作用域指针。 SymbolTable*outer(){returnouter_scope_;}private: SymbolTable*outer_scope_; //指向外部作用域 //用哈希map存储符号表。 std::unordered_map<std::string,Symbol*>table_;};类Symbol表示符号表的符号，它也是类VariableSymbol和类FunctionSymbol的基类。一个符号由词素和相应的词法单元标记组成，一个用于关键字if的符号对象可以通过以下语句创建：Symbolsymbol_if(“if”,IF);classSymbol{public:Symbol(conststd::string&lexeme,TokenTagtag):lexeme_(lexeme),token_tag_(tag){}virtual~Symbol(){}std::stringlexeme()const{returnlexeme_;}TokenTagtoken_tag()const{returntoken_tag_;}boolIsKeyword()const;private:std::stringlexeme_; //词素。TokenTagtoken_tag_; //词法单元标记，表示词法单元的属性。};类VariableSymbol表示变量符号，用来存储变量信息。offset_表示变量的偏移量，与变量在内存的布局有关；width_表示变量类型的宽度；size_表示变量占用的字节数；is_array_表示变量是否是数组；data_type_表示变量的类型，DataType是一个枚举类型，其中有三个元素，VOID_TYPE、INT_TYPE和CHAR_TYPE；kind_表示变量的种类，VariableKind是一个枚举类型，其中有两个元素，LOCAL表示变量是局部变量，ARGUMENT表示变量是参数。classVariableSymbol:publicSymbol{public: VariableSymbol(conststd::string&identifier):Symbol(identifier,ID){}private: unsignedintoffset_; //偏移量，即相对位置。 unsignedintwidth_; //变量类型的宽度，即占用的字节数。 unsignedintsize_; //整个符号占用的字节数。 boolis_array_; //当前符号是否是数组。 DataTypedata_type_; //数据类型，可以为int、char或void。 VariableKindkind_; //变量的种类，可以为局部变量或参数变量。};enumDataType{ INT_TYPE, CHAR_TYPE, VOID_TYPE};enumVariableKind{ LOCAL, ARGUMENT};类FunctionSymbol表示函数符号，用来存储函数信息。包括函数标示符，返回类型及参数信息。classFunctionSymbol:publicSymbol{public: FunctionSymbol(conststd::string&identifier,DataTypereturn_type) :Symbol(identifier,ID),return_type_(return_type){} DataTypereturn_type()const{returnreturn_type_;} std::vector<Parameter>parameters_; //参数列表。private: DataTypereturn_type_; //函数的返回类型。};类Parameter保存函数的参数信息。包括参数的标示符，类型，是否是数组。classParameter{public: Parameter(DataTypetype,conststd::string&identifier,boolis_array) :type_(type),identifier_(identifier),is_array_(is_array){} DataTypetype()const{returntype_;} std::stringidentifier()const{returnidentifier_;} boolis_array()const{returnis_array_;}private: DataTypetype_; //参数的类型。 std::stringidentifier_; //参数的名字。 boolis_array_; //参数是否为数组。};每个Token有个Tag变量，表示词素的属性，用于做出语法分析决定。用枚举类型TokenTag实现。枚举类型TokenTag的每个元素与编程语言上下文中的符号意义无关。在词法分析阶段，符号所代表的具体意义尚未知晓，在语法分析阶段，才确定符号的具体意义。比如，符号“*”叫做“ASTERISK”或者“STAR”。它可以表示不同的语言元素，比如可能是一个指针，或者乘号。所以在枚举变量TokenTag中，把“*”叫做“ASTERISK”，直到语法分析阶段才能从上下文解析出其具体意义。enumTokenTag{ END_OF_FILE=EOF, PLUS=(int)'+', MINUS=(int)'-', ASTERISK=(int)'*', FORWARD_SLASH=(int)'/', PERCENT=(int)'%', EQUAL=(int)'=', LESS=(int)'<', GREATER=(int)'>', OPEN_BRACE=(int)'{', CLOSE_BRACE=(int)'}', OPEN_PAREN=(int)'(', CLOSE_PAREN=(int)')', OPEN_BRACKET=(int)'[', CLOSE_BRACKET=(int)']', COMMA=(int)',', COLON=(int)':', SEMICOLON=(int)';', EXCLAMATION=(int)'!', LESS_OR_EQUAL=400, GREATER_OR_EQUAL=401, EQUAL_EQUAL=402, NOT_EQUAL=403, OR=404, AND=405, PLUS_PLUS=406, MINUS_MINUS=407, ID=256, NUM_LITERAL=257, STRING_LITERAL=258, //保留关键字。 VOID=300, INT, CHAR, IF, ELSE, FOR, DO, WHILE, SWITCH, CASE, DEFAULT, RETURN, BREAK, CONTINUE, PRINT_INT, PRINT_STR, PRINT_CHAR, READ_INT, READ_STR, GOTO};3.3词法分析器词法分析器的实现按照2.1.2节原理。状态转换图用来跟踪扫描器读入的当前查看字符。随着字符的读入，从一个状态转换到另一个状态。当进入一个状态，紧接着读入下一个字符如果有一条从当前状态发出的边且其上标志的字符和读入的字符相匹配，然后转向改变指向的下一个状态，否则报告错误。词法分析器由类Lexer实现，可用通过GetNextToken()获取下一个Token，或者通过PeekNextToken()查看下一个Token。核心算法在Scan()中实现，忽略注释和空白符，分析出以下类型的Token：算术运算符：+-*/%++--=关系运算符：<>>=<===!=||&&!界符：（）{}[];:,数字字面值和字符、字符串字面值：如123‘a’“name”标示符：如变量名、函数名等关键字：ifelsedowhileforreturnbreakcontinueswitchcasedefaultgotointcharvoidprintIntprintStrprintCharreadIntreadStr当遇到一个单一符号，如“+”，先假设它是多重符号，所以继续读取下一个字符，如果下一个字符是“+”，则返回token“++”，否则返回token“+”，并且回退一个字符。在解析注释时，注释可能为单行注释“//”，也可能为块注释“/*…*/”，都需要做处理。classLexer{public: Lexer(conststd::string&file_name); ~Lexer(); TokenGetNextToken(SymbolTable&symbol_table); TokenPeekNextToken(SymbolTable&symbol_table); std::stringsource_file(){returnsource_file_;}private: voidGetNextChar(); //获取下一个字符。 charPeekNextChar(); //查看下一个字符。 TokenScanToken(SymbolTable&symbol_table); std::stringsource_file_; //源程序的名字。 std::ifstreaminput_stream_; //输入源程序保存在一个输入文件流中。 charcurrent_character_; //当前正在分析的字符。};3.4语法分析器语法分析器从词法分析器获取单词符号串，验证其是否符合语言语法，同时报告语法错误。语法分析器由类Parser实现。对每个非终结符构造一个处理函数。语句的处理函数为ParseStatements()，遇到if则调用if处理过程，遇到for则调用for处理过程。函数ParseStatement()解析C语句，一次解析一个语句，语句包括赋值语句（为了简化，仅支持简单的赋值语句：var_id=expression）；if、for、while、do、switch、break、continue和空语句；IO语句如printInt。函数ParseBlock()解析块并实现作用域，如果正在解析一个函数，则传递相应的函数符号表参数，如果是一个一般的作用域或一个条件语句，传递NULL，这也是默认参数。如果在表达式中遇到一个标示符，它可能是一个变量也可能是一个函数，先通过函数ParseId()将其解析为一个变量，如果不能成功则通过函数ParseFunctionCall()将其解析为函数调用。函数NextToken()从词法分析器获得下一个token；函数Match()匹配token并获取下一个token，如果有错误，则生成错误信息。语法分析器在解析的过程中，通过函数Emit()生成四元式。变量offset_记录局部变量的相对偏移量；变量temp_counter_和label_counter_记录临时变量和标记的计数；变量current_token_记录当前正在解析的token。classParser{public: Parser(Lexer*lexer,IntermediateInstrsList*interm_list,std::vector<Message>*errors_list); ~Parser(); voidParse();private: voidNextToken(); boolMatchIf(TokenTagtag); voidMatch(TokenTagtag); voidMatch(TokenTagtags[],intn,conststd::string&msg); voidEmit(IntermediateInstr*instr); voidEmitLabel(conststd::string&label); voidEmitLabel(LabelOperand*label); unsignedintGetStackSize(); LabelOperand*NewLabel(); VariableOperand*NewTemp(DataTypetype=INT_TYPE,boolis_array=false,unsignedintelems=1); voidParseFunctions(); voidParseBlock(FunctionSymbol*func_symbol=NULL); voidParseDeclarations(); voidParseInitialization(conststd::string&var_id); voidParseStatements(); voidParseStatement(); voidParseAssignment(Operand*lhs_operand=NULL); Operand*ParseBool(); Operand*ParseAnd(); Operand*ParseEquality(); Operand*ParseRel(); Operand*ParseExpr(); Operand*ParseTerm(); Operand*ParseFactor(); Operand*ParseId(boolallow_func); Operand*ParseFunctionCall(conststd::string&func_id); std::vector<Operand*>*ParseArgumentsList();private: unsignedinttemp_counter_; //临时变量计数。 unsignedintoffset_; //变量相对地址。 unsignedintlabel_counter_; //标号计数。 Lexer*lexer_; //指向词法分析器。 std::stack<LabelOperand*>break_stack_; //用于break。 std::stack<LabelOperand*>continue_stack_; //用于continue。 SymbolTable*current_scope_table_; //当前作用域符号表。 SymbolTable*root_symbol_table_; //根符号表 FunctionSymbol*current_function_; //指向当前函数。 Tokencurrent_token_; //当前词法单元。};3.5中间代码生成器中间代码的四元式表示由类IntermediateInstr实现，该类包含四个数据成员，operation_表示运算符，operand1_、operand2_、operand3_表示两个操作数和结果。IntermediateOp是一个枚举类型。针对常见结构，按照2.3.2节中的原理进行翻译。classIntermediateInstr{public: IntermediateInstr(IntermediateOpop,Operand*operand1=NULL, Operand*operand2=NULL,Operand*operand3=NULL) :operation_(op),operand1_(operand1),operand2_(operand2),operand3_(operand3){} IntermediateOpoperation(){returnoperation_;} Operand*operand1(){returnoperand1_;} Operand*operand2(){returnoperand2_;} Operand*operand3(){returnoperand3_;} std::stringToString();private: IntermediateOpoperation_; //操作符。 Operand*operand1_; //操作数。 Operand*operand2_; //操作数。 Operand*operand3_; //操作数。};枚举类型IntermediateOP存储跟四元式中运算符相关的信息。enumIntermediateOp{ ASSIGN_OP=(int)'=', ADD_OP=(int)'+', SUBTRACT_OP=(int)'-', MULTIPLY_OP=(int)'*', DIVIDE_OP=(int)'/', NOT_OP=(int)'!', DIV_REMINDER_OP=(int)'%', LESS_THAN_OP=(int)'<', GREATER_THAN_OP=(int)'>', LESS_OR_EQUAL_OP=400, GREATER_OR_EQUAL_OP=401, EQUAL_EQUAL_OP=402, NOT_EQUAL_OP=403, OR_OP=404, AND_OP=405, IF_OP, GOTO_OP, LABEL_OP, INC_STACK_PTR_OP, DEC_STACK_PTR_OP, PARAM_OP, ENTER_OP, CALL_OP, RETURN_OP, PRINT_INT_OP, PRINT_STR_OP, PRINT_CHAR_OP, READ_INT_OP, READ_STR_OP};3.6GUI本设计实现的图形界面包含菜单栏、标签栏及编辑框。菜单栏包含“File”、“Edit”、“View”、“Tool”、“About”。如图3.1所示。标签栏支持多标签，当前编辑的标签上方会有黄色线条显示。编辑框支持显示行号，可在视图“View”菜单中选中“LineNumberMargin”进行显示。图3.1菜单栏菜单“File”包含的菜单项有“New”、“Open”、“Close”、“CloseAll”、“Save”、“SaveAll”、“SaveAs”、“Exit”。如果3.2所示。“New”：新建文件；“Open”：打开文件；“Close”：关闭文件；“CloseAll”：关闭所有当前打开的文件；“Save”：保存文件；“SaveAll”：保存所有当前打开的文件；“SaveAs”：将当前文件另存为；“Exit”：退出Front_end。图3.2菜单File菜单“Edit”包含的菜单项有“Undo”、“Redo”、“Cut”、“Copy”、“Paste”、“Delete”、“SelectAll”、“Find…”、“FindNext”、“Replace”。如图3.3所示“Undo”：撤销；“Redo”：恢复；“Cut”：剪切；“Copy”：复制；“Paste”：粘贴；“Delete”：删除当前所选区域；“SelectAll”：全选；“Find…”：点击显示查找对话框，如图3.4所示；查找的时候，可以选择匹配整个单词、匹配大小写、匹配正则表达式、循环匹配，查找方向可为上或下。“FindNext”：查找下一个；“Replace”：点击显示替换对话框，如图3.5所示。替换时可以选择替换当前匹配的单词，也可以选择替换所有匹配的单词。匹配时要进行查找，此处查找功能与“Find…”相同，同样可以选择匹配整个单词、匹配大小写、匹配正则表达式、循环匹配，查找方向可为上或下。图3.3菜单Edit图3.4查找对话框图3.5替换对话框菜单“View”包含的菜单项有“LineNumberMargin”、“Zoomin”、“Zoomout”。如图3.6所示。“LineNumberMargin实现显示行号功能”；“Zoomin”和“Zoomout”实现放大缩小功能。图3.6菜单View菜单“Tool”包含的菜单项有“Translate”。如图3.7所示。点击“Translate”将源代码转换成中间代码。图3.7菜单Tool点击菜单“About”，会弹出关于对话框。如图3.8所示。图3.8关于对话框本设计的图形界面通过类FrontEnd实现。classFrontEnd:publicWindow{public: FrontEnd():Window(),_mainWindowStatus(0),_pMainSplitter(NULL), _hTabPopupMenu(NULL),_pEditView(NULL),_pDocTab(NULL){}; voidinit(HINSTANCE,HWND,constchar*); virtual~FrontEnd(); voidkillAllChildren(); virtualvoiddestroy(); staticconstchar*getClassName(); voidsetTitle(constchar*title)const; voidsetTitleWith(constchar*filePath); boolisDlgMsg(MSG*msg)const; booldoOpen(constchar*fileName);private: staticconstchar_className[32]; Window*_pMainWindow; unsignedchar_mainWindowStatus; DocTabView_mainDocTab; DocTabView_subDocTab; DocTabView*_pDocTab; ScintillaEditView_mainEditView; ScintillaEditView_subEditView; ScintillaEditView*_pEditView; SplitterContainer*_pMainSplitter; SplitterContainer_subSplitter; HMENU_hTabPopupMenu; FindReplaceDlg_findReplaceDlg; AboutDlg_aboutDlg; staticLRESULTCALLBACKFrontEnd_Proc(HWNDhwnd,UINTMessage,WPARAMwParam,LPARAMlParam); LRESULTrunProc(HWNDhwnd,UINTMessage,WPARAMwParam,LPARAMlParam); voidnotify(SCNotification*notification); voidcommand(intid); voidfileNew(); voidfileOpen(); boolfileClose(); boolfileCloseAll(); voidhideCurrentView(); intdoSaveOrNot(constchar*fn); intdoReloadOrNot(constchar*fn); intdoCloseOrNot(constchar*fn); boolfileSave(); boolfileSaveAll(); boolfileSaveAs(); voidfilePrint(boolshowDialog); booldoSave(constchar*filename); voidenableMenu(intcmdID,booldoEnable); voidenableCommand(intcmdID,booldoEnable,intwhich); voidcheckClipboard(); voidcheckDocState(); voidcheckUndoState(); voiddropFiles(HDROPhdrop); voidcheckModifiedDocument(); voidreload(constchar*fileName); voidgetMainClientRect(RECT&rc)const; voidswitchEditViewTo(intgid); voiddynamicCheckMenuAndTB()const; intgetCurrentView()const; DocTabView*getNonCurrentDocTab(); ScintillaEditView*getNonCurrentEditView(); voidsynchronise(); voidchangeCheckedItemFromTo(intid2Uncheck,intid2Check)const; voidcheckMenuItem(intitemID,boolwillBeChecked)const;};类FrontEnd对创建一个窗口的基本过程进行了封装，如初始化窗口类结构，注册窗口类，显示窗口并进入消息循环。并且根据设计要求添加了菜单栏，标签栏和编辑框。还添加了其他一些消息处理过程，如打开文件、保存文件等。对于菜单栏、标签栏和编辑框的使用，与Windows标准相一致，也就是说会使用如记事本之类的编辑器，就会使用该图形界面。快捷键的设置，也是按照Windows的常用设置，即得即用，不会与自己平常的Windows操作习惯产生冲突。在实现本设计的图形界面时，充分考虑各种可能出现的使用情况，以保证其不会崩溃。例如当打开一个文件时，若该文件已经打开，则直接跳转到相应的标签栏，而不是再重复打开一个标签。当打开的标签数量过多以致标签超过窗口宽度时，标签栏右侧会出现调控控件。

4测试（1）打开源程序点击菜单“File”中“Open”，显示打开对话框，选择要打开的源程序，如图4.1所示。此处只支持打开C源程序文件。打开文件fact-rec.c后如图4.2所示。图4.1打开源程序图4.2fact-rec.c源程序（2）翻译成中间代码fact-rec.c由C子语言编写，用户输入整数n，输出结果为n!。点击菜单“Tool”中的“Translate”，运行结果如图4.3所示：图4.3运行结果（3）现在更改源程序，去掉第11行的“；”号，重新翻译以显示错误信息。错误信息如图4.4所示。图4.4错误信息（4）在fact-rect.c中查找有哪些输出语句。“Ctrl+F”打开查找对话框，输入print，选择“MatchCase”和“Wraparound”，点击“FindNext”进行查找，结果如图4.5所示。图4.4查找print（5）支持基本的编辑操作，如“复制”、“粘贴”、“剪切”、“全选”、“删除”、“撤销”和“恢复”。选中要删除的字符串，点击“Edit”菜单中的“Delete”或右键单击编辑框，在弹出的上下文菜单中选择“Delete”或按快捷键“Del”即可删除。现删除第16行的“printChar('\n');”，删除方法如图4.5所示，删除结果如图4.6所示。图4.5删除方法图4.6删除结果（6）保存生成的中间代码。右键单击选项卡，选择“Save”则在fact-rec.c所在目录下生成er文件，选择“SaveAs…”则打开“另存为”对话框，可以设计要保存的位置及文件名。如图4.7所示。图4.7保存文件

总结本设计实现的编译器前端，拥有友好的图形界面，可将C子语言编写的源程序翻译成中间代码（四元式），若源程序有错误，可以指出错误所在的行列。该设计虽然圆满完成了给定的任务，但仍有以下两个问题需要改进：（1）中间代码的正确性对于简单源程序，翻译成的中间代码可以马上看出其是否正确，但是对于复杂的程序，仍由人工验证其代码的正确性就有点低效了。可选的解决方案是继续完成编译器的最后一个阶段，将中间代码生成汇编代码，然后由汇编器将汇编代码生成可执行程序，通过执行程序的运行结果验证中间代码的正确性。（2）垃圾回收不能被引用的数据通常称为垃圾，如果实现了自动垃圾回收机制，就可以减轻手工存储管理的负担。

参考文献[1][美]KENNETHC.LOUDEN著,冯博琴、冯岚等译.编译原理及实践[M]——计算机科学丛书.北京:机械工业出版社,2005.3.[2]金成植.编译程序构造原理和实现技术[M].北京:高等教育出版社,2000.7.[3]陈火旺等.程序设计语言编译原理（第3版）[M].北京:国防工业出版社,2000.1.[4]王雷、刘志成、周晶.编译原理课程设计[M].北京:机械工业出版社,2005.3.[5]吕映芝、张素琴、蒋维杜.编译原理[M].北京:清华大学出版社,2004.2.[6]范文庆、周彬彬、安靖.深入剖析WindowsAPI开发详解[M].北京：人民邮电出版社，2011.3.[7][美]AlfredV、MonicaS等著,赵建华、郑滔等译.编译原理（第2版）[M].北京:机械工业出版社,2012.12.[8][美]AndrewW.Appel著,赵克佳、