编译原理课设报告(共43页).doc

《编译原理课设报告(共43页).doc》由会员分享，可在线阅读，更多相关《编译原理课设报告(共43页).doc（43页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上北华航天工业学院编译原理课程设计课程设计题目： 编译程序构造 作者所在系部： 计算机科学与工程系 作者所在专业： 计算机科学与技术 作者所在班级： B08512 作 者 学 号： 作 者 姓 名 ： 陈程 指导教师姓名： 李建义 完 成 时 间 ： 2011年6月8日 课程设计任务书课题名称编译原理课程设计完成时间2011.6.8指导教师李建义职称副教授学生姓名陈程班级B08512总体设计要求总体设计要求： 课程设计内容共给定1个题目，每个学生按照课程设计要求，在规定的两周时间内独立完成。题目： 编译程序构造涉及内容：词法分析、语法分析、语义分析生成中间代码工作内容及

2、时间进度安排第一周、周：设计动员，布置课程设计任务，查阅资料，制定方案，进行程序方案设计。第一周、周2-周5：编写和调试程序第二周、周1-周3：编写和调试程序第二周、周4：整理，撰写设计报告。第二周、周5：验收，提交设计报告，评定成绩。毕业设计成果1、课程设计报告书一份2、源程序清单一份3、成果使用说明书一份目 录专心-专注-专业第一章课程设计目的编译原理课程设计是编译原理课程必不可少的一个环节，通过课程设计，加深对编译原理的教学内容的了解，以及实现编译原理各部分知识的融合。进而提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力。编译原理是一门理论性和实践性非常强的课程，特别是其中

3、涉及的文法理论、自动机理论和优化方法等内容都比较抽象，仅仅通过课堂教学不足以深刻理解和掌握这方面的知识。另一方面，虽然，所培养的学生今后真正从事编译程序的开发的机会并不多，但是，编译原理作为计算机科学与技术专业知识体系中为数不多的大型系统软件开发的理论方法的介绍，其意义决不仅仅局限在开发编译系统本身。本课程设计的目的是要求学生运用编译原理重点章节的相关知识和思想方法，结合高级语言程序设计等相关课程的知识，去解决实际问题。通过这样的实践，训练学生理论联系实际的能力，特别是引导学生在面临实际问题时候进行发散思维，开拓思路，解决问题。同时也对学生进行复杂程序设计的技能训练和培养良好程序设计的习惯。第

4、二章 课程设计内容2.1 课设题目编译程序构造2.2 课设内容涉及词法分析、自下而上语法分析程序的实现：SLR（1）分析器的实现以及生成中间代码。2.3 具体要求根据LR分析算法构造SLR（1）分析程序，并完成语法分析动作（当需要一个单词时，调用词法分析程序获取），同时完成语义分析生成四元式输出。要求程序具有通用性，改变文法时只需改变程序的数据初值，无需改变程序主体；2.3.1 基本要求：完成1条说明语句、2条算数表达式和赋值语句的翻译，生成中间代码。2.3.2 高级要求：在完成基本要求的基础上，实现if语句和布尔表达式的翻译。if语句的文法和翻译方案参见课本。变量说明语句的文法及相应的语义子

5、程序：.att表示数据类型属性，fill函数表示将单词id及其类别属性填写符号表。（0）SD； acc（1）Dint id fill（id，int）；D.att=int; （2）Dfloat id fill(id,float); D.att=float; （3）DD（1），id fill(id,D(1).att);D.att=D(1).att; 算数表达式和赋值语句的文法及相应的语义子程序。（1）Aid=E； p=lookup(id.name);emit（E.PALCE, , p）; （2）EE(1)+T E.PALCE=newtemp(); emit(+，E(1).PALCE，T.PALCE

6、，E.PALCE)（3）ET E.PALCE=T.PALCE;（4）TT(1)*F T.PALCE=newtemp(); emit(+，T(1).PALCE，F.PALCE，T.PALCE)（5）TF T.PALCE=F.PALCE;（6）F(E) F.PALCE=E.PALCE;（7）Fid P=LOOKUP(id.name)F.PALCE=P;（8）Fnum P=LOOKUP(num.value)F.PALCE=P;构造其用于SLR（1）分析的识别活前缀的DFA以及action表和goto表。然后编程实现。（关于词法分析部分只需识别出与此文法相关的单词即可（+，*，（，），id，=）。2.

