编译原理课程设计---C语言编译器的实现.doc

扬州大学编译原理课程设计 学 号： 091202122 姓 名： 专 业： 计算机科学与技术 课 程： 编译原理 指导教师： 陈宏建 目录一程序简介与分析-3二程序适用范围-3三词法分析-3四语法分析-4五语义分析和中间代码生成-10六代码生成-12七流程图-13八实现-14九程序运行结果-14十总结-18十一.附录（源程序）-18 简单的编译程序设计一 程序简介与分析本程序由四个部分组成：词法分析子程序，语法分析子程序，语义分析子程序，目标代码生成程序。本程序输入一个叫libo.txt的c语言源程序，然后对它进行词法，语法，语义分析，并输出汇编代码。词法分析输入的是c语言源程序，输出的3是具有独立语法意义的单词符号。语法分析以词法分析产生的编码流为输入，按照slr(1)分析方法进行语法分析，产生语法树，输出移进和归约的动作，如果源程序不符合文法，则有“语法分析出错”的提示。语义分析阶段，在语法分析的同时，在归约的时候，给出相应的语义动作，最后输出中间代码四元式和新的符号表，如果有未声明的变量出现，则会提示出出错，并显示出此变量的名称。代码生成阶段，将语义分析得到的中间代码四元式转化为汇编语言的目标代码并输出。二 程序适用范围 本程序的使用范围为：整型常量，四则运算（为了简化问题，本程序只考虑加法运算和乘法运算）和布尔表达式以及相应的赋值语句，条件转移语句和循环语句。三 词法分析根据词法分析的需要，我将源程序中的单词符号分为：保留字，字母（标识符），界符三类，统一用一张表表示如下：界符，保留字表单词=+*:;()andifthenwhiledoint标志符编码1234567891031323335363725程序从源程序文件libo.txt中一次读入一个字符，并判断它是不是字母，界符，保留字，空格，换行，结束符号或者非法字符。流程图如下： 词法分析流程图四 语法分析源程序中涉及的文法gp定义如下表：说明语句表达式布尔表达式句法0、pp1、pid () l;r2、ll;d3、ld4、did:int5、ee+t6、et7、tt*f8、tf9、f(e)10、fid11、bb and b12、bidid13、mid=e14、sif b then m15、swhile b do m16、sm17、nn;s18、ns19、rn.上述文法的每个非终结符的first 集和follow集如下表： first 集 follow 集p id # l id ; d id ; e (,id ,;,+,),#t (,id ,;,+,),*,#f (,id ,;,+,),*,#b id then,do,andm id ,; s id,while,if ,; n id,while,if ,; r # .文法gp的项目集部分如下：0. p.p 1. pp.2. p.id()l;r 3. pid.()l;r 4. pid(.)l;r 5. pid().l;r 6. pid()l.;r 7. pid()l;.r 8. pid()l;r. 9. l.l;d10.ll.;d 11. ll;.d 12. ll;d. 13.d.id:int 14. did .:int 15. did: .int 16. did:int. 17.e.e+t 18. ee.+t 19. ee+.t 20. ee+t. 21. e.t 22. et. 23. t.t*f 24. tt.*f 25. tt*.f 26. tt*f. 27. t.f 28. tf. 29. f (e) 30. f (.e) 31. f (e.) 32. f (e). 33. f.id 34. fid. .再由项目集构造文法的dfa活前缀。为了方便，省去了项目族集的每个状态的项目，直接在状态转换的箭头上标明终结符或非终结符。对于有规约动作和接受的状态，将其特别标明。文法gp的dfa图如下： 有归约动作812765 : int 说明语句接受状态 d id d id3021491011r ; l ) ( id p26252423 if b then m271430292028191718222113 id and id 句法s id = if idm n ; s id m while while b do m id and353431 id b 布尔表达式 and3233 id1536 t id38 id ( f e3716 * (403941 f ( id f id + e ( 表达式4342 + ) t4445 *gp：slr（1）分析表actiongotoid();:*+=intandifthenwhiledo$pdretfbmsln012345678910111213141516170123456789100s211acc2s33s44s5895s66s77r48r39s1010s5s13121111r112r213s14s23s2722211714s1515s36s4116383716r13s43r1317s19s1818r1919s14s23s272220gp：slr（1）分析表actiongotoid();:*+=intandifthenwhiledo$pdretfbmsln0123456789101112131415161701234567891020r17r1721r18r1822r16r1623s312424s34s2525s142626r14r1427s312828s3429s14s293030r15r1531s3232s3333r12r12r1234s313535r11r11r1136r10r10r10r10r1037r8r8r8r8r838r6r6s39r6r639s36s4140gp：slr（1）分析表actiongotoid();:*+=intandifthenwhiledo$pdretfbmsln0123456789101112131415161701234567891040r7r7r7r7r741s36s4142383742s45s4343s36s41443744r5r5s39r5r545r9r9r9r9r9五 语义分析和中间代码生成载语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。语法制导翻译归约动作翻译方案ee+tee1+te.place=newtemp;emit(e.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;fidfid p:=lookup(); if pnil then f.place:=p else error;bb and bbb1 and a b2backpatch(b1.truelist,a.quad);b.truelist:=b2.truelist;b.falselist:=merge(b1.falselist,b2.falselist);aa.quad:=nextquadbididbid1id2b.truelist:=makelist(nextquad); b.falselist:=makelist(nextquad+1); emit(if id1.placeid2.placegoto_ _); emit(goto_ _);mid=emid=e p:=lookup(); if pnil then emit(p:=e.place) else error;sif b then msif b then a mbackpatch(b.truelist,a.quad) backpatch(b.falselist,nextquad)aa.quad:=nextquadswhile b do mswhile a1 b do a2 m backpatch(b.truelist,a2.quad) backpatch(b.falselist,nextquad+1) emit(gotoa1.quad)a1a1.quad:=nextquada2a2.quad:=nextquad语法翻译生成的四元式如下：六 代码生成目标代码生成阶段的任务是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译的最后阶段，它的工作与硬件系统结构和指令含义有关，这个阶段的工作很复杂，涉及到硬件系统功能部件的运用、机器指令的选择、各种数据类型变量的存储空间分配以及寄存器和后缓寄存器的调度等。本程序生成的目标代码与0x8086微处理器兼容。下面列举几个简单的四元式与汇编代码的转化列子：（+，a，b，t）mov r ，a ；add r ，b ;st r , t. ( *, a , b , t ) mov r ，a ；mul r ，b ;st r , t. ( j, _ , _ , l) jmp l. ( j , a , b , l ) mov r , a cmp r , b jb l. ( =,a , _ ,t ) ld r , a st r , t 本程序生成的目标代码如下： 七 程序流程图 编译程序流程图 八 实现本程序运行的硬件环境为cpu1.66hz ,内存为768m .软件环境为windows xp系统，visual c+环境。九 程序运行结果1 输入源文件路径：2 输出保留字 3输出符号表的内容5输出语法分析的结果（本程序采用自下而上的lr语法分析）6输出中间代码7输出目标代码十 总结通过本次实验，我对编译程序各阶段有了更深刻更深入的了解，也纠正了自己在某些方面的的错误，丰富了自己关于编译原理方面的知识。同时也培养了自己热爱思考，勤查资料的习惯。由于水平本次实验涉及面并不是很全面，我只考虑了c语言的一个子集。当然本程序的算法在某些地方也还存在一些缺陷。十一 附录（源程序）本程序输入的c源代码如下：libo()a:int;b:int;ccc:int;d:int;if cccb and ccca then 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;/编号string word;/字符串内容str *next;str *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;/状态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;/*四元式链，true链，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);/插入结点到队列stringvoid output();/输出三个队列的内容void outfile();/输出三个队列的内容到相应文件中/语法分析有关函数声明void yufa_main();/语法分析主程序void yufa_initialize();/初始化语法分析数据结构int yufa_slr1(int a);/语法分析主体部分int id1(int a);/给输入字符编号，转化成action表列编号string id10(int i);/给输入字符反编号int id2(char ch);/给非终结状态编号，转化成go_to表列编号int id20(char ch);/给非终结状态编号char id21(int j);/给非终结状态反编号void add(ike *temp);/给ike分析栈链表增加一个结点void del();/给ike分析栈链表删除一个结点/语义分析相关函数的声明void yuyi_main(int m);/语义分析主程序void add_l_four(l *temp);/向四元式链中加一个结点void add_l_true(l *temp);/向true链中加一个结点void add_l_false(l *temp);/向false链中加一个结点void add_symb(symb *temp);/向语义符号表链中加一个结点void output_yuyi();/输出中间代码四元式和最后符号表string newop(int m);/把数字变成字符串string id_numtoname(int num);/把编号转换成相应的变量名int lookup(string m);/变量声明检查/全局变量的声明file *fp;/文件指针int wordcount;/标志符计数int err;/标志词法分析结果正确或错误int nl;/读取行数int yuyi_linshi;/语义临时变量string e_name,t_name,f_name,m_name,id_name,id1_name,id2_name,errword;/用于归约时名称传递和未声明变量的输出int id_num,id1_num,id2_num,id_left,id_while,id_then,id_do;/用于记录一些特殊的字符位置信息/主程序开始int main()cout*endl;cout* 说明： *endl;cout* 第一部分：词法分析 *endl;cout* 第二部分：语法分析 *endl;cout* 第三部分：语义分析 *endl;cout* 第四部分：目标代码生成 *endl;cout*endl;cifa_main();/词法yufa_main();/语法output_yuyi();/语义 outdaima(); /代码生成coutnext=null;token_tail=new token;token_tail-next=null;string_head=new str;string_head-next=null;string_tail=new str;string_tail-next=null;/初始化三个队列的首尾指针l_four_head=new l;l_four_head-next=null;l_four_tail=new l;l_four_tail-k=0;l_four_tail-next=null;l_true_head=new l;l_true_head-ltrue=null;l_false_head=new l;l_false_head-lfalse=null;symb_head=new symb;symb_head-next=null;symb_tail=new symb;symb_tail-next=null;yuyi_linshi=-1;id_num=0;wordcount=0;/初始化字符计数器err=0;/初始化词法分析错误标志nl=1;/初始化读取行数scan();if(err=0)char m;output();cout词法分析正确完成!endlendlm;coutendl;if(m=y)outfile();cout结果成功保存在token.txt和sting.txt两个文件中，请打开查看endl;coutendl;void scan()coutendl;system(pause);coutendl;char ch;string word;char document50;int flag=0;coutdocument;coutendl;cout*endl;cout* 第一部分：词法分析 *endl;cout*endl;if(fp=fopen(document,rt)=null)err=1;cout无法找到该文件!endl;return;while(!feof(fp)word=;ch=fgetc(fp);flag=judge(ch);if(flag=1)out1(ch);else if(flag=3)out3(ch,word);else if(flag=4 | flag=5 |flag=6)continue;elsecoutnl行 错误:非法字符! ch | ch=: | ch=; | ch= | ch= | ch=( | ch=)flag=1;/界符else if(a=ch & ch=z) | (a=ch & ch : id=4;break;case : : id=5;break;case ; : id=6;break;case : id=7;break;case : id=8;break;case ( : id=9;break;case ) : id=10;break;/界符编码default : id=0;token *temp;temp=new token;temp-code=id;temp-num=-1;temp-next=null;input1(temp);return;void out3(char ch,string word)token *temp;temp=new token;temp-code=-1;temp-num=-1;temp-next=null;str *temp1;temp1=new str;temp1-num=-1;temp1-word=;temp1-next=null;int flag=0;word=word+ch;ch=fgetc(fp);flag=judge(ch);if(flag=1 | flag=4 | flag=5 | flag=6)if(word=and | word=if | word=then | word=while | word=do | word=int)if(word=and)temp-code=31;else if(word=if)temp-code=32;else if(word=then)temp-code=33;else if(word=while)temp-code=35;else if(word=do)temp-code=36;else if(word=int)temp-code=37;/关键字编码input1(temp);if(flag=1)out1(ch);else if(flag=4 | flag=5 | flag=6)return;else if(flag=1)wordcount+;temp-code=25;temp-num=wordcount;input1(temp);temp1-num=wordcount;temp1-word=word;input3(temp1);out1(ch);else if(flag=4 | flag=5 | flag=6)wordcount+;temp-code=25;temp-num=wordcount;input1(temp);temp1-num=wordcount;temp1-word=word;input3(temp1);return;else if(flag=2 | flag=3)out3(ch,word);/形成字符串elseerr=1;coutnl行 错误:非法字符! chnext = nu