一个简单的C语言编译器

1、一个简单的C语言编译器.小组成员嘉筱杭林朱王朱朱（）（）（）计算机996计算机996计算机996计算机994在DO*境下运行：Cminus.exe<filename>-h三.概述经过一段时间的学习，我们在初步掌握了编译器的基本原理以后，设计了一个具有基本编译功能的编译器。该编译器接受类C语言语法的源代码输入，输出结果是PC机的汇编源代码。在捆绑了宏汇编编译器Masmt,即可直接生成MSDOS的二进制可执行文件。为方便起见，以下简称为C语言编译器。本编译器实现了基本高级语言所必须的语法要素，包括简单变量声明、函数的实现、整数和字符串运算、条件判断语句和循环语句及跳转语句、基本代数运算

2、、赋值等，还支持汇编语言嵌入。本编译器是利用编译器生成器ParseGenerator和VC6.0在Windows平台上实现的，并开发了一个基于Windows平台的32位编译集成开发环境CompilerMan,提供了关键字彩色提示、出错同屏提示、出错代码跳转等较为完善方便的功能。由于编译程序本身涉及到词法分析、语法分析、代码生成、错误恢复和优化等诸多模块，要在实验中做到面面俱到不太可能，所以本编译器不可避免的会存在各种问题，但作为一个具有基本功能的、可扩充的系统，完全达到了巩固编译原理的理论知识，并将其运用于实践的目的。四.背景编译程序，就是一种具有编撰和翻译功能的程序。人们要用计算机来解决问题

3、，首先面临的一个问题，就是要告诉计算机解决什么问题，或者告诉计算机如何解决这个问题。这就涉及到用什么样的语言来描述的问题，人所习惯的自然语言和计算机认识的机器语言有很大的差别，用机器语言来描述人想解决的问题十分不便，因而，计算机科学家设计一些人们比较习惯的语言来描述要解决的问题，称之为B级语言。用语言来描述的问题，统称为程序。然而，用高级语言写的程序，不能被计算机所直接认识和理解，必须经过等价的转换，变成机器能理解并执行的机器语言的程序。进行这种等价转换工作的工具，就是编译程序。1 .编译程序的结构编译程序是很复杂的，但它可被分为相对独立的几个部分，每个部分承担专门的工作，各部分间互相共享传送

