编译原理课程设计

1、课 程 设 计 报 告设计题目：一个简单文法编译器的设计与实现班 级：计算机1302组长学号：20133823组长姓名：高思坦指导教师：肖桐设计时间：2015年12月1设计分工组长学号及姓名：20133823 高思坦分工：目标代码生成组员1学号及姓名：20133826 李北分工：语法分析、中间代码生成组员2学号及姓名：20133822 方秋生分工：词法分析翻译器组员3学号及姓名：20133839 吴永琪分工：词法分析识别器组员4学号及姓名：20133832 刘向甲分工：符号表管理摘 要现代计算机的程序很多都是用高级语言编写的，而这些高级语言计算机是无法识别的，因此需要将它们转变成计算机能识别的

2、语言，此时就需要借助到编译程序。编译程序是一种翻译程序，它特指把某种高级语言（如C、Java、Pascal）翻译成具体计算机上的低级程序设计语言。编译程序是计算机系统软件最主要的组成部分之，也是用户最直接关系的工具之一。一个编译程序的可以划分为前端和后端。前端包括词法分析、语法分析、语义分析与中间代码生成三个阶段，后端包括优化、目标代码生成两个阶段，另外还有符号表的管理和错误处理贯穿整个过程。一个编译程序，既可以一个阶段一个阶段地对源程序进行分析，也可以前端只对源程序进行一遍分析，后端也只进行一遍分析。本课设实现了对C语言中的一部分功能的编译，包括算术逻辑表达式、if语句、while语句以及一

3、维数组等。前端对源程序扫描一遍实现词法分析、语法分析、语义分析与中间代码生成三个阶段，后端进行目标代码生成，整个过程穿插符号表管理和错误处理。关键词：编译程序，前端，后端目 录摘要.I1 概述 .12 课程设计任务及要求 .2 2.1 设计任务 .2 2.2 设计要求.23 算法与数据结构.3 3.1 算法的总体思想（流程）.3 3.2 词法分析识别器模块.4 3.2.1 功能.4 3.2.2 数据结构.5 3.2.3 算法.9 3.3 语法分析模块.11 3.3.1 功能.113.3.2 数据结构.12 3.3.3 算法.16 3.4 语义分析和中间代码生成模块.30 3.4.1 功能.30

4、3.4.2 数据结构.31 3.4.3 算法.33 3.5 符号表模块.41 3.5.1 功能.413.5.2 数据结构.41 3.5.3 算法.43 3.6 目标代码生成模块.43 3.6.1 功能.433.6.2 数据结构.44 3.6.3 算法.454 程序设计与实现.474.1 程序流程图.47 4.2 程序说明.47 4.3 实验结果.505 结论.616 参考文献.627 收获、体会和建议.62641 概述在计算机上执行一个高级语言程序一般要分为两步；第一步，把高级语言翻译成机器语言程序；第二步，运行所得的机器语言程序求得计算结果。编译程序就是将高级语言程序翻译成机器语言程序或汇编

5、语言程序的工具。工作过程一般可以划分为五个阶段：词法分析、语法分析、语义分析和中间代码生成、优化、目标代码生成。前端包含词法分析、语法分析、语义分析和中间代码生成三个阶段，后端包含优化、目标代码生成两个阶段。词法分析的任务是对构成源程序的字符串进行分解和扫描，识别出一个个Token序列，并标上类别码以区分关键字、标识符、常数、变量、数组界符等。词法分析器用自动机实现，每读入一个字符，就进行状态转移，当转移到终止状态的时候一个Token就识别出来了。此外，词法分析还要进行常数处理、关键字和标识符的区分操作。语法分析在词法分析的基础上，根据语言的语法规则，确定整个输入串在语法上是否是正确的。分析方

