編譯原理實驗報告-SLR分析器設(shè)計

...wd......wd......wd...裝裝訂線編譯原理實驗報告題目：SLR(1)分析器的設(shè)計學(xué)院計算機科學(xué)與技術(shù)專業(yè)xxxxxxxxxxxxxxxxx學(xué)號xxxxxxxxxxxxx姓名xx指導(dǎo)教師xx20xx年xx月xx日SLR(1)分析器的設(shè)計一、實驗?zāi)康臉?gòu)造LR(1)分析程序，利用它進展語法分析，判斷給出的符號串是否為該文法識別的句子，了解LR〔K〕分析方法是嚴格的從左向右掃描，和自底向上的語法分析方法。二、實驗原理對以下文法，用LR〔1〕分析法對任意輸入的符號串進展分析：S->EE->E+TE->TT->T*FT->FF->(E)F->i三、實驗步驟1.總控程序，也可以稱為驅(qū)動程序。對所有的LR分析器總控程序都是一樣的。2.分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將不同，分析表又可以分為動作表〔ACTION〕和狀態(tài)轉(zhuǎn)換〔GOTO〕表兩個局部，它們都可用二維數(shù)組表示。3.分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進后出棧。分析器的動作就是由棧頂狀態(tài)和當前輸入符號所決定。LR分析器由三個局部組成：其中:SP為棧指針，S[i]為狀態(tài)棧，X[i]為文法符號棧。狀態(tài)轉(zhuǎn)換表用GOTO[i，X]=j表示，規(guī)定當棧頂狀態(tài)為i，遇到當前文法符號為X時應(yīng)轉(zhuǎn)向狀態(tài)j，X為終結(jié)符或非終結(jié)符。ACTION[i，a]規(guī)定了棧頂狀態(tài)為i時遇到輸入符號a應(yīng)執(zhí)行。動作有四種可能：(1)移進：action[i，a]=Sj：狀態(tài)j移入到狀態(tài)棧，把a移入到文法符號棧，其中i，j表示狀態(tài)號。(2)歸約：action[i，a]=rk：當在棧頂形成句柄時，則歸約為相應(yīng)的非終結(jié)符A，即文法中有A-B的產(chǎn)生式，假設(shè)B的長度為R(即|B|=R)，則從狀態(tài)棧和文法符號棧中自頂向下去掉R個符號，即棧指針SP減去R，并把A移入文法符號棧內(nèi)，j=GOTO[i，A]移進狀態(tài)棧，其中i為修改指針后的棧頂狀態(tài)。(3)承受acc:當歸約到文法符號棧中只剩文法的開場符號S時，并且輸入符號串已完畢即當前輸入符是'#'，則為分析成功。(4)報錯:當遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入端不是該文法能承受的符號串?！緦嶒炓蟆?、編程時注意編程風格：空行的使用、注釋的使用、縮進的使用等。2、如果遇到錯誤的表達式，應(yīng)輸出錯誤提示信息。3、程序輸入/輸出實例：輸入一以#完畢的符號串(包括+—*/〔〕i#)：在此位置輸入符號串輸出過程如下：步驟狀態(tài)棧符號棧剩余輸入串動作10#i+i*i#四、實驗環(huán)境計算機DEVC++軟件五、實驗程序#include<stdio.h>#include<stdlib.h>intAction[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; } } 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;}intvNumCount(){inti,j; for(i=0;i<grammarNum;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;i<stateNum;i++) { if(stateTop==i) break; } for(j=0;j<vtNum;j++) { if(inputChar==AVT[j]) break; } returnAction[i][j];}intGetGoto(intstateTop,charinputChar){inti,j; for(i=0;i<stateNum;i++){ if(stateTop==i) break; } for(j=0;j<vnNum;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(jj<j) { printf("?"); jj++; } while(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，規(guī)約2，承受3 scanf("%s",&Input); while(Input[i]!='\0') { if(Input[i]>='A'&&Input[i]<='Z') { printf("輸入的不是有效的表達式！"); return0; } i++; } i=0; printf("步驟\t狀態(tài)棧\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) { sta