编译原理课程设计报告

1、精选优质文档-倾情为你奉上 课 程 设 计 报 告 设计题目：一个简单文法的编译器的设计与实现 班 级：计算机1206班 组长学号：2012XXX 组长姓名：XXX 指导教师：XXX 设计时间：2014年12月 设计分工 组长学号及姓名：2012XXX XXX 分工：1）读取源文件进行词法分析 2）进行LL(1)分析生成分析表 3）设计顶层自动机将源程序分段 4）生成可执行的汇编程序 组员1学号及姓名：2012XXXXXX 分工：1）设计第二层自动机处理程序片段 2）生成中间语言四元式 3）源程序错误处理 组员2学号及姓名：2012XXXXXX 分工：1）设计第三层自动机处理复合表达式 2）设

2、计带动作的LL(1) 文法 3）源程序错误处理摘 要编译原理课程具有很强的理论性和实践性，是计算机专业的一门非常重要的专业基础课程，在系统软件中也是占有十分重要的地位。本次课程设计我们是在Visual C+的平台上应用了词法分析、语法分析、语义分析、中间语言生成以及目标语言生成的知识设计了一个简单的编译器前端。其中设计了一个简单的有限自动机来扫描源程序即进行语法分析，并生成了关键字表、标志符表、界符表、常数表和Token串；设计了一个LL(1)文法和一个带动作的文法来实现语法分析，并生成了Select集和LL(1)分析表；采用了四元式序列的设计来生成中间语言；通过汇编语言设计来生成目标语言。最

3、后为了使该编译器更加完善，我们设计了简单的的错误检查机制，能够对源程序进行比较全面的错误检查同时也能够指出错误出现的大致位置，增强了该编译器的健壮性。关键字：编译器，前端，有限自动机，LL(1)文法，汇编语言，错误处理目 录 摘要31、概述52、课程设计任务及要求52.1设计任务52.2设计要求63、算法与数据结构63.1词法分析器的算法63.2 语法分析器的算法12 3.2.1 LL(1)文法设计算法12 3.2.2递归下降子程序设计算法193.3中间语言生成器算法203.4处理复合表达式算法24 3.5目标语言生成器算法30 3.6数据结构394、程序设计与实现394.1编译程序设计与实现

4、39 4.2程序实验结果39 4.2.1待测源程序39 4.2.2词法分析结果40 4.2.3语法分析结果41 4.2.4中间语言生成结果42 4.2.5目标语言生成结果43 4.2.6程序错误处理结果445、参考文献441、概述本次课程设计的编译程序主要包括了词法分析器、语法分析器、中间代码生成器和目标代码生成器四部分，编译程序的输出结果包括了词法分析后的关键字表、界符表、标识符表和Token串，语法分析后的Select集和LL(1)分析表；中间代码生成器产生的四元式序列。最后除了完成设计所要求的内容之外，我们还做了一些扩展例如：设计了目标代码生成器来生成可执行的汇编程序；还设计了错误检查机

5、制来查找源程序的错误并指出错误产生的大致位置。词法分析是编译程序的第一步操作，它的任务是：从左至右扫描源程序的字符串，按照一定的词法规则识别出一个个正确的字符，并转换成该字符相对应的Token码，最终生成一个完整的Token串以供语法分析使用。由此可知，词法分析是整个编译程序的基础，而执行词法分析的一系列操作的就是词法分析器。语法分析是编译程序的第二步操作也是编译程序的核心部分，其主要任务是：分析语法内容，确定语法结构同时生成Select集和LL(1)分析表。中间代码和目标代码的生成是对源程序的进一步操作，其任务是：根据词法分析产生的Token串和语法分析确定的语法结构来生成中间语言四元式和目

