编译原理课设报告

第1章课程设计目的《编译原理》课程设计是编译原理课程必不可少的一个环节，通过课程设计，加深对编译原理的教学内容的了解，以及实现编译原理各部分知识的融合。进而提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力。第2章课程设计内容1．题目：编译程序构造2．内容：涉及词法分析、自下而上语法分析程序的实现：SLR（1）分析器的实现以及生成中间代码。3．具体要求根据LR分析算法构造SLR（1）分析程序，并完成语法分析动作（当需要一个单词时，调用词法分析程序获取），同时完成语义分析生成四元式输出。要求程序具有通用性，改变文法时只需改变程序的数据初值，无需改变程序主体；要求完成一条说明语句、一条算数表达式和赋值语句的翻译，生成中间代码。构造其用于SLR（1）分析的识别活前缀的DFA以及action表和goto表。然后编程实现。（关于词法分析部分只需识别出与此文法相关的单词即可（+，*，（，），id，=））。4．程序设计提示：（1）分析栈设计时可以用一个栈完成，也可以设计三个栈：一个符号栈，一个状态栈，一个语义栈，则归约时，则需要在符号栈中退掉n个符号，在状态栈中退掉n个符号（n为产生式符号个数），语义栈中退掉n个符号对应的语义；（2）终结符表和非终结符表的组织和预测分析程序中相同（将符号对应到一个数字，表示在分析表中对应的下标）。（3）action表中的错误处理：简化的错误处理：当查找action表出现空白时，则当前单词无法移进和规约，可简单的认为当前单词为多余的单词，则抛弃当前单词，读下一单词继续分析。5．程序扩展要求有能力的同学可将编译程序扩展布尔表达式的分析和四元式生成，布尔表达式的翻译参见教材（胡元义《编译原理教程》）104——105页。第3章设计方案介绍3.1模块划分及模块调用本系统总体是三个模块，一个是词法分析模块；一个是语法分析模块；一个是语义分析模块。其中词法分析作为语法分析的子程序调用。模块调用如图3-1所示：词法分析器analyse()词法分析器analyse()语法分析器scan()图3-1模块调用图第4章程序源代码程序源代码如下：#include<iostream.h>#include<string.h>#include<istream.h>#include<fstream.h>#include<stdlib.h> #include<stdio.h>#include<ctype.h>intLetter(charch){ if(isalpha(ch))return1; return0;}intDigit(charch){ if(ch>47&&ch<58)return1; return0;}charbiaozhifu[30][30];charfuhaobiao1[100][10];intfuhaobiao2[100];charsiyuanshi[100][100];#defineMAXSIZE1024typedefstruct{intstate[MAXSIZE]; charsign[MAXSIZE]; charmean[MAXSIZE][100]; inttop;}SeqStack;SeqStack*Init_SeqStack(){ SeqStack*s=newSeqStack; if(!s) { cout<<"未申请到空间!"<<endl; returnNULL; } else { s->top=-1; returns; } }intEmpty_SeqStack(SeqStack*s){if(s->top==-1) return1; elsereturn0;}//入栈voidPush_SeqStack(SeqStack*s,inta,charb,charc[]){if(s->top+1>=MAXSIZE) { cout<<"栈满!!!"; } else { s->top++; s->state[s->top]=a; s->sign[s->top]=b; strcpy(s->mean[s->top],c); }}//出栈voidPop_SeqStack(SeqStack*s){if(Empty_SeqStack(s)) cout<<"栈空!!!"<<endl; else { s->top--; }}//取栈顶元素intTop_SeqStack(SeqStack*s){if(Empty_SeqStack(s)) return0; else returns->state[s->top];//返回状态}//主函数voidmain(){intno1,no2=0,no3=0,i=0,k,flag=0,m=0,s,t,slength=8,f1=0,f=1,error=0,v=49;charstring[20],filename[30],token[30],nn[2];chara,b;charplace[3];place[0]='T';place[1]=v;place[2]=NULL;inti1,j1=0,l,k1=0;charVN[10]={'A','E','E','T','T','F','F'};//非终结符表int length_vn=5;char VT[15]={'i','=','+','*','(',')','#'};//终结符表int length_vt=10;charNT[11]={'i','=','+','*','(',')','#','A','E','T','F'};//综合表int length_nt=11;char Fa[15][10]={"i=E","E+T","T","T*F","F","(E)","i"};/*(0)A→id=E(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i*///构造ACTION和GOTO表int analysis_table[15][11]={2,-1,-1,-1,-1,-1,-1,1,-1,-1,-1, -1,-1,-1,-1,-1,-1,200,-1,-1,-1,-1, -1,3,-1,-1,-1,-1,-1,-1,-1,-1,-1, 7,-1,-1,-1,8,-1,-1,-1,4,5,6, -1,-1,9,-1,-1,-1,100,-1,-1,-1,-1,-1,-1,102,10,-1,102,102,-1,-1,-1,-1,-1,-1,104,104,-1,104,104,-1,-1,-1,-1,-1,-1,106,106,-1,106,106,-1,-1,-1,-1,7,-1,-1,-1,8,-1,-1,-1,13,5,6,7,-1,-1,-1,8,-1,-1,-1,-1,12,6,7,-1,-1,-1,8,-1,-1,-1,-1,-1,11,-1,-1,103,103,-1,103,103,-1,-1,-1,-1,-1,-1,101,10,-1,101,101,-1,-1,-1,-1,-1,-1,9,-1,-1,14,-1,-1,-1,-1,-1,-1,-1,105,105,-1,105,105,-1,-1,-1,-1};SeqStack*A=Init_SeqStack();Push_SeqStack(A,0,'#',"_");//将初态和"#"压入栈中Acout<<"请输入文件名:";cin>>filename;ifstreaminstuf(filename,ios::in);cout<<"**************************操作过程如下************************"<<endl;cout<<"状态栈"<<'\t'<<'\t'<<"符号栈"<<'\t'<<'\t'<<"语义栈"<<'\t'<<'\t'<<"四元式"<<'\t'<<'\t'<<"动作说明"<<endl;cout<<""<<endl;do{//****************状态栈******符号栈******语义栈**************t=0; into=0,p=0,q=0; while(t<=A->top) {cout<<A->state[t];//输出状态栈 if(A->state[t]>=10){ o=o+2; } else { o++; } t++; } if(o<8) { cout<<'\t'<<'\t'; } elseif(o>=8&&o<16) { cout<<'\t'; } t=0; while(t<=A->top) {cout<<A->sign[t];//输出符号栈 p=p++; t++; } if(p<8) { cout<<'\t'<<'\t'; } elseif(p>=8&&p<16) { cout<<'\t'; } t=0; while(t<=A->top)//输出语义栈 {cout<<A->mean[t]; q=q+strlen(A->mean[t]); t++; } if(q<8) { cout<<'\t'<<'\t'; } elseif(q>=8&&q<16) { cout<<'\t'; } //***********************词法分析器************************** if(f==1) {//i:token数组变量,j:标识符数组变量,l:查看标识符数组k:查看符号表for(i1=0;i1<30;i1++) { token[i1]='\0'; } if(f1!=1) { instuf.get(a); } while(1) { i1=0; if(a==''||a==' ')//滤去空格 { instuf.get(a); while(a==''||a==' ') { instuf.get(a); } continue; } elseif(Letter(a)||a=='_') { intflag=0; while(Letter(a)||a=='_'||Digit(a)) { token[i1]=a;//将当前读入的字符送入token数组 i1++; instuf.get(a); f1=1; } //查表是否已存在该标志符 for(l=0;l<30;l++) { if(strcmp(biaozhifu[l],token)==0) { flag=1; break; } } if(flag!=1) { strcpy(biaozhifu[j1],token);//符号如表 j1++; fuhaobiao2[no2]=j1-1; } else { fuhaobiao2[no2]=l; } b='i'; strcpy(fuhaobiao1[no2],"id"); no2++; strcpy(string,token); for(i1=0;i1<30;i1++) { token[i1]='\0'; } break; } elseif(a=='+'||a=='*'||a=='('||a==')'||a=='#'||a=='=') { nn[0]='\0'; nn[1]='\0'; nn[0]=a; strcpy(fuhaobiao1[no2],nn); nn[0]='\0'; nn[1]='\0'; fuhaobiao2[no2]=-1; no2++; f1=0; b=a; strcpy(string,"_"); break; } else { cout<<'\t'<<'\t'; cout<<"非法字符!"<<a; error++; instuf.get(a); continue; } }} k=0; no1=-1; for(intj=0;j<length_nt;j++)//判断输入符号标号 {if(b==NT[j]) { no1=j; break; } } s=analysis_table[Top_SeqStack(A)][no1]; if(s==200) { cout<<'\t'<<'\t'; cout<<"分析完成。共"<<error<<"个错误!!!"<<endl; break; } elseif(s>0&&s<100) { cout<<'\t'<<'\t';cout<<"ACTION["<<A->state[A->top]<<","<<b<<"]"<<"="<<"s"<<s<<"状态"<<s<<"入栈"<<"字符"<<b<<"入栈"<<"语义"<<string<<"入栈"<<endl; Push_SeqStack(A,s,b,string);//状态入栈移进字符 f=1; continue; } elseif(s>=100&&s!=200) { s=s-100; /*(0)A→id=E(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i*/ switch(s) { case0:{ charr[100]; strcpy(r,A->mean[A->top-2]); cout<<"(=,"<<A->mean[A->top]<<",_"<<","<<A->mean[A->top-2]<<")"; strcpy(siyuanshi[no3],"(=,");strcat(siyuanshi[no3],A->mean[A->top]); strcat(siyuanshi[no3],",_,");strcat(siyuanshi[no3],A->mean[A->top-2]);strcat(siyuanshi[no3],")"); no3++; cout<<'\t'; for(intj=0;Fa[s][j]!='\0';j++) { Pop_SeqStack(A);//出栈j<Fa[s].length() }intn1=A->top,n2; for(n2=0;n2<11;n2++) { if(NT[n2]==VN[s])break; } cout<<VN[s]<<"-->"<<Fa[s]<<"规约,且GOTO["<<A->state[n1]<<","<<VN[s]<<"]="<<analysis_table[A->state[n1]][n2]<<endl;Push_SeqStack(A,analysis_table[A->state[n1]][n2],VN[s],r);//入栈规约状态 break; }case1:{ cout<<"(+,"<<A->mean[A->top-2]<<","<<A->mean[A->top]<<","<<place<<")"; cout<<'\t'; strcpy(siyuanshi[no3],"(+,");strcat(siyuanshi[no3],A->mean[A->top-2]); strcat(siyuanshi[no3],",");strcat(siyuanshi[no3],A->mean[A->top]); strcat(siyuanshi[no3],",");strcat(siyuanshi[no3],place);strcat(siyuanshi[no3],")"); no3++; for(intj=0;Fa[s][j]!='\0';j++) { Pop_SeqStack(A);//出栈j<Fa[s].length() }intn1=A->top,n2; for(n2=0;n2<11;n2++) { if(NT[n2]==VN[s])break; } cout<<VN[s]<<"-->"<<Fa[s]<<"规约,且GOTO["<<A->state[n1]<<","<<VN[s]<<"]="<<analysis_table[A->state[n1]][n2]<<endl; Push_SeqStack(A,analysis_table[A->state[n1]][n2],VN[s],place); v++; place[1]=v; break; }case2: { cout<<'\t'<<'\t'; charr[100]; strcpy(r,A->mean[A->top]); for(intj=0;Fa[s][j]!='\0';j++) { Pop_SeqStack(A);//出栈j<Fa[s].length() }intn1=A->top,n2; for(n2=0;n2<11;n2++) { if(NT[n2]==VN[s])break; } cout<<VN[s]<<"-->"<<Fa[s]<<"规约,且GOTO["<<A->state[n1]<<","<<VN[s]<<"]="<<analysis_table[A->state[n1]][n2]<<endl;Push_SeqStack(A,analysis_table[A->state[n1]][n2],VN[s],r); break; } case3: { cout<<"(*,"<<A->mean[A->top-2]<<","<<A->mean[A->top]<<","<<place<<")"<<'\t'; strcpy(siyuanshi[no3],"(*,");strcat(siyuanshi[no3],A->mean[A->top-2]); strcat(siyuanshi[no3],",");strcat(siyuanshi[no3],A->mean[A->top]); strcat(siyuanshi[no3],",");strcat(siyuanshi[no3],place);strcat(siyuanshi[no3],")"); no3++; for(intj=0;Fa[s][j]!='\0';j++) { Pop_SeqStack(A);//出栈j<Fa[s].length() }intn1=A->top,n2; for(n2=0;n2<11;n2++) { if(NT[n2]==VN[s])break; } cout<<VN[s]<<"-->"<<Fa[s]<<"规约,且GOTO["<<A->state[n1]<<","<<VN[s]<<"]="<<analysis_table[A->state[n1]][n2]<<endl; Push_SeqStack(A,analysis_table[A->state[n1]][n2],VN[s],place); v++; place[1]=v; break; } case4: { cout<<'\t'<<'\t'; charr[100]; strcpy(r,A->mean[A->top]); for(intj=0;Fa[s][j]!='\0';j++) { Pop_SeqStack(A);//出栈j<Fa[s].length() }intn1=A->top,n2; for(n2=0;n2<11;n2++) { if(NT[n2]==VN[s])break; } cout<<VN[s]<<"-->"<<Fa[s]<<"规约,且GOTO["<<A->state[n1]<<","<<VN[s]<<"]="<<analysis_table[A->state[n1]][n2]<<endl; Push_SeqStack(A,analysis_table[A->state[n1]][n2],VN[s],r);break; } case5: { cout<<'\t'<<'\t'; charr[100]; strcpy(r,A->mean[A->top-1]); for(intj=0;Fa[s][j]!='\0';j++) { Pop_SeqStack(A);//出栈j<Fa[s].length() }intn1=A->top,n2; for(n2=0;n2<11;n2++) { if(NT[n2]==VN[s])break; } cout<<VN[s]<<"-->"<<Fa[s]<<"规约,且GOTO["<<A->state[n1]<<","<<VN[s]<<"]="<<analysis_table[A->state[n1]][n2]<<endl; Push_SeqStack(A,analysis_table[A->state[n1]][n2],VN[s],r); break; } case6: { cout<<'\t'<<'\t'; charr[100]; strcpy(r,A->mean[A->top]); for(intj=0;Fa[s][j]!='\0';j++) { Pop_SeqStack(A);//出栈j<Fa[s].length() }intn1=A->top,n2; for(n2=0;n2<11;n2++) { if(NT[n2]==VN[s])break; } cout<<VN[s]<<"-->"<<Fa[s]<<"规约,且GOTO["<<A->state[n1]<<","<<VN[s]<<"]="<<analysis_table[A->state[n1]][n2]<<endl; Push_SeqStack(A,analysis_table[A->state[n1]][n2],VN[s],r); break; } } f1=0; f=0; continue; } else { cout<<'\t'<<'\t'; cout<<"错误,略过单词:"<<b<<endl; error++; f=1; continue; } }while(1); instuf.close();//********************输出标识符表*********************** cout<<""<<endl; cout<<"符号表如下:"<<endl; for(intj=0;j<j1;j++) { cout<<j<<'\0'<<'\0'<<biaozhifu[j]<<endl; }//********************二元式*************************** //cout<<""<<endl;cout<<"二元式:"<<endl;for(intu=0;u<no2-1;u++) { if(fuhaobiao2[u]!=-1)cout<<"("<<fuhaobiao1[u]<<","<<fuhaobiao2[u]<<")"<<endl; else cout<<"("<<fuhaobiao1[u]<<",)"<<endl; } //cout<<""<<endl;//********************四元式***************************cout<<"四元式:"<<endl;for(intuu=0;uu<no3;uu++) { cout<<siyuanshi[uu]<<endl; } cout<<""<<endl;}第5章程序测试数据和结果变量说明语句的文法及相应的语义子程序：.att表示数据类型属性，fill函数表示将单词id及其类别属性填写符号表。（0）S→D；{acc}（1）D→intid{fill（id，int）；D.att=in