7、4 程序设计提示1. 分析栈设计时可以用一个栈完成，也可以设计三个栈：一个符号栈，一个状态栈，一个语义栈，则归约时，则需要在符号栈中退掉n个符号，在状态栈中退掉n个符号（n为产生式符号个数），语义栈中退掉n个符号对应的语义；2. 终结符表和非终结符表的组织和预测分析程序中相同（将符号对应到一个数字，表示在分析表中对应的下标）。3. action表中的错误处理：简化的错误处理：当查找action表出现空白时，则当前单词无法移进和规约，可简单的认为当前单词为多余的单词，则抛弃当前单词，读下一单词继续分析。2.5 测试数据：作为程序测试数据，以赋值语句area=r*r+r$作为测试输入（源程序）。程

8、序要求输出二元式序列、符号表、语法分析过程、四元式序列。假设AA.TXT的文件内容如下：int area，r；r=1；area=r*r+r；2.5.1 程序运行情况请输入源文件名称：E：AA.TXT语法分析过程如下：状态栈 符号栈 语义栈 动作说明源程序对应的二元式如下：（int，-）（id，0）（，-）（id，1）（；，-）（id，1）（=，）（num，0）（id，0）（=，）（id，1）（*，）（id，1）（+，）（id，1）（；，-）符号表如下：Name type value addr0 area int1 r int数字表如下源程序对应的四元式序列如下：（=，1， ， r）（*，r，r

9、，T1）（+，T1，r，T2）（=，T2，area）分析过程完成。2.6 程序扩展要求有能力的同学可 将编译程序扩展布尔表达式的分析和四元式生成，布尔表达式的翻译参见教材（胡元义编译原理教程）104105页。第三章 设计方案编译程序在编译过程中，需要不断收集、记录和使用源程序中一些语法符号的类型和特征相关信息。编译程序要完成词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成以及符号表和错误处理。3.1 模块划分3.1.1 词法分析词法分析程序是编译程序主要组成部分之一，它的主要任务是从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位(单词)。词法分析程序的输入为字符串

10、，而输出为提供给语法分析的单词串。为了能有效地从源程序文本中分离出这些单词，词法分析程序必须对源程序文本进行编辑，例如消除文本中的注释、空格、换行符以及其它一切对语法分析和代码生成均无关的信息。除此之外，为了能正确识别出单词，有时还需要区别一串字符究竟是保留字(如IF)还是标识符。有时为了将标识符、常量等转换为内部形式并插入表格中，词法分析程序还需要执行维护符号表的工作，等等。词法也是语法的一部分，词法描述完全可以归并到语法描述中去，只不过词法规则更简单些。这在后面的章节中可以看到。为什么将词法分析做为一个独立的阶段? 为什么把编译过程的分析工作划分成词法分析和语法分析两个阶段? 主要的考虑因

11、素为：1 使整个编译程序的结构更简洁、清晰和条理化。词法分析比语法分析简单的多，但是由于源程序结构上的一些细节，常使得识别单词的工作甚为曲折和费时。例如，空白和注释的处理；2 编译程序的效率会改进。大部分编译时间是花费在扫描字符以把单词符号分离出来。把词法分析独立出来，采用专门的读字符和分离单词的技术可大大加快编译速度。另外，由于单词的结构可用有效的方法和工具进行描述和识别，进而可建立词法分析程序的自动构造工具。3 增强编译程序的可移植性。在同一个语言的不同实现中，或多或少地会涉及到与设备有关的特征，比如采用ASCII还是EBCDIC字符编码。都可置于词法分析程序中解决而不影响编译程序其它成分