4、数据。把编译程序分解成较小的部分，不仅便于开发、调试，而且便于编译程序的移植。一个典型的编译程序通常具有如图1的结构目标机器码图1编译器基本结构1.1 词法分析词法分析负责对源程序的字符串进行扫描和分解，根据构词法将字符流(CharacterStream,专化成单词流(TokenStream)。例如对于C-语句：x=y+z-m*10;词法分析的结果是：IDASSIGNIDADDIDSUBIDMULNUMSEMI构词的规则就是词法，例如标识符（ID）可定义为以字母开头，后面跟零个或任意个字母或数字的序列。词法分析程序就根据词法构造有限自动机来识别每一个单词，将产生的单词交给语法分析程序。1.2

5、语法分析语法分析模块的任务是根据文法规则把单词序列分解成各类语法单位，识别出一个一个句子，例如对前面的语句进行语法分析可得到如图2的分析树。如果输入单词不能构成语法树，则说明有语法错误。常见的语法分析方法分为自顶向下分析和自底向上分析两大类。在C-编译器中采用了一种自底向上的方法,即LR方法。图2语法分析树1.3 语义分析这一阶段部分是根据前一阶段产生的语法树，按语言的语义进行翻译，产生四元式或三元式等中间语言。中间语言可以很方便地转换成目标代码。前面的语法树可能产生的四元式序列为：(*,_t0,10,m)(-,_t1,z,_t0)(+,_t0,y,_t1)(二,x,_t0)由于中间语言对后面

6、的代码优化和目标代码生成有密切关系，又和目标机器的体系结构有关，所以中间语言的选择对于编译器的效率和质量有很大的影响。1.4 代码优化代码优化是把中间代码进行变换，以产生更加高效的目标代码。1.5 目标代码生成目标代码生成是编译最后一个阶段，它把中间代码转换成汇编指令或可重定位的目标代码。例如对于前面生成的中间代码，可以产生旧MPC汇编指令为：movax,mmulax,10movbx,zsubbx,axaddbx,ymovx,bx汇编代码经过Masm汇编器(Assembler)和连接器(Linker)处理，就产生了可在IBMPC机器上运行的二进制代码。2 .形式语言简介2.1 文法和语言文法是

7、产生语言的规则，它可定义为：对于一个四元式G=(Vn,Vt,S,P),其中(1) Vn是非终结符号的有限集合(2) Vt是终结符号的有限集合，且VtAVn二(3)开始符号S,SCVn(4) 一组产生式P,P中的每一个产生式都具有如下形式：uv,u(VnUVt)+且至少要有一个非终结符号，vC(VnUVt)*则G表示一个文法。乔姆斯基(NoamChmosky)把文法分成四类：0型文法又称无约束文法，产生式的形式为a-b,a、b是任意字符串。1型文法又称上下有关文法，产生式形式为a-b,且|aR|b|02型文法又称上下文无关文法(Context-FreeGrammar),产生式形式为A-a,a(V

8、nUVt)*,ACVn。3型文法又称正规文法，它的产生式左部是一个非终结符号，右部最多只有一个非终结符号且在右部的最左端或最右端。通常程序设计语言的文法属于2型文法，可被下推机(PushdownAutomaton以别。语言定义为L(G尸wS=*w,wVt*,可见，文法G中的Vt相当于产生语言的字母表，G中的一组产生式是产生语言的一组规则；语言L(G)中的每一个句子w,是由G的开始符号S经推导得到的，完全由终结符号组成的字。非终结符号是引起推导继续进行的中间符号，在推导进行到某一步时，如果再没有非终结符号留在推导的结果中，则称推导成功。在语言的设计和编译器的编写方面，文法都提供了极大的优点：a)

9、文法给出了精确的，也易于理解的语言语法说明。b)对于某些文法类，可以自动产生高效的分析器。额外的好处是，分析器的构造过程可以揭露出语法的二义性和其它难于分析的结构，这些问题在语言和它的编译器的最初设计阶很可能没有发现。c)设计得漂亮的文法，把结构加于程序设计语言，这些结构对把源程序翻译成为正确的目标代码和错误诊断都是有用的。把以文法为基础的翻译的描述转变成程序的开发工具也是存在的。d)语言也是逐渐完善的，需要补充新的结构和完成附加的任务。如果存在以文法为基础的语言的实现，这些新结构的加入就更方便。2.2 巴科斯范式(BNF)巴科斯范式(BackusNormalForm,BNF)是描述语法规则的

10、一种形式方法，在该方法中，使用如下符号：非终结号:=定义符|或者括号内的成份可以重复出现多次，也可以不出现括号内的成份为任选项，可以出现一次或不出现例如C语言中IF-THEN语句可以表示成：IF语句:=IF布尔表达式THEN语句卜ELSE语句习用巴科斯范式的形式表示文法的优点是简洁、清楚并容易被理解。3 .编译程序的实现环境ParseGenerato徜介及其使用编译器生成工具-ParseGenerator基于Windows平台，它集成了词法生成器ALEX和语法生成器AYACC,并提供了较为强大的类库。其主要优点体现在以下几个方面：可以视一个编译程序为一个Project,集成Alex和Ayacc

11、文件的环境有利于整体调试和开发。且编辑界面友好，利于初学者使用。.l文件（lex文件）和.y文件（yacc文件）可生成为标准的C原代码，也可生成VisualC+和BorlandC+格式的原代码。这对习惯与BC或VC编程的程序员，无疑是极大的方便。ALex和AYacc的表驱动代码隐藏在联接库中。库在程序LINK的时候连入系统中。这在程序编译的效率和灵活性两个方面都有较大贡献。ALex和AYacc的原代码和和生成的目标代码（C或C+）可以建立语句的对应，这对生成代码的调试提供很大方便。实验中的编译程序采用将ALex和AYacc文件转化为VisualC+格式的代码。现将程序中使用的联接库中主要类和函

