编译原理实验指导书

PAGEPAGE11目录TOC\o"1-3"\h\z相关问题说明 1实验题 2实验1词法分析（2课时） 3实验2语法分析（2课时） 5实验3语义分析（2课时） 7实验4代码生成（2课时） 9参考书目 11相关问题说明本课程共有4个实验，本课程中所实现的程序为普通C或C++程序，在Windows环境下，属于控制台应用程序。提交实验成果：1.实验成果包括：源程序。用学号加姓名方式命名项目或源程序所在目录，例如，学号：090510xxx，姓名：某某，目录名就是：090510xxx某某。只要源程序，不要编译后文件。实验报告。2.实验报告由班干部收齐后在实验后下一次上课时交给我（最后一个实验除外），源程序发我邮箱。实验成果评价标准：1.及时提交实验成果，过期再交，不计成绩。2.实验成果和他人雷同者，不计成绩。3.实验报告采用手写方式，书写格式按照计算机与信息工程系要求执行，不按要求办事的，不计成绩。4.实验成果不完整的，即缺源程序或实验报告者，不计成绩。5.实验报告内容充实，能够真实反映实验情况的，酌情加分。6.实验报告字迹工整的，酌情加分。7.存在其他加分的可能性。实验时间和地点：班级周次星期节次实验室网络工程0918,9,11,1225-6东8-413网络工程0928,9,11,1225-6东8-415实验题编译整数四则运算表达式，将整数四则运算表达式翻译为汇编语言代码。整数四则运算文法：<expr>::=<expr>+<term>|<expr>-<term>|<term> <term>::=<term>*<factor>|<term>/<factor>|<factor> <factor>::=(<expr>)|num消除左递归得 <expr>::=<term><expr-rest> <expr-rest>::=+<term><expr-rest>|-<term><expr-rest>|ε <term>::=<factor><term-rest> <term-rest>::=*<factor><term-rest>|/<factor><term-rest>|ε <factor>::=(<expr>)|num其中<expr>、<expr-rest>、<term>、<term-rest>和<factor>为非终结符，+、-、*、/、(、)、num为终结符。词法：运算符：+-*/界符：()num是非负整数。空白包括空格、换行符和水平制表符。用来分开运算符、界符和num。也可以不包括换行符，这时换行符就成为表达式的终结标志。实验1词法分析（2课时）实验目的：了解词法分析器的功能和输出形式，掌握词法分析器设计原理和方法。实验内容：设计并实现整数四则运算表达式的词法分析程序。实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。实验环境：VisualC++6.0或以上版本，Windows2000或以上版本，汇编工具（在Software子目录下）。实现要点与提示：需要实现的词法分析程序的功能是，接受一个表达式，输出该表达式中的各类单词符号。测试词法分析程序时，可以按照一定格式输出各类单词符号。单词符号的种类和所属类型可定义如下typedefenumSymbol{ERR=-1,END,NUM,PLUS,MINUS,TIMES,SLASH,LPAREN,RPAREN}Symbol;对运算符和界符只需处理种类编码即可，而对num需要处理其对应的具体属性信息。ERR表示词法分析错，END表示表达式分析结束。例如1+2*(3+4)所对应的单词符号序列为NUM:1+NUM:2*(NUM:3+NUM:4)词法分析函数的原型如下Symbolgettoken();实现的具体方法可参考文献[1]中44-46页。这里不涉及Reserve、InsertId和InsertConst。在实现过程中可能会用到isdigit、isspace、getchar、ungetc、atoi等函数，使用时注意包含相关头文件。状态转换图如下实验2语法分析（2课时）实验目的：理解自上而下分析法的基本思想，理解递归下降分析法的基本思路，掌握构造递归下降子程序的方法。实验内容：运用递归下降子程序法，实现整数四则运算表达式的语法分析程序。实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。实验环境：VisualC++6.0或以上版本，Windows2000或以上版本，汇编工具（在Software子目录下）。实现要点与提示：需要实现的语法分析程序的功能是，接受一个表达式，分析该表达式，并根据输入正确与否给出相应信息。测试时，如果输入的表达式分析正确，则输出表示分析正确的信息；否则，输出表示分析错误的信息。分析程序由一组递归过程组成，文法中每个非终结符对应一个过程。在分析过程中，语法分析程序需要调用实验1所实现的词法分析程序。几个全局过程和变量：ADVANCE，把输入串指示器IP指向下一个输入符号，即读入一个单字符号。SYM，IP当前所指的输入符号。ERROR，出错处理子程序。每个非终结符有对应的子程序的定义，在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。例：给定文法G(E)：E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|i对应的递归子程序为PROCEDUREE;BEGIN T;E'END;PROCEDUREE';IFSYM=‘+’THEN BEGIN ADVANCE;T;E'END;PROCEDURET;BEGINF;T'END;PROCEDURET';IFSYM=‘*’THENBEGINADVANCE;F;T'END;PROCEDUREF;IFSYM=‘i’THENADVANCEELSEIFSYM=‘(’THEN BEGINADVANCE;E；IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR;主程序为：PROGRAMPARSER;BEGINADVANCE; E; IFSYM<>’#’THENERROREND.或者对应的递归子程序为：PROCEDUREE;BEGIN T;E'END;PROCEDURET;BEGINF;T'END;PROCEDUREE';IFSYM=‘+’THEN BEGINADVANCE;T;E'ENDELSEIFSYM<>‘#’ANDSYM<>’)’THENERROR;PROCEDURET';IFSYM=‘*’THENBEGINADVANCE;F;TENDELSEIFSYM<>‘#’ANDSYM<>’)’ANDSYM<>’+’THENERROR;PROCEDUREF;IFSYM=‘i’THENADVANCE ELSEIFSYM=‘(’THENBEGINADVANCE;E;IFSYM=‘)’THENADVANCE ELSEERRORENDELSEERROR主程序为：PROGRAMPARSER;BEGINADVANCE;EEND;具体实现语法分析程序时，ADVANCE的功能由实验1中的gettoken实现。程序中可设置一个全局变量nexttoken，与SYM对应，保存调用gettoken时的返回结果。ERROR的一种简单实现是输出错误提示，然后调用exit，使程序立即终止执行。实现整数四则运算表达式的语法分析程序时，可在上面例子的基础上修改扩充。实验3语义分析（2课时）实验目的：理解属性文法，理解语法制导翻译的基本思想和方法。实验内容：设计并实现实现整数四则运算的递归下降翻译器。实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。实验环境：VisualC++6.0或以上版本，Windows2000或以上版本，汇编工具（在Software子目录下）。实现要点与提示：需要实现的语义分析程序的功能是，接受一个表达式，分析该表达式，并在分析的过程中建立该表达式的抽象语法树。由于四则运算表达式的抽象语法树可基本上看作是二叉树，因此中序遍历序列应该和输入的表达式一样——除了没有括号之外。可输出中序遍历序列检测程序功能是否正确。如果每个分支节点用一个临时变量标记，则对四则运算表达式的抽象语法树进行后序遍历，可以得到输入表达式所对应的四元式序列（实验4要用到这样的四元式序列）。例如输入1+2*(3+4)，对应的抽象语法树的中序遍历序列、四元式序列分别为1+2*3+4和+34T1*2T1T2+1T2T3抽象语法树的一种类型定义为typedefintValType;typedefstructASTNode{ Symbolsym; ValTypeval; structASTNode*arg1,*arg2;}ASTNode,*AST;创建节点的操作为ASTNode*mknode(Symbolop,ASTNode*arg1,ASTNode*arg2);返回新创建的一个运算节点，标号是op，域arg1和arg2分别指向一棵子树。ASTNode*mkleaf(Symbolsym,ValTypeval);返回新创建的一个数节点，标号为num，域val用于存放数的值。建立抽象语法树的语义规则为E::=E1+T E.nptr:=mknode(‘+’,E1.nptr,T.nptr)E::=E1–T E.nptr:=mknode(‘-’,E1.nptr,T.nptr)E::=T E.nptr:=T.nptrT::=T1*F T.nptr:=mknode(‘*’,T1.nptr,F.nptr)T::=T1/F T.nptr:=mknode(‘/’,T1.nptr,F.nptr)T::=F T.nptr:=F.nptrF::=(E) F.nptr:=E.nptrF::=num F.nptr:=mkleaf(num,num.val)消除左递归的翻译模式为E::= T {E'.i:=T.nptr}E' {E.nptr:=E'.s}E'::= +T {E'1.i:=mknode(‘+’,E'.i,T.nptr)}E'1 {E'.s:=E1.s}E'::= -T {E'1.i:=mknode(‘-’,E'.i,T.nptr)}E'1 {E'.s:=E1.s}E'::= ε {E'.s:=E'.i}T::= F {T'.i:=F.nptr}T' {T.nptr:=T'.s}T'::= *F {T'1.i:=mknode(‘*’,T'.i,F.nptr)}T'1 {T'.s:=T1.s}T'::= /F {T'1.i:=mknode(‘/’,T'.i,F.nptr)}T'1 {T'.s:=T1.s}T'::=ε {T'.s:=T'.i}F::=(E){F.nptr:=E.nptr}F::=num{F.nptr:=mkleaf(num,num.val)}递归下降翻译器的设计可参考文献[1]中156-158页。具体实现时，可以以实验2中所实现的语法分析程序为基础进行修改，实现表达式的递归下降翻译器。实验4代码生成（2课时）实验目的：理解代码生成过程中的基本问题。实验内容：设计并实现表达式的代码生成程序。实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。实验环境：VisualC++6.0或以上版本，Windows2000或以上版本，汇编工具（在Software子目录下）。实现要点与提示：需要代码生成程序的功能是，以实验3的语义分析程序的四元式输出作为输入，输出汇编语言程序。例如1+2*(3+4)对应的输出为.386.MODELFLATExitProcessPROTONEAR32stdcall,dwExitCode:DWORDINCLUDEio.h;headerfileforinput/outputcrEQU0dh;carriagereturncharacterLfEQU0ah;linefeed.STACK4096;reserve4096-bytestack.DATA;reservestoragefordatatDWORD40DUP(?)label1BYTEcr,Lf,"Theresultis"result BYTE11DUP(?)BYTEcr,Lf,0.CODE;startofmainprogramcode_start:moveax,3addeax,4movt+0,eaxmoveax,2movebx,t+0mulebxmovt+4,eaxmoveax,1addeax,t+4movt+8,eaxmoveax,t+8dtoaresult,eax;converttoASCIIcharactersoutputlabel1;outputlabelandsumINVOKEExitProcess,0;exitwithreturncode0PUBLIC_start;makeentrypointpublicEND;endofsourcecode输出的汇编代码借鉴了文献[2]中的格式。假定将上面的汇编程序保存到文expression.asm中，将expression.asm复