编译原理SLR(1)语法分析实验报告

学号E10714103专业计算机科学与技术姓名万学进实验日期2010-6-8教师签字成绩实验报告【实验名称】SLR（1）语法分析【实验目的】构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。【实验内容】对下列文法，用LR（1）分析法对任意输入的符号串进行分析：(1)S-E(2)E-E+T(3)E-T(4)T-T*F(5)T-F(6)F-(E)(7)F-i【设计思想】(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。LR分析器由三个部分组成：其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：(1)移进：action[i，a]=Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。(2)归约：action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A-B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，1即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。(3)接受acc:当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。(4)报错:当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。【实验要求】1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2、如果遇到错误的表达式，应输出错误提示信息。3、程序输入/输出实例：输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串输出过程如下：步骤状态栈符号栈剩余输入串动作10#i+i*i#移进【流程图】2【源代码】#includestdio.h#includestdlib.hintAction[12][6]={105,0,0,104,0,0,0,106,0,0,0,-1,0,52,107,0,52,52,0,54,54,0,54,54,105,0,0,104,0,0,0,56,56,0,56,56,105,0,0,104,0,0,105,0,0,104,0,0,0,106,0,0,111,0,0,51,107,0,51,51,0,53,53,0,53,53,0,55,55,0,55,55};intGoto[12][3]={1,2,3,0,0,0,0,0,0,0,0,0,8,2,3,0,0,0,0,9,3,0,0,10,0,0,0,0,0,0,0,0,0,0,0,0};charGrammar[20][10]={'\0'};charVT[10],VN[10];charAVT[6]={'i','+','*','(',')','#'};charGVN[3]={'E','T','F'};intvnNum,vtNum,stateNum=12;intVNum[10];intgrammarNum;typedefstruct{char*base;char*top;}SymbolStack;typedefstruct{int*base;int*top;}StateStack;StateStackstate;SymbolStacksymbol;intScanGrammar(){FILE*fp=fopen(SLR文法.txt,r);FILE*tp;charsingleChar,nextChar;inti=0,j=0,k,count;while(!feof(fp)){fscanf(fp,%c,&singleChar);if(singleChar=='?'){Grammar[i][j]='\0';break;}if(singleChar=='\n'){Grammar[i][j]='\0';i++;j=0;continue;}if(singleChar=='-'){tp=fp;fscanf(tp,%c,&nextChar);if(nextChar==''){fp=tp;continue;}3}if(singleChar=='|'){Grammar[i+1][0]=Grammar[i][0];Grammar[i][j]='\0';i++;j=1;continue;}Grammar[i][j]=singleChar;if(singleChar='A'&&singleChar='Z'){count=0;while(VN[count]!=singleChar&&VN[count]!='\0'){count++;}if(VN[count]=='\0'){vnNum=count+1;if(singleChar=='S'){j++;continue;}VN[count]=singleChar;vnNum=count+1;}}else{count=0;while(VT[count]!=singleChar&&VT[count]!='\0'){count++;}if(VT[count]=='\0'){VT[count]=singleChar;vtNum=count+1;}}j++;}printf(输入的文法：\n);for(k=0;k=i;k++){j=0;while(Grammar[k][j]!='\0'){if(j==1){printf(-);}printf(%c,Grammar[k][j]);j++;}printf(\n);}count=0;printf(VT:);while(VT[count]!='\0'){printf(%3c,VT[count]);count++;}VT[count]='#';vtNum=count+1;printf(%3c,VT[count]);printf(\nVN:);count=0;while(VN[count]!='\0'){printf(%3c,VN[count]);count++;}printf(\n);//printf(\n%d%d\n,vtNum,vnNum);fclose(fp);grammarNum=i+1;returni;}4intvNumCount(){inti,j;for(i=0;igrammarNum;i++){j=1;while(Grammar[i][j]!='\0'){j++;}VNum[i]=j;//printf(%3d,VNum[i]);}printf(\n);return0;}voidInitStack(){state.base=(int*)malloc(100*sizeof(int));if(!state.base)exit(1);state.top=state.base;*state.top=0;symbol.base=(char*)malloc(100*sizeof(char));if(!symbol.base)exit(1);symbol.top=symbol.base;*symbol.top='#';}intJudge(intstateTop,charinputChar){inti,j;for(i=0;istateNum;i++){if(stateTop==i)break;}for(j=0;jvtNum;j++){if(inputChar==AVT[j])break;}returnAction[i][j];}intGetGoto(intstateTop,charinputChar){inti,j;for(i=0;istateNum;i++){if(stateTop==i)break;}for(j=0;jvnNum;j++){if(inputChar==GVN[j])break;}returnGoto[i][j];}intprint(intcount,inti,charInput[],intaction,intgt,intsign){int*p=state.base,stateNum;intj,jj;char*q=symbol.base,symbolNum;printf(%d\t,count);while(p!=state.top+1){stateNum=*p;printf(%d,stateNum);p++;}printf(\t);while(q!=symbol.top+1){symbolNum=*q;printf(%c,symbolNum);q++;}printf(\t);j=i;jj=0;while(jjj){printf();jj++;}5while(Input[j]!='\0'){printf(%c,Input[j]);j++;}printf(\t);if(sign==1){printf(\tS%d\t%d\n,action,gt);}if(sign==2){printf(\tr%d\t%d\n,action,gt);}if(sign==3){printf(\tacc\t%d\n,gt);}if(sign==0)printf(\t0\t0\n);return0;}intPop(intaction){int*p,stateNum,ssValue,i;state.top--;p=state.top;stateNum=*p;i=VNum[action]-1;while(i!=0){symbol.top--;i--;}symbol.top++;*symbol.top=Grammar[action][0];ssValue=GetGoto(stateNum,Grammar[action][0]);if(ssValue==0)returnssValue;state.top++;*state.top=ssValue;returnssValue;}intReduction(){charInput[20];inti=0,count=1;intssValue,action;intstateTop,gt;intsign=-1;//移进1，规约2，接受3scanf(%s,&Input);while(Input[i]!='\0'){if(Input[i]='A'&&Input[i]='Z'){printf(输入的不是有效的表达式！);return0;}i++;}i=0;printf(步骤\t状态栈\t符号栈\t输入串\t\tACTION\tGOTO\n);while(Input[i]!='\0'){if(count==1){print(count,i,Input,0,0,0);count++;}stateTop=*state.top;ssValue=Judge(stateTop,Input[i]);if(ssValue==0){state.top--;if(*symbol.top=='#'){printf(规约出错！);return0;}continue;}if(ssValue==-1){sign=3;6print(count,i,Input,ssValue,0,sign);count++;return1;}if(ssValue=100){sign=1;action=ssValue-100;state.top++;*state.top=action;symbol.top++;*symbol.top=Input[i];i++;pri