12、数作一介绍。类yylexer-所有词法分析器类的基类yylexer类提供由Alex生成的C+词法分析器的一切基本功能。yylexer是一个抽象类，要使用它，必须继承出自己的类，并实现抽象函数yylex和yyaction。C-编译器程序中的词法分析器类是其子类C_Lexer类。类yyparser-所有语法分析器类的基类yyparser类提供由AYacc生成的C+语法分析器的一切基本功能。yyparser是一个抽象类，要使用它，必须继承出自己的类，并实现抽象函数yywork和yyparseaction=C-编译器程序中的语法分析器类是其子类C_Parser类。五.详细设计1.功能说明输入：类C语言

13、纯文本源程序。输出：目标机为具有8086+处理器的MSDOS系统下的二进制可执行代码。PCAssemblyLanguage编语言源代码以供分析使用。本编译程序实现的主要功能如下表所示:功能备注支持以下数据类型：int整型char字符型char口字符数组int口整型数组整型为有符号16位数。字符型为8位数。数组的下标允许为任何合法的表达式。经过简单引、充后，即可实现长整型，无符号整型。支持以下数据操作：+加法-减法*乘法/除法%取余+自力口1-自减1*乘力&,|位与，位或A异或位非&&,|逻辑与，逻辑或!逻辑非<,>,<=,>=关系比较运算=,!=

14、关系比较运算<<,>>算术移位+-*/%=,*=,多达12种赋值<<=,>>=,&=,语句尸，A=,=支持以关键子_asm前导的形式为_asm的嵌入汇编代码(EMBEDEDASSEMBLY)对嵌入汇编的支持大大提高的谛言的可用性，一定程度弥补了系统函数较少的缺憾。提供系统级库函数：voidprint(/*表达式*/,%t);支持字符串，字符，整型三种类型的变量输出，包括任何合法表达式的值。支持循环，转移，判断分支的程序设计，支持if,if.else,if.elseif.forwhile,do.whilegoto.语句。支持Label,允许

15、在任何语句前定义Label作为控制转移目的地。for和while语句支持break,continue流程控制。支持函数概念。系统以main函数为入口函数。支持源程序注释。注释以“/或"/*"，标型支持出错提示。对于嵌入汇编代码的出错提示可以通过重定向汇编代码编译器的出错信息实现。2.词法分析器(lexer)2. 1正规式和DFA e和小都是2上的正规式，它们所表示的正规集分别为e和小 任何aCE,a是2上的一个正规式，它所表示的正规集为a 假定U和V都是2上的正规式，它们所表示的正规集分别记为L(U)和L(V),那么，(U|V)、(U.V)和(U)*也都是正规式，它们所表示

16、的正规集分别为L(U)UL(V)、L(U)L(V)和(L(U)*。仅由有限次使用上述三步骤而定义的表达式才是2上的正规式，仅由这些正规所表示的字集才是2上的正规集。正规式可以有效地描述词法，而确定的有限自动机(DFA)能准确地识别正规集，执行词法分析的功能。2.2利用有限自动机进行词法分析词法分析是整个编译过程的第一阶段，它将字符序列转化为单词序列。识别单词的基本方法是根据词法定义构造有限自动机即描述语言结构特征的状态转换图。例如对于十进制整数正规定义：1-9+0-9*可以构造如图3所示的有限自动机。图3识别十进制整数的有限自动机其中状态2为接收态，若对于一个字符序列有限自动机可以到达2状态，

17、则说明一个整数已被识别出来。词法分析器构造程序LEX正是根据这一原理工作的。构造词法分析器的主要任务是设计词法的正规定义和相关的动作。上面例子的LEX程序段就是：1-9+0-9*returnICON;2. 3C-词法分析器的实现数据结构1）关键字和系统标识符表Ktab保存关键字和系统标识符的信息，定义如下：typedefstructchar*name;intval;KWORD;其中name域保存关键字的名字，val域保存关键字的种类标识。val域就是词法分析器传递给语法分析器的终结符信息。2） C-中的关键字以下为Ktab数组的定义:KWORDKtab="break",BR

18、EAK"char",TYPE"continue",CONTINUE,"do",DO,"else",ELSE,"for",FOR,"goto",GOTO,"if",IF,"int",TYPE,"main",MAIN,"print",PRINT,"while",WHILE;具体实现（参见源文件C-_lex.l）1）对注释的处理：支持/*.*/和/两种注释风格，对于注释内容在匹配到/

19、*和/后，直接通过动作input跳过。处理了注释符号遗漏的情况，并有出错信息显示。2）常数的处理：词法分析器可识别十进制、八进制和十六进制无符号整数以及字符常数（形为a；并通过函数intstoi（char*string,intradix）转化成数值形式。3）标点符号的处理：直接返回其相应的标识。4）标识符的处理：识别标识符后，调用函数id_or_keyword查找其属性值并返回。对于系统保留字和关键字，函数id_or_keyword返回相应的标识（token）返回值相同的，可以通过yytext区别。对于用户自定义的标识符，函数id_or_keyword返回NAME。为了提高查找关键字和系统标识

20、符表的效率，函数id_or_keyword采用二分查找法(bsearch函数)。5)嵌入汇编(_asm)的处理：在函数id_or_keyword()中当遇到yytext="_asm”时，则进入嵌入汇编处理代码：史匹而字符'',如果接下来的第一不字符不是',则打印出错信息。如果匹配则将后续代码原样写入汇编代码中，直至遇到字符结束；如果未遇到则打印出错信息。由于要防止嵌入汇编代码中出现字符立即操作数'或注释语句中的',因此要考虑这些情况。采用上述方法的好处是大大简化了语法分析器的工作，不必设计大量的产生式来处理汇编格式。但是这样就不能检查嵌入汇编的