12、的设计。处理词法分析程序与语法分析程序之间的关系又可采用两种方式：一种方式是将词法分析作为单独一遍扫描，即在语法分析之前，实现源程序的全部词法分析工作，其输出(单词申)形成一个中间文件(内部符号形式的源程序表)，移交给语法程序。另一种方式为将词法分析程序编写成一个子程序，每当语法分析程序需要读一个新单词时，便去调用它。本次课程设计采用前一种方式。3.1.2 语法分析语法分析是编译过程的核心部分，它的主要任务是按照程序语言的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序叫语法分析程序或语法分析器。语法分析程序以词

13、法分析输出的符号串作为输入，在分析过程中检查这个符号串是否为该程序语言的句子。若是，输出该句子的分析树；若不是，则表示源程序存在语法错误，需要报告错误的性质和位置。 常用的语法分析方法大体上可以分成自顶向下和自底向上两大类：1. 自顶向下分析方法：语法分析从顶部(树根、语言的识别符号)到底部(叶子、语言的终结符号)为输入的符号串建立分析树。本章介绍的递归下降分析方法和LL分析方法就属于自顶向下分析方法。2. 自底向上分析方法：语法分析从底部到顶部为输入的符号串建立分析树。最常见的LR分析方法采用的就是自底向上分析方法。我们将在第五章介绍这种分析方法。无论采用哪种分析方法，语法分析都是自左向右地

14、读入符号。 3.1.3 语义分析语义分析是编译过程的一个逻辑阶段， 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查，进行类型审查。语义分析是审查源程序有误语义错误，为代码生成阶段收集类型信息。比如语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。如有的编译程序要对实数用作数组下标的情况报告错误。又比如某些某些程序规定运算对象可被强制，那么当二目运算施于一整型和一实型对象时，编译程序应将整型转换为实型而不能认为是源程序的错误。3.1.4 错误处理错误处理在整个编译程序中都占有很重要的地位，它贯穿于整个编译程序的前后

15、，词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成都涉及错误处理，一个好的词法分析器，错误处理应该占有举足轻重的地位。错误处理的完善是一个编译程序功能强大的后盾。3.2 模块调用语法分析是编译过程的核心部分，它的主要任务是按照程序语言的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成作准备。如图3-2-1所示。语义分析词法分析器语法分析器错误处理中间代码生成错误处理错误处理错误处理图3-2-1 模块调用3.3 模块程序流程图3.3.1 词法分析流程图图3-3-1所示YYYNY初始化读标识符开始查关键字表读取字符填常数表查询常

16、量表读取数字结束写到输出流字母关键字EOF数字相同值特殊字符相同值Error查标识表填标识符表错误状态NYNNYNNNY结束图3-3-1 词法分析流程图3.3.2 语法分析流程图图3-3-2所示YYYN置初值开始对应ri归约项，弹出相应归约项，弹出对应状态，产生式开始符入栈，查询GOTO表，对应状态入栈根据当前单词、栈顶状态查询ACTION表，由ACTION表中对应值作相应操作对应Si跳转项，当前单词、状态、语义入栈错误处理ri? Si?结束打印错误ri打印状态栈、符号栈、语义栈分析完成NN结束图3-3-2 语法分析流程图3.3.3 语义分析流程图图3-3-3所示开始r2r3r4r5r6r7r

17、8r9r10r11r12r13S.place=A.placefill（id，int）；D.att=int;fill(id,float); D.att=float;fill(id,D(1).att);D.att=D(1).att;p=lookup(id.name);emit（E.place, , p）;E. place =newtemp(); emit(+，E(1). place，T. place，E.PALCE)E. place =T. place;T.PALCE=newtemp(); emit(+，T(1). place，F. place，T.PALCE)T. place =F place;

18、F. place =E. place;P=lookup(id.name)F. plce =P;P=lookup(num.value)F.place=P;结束 N N N N图3-3-3 语义分析流程图第四章 程序源代码#include#include#includeusing namespace std;#define MAXSIZE 50string arr14=int,char,float,void,const,for,if,else,then,while,switch,break,begin,end;/初始化保留字string buffMAXSIZE;int M=0,N=0,z=1,e=

