編譯原理SLR1語法分析實(shí)驗(yàn)報告

1、學(xué)號 E10714103 專業(yè) 計算機(jī)科學(xué)與技術(shù) 姓名 萬學(xué)進(jìn)實(shí)驗(yàn)日期2010-6-8 教師簽字 成績實(shí) 驗(yàn) 報 告【實(shí)驗(yàn)名稱】 SLR（1）語法分析【實(shí)驗(yàn)?zāi)康摹繕?gòu)造LR(1)分析程序，利用它進(jìn)行語法分析，判斷給出的符號串是否為該文法識別的句子，了解LR（K）分析方法是嚴(yán)格的從左向右掃描，和自底向上的語法分析方法?！緦?shí)驗(yàn)內(nèi)容】對下列文法，用LR（1）分析法對任意輸入的符號串進(jìn)行分析： (1)S->E(2)E->E+T(3)E->T(4)T->T*F(5)T->F(6)F->(E)(7)F->i【設(shè)計思想】(1)總控程序，也可以稱為驅(qū)動程序。對所有的LR

2、分析器總控程序都是相同的。(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將不同，分析表又可以分為動作表（ACTION）和狀態(tài)轉(zhuǎn)換（GOTO）表兩個部分，它們都可用二維數(shù)組表示。(3)分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進(jìn)后出棧。分析器的動作就是由棧頂狀態(tài)和當(dāng)前輸入符號所決定。u LR分析器由三個部分組成：u 其中:SP為棧指針，Si為狀態(tài)棧，Xi為文法符號棧。狀態(tài)轉(zhuǎn)換表用GOTOi，X=j表示，規(guī)定當(dāng)棧頂狀態(tài)為i，遇到當(dāng)前文法符號為X時應(yīng)轉(zhuǎn)向狀態(tài)j，X為終結(jié)符或非終結(jié)符。u ACTIONi，a規(guī)定了棧頂狀態(tài)為i時遇到輸入符號a應(yīng)執(zhí)行。動作有

3、四種可能：(1)移進(jìn)： actioni，a= Sj：狀態(tài)j移入到狀態(tài)棧，把a(bǔ)移入到文法符號棧，其中i,j表示狀態(tài)號。(2)歸約： actioni，a=rk：當(dāng)在棧頂形成句柄時，則歸約為相應(yīng)的非終結(jié)符A，即文法中有A- B的產(chǎn)生式，若B的長度為R(即|B|=R)，則從狀態(tài)棧和文法符號棧中自頂向下去掉R個符號，即棧指針SP減去R，并把A移入文法符號棧內(nèi)，j=GOTOi,A移進(jìn)狀態(tài)棧，其中i為修改指針后的棧頂狀態(tài)。(3)接受acc: 當(dāng)歸約到文法符號棧中只剩文法的開始符號S時，并且輸入符號串已結(jié)束即當(dāng)前輸入符是'#'，則為分析成功。(4)報錯:當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的

4、文法符號時，則報錯，說明輸入端不是該文法能接受的符號串?！緦?shí)驗(yàn)要求】1、編程時注意編程風(fēng)格：空行的使用、注釋的使用、縮進(jìn)的使用等。2、如果遇到錯誤的表達(dá)式，應(yīng)輸出錯誤提示信息。 3、程序輸入/輸出實(shí)例： 輸入一以#結(jié)束的符號串(包括+*/（）i#)：在此位置輸入符號串 輸出過程如下：步驟 狀態(tài)棧 符號棧 剩余輸入串 動 作 1 0 # i+i*i# 移進(jìn)  【流程圖】【源代碼】#include<stdio.h>#include<stdlib.h>int Action126=105,0,0,104,0,0,0,106,0,0,0,-1,0,52,107,0,52

5、,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;int Goto123=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;char Grammar2010='0'char VT10,VN10;char AVT6='i',&

6、#39;+','*','(',')','#'char GVN3='E','T','F'int vnNum,vtNum,stateNum=12;int VNum10;int grammarNum;typedef structchar *base;char *top;SymbolStack;typedef structint *base;int *top;StateStack;StateStack state;SymbolStack symbol;int ScanGrammar(