21、语法错误。可以采用这样的方法：用Masm编译嵌入的代码，重定向其输出而判断有无汇编语法错误。6)生成的C_Lexer的类定义(参见源文件C-_lex.h):classC_Lexer:publicyyflexerpublic:嵌入C_Lexer();protected:voidyytables();virtualintyyaction(intaction);public:;C_Lexer()实现对词法分析器对象的初始化，它调用yytables()。yyaction()则具体由定义的正则表达式实现归约。3.语法分析器(parser)3.1上下文无关文法上下文无关文法G可以用一个四元组表示G=(V,

22、T,P,S)其中： V是文法的非终结符号集，每个非终结符号表示语言的一个语法变量； T是终结符号集，每个终结符号表示语言的一个基本符号，即词汇； P是产生式集，文法用产生式定义每个非终结符号； S是V中的一个非终结符号，称开始符号。文法的每个产生式由左、右两部分组成，左部是一个非终结符号；右部是由零个或若干个终结符、非终结符组成的符号用。3. 2LR分析方法LR分析方法是自底向上进行语法分析，它的功能很强，适用于多种上下文无关方法。L是指从左向右扫描输入申，R指的是按照最右推导的的逆过程进行归约。LR分析法具有一些优点： 能用上下文无关文法描述的程序设计语言结构，都可以构造其LR分析器进行识别

23、。 LR分析法是具有一般性的无回溯移进归约分析法，并且能有效地被实现。 能用LR分析器分析的文法类包含能用LL(1)分析器分析的全部文法类。 LR分析器在自左向右扫描输入时，可以尽可能地发现语法错误。输入图4LR分析器图4是LR分析器的结构示意。其中分析栈存放状态和移进、归约的文法符号：S0XlSl.Xm-lSm-lS0其中，Si表示状态，Xi表示文法符号；在实现中，文法符号不必进分析栈。动作表中的项目ACTIONSm,ai表示当前输入符号为a、栈顶状态为Sm时，分析算法应执行的动作；若ACTIONSm,a=S,表示移进，然后栈顶状态为i;rj表示用产生式j归约；acc表示接收输入申，err表