6、法有递归下降子程序分析法、LL(1)分析法、LR(0)分析法、简单优先分析法等。在语义分析和中间代码生成这一过程中，对语法分析所识别的各类语法范畴，要分析其含义，并以四元式的形式产生中间代码。优化的任务在于对中间代码进行加工变换以产生出更为高效的目标代码，主要进行常数合并、公共子表达式节省、删除无用赋值、循环优化等操作。目标代码生成的任务是把中间代码变换成特定机器上的低级语言代码，这一步需要考虑硬件系统结构、机器指令以及寄存器个数等情况，将一中间代码程序段翻译成汇编语言或机器语言目标代码。此外，在这五个阶段当中，符号表的管理、错误处理要穿插在当中进行。本次课设将前端的三个阶段整合到一起，通过对

7、输入的源程序扫描一遍的方式实现，入口为语法分析，使用递归下降子程序分析法。将词法分析器作为语法分析的子程序，当语法分析需要用到Token时，调用词法分析器识别出一个Token串，同时在语法分析的过程中插入语义动作，每识别完一定的Token串就能生成四元式。在后端则直接根据四元式生成目标代码。符号表用于存储变量以及检查是否有重定义、未定义的变量。在错误处理中，一旦发现错误，就进行输出并立即停止编译过程。2 课程设计任务及要求2.1 设计任务定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；扩展包括逻辑运算表达式、If语句、While语句等）；扫描器设计实现；语法分析器设计

8、实现；中间代码设计；中间代码生成器设计实现；目标代码生成。2.2 设计要求1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问；6、提交课程设计报告。3 算法与数据结构3.1 算法的总体思想（流程）对给定的一段源程序，先进行前端分析。前端包括词法分析、语法分析、语义分析和中间代码

9、生成三个阶段，这三个阶段通过对输入的源程序扫描一遍的方式即可实现，词法分析器作为语法分析的子程序，当语法分析需要用到Token时，调用词法分析器识别出一个Token串，同时在语法分析的过程中插入语义动作，在进行语法分析的同时也能生成四元式。然后将生成的四元式交给后端进行目标代码生成。此外，符号表用来记录源程序中出现的变量，如果在分析的过程中出现错误，则进行错误处理，将哪一行出现的哪种错误输出。具体流程图如下：源程序前端（词法分析、语法分析、语义分析和中间代码生成）后端（目标代码生成）中间代码目标代码符号表管理错误处理3.2 词法分析模块3.2.1 功能识别器：词法分析器中识别器的具体功能为识别

10、单词的有限自动机。单词符号是一个程序语言的基本语法符号。程序语言的单词符号一般可分为下列4种。（1）关键字：由程序语言定义的具有固定亿的标识符。有时称这些标识符为保留字或基本字。（2）标识符：标示各种名字，如变量名，数组名，函数名等。 （3）常数：程序中出现用来运算的数值，即以自身形态面对用户和系统。（4）界符：单字符界符：+,*,/,！,%等。双字符界符：>=,<=,=,!=,&&,|等。翻译器：根据有限自动机所识别出的对象，完成从单词传到单词的TOKEN串的翻译。输入源程序，对构成源程序的字符串进行分解和扫描，识别出一个个的单词或符号。具体实现为设计各单词的状态

11、转换图，并为不同的单词设计种别码。3.2.2 数据结构识别器关键字或标识符以字母开头，数值型常量以字母开头，字符型常量或字符串常量以或”开头，其它的多以自身形态识别之。如何识别单词并寻找其可达状态，我们的方法是利用链表构建一个识别单词的有限自动机。定义自动机状态的结构体链表：typedef struct statechar acceptkey;int nextstate;struct state *next;state;/自动机状态链表结点构建链表结点：typedef struct tokennode token to; struct tokennode *next;tokennode;自动机

12、图：1230313234668791011121314151617282930212223242526272829llll|ddddd.“>>=<<=!&|&小数整数指数字符字符串>=>><=<<=!=&&|其余翻译器共用体：union extramessage double num;/常数 int subscript;/数组下标;Token结构体：typedef struct tokenchar s20;int code;extramessage extra;token;/token结构体char s

