编译原理课程设计

南华大学计算机科学与技术学院编译原理课程设计名：赋值语句，if语句，while循环语句词法，语法及语义分析，中间代码生成程序设计专业：计算机科学与技术班级：计算机091姓名：Dragon学号:20094440116实验地点：8栋2-209任课老师：刘星完成日期：2012.5.14《编译原理》课程设计指导书一、课程设计教学的目的与要求课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。设计时间：1周。开发工具：DOS环境下使用TurboC；Windows环境下使用VisualC++。其它熟悉语言。二、课程设计的内容：设计题一：算术表达式的语法分析及语义分析程序设计。1．目的通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。2．设计内容及要求：算术表达式的文法：〈无符号整数〉∷＝〈数字〉{〈数字〉}〈标志符〉∷＝〈字母〉{〈字母〉｜〈数字〉}〈表达式〉∷＝[＋｜－]〈项〉{〈加法运算符〉〈项〉}〈项〉∷＝〈因子〉{〈乘法运算符〉〈因子〉}〈因子〉∷＝〈标志符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’〈加法运算符〉∷＝＋｜－〈乘法运算符〉∷＝＊｜／可以选择递归下降法、LL（1）、算符优先分析法、LR法完成以上任务，中间代码选用逆波兰式或四元式。写出算术表达式的符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。设计题二：布尔表达式的语法分析及语义分析程序设计。1．目的通过设计、编制、调试一个布尔表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。2．设计内容及要求（1）可以选择递归下降法、LL（1）、算符优先分析法、LR法完成以上任务，中间代码选用逆波兰式或四元式。（2）如1题写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。（3）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。设计题三：条件语句的语法分析及语义分析程序设计。1．目的通过设计、编制、调试一个语法及语义分析程序，加深对语法及语义分析原理的理解。2．设计内容及要求IF〈布尔表达式〉THEN〈赋值语句〉ELSE〈赋值语句〉其中（1）可以选择递归下降法、LL（1）、算符优先分析法、LR法完成以上任务，中间代码选用四元式。（2）如1题写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。（3）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。设计题四：循环语句的语法分析及语义分析程序设计。1．目的通过设计、编制、调试一个语法及语义分析程序，加深对语法及语义分析原理的理解。2．设计内容及要求WHILE〈布尔表达式〉DO〈赋值语句〉其中（1）可以选择递归下降法、LL（1）、算符优先分析法、LR法完成以上任务，中间代码选用四元式。（2）如1题写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。（3）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。设计题五：自选一种常见高级语言为背景，对其进行简化．例如只包括整型常数和其四则运算以及相应的赋值语句，转移语句，条件语句和最简单的输入输出语句等．编制一个包括必要处理阶段（词法分析、语法分析、语义分析、代码生成）简化又完整的编译程序．。1．目的对编译的完整过程有一个感性认识，对各个环节的任务，处理方法有一定的熟悉。2．设计内容及要求（1）如1题写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。（2）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。三、课程特色《编译原理》课程是理论性较强的课程。其特点是概念多、内容抽象。尤其是文法、形式语言及自动机的概念是计算机专业的理论学习和研究的基础。编译原理与方法对于深刻理解程序设计语言、深入了解程序在计算机中的运行机制、掌握程序设计语言的翻译方法起到不可替代的作用。同时《编译原理》课程也是实践性很强的课程，要求学生在基本掌握了编译理论和技术的基础上，综合应用先修课程及本课程的知识，完成课程的实验和课程设计。四、课程设计步骤与方法第一步需要同学给出语法分析方法及中间代码形式的描述及文法和属性文法的描述；或者词法分析方法及符号表和TOKEN代码的设计。第二步需要同学进行简要的分析与概要设计；第三步需要同学按照学过的语法分析方法和语法制导翻译方法进行详细的算法设计，然后进行实际编程。五、课程设计说明书与图纸课程设计报告书的内容应包括：设计题目、班级、学号、姓名、完成日期；给出语法分析方法及中间代码形式的描述、文法和属性文法的设计；或者词法分析方法及符号表和TOKEN代码的设计。简要的分析与概要设计；详细的算法描述；源程序清单；给出软件的测试方法和测试结果；设计的评价、收获与体会。六、课程设计答辩课程设计完成后由教师上机现场检查并由学生回答老师的提问七、课程设计进度表序号内容所用时间1给出语法分析方法及中间代码形式的描述、文法和属性文法的设计；或者词法分析方法及符号表和TOKEN代码的设计。

