實驗三--LR分析法實驗報告

1、實驗三 LR(1)分析法一、實驗目的 構造LR(1)分析程序，利用它進行語法分析，判斷給出的符號串是否為該文法識別的句子，了解LR（K）分析方法是嚴格的從左向右掃描，和自底向上的語法分析方法。二、LR（1）分析法實驗設計思想及算法(1)總控程序，也可以稱為驅動程序。對所有的LR分析器總控程序都是相同的。(2)分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將不同，分析表又可以分為動作表（ACTION）和狀態(tài)轉換（GOTO）表兩個部分，它們都可用二維數(shù)組表示。(3)分析棧，包括文法符號棧和相應的狀態(tài)棧，它們均是先進后出棧。分析器的動作就是由棧頂狀態(tài)和當前輸入符號

2、所決定。u LR分析器由三個部分組成： u 其中:SP為棧指針，Si為狀態(tài)棧，Xi為文法符號棧。狀態(tài)轉換表用GOTOi，X=j表示，規(guī)定當棧頂狀態(tài)為i，遇到當前文法符號為X時應轉向狀態(tài)j，X為終結符或非終結符。u ACTIONi，a規(guī)定了棧頂狀態(tài)為i時遇到輸入符號a應執(zhí)行。動作有四種可能：(1)移進： actioni，a= Sj：狀態(tài)j移入到狀態(tài)棧，把a移入到文法符號棧，其中i,j表示狀態(tài)號。(2)歸約：actioni，a=rk：當在棧頂形成句柄時，則歸約為相應的非終結符A，即文法中有A- B的產生式，若B的長度為R(即|B|=R)，則從狀態(tài)棧和文法符號棧中自頂向下去掉R個符號，即棧指針SP減

3、去R，并把A移入文法符號棧內，j=GOTOi,A移進狀態(tài)棧，其中i為修改指針后的棧頂狀態(tài)。(3)接受acc:當歸約到文法符號棧中只剩文法的開始符號S時，并且輸入符號串已結束即當前輸入符是#，則為分析成功。(4)報錯:當遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入端不是該文法能接受的符號串。三、程序結構描述1、定義的變量string action126= s5,error,error,s4,error,error, error,s6,error,error,error,acc, error,r2,s7,error,r2,r2, error,r4,r4,error,r4,r4

4、, s5,error,error,s4,error,error, error,r6,r6,error,r6,r6, s5,error,error,s4,error,error, s5,error,error,s4,error,error, error,s6,error,error,s11,error, error,r1,r7,error,r1,r1, error,r3,r3,error,r3,r3, error,r5,r5,error,r5,r5 ;string go123= 1,2,3, error,error,error, error,error,error, error,error,er

5、ror, 8,2,3, error,error,error, error,9,3, error,error,10, error,error,error, error,error,error, error,error,error, error,error,error, ; /初始化預測分析表char Vt6=i,+,*,(,),#; 終結符表string LR6=E-E+T,E-T,T-T*F,T-F,F-(E),F-i;/LR文法stackS; 狀態(tài)棧stackX; 符號棧char input10; 輸入字符2、定義的函數(shù)int num(string s) 判斷字符串中的數(shù)字void prin

6、t(int i,char*c) 剩余輸入串的輸出int same(char a) 用于查找終結符void analyse() 分析程序四、程序源代碼及運行結果#include#include#include #includeusing namespace std;/初始化預測分析表string action126= s5,error,error,s4,error,error, error,s6,error,error,error,acc, error,r2,s7,error,r2,r2, error,r4,r4,error,r4,r4, s5,error,error,s4,error,erro

7、r, error,r6,r6,error,r6,r6, s5,error,error,s4,error,error, s5,error,error,s4,error,error, error,s6,error,error,s11,error, error,r1,r7,error,r1,r1, error,r3,r3,error,r3,r3, error,r5,r5,error,r5,r5 ;string go123= 1,2,3, error,error,error, error,error,error, error,error,error, 8,2,3, error,error,error,

8、 error,9,3, error,error,10, error,error,error, error,error,error, error,error,error, error,error,error, ;char Vt6=i,+,*,(,),#;/終結符表string LR6=E-E+T,E-T,T-T*F,T-F,F-(E),F-i;/LR文法stackS; /狀態(tài)棧stackX; /符號棧char input10; /輸入字符int num(string s) /判斷字符串中的數(shù)字 int i; string str=; for(int j=0;j=0&sj=9) str=str+s

9、j; i=atoi(str.c_str(); return i;void print(int i,char*c)/剩余輸入串的輸出 for(int j=i;j10;j+) coutcj; coutt; int same(char a) /用于查找終結符for(int i=0;i6;i+)if (a=Vti) return i;/*分析程序*void analyse() bool flag=true; /循環(huán)條件 int step=1,point=0,state=0; /步驟、指針、狀態(tài) char ch1,ch2; int m,n,l; /用于判斷終結符,分析表,表達式右部的長度string s

10、tr1; /用于判斷對應分析表中的符號string str2=#,str3=0; /記錄符號棧的所有元素cout請輸入要規(guī)約的字符串：input;X.push(#);S.push(0);cout步驟t狀態(tài)棧t符號棧t輸入串 t動作endl;coutstep+tstr3tstr2t;print(point,input);cout初始化endl; /*初始化/*進入循環(huán)while(flag)state=S.top();ch1=inputpoint;m=same(ch1);str1=actionstatem;/*移進動作if(str10=s)n=num(str1);S.push(n);X.push(

11、ch1);str2=str2+ch1;ch2=n+48;str3=str3+ch2;point+;coutstep+tstr3tstr2t;print(point,input);coutstr1:移進endl;/*歸約動作else if(str10=r)n=num(str1);l=LRn-1.length()-3;for(int i=1;i=l;i+) S.pop();str3=str3.substr(0,str3.length()-1);X.pop();str2=str2.substr(0,str2.length()-1);X.push(LRn-10);str2=str2+LRn-10;st

12、ate=S.top();if(LRn-10=E)S.push(num(gostate0);ch2=num(gostate0)+48;str3=str3+ch2;else if(LRn-10=T)S.push(num(gostate1);ch2=num(gostate1)+48;str3=str3+ch2;else if(LRn-10=F) S.push(num(gostate2);ch2=num(gostate2)+48;str3=str3+ch2;coutstep+tstr3tstr2t;print(point,input);coutstr1:LRn-1歸約endl;/*出錯else if(str1=error)coutERROR程序錯誤，分析結束！endl;flag=false;/*分析成功else if(str1=acc)cout分析成功，終止程序endl;flag=false;int main() analyse(); return 0; 測試：i*i+i結果：五、實驗總結此次課程設計中受益良多，從一開始的不知道從何入手，再到決定用的編程言、設計程序流程、調試，最后到程序運行成功。較好的文法分析器是功能全面的能自動構造其項目集和轉換函