13、tore20；token KT15；token PT25；state *st33一个程序语言的关键字，运算符和界符都是确定的，一般只有几十个或上百个。而对于标识符或常数的使用都不加限制。词法分析器所输出的单词符号常常表示为二元式结构：（单词种别，单词符号的属性值）；相应的数据结构处理为：TokenKT15="void",4,"char",5,"short",6,"int",7,"longlong",8,"float",9,"double",10,"

14、;bool",11,"if",12,"else",13,"while",14,"do",15,"for",16,"main",17,"return",18;/关键字表TokenPT25=">=",19,"<=",20,"=",21,"!=",22,">",23,"<",24,"=",2

15、5,"&&",26,"|",27,"!",28,"+",29,"",30,"*",31,"/",32,"%",33,"<<",34,">>",35,",",36,"",37,"(",38,")",39,"",40,"",41,"&

16、quot;,42,"",43"数组",44;/界符表还有对常数的处理和数组的单独处理（编号和属性的区分）。3.2.3 算法：数组处理：先查找字符找到数组的左括号，将其赋值为“0”，然后再找到右括号，将数组标号的值计算出来。+dd-ddddd.e+|-整数小数e指数e常数处理：词法分析的算法流程图：开始结束调用识别器关键字/标识符算术常数结束符#查KT表查到查填IT表查填CT表常数处理C.TOKEN查PT表P.TOKENI.TOKENK.TOKENyn查到ere:非法界符ynyynnny3.3 语法分析模块3.3.1 功能语法分析是编译的第二阶段，其任务是

17、识别和处理比单词更大的语法单位，如：程序设计语言中的表达式、各种说明和语句乃至全部源程序，指出其中的语法错误；必要时，可生成内部形式，便于下一阶段处理。另一方面语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位也是非常重要。语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按照文法的产生式，识别输入符号串是否为一个句子。  按照语法分析树的建立方法，可以粗略的把语法分析方法分成两类，一类是自上而下的分析方法，另一类是自下而上的分析方法。在本次的课程设计中我们组使用的是

18、自上而下的分析方法中的递归下降分析法，用这种分析法的好处是，直观易懂，便于表示做递归和因子提取，对文法的要求比较低，可以通过文法变换的方法将其转换为递归下降的方式。通过递归下降的方法将文法翻译成语法制导的形式，将接收到的token串进行扫描分析。本次试验我们其中一大亮点就是编译前端在语法分析的基础上进行一遍扫描，完成词法分析，语法分析，符号表填充以及中间代码的生成。这样要求在语法分析时每次接收一个token串(结构体)，这样在进行语法分析的时候将符号表语义动作和四元式生成的语义动作嵌入到其中便可以达到目的。同时我们本次实验一个很大的亮点就是我们对数组进行了识别以及各种运算操作，支持数组声明，赋

19、值，数组元素的计算等等。同时在语法中出现的错误会报告出来，并终止程序的运行。例如缺少分号，大括号，小括号等等。3.3.2 数据结构在词法分析中已经定义的token结构体typedef struct tokenchar s20;int code;extramessage extra;token;/token结构体对于语法分析过程而言，其处理的数据是来自于Token序列，是词法分析的产物。语法分析的任务就是识别和处理比单词更大的语法单位，比如：程序设计语言中的表达式、各种说明和语句乃至全部程序。主要是通过子程序的递归调用完成语法分析，没有过多的结构体。以下是我们本次实验的文法：iT标识符：00cT

20、字符：01sT字符串：02CT常数：03KT关键字：void 04,char 05,short 06,int 07,long long 08,float 09,double 10,bool 11,if 12,else 13,while 14,do 15,for 16,main 17,return 18PT界符：>= 19,<= 20,= 21,!= 22,> 23,< 24,= 25,&& 26,| 27,! 28,+ 29,- 30,* 31,/ 32,% 33,<< 34,>> 35, 36,; 37,( 38,) 39, 4