6、标语言汇编语言程序。2、课程设计任务及要求 2.1设计任务 一个简单文法的编译器前端的设计与实现l 定义一个简单程序设计语言文法（包括变量说明语句、算术运算表达式、赋值语句；扩展包括逻辑运算表达式、If语句、While语句等）；l 扫描器设计实现；l 语法分析器设计实现；l 中间代码设计；l 中间代码生成器设计实现。 l 目标代码生成器设计实现 2.2设计要求l 给出一个源程序文件，作为编译器前端的输入l 输出相关编译阶段的运行结果l 词法分析阶段：l 生成Token序列；l 生成关键字表、界符表、符号表系统。l 中间代码生成阶段：l 生成四元式序列；l 生成符号表系统。3、 算法与数据结构

7、3.1词法分析器的算法 1）一个简单有限自动机(扫描器)的设计：n?d-dd.dd-=-#-d 其中： (字母)，d(数字)，#(源程序结束符) (2)？(空格，回车，换行)需要滤掉 (3)(泛指单词的后继附) (4)(表示省略了其他界符的处理)2）一个简单词法分析器设计：开始结束调用识别器关键字/标识符算术常数结束符#查KT表查到查填IT表查填CT表常数处理C.TOKEN查PT表P.TOKENI.TOKENK.TOKENyn查到ere:非法界符ynyynnny 算法实现如下：Void main() /词法分析部分代码 char p10;string TOKEN;string Source;s