1天2简要的分析与概要设计

1天

3算法设计与程序设计3天4撰写课程设计报告书1天合计

以上布置的任务是基本设计任务，希望同学们自己加大难度，取得更好成绩；同时要求同学们不得出现抄袭现象。上交内容：1、以学号命名的文件夹，包括程序源代码，一组较完备的测试数据(存在一个文本文件中)；2、课程设计报告（纸质版和电子版都要交，电子版放上面那个文件夹下）：包括选题说明，简单的软件需求分析说明，软件设计说明，设计经验总结。功能描述：该程序具有什么功能？程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；另外可以附加函数之间的调用关系图、程序总体执行流程图。设计经验总结包括下列方面：你对你的软件如何评价？你的设计有何特色？你自己觉得应该给多少分？你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你的收获有哪些？四、结果分析：1.输入条件语句：if(a>0)a=b;#（正确输入）错误输入：if(;#(错误输入,则判断有语法错误）3.if语句语法，语义，及中间代码生成中间代码4.while语句词法及语义，语法分析While语句的中间代码生成while和if语句综合分析图5-1六、课程设计总结：词法分析的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。通过本试验的完成，更加加深了对词法分析原理的理解。而语法分析的运行过程，主程序大致流程为：“置初值”调用scaner函数读下一个单词符号调用IrParse结束。递归下降分析的大致流程为：“先判断是否为begin”不是则“出错处理”，若是则“调用scaner函数”调用语句串分析函数“判断是否为end”不是则“出错处理”，若是则调用scaner函数“判断syn=0&&kk=0是否成立”成立则说明分析成功打印出来。不成立则“出错处理”。当词法，语法都分析完成后进行重点的语义分析和中间代码生成。首先，用三地址代码表示中间代码，这需要对输入串判断，是为if语句，while语句，还是赋值语句，不同的输入串将跳转到不同的函数进行相应的处理，并得出最终的中间代码。整个过程花费2天的时间，一天用于编写主要代码，并调试出词法功能模块，第二天主要调试语法及语义功能模块的实现，及中间代码生成工作。在设计条件语句的语义的实现算法时，遇到的小小的困难，经过赖心的调试后解决。之后while循环中尝试加入条件和赋值语句时没遇到什么困难。自己评分：整个设计于调试总共花费4天左右时间，程序基本实现了赋值语句，if语句，While循环语句的词法分析与语法分析及语义分析和中间代码生成的功能。程序能找出简单的错误所在及原因。因此我自己觉得可以打优秀！！！源代码：//编译原理实验，可进行简单的词法分析和语法分析和语义分析，中间代码生成#include<stdio.h>#include<string.h>#include<stdlib.h>charprog[80],token[8],ch,ana[80];intsyn,p,m,n,sum,i;char*rwtab[6]={"begin","if","then","while","do","end"};chararray[10][20];intliter=0,W_flag=0,if_flag=0;voidscaner();intdoanaly();intyuyi();voidmiddle_code();intmain(){ while(1) { p=i=0; W_flag=if_flag=liter=0; printf("\npleaseinputastring(endwith'#'):\n\n"); do{ scanf("%c",&ch); prog[p++]=ana[i++]=ch; }while(ch!='#'); ana[i]='\0'; p=0; printf("**开始词法分析:**\n"); do{ scaner(); switch(syn) { case11:printf("(%-10d%5d)\n",sum,syn); break; case-1:printf("youhaveinputawrongstringwheninscaner\n"); getchar(); break;//exit(0); default:printf("(%-10s%5d)\n",token,syn); break; } }while(syn!=0); printf("\n"); i=doanaly(); if(i==-1) { printf("\n语法分析：awrongstringwheninanalysis\n"); } else { printf("\n语法分析：0error(s),0warning(s)\n"); middle_code(); } getchar(); } return0;}voidscaner(){ sum=0;for(m=0;m<8;m++) token[m++]=NULL;ch=prog[p++];m=0;while((ch=='')||(ch=='\n')) ch=prog[p++];if(((ch<='z')&&(ch>='a'))||((ch<='Z')&&(ch>='A'))){ while(((ch<='z')&&(ch>='a'))||((ch<='Z')&&(ch>='A'))||((ch>='0')&&(ch<='9'))) { token[m++]=ch; ch=prog[p++]; } p--; syn=10; for(n=0;n<6;n++) if(strcmp(token,rwtab[n])==0) { syn=n+1; break; }}elseif((ch>='0')&&(ch<='9')){ while((ch>='0')&&(ch<='9')) { sum=sum*10+ch-'0'; ch=prog[p++]; } p--; syn=11;}elseswitch(ch){ case'<':token[m++]=ch; ch=prog[p++]; if(ch=='=') { syn=22; token[m++]=ch; }else { syn=20; p--; }break;case'>':token[m++]=ch;ch=prog[p++];if(ch=='='){ syn=24;token[m++]=ch;}else{syn=23;p--;}break;case'+':token[m++]=ch;ch=prog[p++];if(ch=='+'){syn=17;token[m++]=ch;}else{syn=13;p--;}break;case'-':token[m++]=ch;ch=prog[p++];if(ch=='-'){syn=29;token[m++]=ch;}else{syn=14;p--;}break;case'!':ch=prog[p++];if(ch=='='){syn=21;token[m++]=ch;}else{syn=31;p--;}break;case'=':token[m++]=ch;ch=prog[p++];if(ch=='='){syn=25;token[m++]=ch;}else{syn=18;p--;}break;case'*':syn=15;token[m++]=ch;break;case'/':syn=16;token[m++]=ch;break;case'(':syn=27;token[m++]=ch;break;case')':syn=28;token[m++]=ch;break;case'{':syn=5;token[m++]=ch;break;case'}':syn=6;token[m++]=ch;break;case';':syn=26;token[m++]=ch;break;case'\"':syn=30;token[m++]=ch;break;case'#':syn=0;token[m++]=ch;break;case':':syn=17;token[m++]=ch;break;default:syn=-1;break;}token[m++]='\0';}intdoanaly(){ intlen,i=0,j=0,leftk=0,rightk=0,endofk=0,result=0;while(ana[i]=='') i++; len=strlen(ana)-i-1;equal: //judgethe"if" if(len>2&&(strncmp(ana+i,"if",2)==0)) { if_flag=1; i+=2;//jumpoverthe"if" while(ana[i]=='') i++; if(ana[i]!='(') { printf("Lose'('afterif\n"); result=-1; } i++;//jumpthe'(' leftk++; j=i; while(ana[i]!='#') { if(ana[i]=='(') leftk++; elseif(ana[i]==')') { rightk++; endofk=i; } elseif(ana[i]==';'&&leftk!=rightk) { printf("Lose')'before';'\n"); result=-1; } elseif(ana[i]=='+'||ana[i]=='-'||ana[i]!='&'||ana[i]=='|') { charch=ana[i]; intcount=0; while(ana[i]==ch)//lianxusuanfudegeshubuda2 { count++; i++; } if(count>2) { printf("Theerrornearthe%c\n",ch); result=-1; } i--; } i++; } if(leftk!=rightk)//judgewhetherthenumberof'('equalstothatof')' { if(leftk>rightk) printf("Lose')'intheif\n"); else printf("Lose'('intheif\n"); result=-1; } i=endofk; if(ana[i]==')') i++;//jumptheright')' while(ana[i]=='')//deletethe'' i++; if(ana[i]!=';')//ifnotlikethis"if(....);" gotoequal; } //judgethe"while" elseif(len>5&&(strncmp(ana+i,"while",5)==0)) { W_flag=1; intflag1=0,flag2=0,t=0,s=0; chararg[2][10]; i+=5;//jumpthe"while"fivechars memset(arg,0,20); while(ana[i]=='') i++;if(ana[i]!='(')//judge"while"followedby'(' result=-1;i++; while(ana[i]!='#'&&ana[i]!=')') { if(ana[i]=='<') {flag1++;t++;s=0;} elseif(ana[i]=='>') {flag2++;t++;s=0;}else arg[t][s++]=ana[j];i++; } if(s==0)//judgetheparaminthe"while(param)" { printf("theerrorinthe(),noparam\n"); result=-1; } if(t!=0&&(arg[0][0]==0||arg[1][0]==0)) {//judgethetwosideof">" if(flag1!=0) printf("Theerrornearthe'<'\n"); elseif(flag2!=0) printf("Theerrornearthe'>'\n"); result=-1; } if(ana[i]!=')') { printf("Thewhilelose')'\n"); result=-1; } i++; while(ana[i]=='') i++; if(ana[i]!=';')//goto"="whensuchstring:"a=b"inthewhile gotoequal; } else//finishthe"="analysis { //gettheleftsidestringof"="intre=0,right_para=0;// printf("entryequal\n"); re=yuyi(); if(re!=2) returnre; while((ana[i]>='A'&&ana[i]<='Z')||(ana[i]>='a'&&ana[i]<='z')) i++; while(ana[i]=='') i++; //judgetherightlocaltionof"=" if((ana[i]=='+'&&ana[i+1]!='=')|| (ana[i]=='-'&&ana[i+1]!='=')||(ana[i]=='='&&ana[i+1]=='#')) { printf("Theerrornear'='\n"); result=-1; } i++; while(ana[i]=='')//jumpthe'' i++; //gettherightsidestringof"=" while((ana[i]>='A'&&ana[i]<='Z')||(ana[i]>='a'&&ana[i]<='z')|| (ana[i]>='0'&&ana[i]<='9')) { i++; right_para++; } if(right_para==0) { printf("Loserightparanearthe'='\n"); result=-1; } if(ana[i]=='')//checkthe";" { while(ana[i]=='') i++; if(ana[i]!=';') { printf("Lose';'\n"); result=-1; } } elseif(ana[i]!=';'&&ana[i]!='')//endupwithno";"wrong { printf("Lose';'\n"); result=-1; } }returnresult;}intyuyi(){ intrep=0,i=0,j=0,nu=0; charbA[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ",para[8][10],*stoken=NULL; intt=0,eq_begin=0,r=0,c=0,len,s=0,result=0,equ_flag=0;charplu_all[8]; while(prog[i]!='#') { if(prog[i]=='=')//findthe'=' { eq_begin=i; break; } i++; }if(eq_begin==0)//no'='inthestring return-1; i=0;j=t=0; while(prog[j]!='#') { //recordtheflag if(prog[j]=='+'||prog[j]=='-'||prog[j]=='*'||prog[j]=='/') plu_all[t++]=prog[j]; if(prog[j]==';')//findthe';'inthestring equ_flag=1; j++; } if(t==0)//t=0meansthatthisstringisaequal return2; printf("**开始语义分析:**\n"); prog[j]='\0'; len=strlen(prog); j=eq_begin-1; while(prog[j]=='')j--;while(j>=0)//returntothebeginningofequaldialogue { if((prog[j]>='A'&&prog[j]<='Z')||(prog[j]>='a'&&prog[j]<='z')) j--; else break; } for(r=0;r<(len-1-j);r++)//deletethe"if(a>0)"in"if(a>0)a=g+g+h;" prog[r]=prog[r+j+1]; prog[r]='\0'; stoken=strtok(prog,"=");//gettheleftparaof'=' r=c=0; len=strlen(stoken); while(c<len) para[r][c++]=*stoken++; para[r][c]='\0';//savetheparainthearrayandmakesurethatitendsupwith'\0' while((stoken=strtok(NULL,"+-*/;"))!=NULL)//getalltheparas { r++; c=0; len=strlen(stoken); while(c<len) para[r][c++]=*stoken++; para[r][c]='\0'; }if(r!=(t+1))//judgewhetherthenumberofparaequalstothenumberofflag { printf("lessparanearrightsideof'='\n"); result=-1; } if(t>1)//morethantwoflags{ s=0; nu=t; intflag=0,be=0; while(s<t&&nu>1)//managethe'*'and'/'first { //first'*'||'/' if((plu_all[s]=='*'||plu_all[s]=='/')&&flag==0) { printf("%c=%s%c%s\n",bA[rep],para[s+1],plu_all[s],para[s+2]); sprintf(array[liter],"%c=%s%c%s\n",bA[rep],para[s+1],plu_all[s],para[s+2]); liter++; flag++; nu--; plu_all[s]=0; be=s;//recordthestartingofserver"*"||"/" para[s+1][0]=bA[rep]; //savethechange para[s+1][1]='\0'; rep++; } //secondlianxu'*'||'/' elseif((plu_all[s]=='*'||plu_all[s]=='/')&&flag!=0&& (plu_all[s-1]==0||plu_all[s-1]==0)) { printf("%c=%c%c%s\n",bA[rep],bA[rep-1],plu_all[s],para[s+2]); sprintf(array[liter],"%c=%c%c%s\n",bA[rep],bA[rep-1],plu_all[s],para[s+2]); liter++; plu_all[s]=0; intgg=be;//usethenewbArepresenttheoldbA[] while(gg<=s) { para[gg+1][0]=bA[rep]; //savethechange para[gg+1][1]='\0'; gg++; } nu--; rep++; } //notlianxu'*'||'/' elseif((plu_all[s]=='*'||plu_all[s]=='/')&&flag!=0&& (plu_all[s-1]!=0&&plu_all[s-1]!=0)) { printf("%c=%s%c%s\n",bA[rep],para[s+1],plu_all[s],para[s+2]); sprintf(array[liter],"%c=%s%c%s\n",bA[rep],para[s+1],plu_all[s],para[s+2]); liter++; plu_all[s]=0; nu--; para[s+1][0]=bA[rep]; para[s+1][1]='\0'; rep++; // printf("ffff\n"); } s++; } // printf("dddddfffffffffffffffd\n"); intg=0; nu=s=0; while(s<t)//computerthenumberofflag { if(plu_all[s]!=0) { nu++; g=s; } s++; } if(nu==1) {//onlyoneflaglast // printf("dddd\n"); if(g==0)//ifleavethefirstflag { printf("%s=%c%c%s\n",para[0],bA[rep-1],plu_all[g],para[1]); sprintf(array[liter],"%s=%c%c%s\n",para[0],bA[rep-1],plu_all[g],para[1]); liter++; } else//notthefirstflag { printf("%s=%c%c%s\n",para[0],bA[rep-1],plu_all[g],para[g+2]); sprintf(array[liter],"%s=%c%c%s\n",para[0],bA[rep-1],plu_all[g],para[g+2]); liter++; } } else//morethantwoflags { s=-1; while(nu>1)//continuewhenmorethanoneflag { s++; if(plu_all[s]!=0&&rep>0)//ifrepbiggerthanzero { //meansthathaving'*'||'/'intheahead if(s!=0)//judgewhetheristhefirstflag { printf("%c=%c%c%s\n",bA[rep],bA[rep-1],plu_all[s],para[s+2]); sprintf(array[liter],"%c=%c%c%s\n",bA[rep],bA[rep-1],plu_all[s],para[s+2]); liter++; } elseif(s==0) { printf("%c=%s%c%s\n",bA[rep],para[s+1],plu_all[s],para[s+2]); sprintf(array[liter],"%c=%s%c%s\n",bA[rep],para[s+1],plu_all[s],para[s+2]); liter++; } nu--;plu_all[s]=0; rep++; } elseif(plu_all[s]!=0&&rep==0) { printf("%c=%s%c%s\n",bA[rep],para[s+1],plu_all[s],para[s+2]); sprintf(array[liter],"%c=%s%c%s\n",bA[rep],para[s+1],plu_all[s],para[s+2]); liter++; nu--;plu_all[s]=0;rep++; } } s=0; while(plu_all[s]==0)//findlastflag s++; printf("%s=%c%c%s\n",para[0],bA[rep-1],plu_all[s],para[s+2]); sprintf(array[liter],"%s=%c%c%s\n",para[0],bA[rep-1],plu_all[s],para[s+2]); liter++; } } elseif(t==1)//onlyoneflag { printf("%s=%s%c%s\n\n",para[0],para[1],plu_all[0],para[2]); sprintf(array[liter],"%s=%s%c%s\n\n",para[0],para[1],plu_all[0],para[2]); liter++; } if(equ_flag==0) { printf("Lose';'intheend\n"); result=-1; }