21、0, 41, 42, 431 语言的文法产生式集合·程序定义<程序> à <类型> <标识符> ( ) <复合语句> /只有主函数·语句定义<复合语句> à <语句表> <语句表> à <语句> <语句表> | <语句> à <变量说明语句> | <赋值语句> | <条件语句> | <while语句><变量说明语句> à <类型> &l

22、t;标识符表>；<标识符表> à <变量> <后继标识符><后继标识符> à ，<变量><后继标识符> | <变量> à <标识符> | <标识符> = <算术表达式> | <标识符> = <字符> |<标识符> = <字符串> <赋值语句> à <标识符> = <算术表达式>； | <标识符> = <字符>； |<标

23、识符> = <字符串>；<条件语句> à if（<逻辑语句>）<复合语句> | if（<逻辑语句>）<复合语句> else <复合语句> <while语句>àwhile (<逻辑语句>) <复合语句>·逻辑语句定义<逻辑语句> à <逻辑语句> | <逻辑项> | <逻辑项> <逻辑项> à <逻辑项> && <逻辑因子>

24、 | <逻辑因子> <逻辑因子> à <逻辑因子> 1 <逻辑因子2> | <逻辑因子2> <逻辑因子2> à <逻辑因子2> 2 <算术表达式> | <算术表达式> ·算术表达式定义<算术表达式> à <算术表达式> 0 <项> | <项> <项> à <项> 1 <因子> | <因子> <因子> à <单元>

25、; | 2 <单元><单元> à <算术量> | ( <逻辑语句> )<算术量> à <标识符> | <常数> ·类型定义<类型> à int | double | char | ·单词集定义<标识符> à <字母> | <标识符> <数字> | <标识符> <字母><常数> à <数> e <数><数> 

26、24; <整数> | <实数><整数> à <数字> | <整数> <数字><实数> à <整数> . <整数> ·字符集定义<字母> à A|B|C|Z|a|b|c|z<数字> à 0|1|2|3|4|5|6|7|8|9 其中：0 +或- 1 *或/或% 2 单目运算符 1 =或!= 2 >=或>或<=或<对文法进行修改：Programàtype identifier()Comp

27、oundStatementCompoundstatementàStateTableStatetableàStatement StateTable|Statementà说明|赋值|条件|循环说明àtype IdentifyTable;IdentifyTableàVariate NextStatementNextStatementà,Variate NextStatementVariateàidentifier AAà=Expression|=字符|=字符串|赋值àidentifier=CCàExp

28、ression；|字符；|字符串；条件àif(LogicStatement) CompoundStatement BBàelse CompoundState|循环àwhile(LogicStatement) CompoundStatement逻辑:LogicStatementà LogicItem| LogicItemLogicItemà LogicFactor1&& LogicFactor1LogicFactor1à LogicFactor2 LogicFactor2LogicFactor2à Expres

29、sion Expression算术:ExpressionàTTTàYYYàF|FFàArithmetic|(LogicStatement)Arithmeticàidentifier|const3.3.3算法下面便是本次递归下降子程序的程序框图（包含语义动作）：主程序开 始-1NEXT(W)Program结 束NError0Program 语法入口入 口typeNEXT(W)出 口identifier(NEXT(W)NEXT(W)CompoundStatementError1Error1Error1NNNNError1入口NEXT(W)State

30、mentTable出 口NError1CompoundStatement 复合语句StatementTable 语句表入 口StatementStatementTable出 口NYNEXT(W)Statement语句入 口出 口NEXT(W)W)typeIdentifyTableIdentifieror arrayPUSH(i);NEXT(W)NEXT(W)W)=NEXT(W)C GEQ(=)IfWhileCompoundStatementW)NEXT(W)W)(LogicStatementLogicStatementW)NEXT(W)W)NEXT(W)W)CompoundStatementN