8、tring temp;FILE* fp;fp=fopen("D:MySourceFile.txt","r");if(!fp) Source="Cannot open file"elseint i;char c;while(!feof(fp)c=fgetc(fp);Source+=c;fclose(fp);for(i=0;i<Source.size();i+)if(Sourcei=13|Sourcei=9|Sourcei=10|Sourcei=-1)Source.replace(i,1," ");Source+

9、='#'cout<<"处理后源程序n"<<Source<<endl<<endl;initKTPT();int i,j;for(i=0;i<Source.size();i+)switch(kindofchar(Sourcei)case 'e':cout<<"n非法字符!,位置:"<<i<<"错误代码"<<Sourcei<<endl<<endl;for(int k=0;k<=i

10、;k+) cout<<Sourcek;exit(0);case 's':break;case 'd':temp+=Sourcei;for(j=1;Sourcei+j='.'|kindofchar(Sourcei+j)='d'j+) temp+=Sourcei+j;i=i+j-1;if(inCT(temp)=-1)temp="N "+temp;CT.push_back(temp);TOKEN+="<CT,"itoa(inCT(temp),p,10);TOKEN+=p;TOKE

11、N+=">"temp=""break;case 'w':temp+=Sourcei;for(j=1;kindofchar(Sourcei+j)='w'|kindofchar(Sourcei+j)='d'|Sourcei+j='_'j+) temp+=Sourcei+j;i=i+j-1;if(inKT(temp)!=-1)TOKEN+="<KT,"itoa(inKT(temp),p,10);TOKEN+=p;TOKEN+=">"temp

12、=""break;if(inIT(temp)=-1) IT.push_back(temp);TOKEN+="<IT,"itoa(inIT(temp),p,10);TOKEN+=p;TOKEN+=">"temp=""break;case 'f':temp+=Sourcei;if(kindofchar(Sourcei+1)='f'&&inPT(temp+Sourcei+1)>=0)temp+=Sourcei+1;i+;TOKEN+="<P

13、T,"itoa(inPT(temp),p,10);TOKEN+=p;TOKEN+=">"temp=""break;case '"':i+;for(j=0;Sourcei+j!='"'&&(i+j)<(Source.size()-1);j+)if(Sourcei+j=''&&Sourcei+j+1='"')temp+='"'j+;if(Sourcei+j=''&

14、&Sourcei+j+1=''')temp+='''j+;if(Sourcei+j=''&&Sourcei+j+1='')temp+=''j+;if(Sourcei+j=''&&Sourcei+j+1='0')temp+='0'j+;else temp+=Sourcei+j;if(i+j)>=(Source.size()-1)cout<<"未找到可匹配的双引号,位置:"<

15、;<i<<endl;for(int k=0;k<=i;k+) cout<<Sourcek;exit(0);i=i+j;if(inCT(temp)=-1)temp="S "+temp;CT.push_back(temp);TOKEN+="<CT,"itoa(inCT(temp),p,10);TOKEN+=p;TOKEN+=">"temp=""break;case ''':if(i+3)<(Source.size()-1)&&

16、Sourcei+1=''&&Sourcei+3=''')switch(Sourcei+2)case '':temp+=''break;case ''':temp+='''break;case '"':temp+='"'break;case '0':temp+="0"break;default:cout<<"错误的单引号使用(转义错误),位置:"

17、;<<i<<endl;for(int k=0;k<=i;k+) cout<<Sourcek;exit(0);i+=3;elseif(i+2)>=(Source.size()-1)cout<<"错误的单引号使用(越界),位置:"<<i<<endl;for(int k=0;k<=i;k+) cout<<Sourcek;exit(0);temp+=Sourcei+1;i+=2;if(inCT(temp)=-1)temp="C "+temp;CT.push_ba

18、ck(temp);TOKEN+="<CT,"itoa(inCT(temp),p,10);TOKEN+=p;TOKEN+=">"temp=""break;case '#':break;default:break;3.2语法分析器的算法首先介绍一下整个课程设计中我们使用到的一些文法。C-文件 -> void main ( ) C<-程序体àC -> Y<-语句-> Y -> S<-声明语句-> ; I<-语句后继->| Z<-赋值语句-

19、> ; I| V<-条件语句->N<-if后继->B I| W<-循环语句-> II->Y | 空S ->类型 标识符 声明后继类型 -> int|float|char声明后继 -> ，标识符 声明后继 | 空Z -> 标识符 = 表达式V -> if （ E ）C N->else C | 空W -> while （ 表达式 ）程序体E -> 详见rull.txt源文件。语法分析主要是对LL(1)文法和递归下降子程序的设计，其算法设计如下：3.2.1 LL(1)文法的设计1）算法原理如下：l 利用一

20、个分析表，登记如何选择产生式的知识；l 利用一个分析栈，记录分析过程；l 此分析法要求文法必须满足 LL(1)文法形式。# Z开始：栈 ; NEXT(w)2） 算法设计如下： 重复执行 、 ，直到栈中只剩 # 为止： （1） （2） 若 栈顶符=A 且 当前符 w=a 且 有产生式： Aàaa， 则 POP,PUSH(aa)R ; 若 栈顶符=a 且 当前符为a； 则 pop,NEXT(w); 否则，错误处理！#栈结束：；当前符 w= # （3）算法实现如下：void maketable()/需要参数指明所需文法/打开文件/switch()/根据参数选择文法FILE* fp=fope

21、n("D:/rull.txt","r");if(fp=NULL)cout<<"打开文件失败"<<endl;getchar();exit(0);/读取文件string source=""char readchar;doreadchar=fgetc(fp);source+=readchar;while(readchar!=EOF);fclose(fp);/cout<<"-source流-"<<endl<<source<<endl

22、;/检查/从source流中提取有效数据Vs=source3;Vn+=Vs;int i,j,k,l;string ps=""for(i=8;sourcei!=''i+) Vn+=sourcei;i+=4;for(;sourcei!=''i+) Vt+=sourcei;i+;while(sourcei!='')for(;sourcei!=' '&&sourcei!=''i+)ps+=sourcei;QRULL.push_back(ps);ps=""if(sour

23、cei=' ') i+;/拆分或符号string ps2=""int flag;for(i=0;i<QRULL.size();i+)flag=0;for(j=0;j<QRULLi.length();j+)if(QRULLij='|')flag=1;break;if(flag=0) continue;ps2+=QRULLi0;ps2+="->"for(j=0;QRULLij!='|'j+) ps+=QRULLij;for(j+;j<QRULLi.length();j+) ps2+=QR

24、ULLij;QRULLi=ps;QRULL.push_back(ps2);ps=""ps2=""cout<<"-有效四元产生式表-"<<endl;/检查for(i=0;i<QRULL.size();i+)/检查cout<<QRULLi<<' '/检查cout<<endl;/检查/从四元产生式转化为普通产生式ps=""for(i=0;i<QRULL.size();i+)k=0;ps=""for(j=0;j<

25、;QRULLi.size();j+)if(QRULLij!='') ps+=QRULLij;else j+=2;RULL.push_back(ps);cout<<"-有效普通产生式表-"<<endl;/检查for(i=0;i<RULL.size();i+)/检查cout<<RULLi<<' '/检查cout<<endl;/检查/检测直接左递归flag=0;for(i=0;i<RULL.size();i+)if(RULLi0=RULLi3) flag=1;if(flag=1

26、)system("cls");system("color CF");cout<<"检测到直接左递归文法,系统已停止运行，请改正产生式。"<<endl;getchar();exit(0);/产生SELECT表Vt+='#'MAXITERATE=RULL.size()*RULL.size();vector<string> SELECT;SELECT=Select();cout<<"-SELECT集-"<<endl<<"SE

27、LECT"<<endl;/检查for(i=0;i<SELECT.size();i+)/检查cout<<SELECTi<<endl;/检查SelectTable=new int*Vn.size();int* intp;for(i=0;i<Vn.size();i+)intp=new intVt.size();SelectTablei=intp;for(i=0;i<Vn.size();i+)for(j=0;j<Vt.size();j+) SelectTableij=-1;for(k=0;k<SELECT.size();k+)

28、for(l=2;l<SELECTk.length();l+)i=inVn(SELECTk0);j=inVt(SELECTkl);SelectTableij=k;cout<<"-SelectTable-"<<endl<<" "/检测for(i=0;i<Vt.size();i+) cout<<Vti<<' '/检测cout<<endl;/检测for(i=0;i<Vn.size();i+)/检测cout<<Vni<<' &#

29、39;/检测for(j=0;j<Vt.size();j+) cout<<SelectTableij<<' '/检测cout<<endl;/检测/进行选择集相交检测if(check()=0)system("cls");system("color CF");cout<<"选择集相交，该文法不是LL1文法，请修改产生式"<<endl;getchar();exit(0);vector<string> Select()int i;vector<s

30、tring> SELECT;string ps=""for(i=0;i<RULL.size();i+)ps=RULLi0;ps+=" "ps+=first(RULLi);SELECT.push_back(ps);/迭代器清零counter=0;return SELECT;string first(string rull)/cout<<"迭代次数"<<counter<<endl;/检测counter+;if(counter>MAXITERATE)system("cls&qu

31、ot;);system("color CF");cout<<"生成选择集时迭代次数过高，疑似出现递归死循环，系统已停止运行，请检查是否有语法错误"<<endl;cout<<"迭代次数上限暂设为产生式数量的平方。过多的迭代会损害设备，若没有语法错误，请简化语法树"<<endl;getchar();exit(0);int i,j;string pp;string res=""if(inVt(rull3)>=0) res=rull3;else if(inVn(rull

32、3)>=0) for(i=0;i<RULL.size();i+)pp=rull;if(RULLi0=pp3)pp=pp0;pp+="->"for(j=3;j<RULLi.size();j+) pp+=RULLij;for(j=4;j<rull.size();j+) pp+=rullj;res+=first(pp);else if(rull3='0') res+=follow(rull);elsesystem("cls");system("color CF");cout<<&qu

33、ot;产生式关键位置检测到非法字符，系统已停止运行。"<<endl;getchar();exit(0);return res;string follow(string rull)/cout<<"迭代次数"<<counter<<endl;/检测counter+;if(counter>MAXITERATE)system("cls");system("color CF");cout<<"生成选择集时迭代次数过高，疑似出现递归死循环，系统已终止运行，请检查是

34、否有语法错误"<<endl;cout<<"迭代次数上限暂设为产生式数量的平方。过多的迭代会损害设备，若没有语法错误，请简化语法树"<<endl;getchar();exit(0);vector<string> p;string res;string pp=""string t=""int i,site,j;if(rull0=Vs) res+='#'for(i=0;i<RULL.size();i+)pp=""for(j=3;j<RU

35、LLi.length();j+) pp+=RULLij;pp+='0'site=pp.find(rull0,0);while(site<pp.size()site=pp.find(rull0,site);if(site=-1) break;t=RULLi0;t+="->"for(j=site+1;j<pp.length();j+) t+=ppj;pp=t;if(pp3='0'&&pp0=rull0) continue;p.push_back(pp);site+;for(i=0;i<p.size();i+

36、) res+=first(pi);return res;3.2.2递归下降子程序的设计l 设计原理如下： 对每一个非终结符，构造一个子程序，用以识别该非终结符所定义的符号串。每个子程序以产生式左部非终结符命名，以产生式右部构造子程序内容。l 构造算法如下： 扩展文法：增设一个产生式，作为主程序：Z->Z ， 入出口约定： 子程序入口时，其首符号已经读来！子程序出口时，其后继符应该读来！ 子程序内容设计：遇终结符，判定之 ，确认后读下一单词；遇非终结符,调用之,返回后不读下一单词； 遇空串(e) ，直接出口； 入口出口NEXT(w)F 2Fyn入口出口NEXT(w)T 1Tynl 程序流程

37、图如下：开始结束 #ENEXT(w)err0yn 3.3中间语言生成器算法 中间语言生成主要是对四元式序列的设计，其算法设计如下： 1）赋值语句的四元式设计 设有赋值语句：v = E ，则有v = E =>quat(E),q(:= res(E) _ v ) 算法实现如下： void Z(int end) /赋值语句四元式生成int i;string str；if(VTOKENtokenp+3.compare("<PT,21>")!=0)tokenp+=2; LL1(end-1);str=VTOKENtokenp+1;str+=SEM.top();SEM.p

38、op();str+="<0,0>"str+=VTOKENtokenp;QT.push_back(str);elsestr=VTOKENtokenp+1;str+=VTOKENtokenp+2;str+="<0,0>"str+=VTOKENtokenp;QT.push_back(str);cout<<"验证赋值语句并产生四元式"<<endl;2） 条件语句的四元式设计文法：S -> if（E）S1 else S2 quat(E)q1(if res(E)_ _ )quat(S1)q2(

39、el _ _ _ )quat(S2)q3(ie _ _ _ )语义结构 ： 四元式结构： E执行S1执行S2可选 falsetrue入口出口算法实现如下：void V(int end) /if语句四元式生成string str;int p,f=0;tokenp+;if(VTOKENpare("<PT,0>")=0) f+=1;p=tokenp+1;else cout<<"源代码错误-ERRO:02/if 当前TOKEN:"<<tokenp<<endl; getchar();exit(0)

40、; do if(VTOKENpare("<PT,0>")=0)f+=1; else if(VTOKENpare("<PT,1>")=0)f-=1; p+; while(f!=0); if(p-1-tokenp)=1) cout<<"源代码错误-ERRO:02/if括号 当前TOKEN:"<<tokenp<<endl; getchar();exit(0); if(p-1-tokenp)=2) string tt; tt=VTOKENtokenp+1; str

