编译器-编译原理课程设计

广西大学编译原理课程设计专业：计算机科学与技术姓名：课程：编译原理指导教师：目录一．程序简介与分析---------------------------------------------------------1二．程序适用范围-----------------------------------------------------------1三．词法分析---------------------------------------------------------------1四．语法分析---------------------------------------------------------------3五．语义分析和中间代码生成------------------------------------------------9六．代码生成--------------------------------------------------------------11七．流程图----------------------------------------------------------------12八．实现------------------------------------------------------------------13九．程序运行结果----------------------------------------------------------13十．总结------------------------------------------------------------------18十一.附录（源程序）--------------------------------------------------------191简单的编译程序设计一．程序简介与分析本程序由四个部分组成：词法分析子程序，语法分析子程序，语义分析子程序，目标代码生成程序。本程序输入一个叫haominjie.txt的c语言源程序，然后对它进行词法，语法，语义分析，并输出汇编代码。词法分析输入的是c语言源程序，输出的3是具有独立语法意义的单词符号。语法分析以词法分析产生的编码流为输入，按照SLR(1)分析方法进行语法分析，产生语法树，输出移进和归约的动作，如果源程序不符合文法，则有“语法分析出错”的提示。语义分析阶段，在语法分析的同时，在归约的时候，给出相应的语义动作，最后输出中间代码四元式和新的符号表，如果有未声明的变量出现，则会提示出出错，并显示出此变量的名称。代码生成阶段，将语义分析得到的中间代码四元式转化为汇编语言的目标代码并输出。二．程序适用范围本程序的使用范围为：整型常量，四则运算（为了简化问题，本程序只考虑加法运算和乘法运算）和布尔表达式以及相应的赋值语句，条件转移语句和循环语句。三．词法分析根据词法分析的需要，我将源程序中的单词符号分为：保留字，字母（标识符），界符三类，统一用一张表表示如下：界符，保留字表2单词=+*:;{}()andifthenwhiledoint标志符编码1234567891031323335363725程序从源程序文件haominjie.txt中一次读入一个字符，并判断它是不是字母，界符，保留字，空格，换行，结束符号或者非法字符。流程图如下：程序读入一个字符ch判断字符ch字母空格换行结束符非法字符EOF界符子程序继续子程序开始编号并输出编号并输出出错处理关闭文件判断是否要写入文件显示错误信息子程序结束写入到磁盘文件YNN词法分析流程图3四．语法分析○1．源程序中涉及的文法G[P]定义如下表：说明语句表达式布尔表达式句法0、P’→P1、P→id()L;R2、L→L;D3、L→D4、D→id:int5、E→E+T6、E→T7、T→T*F8、T→F9、F→(E)10、F→id11、B→BandB12、B→idid13、M→id=E14、S→ifBthenM15、S→whileBdoM16、S→M17、N→N;S18、N→S19、R→{N}○2.上述文法的每个非终结符的FIRST集和FOLLOW集如下表：FIRST集FOLLOW集P{id}{#}L{id}{;}D{id}{;}E{(,id}{},;,+,),#}T{(,id}{},;,+,),*,#}F{(,id}{},;,+,),*,#}B{id}{then,do,and}M{id}{},;}S{id,while,if}{},;}N{id,while,if}{},;}R{{}{#}○3.文法G[P]的项目集部分如下：0.P’→.P1.P’→P.2.P→.id()L;R3.P→id.()L;R4.P→id(.)L;R5.P→id().L;R6.P→id()L.;R7.P→id()L;.R8.P→id()L;R.9.L→.L;D10.L→L.;D11.L→L;.D12.L→L;D.13.D→.id:int14.D→id.:int15.D→id:.int16.D→id:int.17.E→.E+T18.E→E.+T19.E→E+.T20.E→E+T.21.E→.T22.E→T.23.T→.T*F24.T→T.*F425.T→T*.F26.T→T*F.27.T→.F28.T→F.29.F→(E)30.F→(.E)31.F→(E.)32.F→(E).33.F→.id34.F→id.○4.再由项目集构造文法的DFA活前缀。为了方便，省去了项目族集的每个状态的项目，直接在状态转换的箭头上标明终结符或非终结符。对于有规约动作和接受的状态，将其特别标明。文法G[P]的DFA图如下：5:int说明语句DidDidR;L)(idP{ifBthenMidandid句法Sid=}ifidMN;SidMwhilewhileBdoMidandidB布尔表达式andidTidid(FE*(F(idFid+E(表达式+)T1110943201567122324252613212218171927201514302928163134353233383637414245394043448有归约动作接受状态6*G[P]：SLR（1）分析表Actiongotoid();:*+={}intandifthenwhiledo$PDRETFBMSLN012345678910111213141516170123456789100s211acc2s33s44s5895s66s77r48r39s1010s5s13121111r112r213s14s23s2722211714s15715s36s4116383716r13s43r1317s19s1818r1919s14s23s272220G[P]：SLR（1）分析表Actiongotoid();:*+={}intandifthenwhiledo$PDRETFBMSLN0123456789101112131415161701234567891020r17r1721r18r1822r16r1623s312424s34s2525s142626r14r142s28731828s3429s14s293030r15r1531s3232s3333r12r12r1234s313535r11r11r1136r10r10r10r10r1037r8r8r8r8r838r6r6s39r6r639s36s4140G[P]：SLR（1）分析表actiongotoid();:*+={}intandifthenwhiledo$PDRETFBMSLN90123456789101112131415161701234567891040r7r7r7r7r741s36s4142383742s45s4343s36s41443744r5r5s39r5r545r9r9r9r9r9五．语义分析和中间代码生成载语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。语法制导翻译归约动作翻译方案E→E+TE→E1+T{E.place=newtemp;Emit(E.place’:=’E1.place’+’T.place);}E→TE→T{E.place:=T.place;}T→T*FT→T1*F{T.place=newtemp;Emit(T.place’:=’T1.place’+’F.place);}T→FT→F{T.place:=F.place;}F→(E)F→(E){F.place:=E.place;}10F→idF→id{p:=lookup(id.name);ifpnilthenF.place:=pelseerror;}B→BandBB→B1andAB2{backpatch(B1.truelist,A.quad);B.truelist:=B2.truelist;B.falselist:=merge(B1.falselist,B2.falselist);}A→∈{A.quad:=nextquad}B→ididB→id1id2{B.truelist:=makelist(nextquad);B.falselist:=makelist(nextquad+1);emit(ifid1.place’’id2.place’goto__’);emit(’goto__’);}M→id=EM→id=E{p:=lookup(id.name);ifpnilthenemit(p’:=’E.place)elseerror;}S→ifBthenMS→ifBthenAM{backpatch(B.truelist,A.quad)backpatch(B.falselist,nextquad)}A→∈{A.quad:=nextquad}S→whileBdoMS→whileA1BdoA2M{backpatch(B.truelist,A2.quad)backpatch(B.falselist,nextquad+1)emit(’goto’A1.quad)}A1→∈{A1.quad:=nextquad}A2→∈{A2.quad:=nextquad}语法翻译生成的四元式如下：11六．代码生成目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译的最后阶段，它的工作与硬件系统结构和指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。本程序生成的目标代码与0x8086微处理器兼容。下面列举几个简单的四元式与汇编代码的转化列子：○1．（+，A，B，T）→MOVR，A；ADDR，B;STR,T○2.(*,A,B,T)→MOVR，A；MULR，B;STR,T○3.(J,_,_,L)→JMPL○4.(J,A,B,L)→MOVR,ACMPR,BJBL○5.(=,A,_,T)→12LDR,ASTR,T本程序生成的目标代码如下：七．程序流程图13编译程序开始词法分析子程序语法分析子程序语义分析子程序目标代码生成程序编译程序结束出错处理错误处理编译程序流程图八．实现本程序运行的硬件环境为CPU2GHZ,内存为4G.软件环境为windows8.1系统，VisualC++环境。九．程序运行结果1．输入源文件路径：142．输出保留字3．输出符号表的内容155．输出语法分析的结果（本程序采用自下而上的LR语法分析）16176．输出中间代码187．输出目标代码十．总结通过本次实验，对编译程序各阶段有了更深刻更深入的了解，也纠正了自己在某些方面的的错误，丰富了自己关于编译原理方面的知识。同时也培养了自己热爱思考，勤查资料的习惯。由于水平本次实验涉及面并不是很全面，我只考虑了c语言的一个子集。当然本程序的算法在某些地方也还存在一些缺陷。19十一．附录（源程序）本程序输入的c源代码如下：haominjie(