31、EXT(W)BW)NNNNNNNNNNError1Error2Error2Error2Error2Error2Error2IdentifyTable标识符表Variate变量入 口NEXT(W)VariateVariate，出 口N入 口Identifier or arrayPUSH(i)NEXT(W)出 口ANError1A子程序，声明语句分支入 口 =Next(w)出 口PUSH(i)字符NEXT(W)GEQ(=)字符串PUSH(i)GEQ(=)ExpressionGEQ(=)POP(i)NNC子程序，赋值语句分支入 口出 口PUSH(i)字符NEXT(W)字符串PUSH(i)Expres

32、sion；NEXT(W)NNNLogicStatement 逻辑语句B子程序 条件语句分支入 口elseNEXT(W)Compundstater出 口N入 口NEXT(W)LogicItemLogicItem| GEQ(|)出 口NLogicItem 逻辑项入 口NEXT(W)LogicFactor1LogicFactor1&& GEQ(&&)出 口NLogicFactor1 逻辑因子1入 口NEXT(W)LogicFactor2LogicFactor2= GEQ(=)出 口!=NEXT(W)LogicFactor2 GEQ(!=)NNLogicFactor2

33、逻辑因子2入 口NEXT(W)ExpressionExpression>= GEQ(>=)出 口N>NEXT(W)Expression GEQ(>)<=<NEXT(W)Expression GEQ(<=)NEXT(W)Expression GEQ(<)NNNNExpression 表达式入 口NEXT(W)TT+ GEQ(+)出 口-NEXT(W)T GEQ(-)NNT 算数项入 口NEXT(W)YY* GEQ(*)出 口N/NEXT(W)Y GEQ(/)%NEXT(W)Y GEQ(%)NNN入 口NEXT(W)F+ GEQ(+) FN-NEXT

34、(W)F GEQ(-)!NEXT(W)F GEQ(!) 出 口Y 算数因子NNN入 口PUSH(i)Identifier or const出口（NEXT(W)LogicStatement)NEXT(W)NNNError1Error2F 算数单元3.4 语义分析和中间代码生成模块3.4.1 功能中间代码是高级程序语言中，各种语法成分的语义结构表示；它介于源语言和目标语言之间。中间代码设置的目的是便于编译的后期处理（如优化和目标生成）。在我看来，中间代码即四元式的生成其实是为后期的一个准备过程，这样做的好处是：便于进行与机器无关的代码优化工作；使编译程序改变目标机更容易；使编译程序的结构在逻辑上更

35、为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。下面我来介绍一下四元式生成的过程：首先我们要先定义一个语义栈 SEMi,在语法分析扫描的过程中，我们要将接收的终结符压入栈中（PUSH(i) 压栈函数(把当前 i 压入语义栈)），这样每当读到一个语义动作的时候我们就可以执行语义动作（GEQ（i），将栈顶和次栈顶元素弹出，生成四元式。不同的语句的四元式结构不同，在此我将四元式进行分类：（1） 双目运算符（2） 单目运算符（3） 赋值运算符（4） 条件语句（5） 循环语句（6） 数组 在四元式生成过程中要注意栈顶与次栈顶的出栈顺序，分清主操作数和次操作数，我认为合适插入语义动作以及语义动作

36、的调用也要选择恰当时机。3.4.2 数据结构定义语义栈，链式栈typedef struct tokenstack tokennode *base; tokennode *top; SqStack;定义四元式域结构体 struct FourFactor token Factor; bool active; ;定义四元式结构体链表 typedef struct FourItem char operators20; FourFactor Factor3; struct FourItem *next; FourItem;/四元式结构体链表在中间代码生成过程中，考虑到四元式的数量不确定，我们通过结构体链