24、示语法错误。状态转换表中的项目GOTOSi,X表示归约出非终结符号X之后，当前栈顶状态为Si时，分析栈应转换到的下一上状态，即栈顶的新状态。LR分析算法为：根据输入符号a、栈顶状态Sm和动作表项actionSm,a的值，决定当前分析应执行的动作；移进、归约、接收或出错；移进或归约之后要根据动作表或状态转换表设置分析栈的状态。可以把分析栈中的用和等待输入的终结答号用看成是两个分量，这两个分量构成如下形式的二元组：(S0X1S1X2S2.XmSm,siai+1.an#)这个二元组结构表示右句型X1X2.Xmaa+1.an#假定当前分析栈的栈顶为状态Sm,下一个输入符号为ai,分析器的下一个动作由动

25、作表项actionSm,a决定。,如果actionSm,a=移进S,则分析器执行移进，二元组变成(S0XlSlX2S2.XmSmaiS,ai+1.an#)即分析器将输入符号ai和状态S移进栈，于是，a+1变成下一个输入符号。 如果actionSm,a=归约A-0则分析器执行归约，二元组变成(S0XlSlX2S2.Xm-rSm-rAS,ci+1.an#)其中，S由goto表确定：S=gotoSm-r,a,r=|0|,是句柄号用的长度。归约时，分析器先从栈中弹出2r个元素：r个状态和r个文法符号；于是使状态Sm-r出现在栈顶；然后，再把归约产生式左部的非终结符A和由gotoSm-r,A确定的状态S

26、压入栈。在归约过程中不改变输入符号。对LR分析器来说，从栈中弹出的文法符号用Xm-r+1.Xm总是匹配归约产生式的右部B。 如果actionSm,a=acc,则接收输入符号用，语法分析完成 如果actionSm,a=err,则发现语法错误，调用错误处理子程序。3.3C-系统中使用的主要产生式(参见源文件C-_par.h)programMAINLPRPcompound_stmtcompound_stmtLClocal_defsstmt_listRClocal_defsdef_listdef_listdef_listdef|/*epsilon*/defspecifiersdecl_listSEMI

27、decl_listvar_decl|decl_listCOMMAvar_declvar_declnew_name|var_declLBICONRB|LPvar_declRPnew_nameNAMEspecifiersTYPEstmt_liststmt_liststatement|/*epsilon*/statementSEMI|compound_stmt|PRINTLPexprCOMMADIVOPICONRPSEMI|exprSEMI|GOTOtargetSEMI|targetCOLONstatement|IFLPtestRPstatement|IFLPtestRPstatementELSEs

28、tatement|WHILELPtestRPstatement|DOstatementWHILELPtestRPSEMI|FORLPopt_exprSEMItestSEMIopt_exprRPstatement|BREAKSEMI|CONTINUESEMItestexpr|/*epsilon*/targetNAMEopt_exprexprexprexprCOMMAnon_comma_exprnon_comma_exprEQUALnon_comma_expr|non_comma_exprASSIGNOPnon_comma_expr|or_expror_expr:or_listor_list:or

29、_listORORand_expr|and_exprand_expr:and_listand_list:and_listANDANDbinary|binarybinary:binaryRELOPbinary|binaryPOWERbinary|unaryunary:LPexprRP|3. 4系统中符号表的实现1)符号表的组织要求编译程序用符号表跟踪关于名称的汇聚信息和作用域，当词法分析器识别出一个标识符后，编译程序就查找符号表，看它是否在符号表中，如果没有，则把这个新标识符填入符号表。在语义分析阶段和代码生成阶段也要通过查找符号表来获得标识符的属性信息。可见在编译过程中符号表的查、填动作非常频

30、繁，因而提高符号表查填效率是提高编译程序运行效率的关键因素，也是对符号表设计的根本要求。2)符号表的几种组织方式线性表符表项按顺序排列，这种组织方式最简单并且实现也很容易。线性表的缺点是插入和查找的效率较低，虽然可以采用反序查找、表项排序、动态调整表项来提高效率，但其性能的改善是很有限的。,哈希表通过计算符号的哈希值来确定其在表格中的位置。哈希表结构简单、实现较容易，而且其插入和查找效率很高。采用哈希表要解决“冲突”的问题，而解决冲突将会提高哈希表的复杂度。二叉树二叉树的组织方式平均查填效率最高，但实现的复杂度较高。对于名称冲突也要特别处理。在某些情况下，二叉树会退化成线性表，这个问题可以通过

31、采用AVL树的结构来解决，但这会进一步提高实现的代价。3)C-系统中符号表的组织(参见源文件Symbol.h)本编译程序中对符号表的管理和操作在CSymbol类中实现，采用的是哈希杂凑表的方式。该类的声明如下：classCSymbolpublic:CSymbol();symbol*NewSymbol(char*name,unsignedlevel);symbol*FindSymbol(char*name);boolDeleteNest(symbol*pHead);unsignedHash(char*name);virtual-CSymbol();private:Hash_Node*SymTab

