编译原理-简单编译器课程设计报告(共28页).doc
精选优质文档-倾情为你奉上信息科学与工程学院课程设计任务书 题目： 一个简单编译器的设计与分析 姓 名： 学 号： 专业班级： 课 程： 编译原理 指导教师： 职称： 讲 师 完成时间： 2011年 12 月-2011年 12 月枣庄学院信息科学与工程学院制2011年12 月20日课程设计任务书及成绩评定课程设计的任务和具体要求在理解编译原理相关理论的基础上，要求用C或C+语言描述及上机调试，实现一个小编译器（包括符号表的构造，词法分析，语法分析，语义分析，目标代码生成等重要子程序，其中词法分析、语法分析及语义分析功能必须完成），使学生将理论与实际应用结合起来，受到软件设计等开发过程的全面训练，从而提高学生软件开发的能力。指导教师签字： _ 日期： 指导教师评语成绩：_ 指导教师签字： 日期： 课程设计所需软件、硬件等硬件环境：WindowsXP/Win7操作系统 软件环境：Microsoft visual C+6.0课程设计进度计划起至日期工作内容备注2011-12-01052011-12-06102011-12-1116查找资料理清思路，编写程序完善程序，编辑文档参考文献、资料索引序号文献、资料名称编著者出版单位【1】 程序设计语言编译原理 陈火旺 李春林 国防工业出版社【2】 数据结构 严蔚敏 清华大学出版社【3】 C+程序设计 吴乃林 况迎辉 高等教育出版社【4】 C语言程序设计 谭浩强 清华大学出版社【5】 程序设计语言编译原理 陈火旺、刘春林等 国防工业出版社目录一、摘要编译程序的工作过程一般可以分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。每一个阶段在功能上是相对独立的，它一方面从上一个阶段获取分析的结果来进行分析，另一方面由将结果传递给下一个阶段。由编译程序的五个阶段就对应了编译系统的结构。其中词法分析器利用超前搜索、状态转换等方法，将源程序转化成为一个一个的单词符号二元式。一般程序语言的单词符号包括关键字、运算符、常数、标识符和界符。语法分析器将这些单词符号作为输入，对它进行语法分析。语法分析分为两种方法：自上而下分析法和自下而上分析法。针对不同程序语言的语法规则可以采取不同的分析方法，当然两种方法也可以同时使用。语法分析器把语法单元作为输入供语义分析器使用。一般的语义分析器主要采用的是语法制导方法，即在语法分析的同时进行语法分析，并产生一定的语义动作，来生成中间代码。上面三个过程可以与硬件无关，而接下来的优化器和目标代码生成器是针对某一种处理器而言的。代码优化是将语义分析生成的中间代码进行优化，产生执行效率更高的代码。目标代码生成器最终生成可以在某种机器上运行的机器语言或者汇编语言。在整个编译过程中还包括对表格的操作和对错误的处理，这些也都是非常重要的环节。下图给出了编译系统的结构框表格管理出错处理单词符号语法单元中间代码中间代码目标代码语法分析器语义分析与中间代码生成器优化器目标代码生成器词法分析器图 二、总体设计方案及主要设计原理2.1、单词符号及种别表示单词符号种别编码单词值main1int 2float3double4char5if 6else 7do8while9l(l|d)*10内部字符串 ( +|-| ) d*(.dd* | )( e ( +|-| ) dd*|) 20二进制数值表示=21+22- 23* 24/ 25(26)272829,30;31>32>=33<34<=35=36!=372.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<关系运算符> := <|<=|>|>=|=|!=2.3、主要算法2.3.1、词法分析主要算法这部分对源文件进行分析，允许/* */注释。从源文件依次读取字符，对字符进行分析，组成字符串、数字、关系符等固定含义的token符，并把它们添加到token链中，如果遇到非法字符报错并退出程序。2.3.2、语法分析主要思想这部分对Token链进行分析，利用自底向上的分析方法，构建SLR（1）分析表的过程是手工完成的。语法分析的同时构建语法树，移进时创建叶子，规约时创建节点。2.3.3、语义分析主要分析这部分对语法树从左到右进行遍历，节点记录了规约式的编号，遍历到节点时就进行相应处理。语义分析主要检查变量、函数是否被定义或重定义，同时产生四元式。三、源程序代码#include<stdio.h>#include<string.h>#include<math.h>#include<stdlib.h>char 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;i<nextq;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<=37)&&(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<=37)&&(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填进四元式circle的第四分量sprintf(fourComcircle.result,"%d",t);circle=w; /w记录的是链条上下一个四元式，移动！return;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后边void emit(char *res,char *num1,char *op,char *num2)strcpy(fourComnextq.result,res);strcpy(fourComnextq.arg1,num1);strcpy(fourComnextq.opera,op);strcpy(fourComnextq.arg2,num2);nextq+;void scanner() sum=0; decimal=0; m=0; for(n=0;n<8;n+) tokenn=NULL; ch=progp+; /从prog中读出一个字符到ch中 while(ch=' '|ch='n') /跳过空字符（无效输入） ch=progp+; if(ch>='a')&&(ch<='z')|(ch>='A')&&(ch<='Z') /ch是字母字符 while(ch>='a')&&(ch<='z')|(ch>='A')&&(ch<='Z')|(ch>='0')&&(ch<='9') tokenm+=ch; /ch=>token ch=progp+; /读下一个字符 tokenm+='0' p-; /回退一格 syn=10; /标识符 /如果是"begin","if","then","while","do","end"标识符中的一个 for(n=0;n<9;n+) if(strcmp(token,rwtabn)=0) syn=n+1; break; else if(ch>='0')&&(ch<='9') IsNum: if(isSignal=1) /tokenm+='-' while(ch>='0')&&(ch<='9') sum=sum*10+ch-'0' /ch中数字本身是当做字符存放的 ch=progp+; if(ch='.') isDecimal=1; ch=progp+; count=0; /之前忘了清零,123.123+123.123#两个浮点数就无法识别 while(ch>='0')&&(ch<='9') /pow(x,y)计算x的y次幂 temp=(ch-'0')*pow(0.1,+count); decimal=decimal+temp; /AddToDec(); ch=progp+; sum=sum+decimal; if(ch='e'|ch='E') isExp=1; ch=progp+; if(ch='-') isNegative=1; ch=progp+; while(ch>='0')&&(ch<='9') /指数 index=index*10+ch-'0' ch=progp+; /10的幂 /123e3代表123*10(3) /sum=sum*pow(10,index);是错误的 if(isNegative) sum=sum*pow(0.1,index); else sum=sum*pow(10,index); if(isSignal=1)sum=-sum;isSignal=0; p-; syn=20; else switch(ch) case '<': m=0; tokenm+=ch; ch=progp+; if(ch='=') syn=35; tokenm+=ch; else syn=34; p-; break; case '>': m=0; tokenm+=ch; ch=progp+; if(ch='=') syn=33; tokenm+=ch; else syn=32; p-; break; case '=': m=0; tokenm+=ch; ch=progp+; if(ch='=') syn=36; tokenm+=ch; else syn=21; p-; break; case '+':temp2=progp;tokenm+=ch;if(temp2>='0')&&(temp2<='9')&&(repeat=1)isSignal=2;ch=progp+;repeat=0;goto IsNum;if(temp2='+')|(temp2='-')&&(repeat=0) /如果重复出现符号，才将后边的+，-视为正负号repeat=1;/ch=progp+;syn=22;break;case '-':temp2=progp;tokenm+=ch;if(temp2>='0')&&(temp2<='9')&&(repeat=1)isSignal=1;ch=progp+; /读“-”下一个字符repeat=0;goto IsNum; /转到数字的识别if(temp2='+')|(temp2='-')&&(repeat=0) /如果重复出现符号，才将后边的+，-视为正负号repeat=1; /预言会重复/ch=progp+; /读下一个字符syn=23;break; case '*':temp2=progp;tokenm+=ch;if(temp2='+')isSignal=2;repeat=1;else if(temp2='-')isSignal=1;repeat=1;syn=24;break; case '/': syn=25; tokenm+=ch; break; case '(':temp2=progp;tokenm+=ch;if(temp2='+')isSignal=2;repeat=1;else if(temp2='-')