37、表作为主要的数据结构来存储生成的四元式，同时套用结构体来对四元式的4个域进行分定义：token类型和bool类型。Bool类型为了后期的目标代码生成做准备。定义的链式栈也是担心空间不够用。同时我们组对临时变量的处理也是恰到好处：token Token1; Token1.s0='t' tot+; int now=tot; int len; for(len=1;now;len+) Token1.slen=now%10+'0' now=now/10; for(int i=1;i<=len/2;i+) char tmp=Token1.si; Token1.si=T

38、oken1.slen-i; Token1.slen-i=tmp; Token1.slen='$'Token1.slen+1='0'通过一个字符数组来对要生成的临时变量t进行标号，从t1开始，由于我们的栈操作都是token类型，所以临时变量也定义成token类型，解决了类型问题。3.4.3算法：四元式的流程图在语法分析中也涵盖了，下面我来分模块来列举一下语义动作的插入，不一一介绍了。四元式生成流程图：开 始语法分析扫描判断是否为语义动作？终结符入栈将语义栈顶和次栈顶弹栈处理生成四元式结 束双目算术运算符：+，-，*，/,%入 口NEXT(W)TT+ GEQ(+)出

39、 口-NEXT(W)T GEQ(-)NN单目运算符：正，负，非入 口NEXT(W)F+ GEQ(+) FN-NEXT(W)F GEQ(-)!NEXT(W)F GEQ(!) 出 口NNN双目逻辑运算符：>=,>,<=,<,=,!=,|,&&入 口NEXT(W)ExpressionExpression>= GEQ(>=)出 口N>NEXT(W)Expression GEQ(>)<=<NEXT(W)Expression GEQ(<=)NEXT(W)Expression GEQ(<)NNNN赋值语句：入 口出 口I

40、dentifieror arrayPUSH(i)NEXT(W)W)W)=NEXT(W)W)C GEQ(=)NError2条件语句（if, else,ifend）If(LogicStatement)NEXT(W)W)CompoundStatementNEXT(W)W)GEQ(IE)W)GEQ(IF)W)BW)出 口入 口Error2Error2NN入 口elseNEXT(W)Compundstater出 口NGEQ(EL)循环语句（while,do,while end）出 口WhileCompoundStatementW)NEXT(W)W)(LogicStatementW)NEXT(W)W)NN

41、NError1Error2Error2GEQ(WH）W)GEQ(DO)GEQ(WE)W)入 口3.5 符号表模块3.5.1功能在编译的各个分析阶段，每遇到一个名字都要查找符号表。如果发现一个新的名字或者发现已有信息名字，则要修改符号表，填入新的名字和信息。符号表所登记的信息在编译不同阶段要用到。例如在语义分析中，符号表所登记的内容将用于语义检查和产生中间代码。在目标代码生成阶段，当对符号名进行地址分配时，符号表是地址分配的依据。对于一个多遍扫描的编译程序，不同遍所用的符号表也往往不同。3.5.2数据结构所用的数据结构为嵌套的结构体链表，是一个复合表。共有三个表：表，类型表，数组表。其中主表存有

42、name（标识符名字），type（指向类型表相应项的指针），cat（种类），add（地址），active（活跃状态）。类型表tval(类型代码)，tpoint（如果数据类型为数组型，则指向数组表的指针）。数组表有low（下界），up（上界），ctp（数组成分类型），clen（数组长度）。具体如下：typedefstructint low;int up;intctp;intclen;bool *active;Array; /数组表typedefstructinttval; Array *tpoint;Tapel;/类型表typedefstruct Symbolchar name20;Tapel

43、*type;int kind;bool active;intaddr; Symbol *next;Symbol,*Sym; /主表3.5.3 算法结构体链表采用尾插法建立，即设立头尾节点，将新的节点插入尾结点处。当初始化变量时，先从头节点开始扫描，如果表中有相同名字项，则报错，同时停止编译（重定义），如果没有，插入新的节点，将新的变量的类型，种类，地址写入符号表。当查找时，同样从头扫描符号表，如果有重复项则表明已定义且正确。如果没查到则报错（未定义）且终止编译。如果查到的项的类型与参数的不相符，报错（类型不匹配）且终止编译。在生成四元式过程中，为临时变量建立了一个小符号表，每当生成一个临时变量