19、0,con=0,conn=0;/M为符号表中符号的个数，N为数字表中数字的个数，z记录行数，e记录错误数,con二元式的个数，conn四元式的个数int aMAXSIZE;/存储错误的所在行char ch=0;FILE *fp;struct two /二元式string name;string value1;int value2;BMAXSIZE,B1MAXSIZE;struct four /四元式string mark;string arg1;string arg2;string result;FMAXSIZE;struct VNSTR /非终结符,为语义分析服务string name;st

20、ring att;string place;VMAXSIZE;struct digit /数字表string name; double value;DMAXSIZE;struct word /标识符表string name;string type;string value;WMAXSIZE;typedef struct /栈定义int statuesMAXSIZE; /状态栈 string dataMAXSIZE; /符号栈string meanMAXSIZE; /语义栈int top;SeqStack;/* 0 MS 1 SD；2 Dint id3 Dfloat id4 DD（1），id5

21、SA6 Aid=E；7 EE(1)+T8 ET9 TT(1)*F10 TF11 F(E)12 Fid13 Fnum */string FA215=M,S,D,A,E,T,F,; /语义分析string VN6=S,A,E,D,T,F; /非终结符集合string VT12=;,int,float,id,=,+,*,num,(,),#; /终结符集合string FA114=M,S,D,D,D,S,A,E,E,T,T,F,F,F; string FA14=S,D;,int id,float id,D,id,A,id=E;,E+T,T,T*F,F,(E),id,num; /归约时，弹出的字符串in

22、t count14=1,2,2,2,3,1,4,3,1,3,1,3,1,1; /记录归约时，弹出字符的个数int ACTION2612=0,3,4,6,0,0,0,0,0,0,0,0, /0 0,0,0,0,0,0,0,0,0,0,0,512, /17,0,0,0,8,0,0,0,0,0,0,0, /20,0,0,9,0,0,0,0,0,0,0,0, /30,0,0,10,0,0,0,0,0,0,0,0, /40,0,0,0,0,0,0,0,0,0,0,-5, /5 0,0,0,0,0,11,0,0,0,0,0,0, /60,0,0,0,0,0,0,0,0,0,0,-1, /7 0,0,0,1

23、2,0,0,0,0,0,0,0,0, /8-2,0,0,0,-2,0,0,0,0,0,0,0, /9-3,0,0,0,-3,0,0,0,0,0,0,0, /100,0,0,15,0,0,0,0,17,16,0,0, /11-4,0,0,0,-4,0,0,0,0,0,0,0, /1219,0,0,0,0,0,20,0,0,20,0,0, /13-8,0,0,0,0,0,-8,21,0,0,0,0, /14-12,0,0,0,0,-0,-12,-12,0,0,-12,0, /150,0,0,15,0,0,0,0,17,16,0,0, /16-13,0,0,0,0,-0,-13,-13,0,0,-1

24、3,0, /17-10,0,0,0,0,-0,-10,-10,0,0,-10,0, /180,0,0,-6,0,0,0,0,0,0,0,-6, /490,0,0,15,0,0,0,0,17,16,0,0, /200,0,0,15,0,0,0,0,17,16,0,0, /210,0,0,0,0,0,20,0,0,25,0,0, /22-7,0,0,0,0,0,-7,21,0,0,-7,0, /23-9,0,0,0,0,0,-9,-9,0,0,-9,0, /24-11,0,0,0,0,0,-11,-11,0,0,-11,0,; /25int GOTO266=1,5,0,2,0,0, /00,0,0

25、,0,0,0, /10,0,0,0,0,0, /20,0,0,0,0,0, /30,0,0,0,0,0, /40,0,0,0,0,0, /50,0,0,0,0,0, /60,0,0,0,0,0, /70,0,0,0,0,0, /80,0,0,0,0,0, /90,0,0,0,0,0, /100,0,13,0,14,18, /110,0,0,0,0,0, /120,0,0,0,0,0, /130,0,0,0,0,0, /140,0,0,0,0,0, /150,0,22,0,14,18, /160,0,0,0,0,0, /170,0,0,0,0,0, /180,0,0,0,0,0, /190,0,

