编译原理课程设计.doc

枣 庄 学 院计算机科学系课程设计任务书 题目： 一个简单编译器的设计与分析 学 号： 姓 名： 专 业： 计算机科学与技术 课 程： 程序设计语言 编译原理 指导教师： 王 艳 秋 职称： 讲 师 完成时间： 2010年 12月- 2011 年 01月 枣庄学院计算机科学系制 2010年12 月20日课程设计任务书及成绩评定课程设计的任务和具体要求一 任务：（1）设计符号表确定符号表的组织方式，一般应包括名字栏和信息栏，其中名字栏作为关键字。要考虑能够存储有关名字的信息，并可以高效地完成如下操作：a.查找：根据给定的名字，在符号表中查找其信息。如果该名字在符号表中不存在，则将其加入到符号表中，否则返回指向该名字的指针；b.删除：从符号表中删除给定名字的表项。（2）设计词法分析器设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括：a. 具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；b. 能够拼出语言中的各个单词；c. 将拼出的标识符填入符号表；d. 返回（种别码， 属性值）。（3）语法分析器要求用预测分析法、递归下降分析法、算符优先分析法、SLR分析法（几种方法任选），实现对表达式、各种说明语句、控制语句进行语法分析。（4）中间代码与目标代码生成部分进行原理性分析,给出可行性报告。3、样本语言样本语言为C-语言(见附录)，其中基本的语句要求必须实现，其余部分可根据自己的实际情况选择实现。二 要求：各函数和过程应有框图描述，有功能说明，有入口和出口参数说明指导教师签字： 日期： 指导教师评语成绩： 指导教师签字： 日期： 课程设计所需软件、硬件：实验环境：WIN-TC、windows操作系统硬件：电脑一台参考文献、资料索引序号文献、资料名称编著者出版单位1程序设计语言编译原理陈火旺国防工业出版社2编译原理吕映芝、张素琴、蒋维杜清华大学出版社3编译原理Alfred V.Aho机械工业出版社 目录课程设计要求.5总体设计思想61.所有函数一览92.void emit(char *res,char *num1,char *op,char *num2)103.char *newTemp()104.int merge(int p1,int p2)105.void backpatch(int p,int t)116.void fuzhi()117.void tiaojian(int *nChain)128.void xunhuan()13程序运行结果15编译器使用说明17心得与体会17源程序清单18 课设要求用C语言对下述文法和单词表定义的语言设计编制一个编译器。（1）单词符号及种别表单词符号种别编码单词值main1int 2float3double4char5if 6else 7do8while9l(l|d)*10内部字符串 ( +|-| ) d*(.dd* | )( e ( +|-| ) dd*|) 20二进制数值表示=21+22- 23* 24/ 25(26)272829,30;3132=3334=35=36!=37（2）语法结构定义 := main() := /程序用括号括起来:=;:=|:=ID= /赋值语句用”=”号:=if /条件怎么没有括号，囧（自己加1个）:=do while := /没有布尔运算，还算简单 := +|- := *|/ :=ID|num|()num:= ( +|-| ) 数字*(.数字数字* | )( e ( +|-| ) 数字数字*|)ID:=字母(字母|d数字)*字母:=a|b|c|z|A|B|C|Z数字:=0|1|2|9 := |=|=|!=总体设计思想采用递归下降（自上而下）的语法制导翻译法。详细算法设计在前三次试验的基础上改进。词法分析程序 语法分析程序 语义分析程序 编译器。不断完善，不断改进。渐变的过程。流程框图图 I 主函数示意图图 II 递归下降分析程序示意图是否为main？调用scanner是否为（？调用scanner是否为）？调用scanner调用语句块分析函数staBlock出错处理否否否图 III 语句块分析示意图是否为 ？调用scanner调用语句串分析函数staString调用scanner是否为 ？出错处理否否调用语句分析函数sta回溯，调用backpatch是否为 ; ？调用scanner调用语句分析函数sta否出错处理图 IV 语句串分析示意图图 V 语句分析示意图调用赋值语句分析函数fuzhi是否为 字符串？是否为 if ？调用条件语句分析函数tiaojian是否为 do ？调用循环语句分析函数xunhuan函数相关说明1. 所有函数一览void scanner(); /扫描void lrparser(); void staBlock(int *nChain); /语句块void staString(int *nChain); /语句串void sta(int *nChain); /语句void fuzhi(); /赋值语句void tiaojian(int *nChain); /条件语句void xunhuan(); /循环语句char* E(); /Expresiion表达式char* T(); /Term项char* F(); /Factor因子char *newTemp(); /自动生成临时变量void backpatch(int p,int t); /回填int merge(int p1,int p2); /合并p1和p2void emit(char *res,char *num1,char *op,char *num2); /生成四元式2. void emit(char *res,char *num1,char *op,char *num2)该函数的功能是生成一个三地址语句送到四元式表中。void emit(char *res,char *num1,char *op,char *num2)strcpy(fourComq.result,res);strcpy(fourComq.arg1,num1);strcpy(fourComq.opera,op);strcpy(fourComq.arg2,num2);q+;四元式表中的结构如下：structchar result10; /字符串（字符数组）char arg110; /操作数1char opera10; /运算符char arg210; /操作数2fourCom20; /结构体数组3. char *newTemp()该函数的功能是会动一个新的临时变量，临时变量名产生的顺序是T1,T2,T3,.char *newTemp()char *p;char varTemp10;p=(char *)malloc(10);kk+;itoa(kk,varTemp,10); /整数转换为字符串strcpy(p+1,varTemp);p0=T; /字符串前加T，便于识别return p;4. int merge(int p1,int p2)该函数的功能是将以P1,P2为链首的两条链合并成一条链，返回时的函数值作为合并后的链首。int merge(int p1,int p2) /合并p1和p2char circle,nResult;if(p2=0)nResult=p1;elsenResult=circle=p2;while(atoi(fourComcircle.result) /四元式第四个分量不为0circle=atoi(fourComcircle.result); /strcpy(fourComcircle.result,p1);sprintf(fourComcircle.result,%s,p1);/目的是用p1的值覆盖0return nResult; /p2是头，p1覆盖0，接在p2后边5. void backpatch(int p,int t)该函数的功能是把P所链接的每个四元式的第四区段（result段）都回填t。void backpatch(int p,int t) int w,circle=p;while(circle) /circle不为0的时候w=atoi(fourComcircle.result); /四元式circle第四分量内容/strcpy(fourComcircle.result,t); /把t填进四元式circle的第四分量sprintf(fourComcircle.result,%d,t);circle=w; /w记录的是链条上下一个四元式，移动！return;6. void fuzhi()该函数的功能是对赋值语句进行分析。void fuzhi() /赋值语句只有1个操作数char res10,num10; /num操作数if(syn=10) /字符串strcpy(res,token); /结果scanner();if(syn=21) /=scanner();strcpy(num,E();emit(res,num,=,);elseprintf(缺少=号n);7. void tiaojian(int *nChain)该函数的功能是对条件语句进行分析。/-if()void tiaojian(int *nChain)char res10,num110,num210,op10;int nChainTemp;/-if(syn=6) /ifscanner();/strcpy(num1,E();if(syn=26) /(scanner();strcpy(num1,E();if(syn=32) switch(syn)case 32:strcpy(op,);break;case 33:strcpy(op,=);break;case 34:strcpy(op,);break;case 35:strcpy(op,=);break;case 36:strcpy(op,=);break;case 37:strcpy(op,!=);break;default:printf(error);scanner();strcpy(num2,E();strcat(num1,op);strcat(num1,num2);/nfc=nextq+1;ntc=nextq; /记住if语句位置emit(0,if,num1,goto); nfc=nextq; /if中表达式为假emit(0,goto);/第一个0已回填backpatch(ntc,nextq); /ntc链接的所有四元式都回填nextqif(syn=27) /)scanner();staBlock(&nChainTemp); /语句块*nChain=merge(nChainTemp,nfc);8. void xunhuan()该函数的功能是对循环语句进行分析。/:=do while void xunhuan()char res10,num110,num210,op10;int nChainTemp;if(syn=8) /donnc=nextq; /记住if语句位置，emit之后nextq就变了/emit(0,if,num1,goto); scanner();staBlock(&nChainTemp); /语句块if(syn=9) /whilescanner();if(syn=26) /(scanner();strcpy(num1,E();if(syn=32) switch(syn)case 32:strcpy(op,);break;case 33:strcpy(op,=);break;case 34:strcpy(op,);break;case 35:strcpy(op,=);break;case 36:strcpy(op,=);break;case 37:strcpy(op,!=);break;default:printf(error);scanner();strcpy(num2,E();strcat(num1,op);strcat(num1,num2);nnb=nextq;emit(0,if,num1,goto); backpatch(nnb,nnc);nna=nextq;emit(0,goto);backpatch(nna,nextq);if(syn=27) /)scanner();程序运行结果图 VI 赋值语句的分析图 VII 条件语句的分析图 VIII 循环语句的分析图 IX 综合编译器使用说明程序提示用户输入字符串“Please input your source string:”，用户输入字符串并以“#”号结束。回车后，程序显示运行结果。心得与体会刚拿到课设题目的时候，感觉很难，没有头绪。虽然之前实验时候，词法分析程序和语法分析程序的代码都是自己一个一个敲的。但是记得那时的语法分析程序用的是递归下降分析法，而且只判断输入串是否是文法的句子（输出只有简单的success或者error）。课设的要求呢？要加上语义分析，而且要输出四元式。好像语义分析的部分，我一点印象也没有了，老师那一部分上得有点快。运动会3天假，时间全用来啃课本了。“语义分析与中间代码生成”，我又一点一点的看。3天时间，终于可以写出语义程序了。这是课设的第1个里程碑。采用递归下降的语法制导翻译法，实现了对赋值表达式的语义分析，并生成四元式。但是后来发现，更难的东西在后边。程序语句有3种：赋值语句，条件语句，循环语句。而赋值语句的翻译，恰恰是最简单的。对于赋值语句的翻译，课本上有详细的讲解，有代码的简单举例。而对于条件语句（ifelse）和循环语句（dowhile），课本讲解不那么详细，没有代码举例，上课时候我也没太理解老师所讲解的。特别是其中链nChain的概念，一直看不懂。因为这个困难，课设被我搁置了3天。再后来利用上机的时间，请教了一下老师和另外一个同学，发现课本后给的样例程序是错的，而且错得一塌糊涂。只好自己写，写，写。然后就是课设的第2个里程碑。实现了对条件语句（if语句）的分析，并生成四元式。接下来又是开发停滞的一段时间，直到11月18日。熟悉了一下原先写的代码，然后开始继续后边的部分。迎来了课设的第3个里程碑。实现了对循环语句（while语句）的分析，并生成四元式。而且好像没有预期中困难，可能是有条件语句的铺垫吧。他们的处理方法其实很类似，也是emit+backpatch+merge。而且由于老师给的语法中没有布尔表达式，所以很多merge的工作也可以省略了，嘿嘿。最后一步就是整合，系统测试，书写文档了。个人认为这次课设的机会非常宝贵，加深了我对编译器处理语言的过程的理解。我想，作为学软件的学生，不应该只会用Java，或者C+，或者C#。一门高级语言其实学起来是很容易的，而在校期间，这些计算机基础课程一定要学好！才能为将来打好基础。源程序清单/*编译器*/*编译原理*/*计算机科学系*/*大当家的*/*#include#include#include#includechar prog80; /存放所有输入字符 char token8; /存放词组 char ch; /单个字符 int syn,p,m,n,i; /syn:种别编码 double sum; int count; int isSignal; /是否带正负号(0不带，1负号，2正号）int isError;int isDecimal; /是否是小数 double decimal; /小数 int isExp; /是否是指数 int index; /指数幂 int isNegative; /是否带负号 double temp; int temp2;int repeat; /是否连续出现+,-int nextq;int kk; /临时变量的标号int ntc,nfc,nnc,nnb,nna;char *rwtab9=main,int,float,double,char,if,else,do,while; structchar result10; /字符串（字符数组）char arg110;char opera10;char arg210;fourCom20; /结构体数组void scanner(); /扫描void lrparser(); void staBlock(int *nChain); /语句块void staString(int *nChain); /语句串void sta(int *nChain); /语句void fuzhi(); /赋值语句void tiaojian(int *nChain); /条件语句void xunhuan(); /循环语句char* E(); /Expresiion表达式char* T(); /Term项char* F(); /Factor因子char *newTemp(); /自动生成临时变量void backpatch(int p,int t); /回填int merge(int p1,int p2); /合并p1和p2void emit(char *res,char *num1,char *op,char *num2); /生成四元式void main()p=0;count=0;isDecimal=0;index=0;repeat=0;kk=0;printf(nPlease input your source string:n);doch=getchar();progp+=ch;while(ch!=#);p=0;isError=0;scanner();lrparser();for(i=1;inextq;i+) /循环输出四元式printf(n%dt,i);printf(%5s %5s %5s t%5s )n,fourComi.arg1,fourComi.opera,fourComi.arg2,fourComi.result);void lrparser()int nChain;nfc=ntc=1;nextq=1;if(syn=1) /mainscanner();if(syn=26) /(scanner();if(syn=27) /)scanner();staBlock(&nChain);elseprintf(缺少右括号n);else printf(缺少左括号n);elseprintf(缺少mainn);/ := void staBlock(int *nChain) /语句块if(syn=28) /scanner();staString(nChain);/backpatch(*nChain,nextq);if(syn=29) /scanner(); /读下一个elseprintf(缺少号n);elseprintf(缺少号n);/:=;void staString(int *nChain) /语句串sta(nChain);backpatch(*nChain,nextq);while(syn=31) /;scanner();sta(nChain);/backpatch(*nChain,nextq-1);void sta(int *nChain) /语句if(syn=10)fuzhi();/*nChain=0;else if(syn=6) /iftiaojian(nChain);else if(syn=8) /doxunhuan();/-if()void tiaojian(int *nChain)char res10,num110,num210,op10;int nChainTemp;/-if(syn=6) /ifscanner();/strcpy(num1,E();if(syn=26) /(scanner();strcpy(num1,E();if(syn=32) switch(syn)case 32:strcpy(op,);break;case 33:strcpy(op,=);break;case 34:strcpy(op,);break;case 35:strcpy(op,=);break;case 36:strcpy(op,=);break;case 37:strcpy(op,!=);break;default:printf(error);scanner();strcpy(num2,E();strcat(num1,op);strcat(num1,num2);/nfc=nextq+1;ntc=nextq; /记住if语句位置emit(0,if,num1,goto); nfc=nextq; /if中表达式为假emit(0,goto);/第一个0已回填backpatch(ntc,nextq); /ntc链接的所有四元式都回填nextqif(syn=27) /)scanner();staBlock(&nChainTemp); /语句块*nChain=merge(nChainTemp,nfc);/:=do while void xunhuan()char res10,num110,num210,op10;int nChainTemp;if(syn=8) /donnc=nextq; /记住if语句位置，emit之后nextq就变了/emit(0,if,num1,goto); scanner();staBlock(&nChainTemp); /语句块if(syn=9) /whilescanner();if(syn=26) /(scanner();strcpy(num1,E();if(syn=32) switch(syn)case 32:strcpy(op,);break;case 33:strcpy(op,=);break;case 34:strcpy(op,);break;case 35:strcpy(op,=);break;case 36:strcpy(op,=);break;case 37:strcpy(op,!=);break;default:printf(error);scanner();strcpy(num2,E();strcat(num1,op);strcat(num1,num2);nnb=nextq;emit(0,if,num1,goto); backpatch(nnb,nnc);nna=nextq;emit(0,goto);backpatch(nna,nextq);if(syn=27) /)scanner();void fuzhi() /赋值语句只有1个操作数char res10,num10; /num操作数if(syn=10) /字符串strcpy(res,token); /结果scanner();if(syn=21) /=scanner();strcpy(num,E();emit(res,num,=,);elseprintf(缺少=号n);char* E() /Expression表达式char *res,*num1,*op,*num2;res=(char *)malloc(10);num1=(char *)malloc(10);op=(char *)malloc(10);num2=(char *)malloc(10);strcpy(num1,T();while(syn=22)|(syn=23) /+ -if(syn=22) /+strcpy(op,+);elsestrcpy(op,-);scanner();strcpy(num2,T();strcpy(res,newTemp();emit(res,num1,op,num2);strcpy(num1,res);return num1;char* T() /Term项char *res,*num1,*op,*num2;res=(char *)malloc(10);num1=(char *)malloc(10);op=(char *)malloc(10);num2=(char *)malloc(10);strcpy(num1,F();while(syn=24)|(syn=25) /* /if(syn=24) strcpy(op,*);elsestrcpy(op,/);scanner();strcpy(num2,F();strcpy(res,newTemp();emit(res,num1,op,num2);strcpy(num1,res);return num1;char* F() /Factor因子char *res;res=(char *)malloc(10);if(syn=10) /字符串strcpy(res,token);scanner();else if(syn=20) /二进制数itoa(int)sum,res,10); /整数转换为字符串scanner();else if(syn=26) /(scanner();res=E();if(syn=27) /)scanner();else isError=1;elseisError=1;return res;char *newTemp()char *p;char varTemp10;p=(char *)malloc(10);kk+;itoa(kk,varTemp,10);strcpy(p+1,varTemp);p0=T;return p;/将p所链接的每个四元式的第四个分量都回填tvoid backpatch(int p,int t) int w,circle=p;while(circle) /circle不为0的时候w=atoi(fourComcircle.result); /四元式circle第四分量内容/strcpy(fourComcircle.result,t); /把t填进四元式c