44、时就将其存入该表。与主表不同的是，小符号表只存有临时变量的名字与类型以及活跃信息active，小符号表为一个单表。小符号表的数据结构也是结构体链表，构造方法同样为尾插法。typedefstruct Temporarychar name20;int type;struct Temporary *next;bool active;Temporary; /临时变量表3.6 目标代码生成模块3.6.1 功能目标代码生成是编译程序的最后一个阶段，它以中间代码作为输入，以与中间代码功能相同的目标代码作为输出。一般来说，生成的目标代码要么是能立即执行的机器语言代码，要么是汇编语言代码，还需经过汇编程序汇编才

45、能执行。在进行代码生成时，不经要考虑如何使生成的代码尽量短，还要考虑如何更多地利用寄存器，使目标代码执行的时间更短。本课设生成的目标代码为汇编语言代码，但不针对特定的模型机。3.6.2 数据结构在这一模块用到的数据结构有汇编指令链表和汇编指令标号栈，它们的定义如下：typedef struct assembly_instruction int id;/标号 char operation5;/操作指令 char dest5;/第一操作数 char res5;/第二操作数 int destid;/跳转到的汇编指令标号（针对跳转指令） struct assembly_instruction *nex

46、t;/该结点指向的下一个结点assembly_instruction;/汇编指令链表结点typedef struct idstacknode int id;/标号 struct idstacknode *next;/该结点指向的下一个结点idstacknode;/汇编指令标号栈结点typedef struct idstack idstacknode *base;/栈底 idstacknode *top;/栈顶idstack;/汇编指令标号栈3.6.3 算法该模块执行过程如下：先对四元式划分基本块，然后目标代码以基本块为单位生成。对于每个基本块，先初始化变量的活跃信息，然后逆序对每个四元式内涉及

47、的变量的活跃信息更新，再依次取出每条四元式进行汇编代码生成，同时更新当前寄存器由哪个变量占用，当一个基本块结束时，要释放寄存器的内容。最后还要编一条结束指令。具体流程图如下：开始划分基本块取下一基本块存在下一基本块？否生成结束指令结束是初始化变量活跃信息逆序更新四元式中变量活跃信息取下一四元式生成汇编指令到达基本块出口？否是释放寄存器更新寄存器当前占用变量4 程序设计与实现4.1 程序流程图程序总体流程图如下：开始前端（词法分析、语法分析、语义分析和中间代码生成）有错误？是输出错误信息否后端（目标代码生成）结束4.2 程序说明词法分析：void init()；创建链表int changesta

48、te(int nowstate,char ch)；状态转换int state_to_code(int laststate)；判别函数void getnum(token &to)；常数处理void getnameandsubscript(token &to)；数组处理token parse(int code,char* store)；token配对token get()；扫描函数语法分析：void Program();语法分析void CompoundStatement();复合语句子程序void StatementTable();语句表子程序void Statement();语

49、句子程序void IdentifyTable();标识符表子程序void Variate();变量子程序void LogicStatement();逻辑语句子程序void LogicItem();逻辑项子程序void LogicFactor1();逻辑因子1子程序void LogicFactor2();逻辑因子2子程序void Expression();表达式子程序void A();声明子程序void B();条件语句else子程序void C();赋值子程序void T();算术项子程序void Y();算术因子子程序void F();算术单元子程序void error1();错误处理1void error2();错误处理2void GoNext();取当前token中间代码生成：void GEQ_double(char symbol);双目运算符四元式void GEQ_single(char symbol);单目运算符四元式void GEQ_assign(char symbol);赋值运算四元式void IF();条