41、="<KT,3>" str+=tt; str+="<0,0>" str+="<0,0>"QT.push_back(str);tokenp+=3; else tokenp+; LL1(p-2); tokenp=p; str="<KT,3>" str+=SEM.top(); SEM.pop(); str+="<0,0>" str+="<0,0>" QT.push_back(str); C(end);cout&

42、lt;<"验证if语句并产生四元式"<<endl;void N(int end) /else语句四元式生成 string str;str="<KT,1>"str+="<0,0>"str+="<0,0>"str+="<0,0>"QT.push_back(str);tokenp+;C(end);cout<<"验证else语句并产生四元式"<<endl;3）循环语句的四元式设计文法：S -&g

43、t; while（E）S 语义结构： 四元式结构：q2(do res(E)_ _ )quat(S)q3(we _ _ _ )q1(wh _ _ _ )quat(E) E 执行 Sfalsetrue入口 出口 算法实现如下：void W(int end) /循环语句四元式生成string str; int p,f=0;str="<KT,7>"str+="<0,0>"str+="<0,0>"str+="<0,0>"QT.push_back(str);tokenp+;p=t

44、okenp;do if(VTOKENpare("<PT,0>")=0)f+=1; else if(VTOKENpare("<PT,1>")=0)f-=1; p+; while(f!=0); if(p-1-tokenp)=1) cout<<"源代码错误-ERRO:02/while括号当前TOKEN:"<<tokenp<<endl; getchar();exit(0); if(p-1-tokenp)=2) string tt; tt=VTOKENtokenp+