26、0,0,23,18, /200,0,0,0,0,24, /210,0,0,0,0,0, /220,0,0,0,0,0, /230,0,0,0,0,0, /240,0,0,0,0,0; /25void initVNSTR() /初始化非终结符,为语义分析服务 / 0 1 2 3 4 5 6for(int v=0;FA2v!=0;v+) / M S D A E T F Vv.name=FA2v;string newtemp() /生成中间变量string str=T;return str+(+ch);void store_2(string p,string u,int q) /存储二元式 if(p

27、=id)|(p=num) /存储变量和数字Bcon.name=p;Bcon.value2=q;con+; /二元式的个数 else /其他二元式Bcon.name=p; Bcon.value1=u; con+;void initbuff() /初始化buff,;号后加# int id,id;# id=num;# id=id*id+id;# int i,j=0;for(i=0,j=0;Bi.name!=0;i+,j+)if(Bi.name=;) buffj=Bi.name;B1j.name=Bi.name;B1j.value1=Bi.value1;B1j.value2=Bi.value2;buf

28、fj+1=#;B1j+1.name=#;j+;elsebuffj=Bi.name;B1j.name=Bi.name;B1j.value1=Bi.value1;B1j.value2=Bi.value2;void display_two() /从结构体中输出存储二元式cout二元式如下:endl;for(int i=0;Bi.name!=0;i+)if(Bi.name=id)|(Bi.name=num) /输出变量和数字cout(Bi.name,Bi.value2)endl;else /其他二元式cout(Bi.name,Bi.value1)=a&s=A&s=Z)|(s=0)b=b+s;s=fge

29、tc(fp);i+;bi=0; /单词结束i=0; while(i14) /保留字if(arri=b) store_2(b,NULL,-1);if(s!=EOF) back();return;else i+;/查标识符表if(i=14)for(;k=M)WM.name=b;store_2(id,0,M); M+;if(s!=EOF)back();void reg_num(char s) /识别实数string n;int i=1;n=n+s;s=fgetc(fp);while(s=0)|s=.|s=e|s=+|s=-)if(s=+|s=-) n=n+s; s=fgetc(fp); i+;if(

30、s47) n=n+s;else back();ni-1= ;elsen=n+s; s=fgetc(fp); i+;ni=0; i=0;while(i=N) DN.name=n;store_2(num,0,i); N+;if(s!=EOF)back();void reg_div(char s) /识别除号/和注释s=fgetc(fp);if(s=/) s=fgetc(fp); while(s!=n&s!=EOF) s=fgetc(fp);if(s=EOF) return;if(s=n)z+;else if(s=*)char c2= ;s=fgetc(fp);while(c2!=*/)if(s=*

31、)c0=s; s=fgetc(fp);c1=s;if(c0=*&c1=/)break; else s=fgetc(fp);else if(s=)store_2(/=,NULL,-1);elsestore_2(/,NULL,-1);if(s!=EOF)back();void cf_error() /输出错误信息到屏幕int i=0;cout词法分析完成，共计e个错误n;for(i=0;ie;i+) cout第ai:s=fgetc(fp); if(s=) store_2(rlop,=,-1); else back(); store_2(rlop,-1); break;case :s=fgetc(f

32、p); if(s=) store_2(rlop,=,-1); else back(); store_2(rlop,-1); break;case %:s=fgetc(fp); if(s=) store_2(%=,NULL,-1); else back(); store_2(%,NULL,-1); break;case =:s=fgetc(fp); if(s=) store_2(rlop,=,-1); else back(); store_2(=,NULL,-1); break;case !:s=fgetc(fp); if(s=) store_2(rlop,!=,-1); else back(); store_2(not,NULL,-1); break;