编译原理课程设计.docx

《编译原理课程设计.docx》由会员分享，可在线阅读，更多相关《编译原理课程设计.docx（25页珍藏版）》请在课桌文档上搜索。

1、课程设计报告设计题目：一个简洁文法的编译器前端的设计与实现班级：计算机1206组长学号：202239组长姓名：闫智宣指导老师：李晓华设计时间:2022年12月设计分工组长学号及姓名：20223974闫智宣分工：语法分析，四元式生成，目标代码优化及生成组员1学号及姓名：20223977廖峭分工：词法分析，错误处理组员2学号及姓名：20223959郭天龙分工：符号表生成，语义动作插入，操作界面编译原理课程设计是通过C语言编译器相关子系统的设计，进一步深入对编译器构造的理解；第一部分词法分析，设计各单词的状态转换图，并为不同的单词设计种别码，制作扫描器识别一个个单词，返回值为识别码的序号，返回TOk

2、en序列。将词法分析器设计成供语法分析器调用的子程序。词法分析器具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；其次部分，语法分析，用递归下降法，实现对表达式、各种说明语句、掌握语句进行语法分析。若语法正确，则用语法制导翻译法进行语义翻译；生成并打印出语法树；若语法错误，要求指出出错性质和出错位置（行号）。我们还做了附加功能，即编译后端，有中间代码优化，生成目标代码汇编语言。通过此次课程设计，提高了我们的独立分析问题、解决问题的力量，以及系统软件设计的力量；提高程序设计力量、程序调试力量，团结协作力量关键词：词法分析，语法分析，四元

3、式生成，错误处理，符号表生成，语义动作插入,中间代码优化，生成目标代码名目摘要1 .峻2 .课程设计任务及要求2.1 设计任务2.2 设计要求3 .算法及3.1 算法的总体思想（流程）3.2 词法分析模块3.2.1 功能3.2.2 数据结构3.2.3 算法33语法分析模块功能1.1.2 数据结构1.1.3 算法1.4 符号表模块1.4.1 功能1.4.2 数据结构1.4.3 算法1.5 四元式模块1.5.1 功能1.5.2 数据结构1.5.3 算法1.6 语义动作分析模块1.6.1 功能1.6.2 数据结构1.6.3 算法1.7 错误处理模块1.7.1 功能1.7.2 数据结构1.7.3 算法

4、1.8 目标代码模块1.8.1 功能1.8.2 数据结构1.8.3 算法4 .程序设计与实现4.1 程序流程图4.2 程序说明43试验结果5 .结论6 .会城。7 .收获、体会和建议。编译器是将C语言翻译为汇编语言代码的计算机程序。编译器将源程序(sourcelanguage)编写的程序作为输入，翻译产生目标语言(targetlanguage)机器代码的等价程序。通常地,源程序为高级语言(high-levellanguage),C语言程序,而目标则是机器语言的目标代码(ObjeCtCode),也就是可以在计算机硬件中运行的机器代码软件程序。这一过程可以表示为：源程序一编译器一目标机器代码程序2

5、 .课程设计任务及要求2.1 设计任务同学在学习编译原理课程过程中，结合各章节的构造编译程序的基本理论，要求用C#言描述及上机调试，实现一个C编译程序(包括词法分析，语法分析等重要子程序)，使同学将理论与实际应用结合起来，受到软件设计等开发过程的全面训练，从而提高同学软件开发的力量。2.2 设计要求要求:(1)设计词法分析器设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括：a.具备预处理功能。将不翻译的注释等符号先滤掉，只保留耍翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；b.能够拼出语言中的各个单词;C.返回（种别码，属性值，

6、行号）。（2）语法分析要求用学习过的自底向上或自顶向下的分析方法等，实现对表达式、各种说明语句、掌握语句进行语法分析。若语法正确，则用语法制导翻译法进行语义翻译；生成并打印出语法树；若语法错误，要求指出出错性质和出错位置（行号）。3 .算法及数据结构 .1算法的总体思想（流程）本节主要分析程序的代码结构和代码工程文件的划分。（程序由几个类组成：TOken类和Variable类SymbolTable类ObjectCode类LeXiCaI类Grammar类Four_Yuan类Action类ErrorItem类，分别为词法分析和语法分析类。工程分为几个文件：Forml.cs,Token,cs,Var