45、1; str="<KT,8>" str+=tt; str+="<0,0>" str+="<0,0>"QT.push_back(str);tokenp+=3; elsetokenp+;LL1(p-2);str="<KT,8>"str+=SEM.top();SEM.pop();str+="<0,0>"str+="<0,0>"QT.push_back(str); tokenp=p;C(end);str=&quo

46、t;<KT,10>"str+="<0,0>"str+="<0,0>"str+="<0,0>"QT.push_back(str);cout<<"验证了循环语句并产生四元式"<<endl;3.4处理复合表达式的算法1） 表达式四元式设计文法：Vs E; Vn XTYFMNQSAB; Vt jcibpk(); E->TX X->jTGX|0 T->FY Y->cFGY|0 F->MN N->bMGN|0

47、M->SQ Q->pSGQ|0 S->AB B->kAGB|0 A->iP|(E);四元式结构：q:( o1 o2 t ）/*算符，对象1，对象2，结果*/算法实现如下：void GEQ(string a)/运算符a，计数器qtpchar p10;ele num;="t"num.val="0"int i=0;string str;string left;/左操作数string right;/右操作数string t;if(pare("<PT,5>")=0|pare("

48、<PT,22>")=0)SEM.push("<0,0>"); right=SEM.top();SEM.pop();left=SEM.top();SEM.pop();if(left1='C')str=translate(left);for(i=0;i<sizeof(str);i+)if(stri='.')ITf.push_back(num);t+="<ITf,"itoa(ITf.size()-1,p,10);t+=p;t+=">"break;else c

49、ontinue;ITi.push_back(num);t+="<ITi,"itoa(ITi.size()-1,p,10);t+=p;t+=">"elseint flag=0;str=translate(left);for(i=0;i<ITi.size();i+)if(pare(IT)=0)flag=1;break;else continue;for(i=0;i<ITf.size()&&flag=0;i+)if(pare(IT)=0)flag=2;break;else continue;f

50、or(i=0;i<ITc.size()&&flag=0;i+)if(pare(IT)=0)flag=3;break;else continue;switch(flag)case 0:cout<<"使用了未声明的变量-ERRO:02 当前TOKEN:"<<tokenp<<endl;exit(0);/未声明的变量case 1:ITi.push_back(num);t+="<ITi,"itoa(ITi.size()-1,p,10);t+=p;t+=">"br

51、eak;case 2:ITf.push_back(num);t+="<ITf,"itoa(ITf.size()-1,p,10);t+=p;t+=">"break;case 3:ITc.push_back(num);t+="<ITc,"itoa(ITc.size()-1,p,10);t+=p;t+=">"break;if(right1='I'&&right3=',')int flag=0;str=translate(right);for(i=0;

52、i<ITi.size();i+)if(pare(IT)=0)flag=1;break;else continue;for(i=0;i<ITf.size()&&flag=0;i+)if(pare(IT)=0)flag=2;break;else continue;for(i=0;i<ITc.size()&&flag=0;i+)if(pare(IT)=0)flag=3;break;else continue;if(flag=0)cout<<"使用了未声明的变量-ERRO:02 当前TOKEN:"<<tokenp<<endl;exit(0);a+=left;a+=right;a+=t;QT.push_back(a);SEM.push(t);2） 带语义动作的LL（1）自动机开始 初始化 #入栈，开始符号E入栈 N N/P? P read(w)执行栈操作(SYN(top),w)查分析表结束空?OK? y n y err算法实现如下：（1） 将token翻译成非终结符if(