编译器_编译原理课程设计报告书.doc

1、下载可编辑广西大学编译原理课程设计专业： 计算机科学与技术姓名：课程：编译原理.专业 .整理 .下载可编辑指导教师：目录一程序简介与分析-1二程序适用范围 -1三词法分析 -1四语法分析 -3五语义分析和中间代码生成-9六代码生成 -11.专业 .整理 .下载可编辑七流程图 -12八实现 -13九程序运行结果 -13十总结 -18十一 .附录 （源程序 ） -19.专业 .整理 .下载可编辑简单的编译程序设计一 程序简介与分析本程序由四个部分组成：词法分析子程序 ，语法分析子程序 ，语义分析子程序，目标代码生成程序 。本程序输入一个叫haominjie.txt的 c 语言源程序，然后对它进行词

2、法 ，语法，语义分析 ，并输出汇编代码 。词法分析输入的是c 语言源程序 ，输出的 3 是具有独立语法意义的单词符号。语法分析以词法分析产生的编码流为输入，按照SLR(1)分析方法进行语法分析 ，产生语法树 ，输出移进和归约的动作，如果源程序不符合文法，则有“语法分析出错 ”的提示。语义分析阶段 ，在语法分析的同时 ，在归约的时候 ，给出相应的语义动作，最后输出中间代码四元式和新的符号表，如果有未声明的变量出现，则会提示出出错 ，并显示出此变量的名称 。代码生成阶段 ，将语义分析得到的中间代码四元式转化为汇编语言的目标代码并输出 。二 程序适用范围本程序的使用范围为 ：整型常量 ，四则运算 （

3、为了简化问题 ，本程序只考虑加法运算和乘法运算）和布尔表达式以及相应的赋值语句，条件转移语句和循环语句 。.专业 .整理 .下载可编辑三 词法分析根据词法分析的需要，我将源程序中的单词符号分为：保留字 ，字母（标识符），界符三类 ，统一用一张表表示如下 ：界符 ，保留字表标单anthewhildin=+*:;()if志词dneot符编133312345678931333525码0267程序从源程序文件haominjie.txt中一次读入一个字符 ，并判断它是不是字母，界符，保留字，空格，换行，结束符号或者非法字符 。流程图如下 ：.专业 .整理 .下载可编辑子程序开始程序读入一个字符ch判断字

4、符 ch格 行符符母束空 换界字结子程序继编号并输编号并输续出出判断是否要写入文件Y写入到磁盘文件N子程序结束符字法非出错处理显示错误信息FOE关闭文件词法分析流程图四 语法分析1 源程序中涉及的文法GP定义如下表 ：说明语句表达式布尔表达式句法0、 PP5、E11 、 B B and13、 M id=E1、 Pid () L;RE+TB14、 S if B then M.专业 .整理 .下载可编辑2、 LL;D6、 ET12、 Bidid15 、 S while B do3、 LD7、TM4、 D id:intT*F16、SM8、 TF17、NN;S9、F18、NS(E)19、 RN10、F

5、id2 .上述文法的每个非终结符的FIRST 集和 FOLLOW 集如下表 ：FIRST 集FOLLOW 集P id # L id ; D id ; E(,id ,;,+,),#T(,id ,;,+,),*,#F(,id ,;,+,),*,#B idthen,do,andM id ,;Sid,while,if ,;.专业 .整理 .下载可编辑Nid,while,if ,;R# 文法 GP的项目集部分如下 ：3 .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;.R

6、8. P id()L;R.9. L .L;D10.L L.;D11. L L;.D12.LL;D.13.D .id:int14. D id .:int15.Did: .int16. D id:int.17.E .E+T18.E E.+T19. E E+.T20. E E+T.21. E .T22. ET.23. T .T*F24.T T.*F25.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 活前缀 。为了方便 ，省去了项目族集的每个状态的