7、iable,cs,SymbolTable.cs,ObjectCode.cs,Lexical,cs,Grammar,cs,Four_Yuan,cs,Action,cs,ErrorItem,cs分别对应Token类和VariabIe类SymbolTable类ObjectCode类Lexical类Grammar类FourYuan类ACtion类ErrorItem类的声明和实现文件）。本程序采纳C#语言以面对对象的思想编写，程序分为几部分：词法分析（Lexical）,语法分析（Grammer）,目标代码生成（ObjectCode）oLeXiCaI类主要的工作是词法分析猎取TOkenOGrammer类的

8、主要工作是依据Lexical类词法分析之后的Token进行语法分析，生成语法树，最终并输出语法树。在处理过程中，Token类的对象作为Lexical类的一个成员变量，协作Grammer类进行语法分析。工程文件总体上是依据九个类的格局分为十个文件，分别是九个类的声明文件和实现文件。十个文件为Forml.cs,Token,cs,Variable,cs,SymbolTable.cs,ObjectCode.cs,Lexical,cs,Grammar,cs,FourYuan,cs,Action,cs,ErrorItem.cs,他们分别是Lexical类声明文件、Lexical类实现文件、GraInmer

9、类声明文件、Grammer类实现文件。H解决方案-CompHerF个项目）/回compilerProperties 引用cAction.cscErrorltemxs 国Form1.cs cFour_Yuan.csC*Grammar.es cLexical.escObjectCodexsDc，Program.esC*SymbolTable.es cTokenxsDc*Variable.es程序流程在程序中，Lexical类的对象(Token)作为Grammer类中的一个成员变量，协作Grammer类进行语法分析。它们的关系是这样的：Grammer类的一个成员变量temp首先对源程序删除注释，然后

10、进行词法分析猎取全部TOkCrb并将猎取的Tokerl存储在Tokerl对象的tokenList(List类型)中。然后Gramner类的语法分析程序就依据tokenList中的Token进行语法分析，生成语法树，最终打印语法树。同时，这也是程序的流程。3.2词法分析模块3.2.1功能1.exical类主要的工作是词法分析猎取Token序列。词法分析阶段的代码被封装成一个类Lexical,Token中主要是Lexical类的声明代码，Lexical.cs中主要是LeXiCal类的实现代码。LeXiCal类对外供应的函数主要有：staticpublicintRecogIcKstringstr,i

11、nti),static publicintRecogDig(stringstr,inti),staticpublicintRecogOperator(stringstr,inti),staticpublicintRecogBound(stringstr,inti),以上几个函数构成了词法分析的骨架，在LCXiCal类中还有其他成员变量和函数，主要作为这三个函数处理过程的中间步骤，为这三个函数服务。Lexical类的代码结构和主要的成员变量和函数及其含义如下图所示：staticpublicstringPrirrtTOkenLiSto/HmTOkerl序歹1|口i个引用staticpublicbo