7、)FILE *fp=fopen("SLR文法.txt","r"); FILE *tp;char singleChar,nextChar;int i=0,j=0,k,count;while(!feof(fp)fscanf(fp,"%c",&singleChar);if(singleChar='?')Grammarij='0'break;if(singleChar='n')Grammarij='0'i+;j=0;continue;if(singleChar='

8、-')tp=fp;fscanf(tp,"%c",&nextChar);if(nextChar='>')fp=tp;continue;if(singleChar='|')Grammari+10=Grammari0;Grammarij='0' i+;j=1;continue;Grammarij=singleChar;if(singleChar>='A'&&singleChar<='Z')count=0;while(VNcount!=singleCha

9、r&&VNcount!='0')count+;if(VNcount='0')vnNum=count+1;if(singleChar='S')j+;continue;VNcount=singleChar;vnNum=count+1;else count=0;while(VTcount!=singleChar&&VTcount!='0')count+;if(VTcount='0')VTcount=singleChar;vtNum=count+1;j+;printf("輸入的文法

10、：n");for(k=0;k<=i;k+)j=0;while(Grammarkj!='0')if(j=1)printf("->");printf("%c",Grammarkj);j+; printf("n");count=0;printf("VT:");while(VTcount!='0')printf("%3c",VTcount); count+;VTcount='#'vtNum=count+1;printf("%

11、3c",VTcount);printf("nVN:");count=0;while(VNcount!='0')printf("%3c",VNcount);count+;printf("n");/printf("n%d %dn",vtNum,vnNum);fclose(fp);grammarNum=i+1; return i;int vNumCount()int i,j;for(i=0;i<grammarNum;i+)j=1;while(Grammarij!='0')j

12、+;VNumi=j;/printf("%3d",VNumi);printf("n");return 0;void InitStack()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='#'

13、int Judge(int stateTop,char inputChar)int i,j;for(i=0;i<stateNum;i+)if(stateTop=i)break;for(j=0;j<vtNum;j+)if(inputChar=AVTj)break;return Actionij;int GetGoto(int stateTop,char inputChar)int i,j;for(i=0;i<stateNum;i+)if(stateTop=i)break;for(j=0;j<vnNum;j+)if(inputChar=GVNj)break;return G

14、otoij;int print(int count,int i,char Input,int action,int gt,int sign)int *p=state.base,stateNum;int j,jj;char *q=symbol.base,symbolNum;printf("%dt",count);while(p!=state.top+1)stateNum=*p;printf("%d",stateNum);p+;printf("t");while(q!=symbol.top+1)symbolNum=*q;printf(&q

15、uot;%c",symbolNum);q+;printf("t");j=i;jj=0;while(jj<j)printf(" ");jj+;while(Inputj!='0')printf("%c",Inputj);j+;printf("t");if(sign=1)printf("tS%dt%dn",action,gt);if(sign=2)printf("tr%dt%dn",action,gt);if(sign=3)printf("

16、tacct%dn",gt);if(sign=0)printf("t0t0n");return 0;int Pop(int action)int *p,stateNum,ssValue,i;state.top-;p=state.top;stateNum=*p;i=VNumaction-1;while(i!=0)symbol.top-;i-;symbol.top+;*symbol.top=Grammaraction0;ssValue=GetGoto(stateNum,Grammaraction0);if(ssValue=0)return ssValue;state.t

17、op+;*state.top=ssValue;return ssValue;int Reduction()char Input20;int i=0,count=1;int ssValue,action;int stateTop,gt;int sign=-1;/移進(jìn)1，規(guī)約2，接受3scanf("%s",&Input); while(Inputi!='0')if(Inputi>='A'&&Inputi<='Z')printf("輸入的不是有效的表達(dá)式！");return 0

18、;i+;i=0;printf("步驟t狀態(tài)棧t符號棧t輸入串ttACTIONtGOTOn");while(Inputi!='0')if(count=1)print(count,i,Input,0,0,0);count+;stateTop=*state.top;ssValue=Judge(stateTop,Inputi);if(ssValue=0)state.top-;if(*symbol.top='#')printf("規(guī)約出錯！");return 0;continue;if(ssValue=-1)sign=3;print(count,i,Input,ssValue,0,sign);count+;return 1;if(ssValue>=100)sign=1;action=ssValue-100;state.top+;*state.top=ac