编译原理实验指导书.docx
编译原理实验指导书 目录相关问题说明1实验题2实验1词法分析（2课时）3实验2语法分析（2课时）5实验3语义分析（2课时）7实验4代码生成（2课时）9参考书目11相关问题说明本课程共有4个实验，本课程中所实现的程序为普通C或C+程序，在Windows环境下，属于控制台应用程序。 提交实验成果： 1.实验成果包括： n源程序。用学号加姓名方式命名项目或源程序所在目录，例如，学号：090510xxx，姓名：某某，目录名就是：090510xxx某某。只要源程序，不要编译后文件。 n实验报告。 2.实验报告由班干部收齐后在实验后下一次上课时交给我（最后一个实验除外），源程序发我邮箱。 实验成果评价标准： 1.及时提交实验成果，过期再交，不计成绩。 2.实验成果和他人雷同者，不计成绩。 3.实验报告采用手写方式，书写格式按照计算机与信息工程系要求执行，不按要求办事的，不计成绩。 4.实验成果不完整的，即缺源程序或实验报告者，不计成绩。 5.实验报告内容充实，能够真实反映实验情况的，酌情加分。 6.实验报告字迹工整的，酌情加分。 7.存在其他加分的可能性。 实验时间和地点： 班级周次星期节次实验室信管0517,9,11,13,1611-2东7-405软件工程0621411-2东7-405软件工程0711811-2东7-405计算机0627,9,11,12,14,16,1711-2东7-406信息管理0711811-2东7-406信息管理0611611-2东7-408信息管理0714,7,11,13,15,1711-2东7-408软件工程0619,1411-2东7-408信息管理0621611-2东7-412软件工程07111,12,13,14,1511-2东7-412软件工程062911-2东7-412计算机05113,14,15,1611-2东7-413物流管理0827,8,9,10,11,12,13,14,15,1611-2东8-405广告学0817,8,9,10,11,12,13,14,15,1611-2东8-409信息管理05113,14,15,16,17,1813-4东7-405计算机05213,14,15,1613-4东7-406信管06111,12,17,1813-4东7-406网络工程0918,9,11,1225-6东8-413信管0527,9,11,13,1613-4东7-412信管0611513-4东7-412计科0514,6,8,10,12,14,16,1813-4东7-413计算机应用0811713-4东7-413艺术设计0841413-4东8-405计算机应用0814,5,6,7,8,9,10,11,12,13,14,15,1613-4东8-409信息与计算科学06111,12,13,141中午东7-405软件工程0818,9,10,11,12,13,14,151中午东7-406软件工程0619,10,11,12,13,141中午东7-408软件工程0629,10,11,12,13,141中午东7-412软件工程07113,14,15,161中午东7-413计算机0637,9,11,12,14,16,171中午东8-405计算机应用0824,5,6,7,8,9,10,11,12,13,14,15,16,171中午东8-409艺术设计08413,1515-6东7-405计算机06110,12,14,1615-7东7-405电信科学0827,8,9,10,11,12,13,14,15,1615-6东7-406计算机05313,14,15,1615-6东7-408艺术设计0847,8,9,10,11,1215-6东7-408信息与计算0818,9,10,11,12,13,14,1515-6东7-412艺术设计0841615-6东7-412信息管理05213,14,15,16,17,1815-6东7-413艺术设计0817,8,9,10,11,12,13,14,15,1615-6东8-405国际贸易0817,8,9,10,11,12,13,14,15,1615-6东8-409信管06211,12,15,17,1817-8东7-406电信科学08113,1417-8东7-406电信科学08115,1617-8东7-408信息与计算科学06211,12,13,1417-8东7-408艺术设计0837,8,9,10,11,12,13,14,15,1617-8东7-412软件工程07213,14,15,1617-8东7-413电信科学0817,8,9,10,11,1217-8东7-413艺术设计0827,8,9,10,11,12,13,14,15,1617-8东8-405金融学0817,8,9,10,11,12,13,14,15,1617-8东8-409信管0511821-2东7-405计算机应用0811721-2东7-408计算机应用0815,6,7,8,9,10,11,12,13,14,15,1621-2东7-412计科0524,6,8,10,12,14,16,1821-2东7-413计算机05114,1521-2东8-405计算机科学0818,9,10,11,12,13,14,1521-2东8-409计算机应用0825,6,7,8,9,10,11,12,13,14,15,16,1723-4东7-405计算机0611723-4东7-406网络工程0818,9,10,11,12,13,14,1523-4东7-406软件工程06114,15,1623-4东7-408计科0511723-4东7-408计科05114,15,1623-4东7-412计科0518,9,11,12,1323-4东7-413计算机05214,1523-4东7-413计算机0617,9,11,12,14,1623-4东8-405计科(成)6,8,10,12,1423-4东8-409信管052182中午东7-405软件工程06214,15,162中午东7-412信管0515,6,8,10,12,13,14,15,1625-6东7-405信息管理0618,9,10,11,12,13,14,1525-6东7-406软件工程0721825-6东7-406软件工程07211,12,13,14,1525-6东7-408信管0511725-6东7-413计科0528,9,11,12,1325-6东7-413信息管理0828,9,10,11,12,13,14,1525-6东8-405管理类08077,8,9,10,11,12,13,14,15,1625-6东8-409信管0525,6,8,10,12,13,14,15,1627-8东7-405信息管理0628,9,10,11,12,13,14,1527-8东7-406信管0521727-8东7-413计科0538,9,11,12,1327-8东7-413电气类08068,9,10,11,12,13,14,1527-8东8-405艺术设计0867,8,9,10,11,12,13,14,15,1627-8东8-409公选6,7,8,9,10,11,1229-11东7-408/12信息管理0518,9,14,15,1631-2东7-405信息管理06111,1631-2东7-408软件工程0616,9,13,1431-2东7-408信息管理06211,1631-2东7-412软件工程0626,9,13,1431-2东7-412计科0534,6,8,10,12,14,16,1831-2东7-413广告0513,731-2东7-413广告学0827,8,9,10,11,12,13,14,15,1631-2东8-409信管05210,11,13,16,1833-4东7-405计算机0711833-4东7-406计算机07111,12,13,14,1533-4东7-408计科0521733-4东7-408计科05214,15,1633-4东7-412广告0523,733-4东7-413信息管理0721733-4东7-413计算机05314,1533-4东8-405信息管理07115,16,173中午东7-405信管051183中午东7-405汉语言0615,7,11,13,153中午东7-406网络工程07111,12,13,14,15,183中午东7-408计算机06310,11,12,13,143中午东7-409计算机06113,15,173中午东7-412计算机06315,16,173中午东7-413软件工程0614,6,8,10,12,14,15,163中午东8-405软件工程0828,9,10,11,12,13,14,153中午东8-409信管05110,11,13,1635-6东7-405行政管理0715,7,11,13,1535-6东7-406信息管理0527,835-6东7-413行政管理06110,11,12,1335-7东7-413信息管理07215,16,1735-7东7-413电气类08078,9,10,11,12,13,14,1535-6东8-405行政管理0817,8,9,10,11,12,13,14,15,1635-6东8-409计算机0621736-8东7-408计算机06213,1536-8东7-412汉语言0625,7,11,13,1537-8东7-406软件工程0624,6,8,10,12,14,15,1637-8东7-408信息管理0527,8,937-8东7-413行政管理06210,11,12,1338-10东7-413校公选7,8,9,10,11,1239-11东7-408/12计算机06313,15,1739-11东7-412软件工程0616,7,8,9,10,11,12,1341-2东7-405信息管理07217,1841-2东7-405计算机06110,11,12,13,1441-2东7-409信息管理0724,7,11,13,1541-2东7-412计算机06115,16,1741-2东7-413信息管理0818,9,10,11,12,13,14,1541-2东8-405电气类0838,9,10,11,12,13,14,1541-2东8-409网络工程0928,9,11,1225-6东8-415实验题编译整数四则运算表达式，将整数四则运算表达式翻译为汇编语言代码。 整数四则运算文法： :=+|-|:=*|/|:=()|num消除左递归得:=:=+|-|:=:=*|/|:=()|num其中、和为非终结符，+、-、*、/、(、)、num为终结符。 词法： 1运算符：+-*/2界符：()3num是非负整数。 4空白包括空格、换行符和水平制表符。用来分开运算符、界符和num。也可以不包括换行符，这时换行符就成为表达式的终结标志。 实验1词法分析（2课时）实验目的：了解词法分析器的功能和输出形式，掌握词法分析器设计原理和方法。 实验内容：设计并实现整数四则运算表达式的词法分析程序。 实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。 实验环境：VisualC+6.0或以上版本，Windows2021或以上版本，汇编工具（在Software子目录下）。 实现要点与提示： 需要实现的词法分析程序的功能是，接受一个表达式，输出该表达式中的各类单词符号。测试词法分析程序时，可以按照一定格式输出各类单词符号。 单词符号的种类和所属类型可定义如下typedefenumSymbolERR=-1,END,NUM,PLUS,MINUS,TIMES,SLASH,LPAREN,RPARENSymbol;对运算符和界符只需处理种类编码即可，而对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或以上版本，Windows2021或以上版本，汇编工具（在Software子目录下）。 实现要点与提示： 需要实现的语法分析程序的功能是，接受一个表达式，分析该表达式，并根据输入正确与否给出相应信息。测试时，如果输入的表达式分析正确，则输出表示分析正确的信息； 否则，输出表示分析错误的信息。 分析程序由一组递归过程组成，文法中每个非终结符对应一个过程。在分析过程中，语法分析程序需要调用实验1所实现的词法分析程序。 几个全局过程和变量： xxxx，把输入串指示器IP指向下一个输入符号，即读入一个单字符号。 SYM，IP当前所指的输入符号。 ERROR，出错处理子程序。 每个非终结符有对应的子程序的定义，在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。 例：给定文法G(E)： ETEE+TE|TFTT*FT|F(E)|i对应的递归子程序为xxxxREE;BEGINT;EEND;xxxxREE;IFSYM=+THENBEGINxxxx;T;EEND;xxxxRET;BEGINF;T¢END;xxxxRET;IFSYM=*THENBEGINxxxx;F;T¢END;xxxxREF;IFSYM=iTHENxxxxELSEIFSYM=(THENBEGINxxxx;E； IFSYM=)THENxxxxELSEERRORENDELSEERROR;主程序为： xxxxPARSER;BEGINxxxx;E;IFSYM#THENERROREND.或者对应的递归子程序为： xxxxREE;BEGINT;EEND;xxxxRET;BEGINF;TEND;xxxxREE;IFSYM=+THENBEGINxxxx;T;EENDELSEIFSYM#ANDSYM)THENERROR;xxxxRET;IFSYM=*THENBEGINxxxx;F;T¢ENDELSEIFSYM#ANDSYM)ANDSYM+THENERROR;xxxxREF;IFSYM=iTHENxxxxELSEIFSYM=(THENBEGINxxxx;E;IFSYM=)THENxxxxELSEERRORENDELSEERROR主程序为： xxxxPARSER;BEGINxxxx;EEND;具体实现语法分析程序时，xxxx的功能由实验1中的gettoken实现。程序中可设置一个全局变量nexttoken，与SYM对应，保存调用gettoken时的返回结果。ERROR的一种简单实现是输出错误提示，然后调用exit，使程序立即终止执行。 实现整数四则运算表达式的语法分析程序时，可在上面例子的基础上修改扩充。 实验3语义分析（2课时）实验目的：理解属性文法，理解语法制导翻译的基本思想和方法。 实验内容：设计并实现实现整数四则运算的递归下降翻译器。 实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。 实验环境：VisualC+6.0或以上版本，Windows2021或以上版本，汇编工具（在Software子目录下）。 实现要点与提示： 需要实现的语义分析程序的功能是，接受一个表达式，分析该表达式，并在分析的过程中建立该表达式的抽象语法树。由于四则运算表达式的抽象语法树可基本上看作是二叉树，因此中序遍历序列应该和输入的表达式一样除了没有括号之外。可输出中序遍历序列检测程序功能是否正确。如果每个分支节点用一个临时变量标记，则对四则运算表达式的抽象语法树进行后序遍历，可以得到输入表达式所对应的四元式序列（实验4要用到这样的四元式序列）。例如输入1+2*(3+4)，对应的抽象语法树的中序遍历序列、四元式序列分别为1+2*3+4和+34T1*2T1T2+1T2T3抽象语法树的一种类型定义为typedefintValType;typedefstructASTNodeSymbolsym;ValTypeval;structASTNode*arg1,*arg2;ASTNode,*AST;创建节点的操作为ASTNode*mknode(Symbolop,ASTNode*arg1,ASTNode*arg2);返回新创建的一个运算节点，标号是op，域arg1和arg2分别指向一棵子树。 ASTNode*mkleaf(Symbolsym,ValTypeval);返回新创建的一个数节点，标号为num，域val用于存放数的值。 建立抽象语法树的语义规则为E:=E1+TE.nptr:=mknode(+,E1.nptr,T.nptr)E:=E1TE.nptr:=mknode(-,E1.nptr,T.nptr)E:=TE.nptr:=T.nptrT:=T1*FT.nptr:=mknode(*,T1.nptr,F.nptr)T:=T1/FT.nptr:=mknode(/,T1.nptr,F.nptr)T:=FT.nptr:=F.nptrF:=(E)F.nptr:=E.nptrF:=numF.nptr:=mkleaf(num,num.val)消除左递归的翻译模式为E:=TE.i:=T.nptrEE.nptr:=E.sE:=+TE1.i:=mknode(+,E.i,T.nptr)E1E.s:=E1.sE:=-TE1.i:=mknode(-,E.i,T.nptr)E1E.s:=E1.sE:=E.s:=E.iT:=FT.i:=F.nptrTT.nptr:=T.sT:=*FT1.i:=mknode(*,T.i,F.nptr)T1T.s:=T1.sT:=/FT1.i:=mknode(/,T.i,F.nptr)T1T.s:=T1.sT:=T.s:=T.iF:=(E)F.nptr:=E.nptrF:=numF.nptr:=mkleaf(num,num.val)递归下降翻译器的设计可参考文献1中156-158页。具体实现时，可以以实验2中所实现的语法分析程序为基础进行修改，实现表达式的递归下降翻译器。 实验4代码生成（2课时）实验目的：理解代码生成过程中的基本问题。 实验内容：设计并实现表达式的代码生成程序。 实验要求：编写程序，上机调试和测试，纪录调试和测试情况，结合程序进行分析。 实验环境：VisualC+6.0或以上版本，Windows2021或以上版本，汇编工具（在Software子目录下）。 实现要点与提示： 需要代码生成程序的功能是，以实验3的语义分析程序的四元式输出作为输入，输出汇编语言程序。例如1+2*(3+4)对应的输出为.386.MODELFLATExitProcessPROTONEAR32stdcall,dwExitCode:DWORDxxxxio.h;headerfileforinput/outputcrEQU0dh;carriagereturncharacterLfEQU0ah;linefeed.STACK4096;reserve4096-bytestack.DATA;reservestoragefordatatDWORD40DUP(?)label1BYTEcr,Lf,“Theresultis“resultBYTE11DUP(?)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复制到汇编器所在目录。然后在命令提示符下，在汇编器所在目录依次执行ml/c/coffexpression.asmlink/debug/subsystem:console/entry:start/out:expression.exeexpression.objio.objkernel32.libexpression就会得到Theresultis15注意，上面link那一行应该连续输入。为方便起见，在汇编器所在目录下有一个批处理文件compile.bat。执行compileexpression可完成上面三步所能完成的任务。 所生成的汇编代码中tDWORD40DUP(?)定义了40个双字（占4字节大小），用作临时变量，可根据需要调整大小。更好的方法是在栈中分配临时变量。 生成代码时，只需考虑如何生成_start:和dtoaresult,eax之间的汇编码。开头到_start:部分和dtoaresult,eax到结尾部分的汇编码可以按所给的例子原样输出。 通过分析、对比1+2*(3+4)的四元式序列和汇编码的对应关系，考虑如何将四元式翻译为汇编码。需要特别注意寻址方式问题，乘法和除法的翻译。 所给汇编程序例子中各个成分的含义，可以参考文献2。目录中有文献2的英文版电子书。 参考书目1陈火旺等.程序设计语言编译原理（第3版）.北京：国防工业出版社，2021.12RichardC.Detmer.80x86汇编语言与计算机体系结构（英文版）.北京：机械工业出版社，2021.11 9