12、ollsSign(charch)/识311下划绑口i个引用staticpublicintRecogld(stringstr,inti)/识别单词匚i个引用staticpublicintReCOgDig(StlingStLinti)识别数字匚i个引用staticpublicintRecogperator(stringstr,inti)/识操作符口i个引用staticpublicintRecogBound(stringstr,inti个引用staticpublicboollsBound(charch)/判断界符口个引用staticpublicboollsperator(charCh)判断操作符匚i

13、个引用staticpublicvoidGetString(stringstr)读入字符串口算法算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想是依据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。主程序示意图：主程序示意图如图3T所示。关键字表的初值。关键字作为特别标识符处理，把它们预先支配在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。（2）程序中需要用到的主要变量为type和number扫描子程序的算法思想：首先设置3个变量:token用来存放构成单词符号的字符串;number用

14、来整型单词；type用来存放单词符号的种别码。Token定义Token定义：classToken(publicintLineNo;publicstringName;publicstringType;)Token3!(TokenType)：publicstaticListTokenList=newList0；publicstaticListKeyword=newListauto,fdouble,int,struct1,break,elsen,long,switch,case,enum,register41,*typedef,char,extemfreturn,union,const,i,lflo

15、at,7short,funsigned,continue,lorj,signedn,l,void,defaultfgoto,f,sizeofi,Volatile,do,7if,while,7static;关键字staticListBound=newLiStVSt而gJ。,；*?，MTW,#N；/界符表staticUstOperator=newUst+,7,*-r,%,711r,!,7,=f=Mf=,f=f,*=,f,7=；33语法分析模块功能语法分析是编译过程的一个规律阶段。语法分析的功能是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序推断源

16、程序在结构上是否正确.源程序的结构由上下文无关文法描述.33.2城的下图为实现语法分析的类Grammar,属性与方法的作用都已说明na*espaceconpilerclassGranmarpublicstaticinttoken_no=0:BIII/判断是否为数据类型/paranname=strX/Paran1IIIEpublicstaticboolIsTypeCode(stringstr)/判断是否为药据类型HpublicstaticvoidParentheSiSNatChingO花名号坨g?文法!吾有英)?)j.publicstaticvoidVarlabIe0标浜苻或括号Q().publ

17、icstaticvoidLogiCo/逻辑表达式文法LOC工(publicstaticvoidCgpareO比较表达式文法F0.JSpublicstaticvoidRUlDiV()算术(束除)表达式支法申publicstaticvoidEXPre6sion()尊犷表谊式文法E()T7-EpublicstaticvoidComJIao逗号表达式31);OlpublicstaticvoidStatementBlock()/整体流程簿句；.publicstaticvoidStarto开始语法分析，处理的航f()匚7333算法1 .文法下面终结符与非终结符意义B程序开头Z数据类型，如inl,char,

18、fk)al等V标识符S晌P语句块E加减算术表达式D逗号表达式T乘除算术表达式C关系表达式1.规律表达式Q标识符或圆括号e表示空i表示标识符a)函数文法B-ZV()Sb)语句块文法P-SPeS-Pc)语句文法表达式语句文法S-V=Egoto语句文法S-T:SS-gotoiif语句文法S-iRE)SelseSwhile语句文法S-While(E)S声明语句文法S-ZVDD.,VD=EDed)表达式文法ETE+TE-TT-FTFlTFC-CCLOLC=CCbolTable(publicstringname:publicstringtype;publicstringcategory;publicstr

19、ingaddress:publicboolisactivity;publicstaticintsybol-i=0;publicstaticStacktypestack=newStaCkstring)。；/类型栈：声明时保存逗号表达式的变里类空publicstaticListSymList=newListbolTable();3个弓I用publicstaticboolGetIsActivity(stringna*e,booltep)查找符号裹返回活跃信息匚二I个引用publicstaticstringPrintSymList().1个引用publicstaticvoidDefault().5个引