7、项目 ，直接在状态转换的箭头上标明终结符或非终结符。对于有规约.专业 .整理 .下载可编辑动作和接受的状态 ，将其特别标明 。文法 GP的 DFA 图如下：.专业 .整理 .下载可编辑有归约动作8125:6int7说明语句接受状态DidDid1110943201R;L)(idP23242526ifBthenM.专业 .整理 .下载可编辑18idandid句211314法17192022Sid=27282930ifidMN;SidMwhilewhileBdoMidand31id34B35布尔表达式and3233id15.专业 .整理 .下载可编辑Tid36id38(FE37*(16403941F

8、(idFid+E(表达式4243+)T4544*GP ：SLR （ 1）分析表Actiongotoi();:*+=iaitwd$PDRET F BMSL Ndnnfhhotdeilne012345678911111111701234567891012345600s121acc2s.专业 .整理 .下载可编辑33 s 44s8955s66s77r48r39s101ss110512131r111r221sss22131222174371s4151ss133534687611rsr61413331ss711981r1981sss22912220437.专业 .整理 .下载可编辑GP ：SLR （ 1

9、）分析表Actiongotoi();:*+=iaitwd$PDRET F BMSL Ndnnfhhotdeilne012345678911111111701234567891012345602rr011772rr111882rr211662s233412ss432452s251642rr611442s273812s8342ss39120493rr011553s.专业 .整理 .下载可编辑1323 s2 333rrr31112223s343513rrr51111113rrrrr611111000003rrrrr7888883rrsrr86636693ss4934061GP ：SLR （ 1）分析

10、表actiongotoi();:*+=iaitwd$PDRETFBMSL Ndnnfhhotdeilne012345678911111111701234567891012345604rrrrr0777774ss433134287614ss24453.专业 .整理 .下载可编辑4ss4333447614rrsrr45535594rrrrr599999五 语义分析和中间代码生成载语法分析过程中 ，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。语法制导翻译归约动作翻译方案EE+TEE1+TE.place=newtemp;Emit(E.

11、place := E1.place +T.place);ETET E.place:=T.place;TT*FTT1*FT.place=newtemp;Emit(T.place := T1.place +F.place);TFTF.专业 .整理 .下载可编辑T.place:=F.place;F(E)F(E)F.place:=E.place;FidFidp:=lookup();if pnil then F.place:=pelse error;BB and BBB1 and A B2backpatch(B1.truelist,A.quad);B.truelist:=B2.trueli

12、st;B.falselist:=merge(B1.falselist,B2.falselist);A A.quad:=nextquadBididBid1id2B.truelist:=makelist(nextquad);B.falselist:=makelist(nextquad+1);emit(if id1.placeid2.place goto_ _ );emit( goto_ _ );M id=EM id=E p:=lookup();if pnil then emit(p:= E.place).专业 .整理 .下载可编辑else error;Sif B then MSif

13、B then A Mbackpatch(B.truelist,A.quad)backpatch(B.falselist,nextquad)A A.quad:=nextquadSwhile B do MSwhile A1 B do A2 M backpatch(B.truelist,A2.quad) backpatch(B.falselist,nextquad+1)emit( goto A1.quad)A1 A1.quad:=nextquadA2 A2.quad:=nextquad语法翻译生成的四元式如下：.专业 .整理 .下载可编辑六 代码生成目标代码生成阶段的任务是把中间代码变换成特定机器上

14、的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译的最后阶段 ，它的工作与硬件系统结构和指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用 、机器指令的选择 、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。本程序生成的目标代码与0x8086 微处理器兼容。下面列举几个简单的四元式与汇编代码的转化列子：1（ +， A，B，T）MOVR，A；ADDR ，B;STR , T2.(*,A,B,T)MOVR，A；MULR ，B;.专业 .整理 .下载可编辑STR , T3.(J,_,_,L)JMPL4.(J,A,B,L)MOVR , ACMPR , BJBL5 .(

15、=,A,_,T)LDR , ASTR , T本程序生成的目标代码如下：.专业 .整理 .下载可编辑七 程序流程图.专业 .整理 .下载可编辑编译程序开始词法分析子程序语法分析子程序理处错出语义分析子程序目标代码生成程序错误处理编译程序结束编译程序流程图八 实现本程序运行的硬件环境为CPU 2GHZ , 内存为 4G .软件环境为 windows 8.1系统，Visual C+ 环境 。九 程序运行结果1 输入源文件路径 ：.专业 .整理 .下载可编辑2 输出保留字3输出符号表的内容.专业 .整理 .下载可编辑5输出语法分析的结果 （本程序采用自下而上的LR 语法分析 ）.专业 .整理 .下载可

16、编辑.专业 .整理 .下载可编辑6输出中间代码.专业 .整理 .下载可编辑7输出目标代码.专业 .整理 .下载可编辑十 总结通过本次实验 ，对编译程序各阶段有了更深刻更深入的了解，也纠正了自己在某些方面的的错误，丰富了自己关于编译原理方面的知识。同时也培养了自己热爱思考 ，勤查资料的习惯 。 由于水平本次实验涉及面并不是很全面，我只考虑了c 语言的一个子集。当然本程序的算法在某些地方也还存在一些缺陷。.专业 .整理 .下载可编辑十一 附录（源程序 ）本程序输入的 c 源代码如下 ：haominjie()a:int;b:int;ccc:int;d:int;if cccb and ccca the

17、n a=b+a;while cccd do a=d;a=(b+ccc)*a+d本程序的完整源代码如下：#include#include#include#include#include#includeusing namespace std;.专业 .整理 .下载可编辑struct token/词法 token 结构体int code;/编码int num;/递增编号token *next;token *token_head,*token_tail;/token队列struct str/词法 string 结构体int num;/编号stringword;/ 字符串内容str *next;str

18、*string_head,*string_tail;/string队列struct ivan/ 语法 产生式结构体char left;/ 产生式的左部string right;/产生式的右部int len;/ 产生式右部的长度;ivan css20;/ 语法20 个产生式struct pank/语法 action 表结构体.专业 .整理 .下载可编辑char sr;/ 移进或归约int state;/ 转到的状态编号;pank action4618;/action表int go_to4611;/语法 go_to 表struct ike/语法 分析栈结构体 ，双链ike *pre;int num

19、;/状态int word;/符号编码ike *next;ike *stack_head,*stack_tail;/分析栈首尾指针struct L/ 语义四元式的数据结构int k;string op;/操作符string op1;/操作数string op2;/操作数string result;/结果L *next;/ 语义四元式向后指针.专业 .整理 .下载可编辑L *Ltrue;/ 回填 true 链向前指针L *Lfalse;/ 回填 false 链向前指针;L *L_four_head,*L_four_tail,*L_true_head,*L_false_head;/*四元式链 ，tr

20、ue 链，false 链 */struct symb/语义输入时符号表string word;/变量名称int addr;/变量地址symb *next;symb *symb_head,*symb_tail;/语义符号链表/词法分析有关函数声明void outdaima() ;void scan();/ 按字符读取源文件void cifa_main();/词法分析主程序int judge(char ch);/判断输入字符的类型void out1(char ch);/写入 token.txtvoid out3(char ch,string word);/写入 string.txtvoid input1(token *temp);/插入结点到队列 tokenvoid input3(str *temp);/插入结点到队列 string.专业 .整理 .下载可编辑void output();/输出三个队列的内容void outfile();/输出三个队列的内容到相应文件中/语