32、leTABLE_LEN;类中所涉及到的结构声明如下:structsymbol/输入变量名/实际变量名/当前嵌套级/变量类型/指向同层的下一个变量charnameNAME_MAX+1;charrnameNAME_MAX+1;unsignedlevel;type*pType;symbol*next;structHash_NodeHash_Node*pre;Hash_Node*next;symbol*sym;/上一个冲突节点/下一个冲突节点/指向此节点上的变量CSymbol采用哈希表来实现对变量的管理和查找。变量表采用数组实现，对于每一个产生哈系冲突的变量节点，利用链表将其连接到已有的节点后。在本编

33、译程序中，采用了较复杂的计算哈系值的算法，其伪码如下：unsignedCSymbol:Hash(char*name)hash_val=0;for(制变量名中的每一个字符)hash_val=(hash_val<<2)+变量字符值;if(i=hash_val&0x3fff)hash_val=(hash_valA(i>>12)&0x3fff;返回hash_val;CSymbol类中两个主要的成员函数是：symbol*FindSymbol(char*name),实现根据变量名，在变量表中查找该一项。-symbol*NewSymbol(char*name,unsi

34、gnedlevel),实现在变量表中力入个symbol项。4)其他主要结构定义(参见源文件structtypeunsignednoun;intnum_ele;intv_int;一Structs.h)/CHARINTnumberofelementsifarrayValueifconstantstructvaluecharnameNAME_MAX*2;type*pType;symbol*sym;boollvalue;boolis_tmp;unsignedoffset;/Operandthataccessesthevalue/Variable'stype/Originalsymbol/TRU

35、E=lvalue,FALSE=rvalue/TRUE=temp,FALSE=non-temp/Abolutevalueofoffsetfrombaseoftemp/stack;3. 5系统中局部变量的处理虽然本编译程序采用预分配栈来存放局部变量，这样的做法浪费空间且缺乏灵活性，但是它带来的一个好处是局部变量可以回收，而不像很多编译程序存在着局部变量无法回收的缺憾。处理局部变量的主要函数有(参见源文件Functions.h及Functions.cpp):voidfigure_local_offsets(symbol*s);voidrelease_local(symbol*s);函数巾gure_l

36、ocal_offsets为一个层中的局部变量分配空间，而函数release_local则释放在某一层灰行疝寸释放其中的所有变量。这可以通过遍历杂凑链表中的该层一的变量链表(单向链表)得到所有变量的存储总长度，然后把局部变量堆栈指针减掉这个长度就可以了。这样该层的所有变量所占的空间都释放掉了。下一次又可以使用这些释放的空间。4. 6系统中临时变量的处理临时变量是编译系统中使用较多的部分，通过建立临时变量来记录每一次运算的结果，使后续的运算能方便地引用前次的值，是一个较通用的方法。所以，临时变量的管理成为编译程序中一个比较重要的部分。因为本编译程序的条件限制，系统中对临时变量的处理采取栈式结构存放

37、的方法。存放临时变量的堆栈是系统全局的，通过在编译程序初始化是建立，如下：fprintf(OutPut,"t%stdbt%ddup(?)nn",TMP_STACK,TMP_STACK_LEN);此语句将在汇编源代码中生成如下的语句：t_stackdb1024dup(?)系统通过一个布尔型数组对临时变量栈进行管理。boolTmp_RegTMP_STACK_LEN;Tmp_Regoffset的值表示临时变量栈中偏移量为offset的空间是否已被分配为临时变量的存放。系统使用以下4个函数完成对临时变量的管理:inttmp_a110c(intsize)；value*tmp_create(type*t)；voidtmp_free(intoffset,intsize)；voidtmp_freeall(void)；3.7系统中代码的生成编译程序中的翻译的推导规则和每一个推导的相应动作，生成汇编源代码。(详见程序清单)主程序框架的生成通过函数voidInit(void)和voidEnd(void)完成。Init主要任务： 生成数据段、代码段； 生成主程序的起始代码； 返回地址入栈； 创建全局和系统堆栈； 初始化系统变量。End主要任务： 生成返回操作系