20、用publicstaticvoidDealSymbol().1个引用publicstaticvoidUpdateList().1个引用publicstaticvoidAddList().1个引用staticboolSearchList().3.4.3算法35四元式模块3.5.1功能四元式为中间代码，编译程序进行完语义分析后，先生成中间代码作为过渡，此时中间代码与目标代码已经比较相像classFour_Yuan(publicstringop:四元式笫一个参数，操作苻publicVariableargl=nevVariableO.publicVariablearg2=ncvVariableO；pu

21、blicVariableresult=newVariable。：第四个暂数竺豹类皆为VarIaIbe保存W持名和基独活帙信息staticpublicinttenp=O;staticstringgetres()获16时笠里二publicstringgetResult()/方甲四五立法四彳至数匚7publicstringPrIntFOUrYUan()：,打目:篇1,四元式列字二二publicFourwYuai(stringop,stringargl,siringarc2,stringresult)打印四元式.JclassVariable(publicstringnae;publicboolisac

22、tivity;3.5.3算法3.6语义动作分析模块3.6.1 功能在语法分析中嵌入相应的语义动作，生成四元式3.6.2 数据结构-namespacecompiler98个引用三classAction(publicStatiCListFouryuanList=newList();publicstaticStackstack=newStaCkstring。：语义栈i个弓i用publicstaticstringPrintFouryuanList().7输出函数4个引用publicstaticvoidPush(stringi)./压核函数(把当前i压入语义校)1个引用publicstaticvoidW

23、OGEQoI.非运算运茸)2个弓I用publicstaticvoidASSlo匚Iy/喊值语句11个引用publicstaticvoidGEQ(stringOP)I.达式四元式生成函数1个引用publicstaticvoidGOTO(stringi).7got。语句动作1个引用publicstaticvoidLABER.标签语句动作1个引用publicstaticvoidIF()./Iif语句动作1个引用publicstaticvoidEL()./else语句动作1个引用publicstaticvoidIE()./ifend语句动作1个引用publicstaticvoidH()./WhiIe语

24、句动作1个弓I用二publicstaticvoidWE().fwhileend语句动作1个引用publicstaticvoidDO()./do语句动作3.6.3算法GEQ(+)(一)(*)()(+,il,i2,t)PUSH(i)ASSI(=)(=X_,POP)LABER(i)(lb,_,_,i)GOTO(i)(gt一i)IF(if)(if,a,_)EL(el)IE(ie)WH()(Wh,_,_QDoO(do,吐QWE(we)(we,_,_,J3.7 错误处理模块3.7.1 功能保存运行时发觉的错误，储存行号已经具体信息并输出。3.7.2 数据结构classErroritemintIineno;

25、stringcontent;publicstaticListErrorList=newList():25个引用publicstaticvoidAddErrorMessage(intIineno,stringcontent)vartemp=newErrorItem():temp,content=content;temp.Iineno=Iineno：ErrorList.Add(te三p);1个引用publicstaticstringPrintErrorListO(vartemp=行号详细信息rn:foreach(variteminErrorList)(temp+=ite.Iineno.ToStri

26、ng().PadLeft(4)+”+item,content+“rn;)if(ErrorList.Count=O)temp=编译成功，没有错误；returntemp;)3.7.3 算法publicstaticvoidAddErrorMessage(intIineno,stringContem)函数用作在发觉错误时保存错误信息以及行号。publicstaticstringPrintErrOrLiSt()把全部发觉的错误格式化后统一输出。错误信息在语法分析，语义分析，符号表检错中添加。3.8 目标代码模决3.8.1 功能目标代码生成把优化后的中间代码变换成目标代码,此处的目标代码为汇编代码，采纳单

27、寄存器生成目标代码3.8.29 结构classObjectCodeintadd;stringop;stringargl;stringarg2;publicstaticStacksen=newStack0：/程序栈publicstaticintpcount=0;staticstringrdl;单寄存器publicstaticListObjList=newLisKObjectCodeX);publicstaticintfouryuanlist_no=0;四元式索弓I1个引用publicstaticstringPrirrtobjLiSt()，/输出目标代码2个用publicstaticboolIsB

28、aseOp(stringOP)I./是否基本操作数1个引用publicstaticboolISArgEXange(StringOP)I.，/参数是否可交换3个弓I用publicstaticvoidArgIACtiVityDeal。匚，/参数第一操作数是否活跃20个引用publicstaticvoidOpAddObjCode(stringop,stringarg)/WB,C.四元式对应目标代码1个引用publicstaticstringExchangeQTOpTo0bjOp(stringOP)I./交换操作数4个弓I用publicstaticvoidRDLEmPty()匚二/寄存器为空的处理1个

29、引用publicstaticvoidBaseOpDeal(stringOP)I./基本操作符处理1个弓I用_publicstaticvoidCreateObjCodeo匚二J/生成目标代码1个引用publicstaticvoidFUllACtiVityMSgO匚/填活跃信息源代码一T前端IW间代码一T代码生成I目标代码中间代码优化II目标代码优化I对于一个基本块有如下流程图W：操作符，B：第一操作数，C：其次操作数，R：寄存器5.结论网上找一段话抄上6.测试测试打开文件测试保存文件目掠代码假如没打开文件，直接敲代码，点保存时会弹出另存为窗口测试错误检测，程序缺少main函数的类型，错误列表中显

30、示第一行函数缺少错误类型。目标代码楮谀列袤酝式，Ilii成功.才登生成四元式测试错误检测，程序缺少分号，错误列表中显示该行缺少语句结束标志T单击错误列表，会自动选定错误行opensaverun编修成功,牙琏成四元式目标代码编年成功,才H骸:娟ntmaintacfloatck11intt=1startc=a*bgotostart编译胜利，生成并显示token申、符号表、四元式与目标代码USTUSUSTU“益STulSTLDbgJSm“口Irw*ntmainSt8102C6arty=x=ywtla0测试if与while语句，而且while嵌套在if当中MWyJ堤话成功.测试goto语句，结果正确。

31、目标代码RRRRR3然口嘴S测试优化，输入课件中的代码，结果与课件一样穗误列表幅在成功,没有惜读值-bcx62p3M2Bi三9三三挣勘E装一-t1s窝义称unabCXP1P2P3XPs名3*nTE60.4瓦t(if,t4tp(.,.t(,tnp2,c,to3)【例9.7】单寄存器下(8)(ie)-hif(ab)=(a+b)*c;else=5-a*b：JN(DOa(y)b(y)t1(y)z(ift1(n)_)/(十a(y)b(y)t2(y)/(4)(*t2(n)c(y)X(y)Y(5)(el_)-(6)(*a(y)b(y)t3(y)-(-5t3(n)X(y)-./1I3J?*Ftu.ast35R

32、:XRqqqRt二ERIR.RRRRRR,一FRF4LDGTFJLDADMUSTJMXDMUSTLDSUST.软R,R,b9.6.然戏。1、陈火旺.程序设计语言编译原理（第3版）.北京:国防工业出版社.2000.返2被填返时2、美AlfredV.AhoRaviSethiJeffreyD.Ullman著.李建中，姜守旭译.编译原珊.北京：机械工业出版社.2003.3、美KennethC.Louden著.冯博琴等译.编译原理及实瞬.北京:机械工业出版社.2002.4、金成植著.编译程序构造原理和实现技福.比京:高等教育出版社.2002.7.收获、体会和建议。直接拷贝好歹也检查一下错误对于编译原理的

33、这次课程设计，自己经受了从刚开头的不懂今明白任务的要求和内容+理论学问的了解分开头着手写代码9完成基本功能-依据DFA及自顶向下等理论修改完善代码等这些过程。自己着手写词法分析的时候还不清晰词法分析的任务内容，还不知道词法分析的结果是什么，词法分析出错的状况和类型有哪些，也总是将词法分析和语法分析混在一起，不明白哪些错误在词法分析中报，哪些错误在语法分析中推断，后来经过查书、网上资料、请教同学等途径逐步清晰了词法分析的工作内容是从源代码文件中猎取出Token,供语法分析使用。在充分了解了语法分析需要哪些信息时,我才真正了解了词法分析的工作内容和目标才知道词法分析需要完成哪些任务猎取到哪些信息。

34、充分了解了词法分析的任务之后，就开头理论学问的学习。经过揣摩书上的例子，自己理解和把握了怎么设计过滤注释利分析程序中Token的DFA,于是开头依据设计好的DFA进行编码，最终经过调试已经可以正确地完成词法阶段的任务了。这只是词法分析的原始代码，在之后还进行了两次彻底的改动。虽然之前写的词法分析的代码已经完成了词法分析的需求，也是依据DFA的原理编写的，但是在代码结构上却难以体现，在对书上的依据己知DFA写代码的例子进行了具体的讨论之后，发觉自己的代码并没有像书上那样完全依据所依据的DFA各状态转移的关系进行编写，所以对代码进行了重写，像书上一样严格依据状态之间转移的方式进行编写，将状态划分成

35、11个状态，状态分别按1-11进行标注，程序也依据DFA来编写，也实现了词法分析的功能。再后来写报告的时候，发觉分析出TOken的那个DFA并不是最简的，有很多多余的状态，完全可以用一个flag标志来标识，从而简化代码结构，于是又重写了一次词法分析函数SCan()的代码，将状态缩减为5个，且不再用1-5来表示，而是像书上那样分别取了名字(START、工NNUM、工N工D、工NDBSYM、DONE),同时为了简化代码将输出Token到文件的部分从scan()中剥离开来，而在Lexical类中加了一个printToken()的函数，使scan()函数规律更加清晰，使读者能够简洁地将R码与DFA进行

36、查看比照。在写语法分析的时候，已经对编译器的语法分析的内容有了肯定的了解，所以直接进行了理论的学习。首先自己对递归向下分析法进行了学习，将书上的几个递归向下分析的伪代码看过之后，自己对递归向下的分析方法的原理有了初步的熟悉，也许知道了依据文法怎么分析，但是对于如何编写代码却还是难以下手，于是就对比TINY语言的文法看了Jl三书后面的TINY语言的递归向下分析的语法分析程序，这样就基本知道了C-语言的语法分析程序怎么写。由于C-语言给出的文法有左递归存在，于是自己将存在左递归的文法改写成EBNF的形式，并据此进行代码编写。由于在编写代码的过程中需要确定分析是否正确或选择多个文法中的某一个文法进行

37、分析，有时必需探测需要的或下一个TOken的类型，在这种状况下需要求FirSt集合，在推导中若存在empty,又需要求FoIIoW集合，所以这样又需要我了解First集合和Follow集合自己在程序中也依据求出的First集合和Follow集合进行推断以确定程序的走向。在编写过程中，还有一类问题，就是存在公共左因子，如文法expressio11fvar=expressionIsimple-expression,左因子为ID,在分析过程中，由于已经取出了一个IDMToken,且生成了一个IdK的节点，但是在当前状态无法确定是哪一个推导，然而工dK节点己经生成，又无法回退，并且是使用自顶向下的分析

38、方法，已经生成的工dK在程序上方无法使用，自己通过查阅资料等途径的学习确定了在这种情形下的处理方式：将已经生成的工dK节点传到下方的处理程序，所以TreeNode*SimPIe.expression(TreeNode*k)、TreeNode*additive_expression(TreeNode*k)等函数都被设计成有节点类型参数的函数，目的就是将已经生成的节点传到下面的分析函数中去。通过这次的编译原理课程的学习和实践，自己获益良多。首先最基本的成果是完成了课程设计的任务，实现了编译器的词法分析和语去分析阶段的功能，词法分析主要能过滤注释、分析出语法分析阶段需要的Token并满意语法阶段的全

39、部要求，能够判别词法分析阶段是否出错和出错类型和位置。语法分析主要能依据递归向下的分析思想和C-文法对词法分析猎取的Token进行语法分析，能够构造出语法树，能够判别语法分析过程中是否出错以及出错位置和错误类型。由于在编写程序过程中，涉及到了正则表达式DFA,提取公共左因子、消退左递!HEBNK求FirStI集合和FolIOW集合、递归向下分析方法以及编程语言方面的学问，所以，通过本次的课程设计的实践，使得自己对编译原理这门课的很多学问点有了更深入刻和具体的理铎而不再只限制于做题。止匕外，对以前那些已把握的学问有了温习和动手熬炼的机会。如：以前在编译原理课上虽然知道First集合和F。：LlOW集合怎么求的，却不知道FirSt集合和FoIloW集合究竟是干什么的，通过编写程序自己明白了他们的实际作用，使得自己不仅知其然还知其所以然，从而使得自己深入了对学问点的理解和把握。由于以前编写代码都是使用JAVA语言，所以C/C+很多内容都遗忘了，通过本次的实践，自己又重新捡起了以前的学问。此外，由于在做报告的时候，需要描绘DFA和程序流程图，使得自己初步把握了使用ViSio和Word画图的力量。此外，对于文档的编写和美化自己也获得了很多有用的阅历。