實(shí)驗(yàn)三--LR分析法實(shí)驗(yàn)報(bào)告

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

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

3、去R，并把A移入文法符號(hào)棧內(nèi)，j=GOTOi,A移進(jìn)狀態(tài)棧，其中i為修改指針后的棧頂狀態(tài)。(3)接受acc:當(dāng)歸約到文法符號(hào)棧中只剩文法的開始符號(hào)S時(shí)，并且輸入符號(hào)串已結(jié)束即當(dāng)前輸入符是#，則為分析成功。(4)報(bào)錯(cuò):當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號(hào)時(shí)，則報(bào)錯(cuò)，說明輸入端不是該文法能接受的符號(hào)串。三、程序結(jié)構(gòu)描述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, ; /初始化預(yù)測(cè)分析表char Vt6=i,+,*,(,),#; 終結(jié)符表string LR6=E-E+T,E-T,T-T*F,T-F,F-(E),F-i;/LR文法stackS; 狀態(tài)棧stackX; 符號(hào)棧char input10; 輸入字符2、定義的函數(shù)int num(string s) 判斷字符串中的數(shù)字void prin

6、t(int i,char*c) 剩余輸入串的輸出int same(char a) 用于查找終結(jié)符void analyse() 分析程序四、程序源代碼及運(yùn)行結(jié)果#include#include#include #includeusing namespace std;/初始化預(yù)測(cè)分析表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,+,*,(,),#;/終結(jié)符表string LR6=E-E+T,E-T,T-T*F,T-F,F-(E),F-i;/LR文法stackS; /狀態(tài)棧stackX; /符號(hào)棧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) /用于查找終結(jié)符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; /用于判斷終結(jié)符,分析表,表達(dá)式右部的長(zhǎng)度string s

10、tr1; /用于判斷對(duì)應(yīng)分析表中的符號(hào)string str2=#,str3=0; /記錄符號(hào)棧的所有元素cout請(qǐng)輸入要規(guī)約的字符串：input;X.push(#);S.push(0);cout步驟t狀態(tài)棧t符號(hào)棧t輸入串 t動(dòng)作endl;coutstep+tstr3tstr2t;print(point,input);cout初始化endl; /*初始化/*進(jìn)入循環(huán)while(flag)state=S.top();ch1=inputpoint;m=same(ch1);str1=actionstatem;/*移進(jìn)動(dòng)作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:移進(jìn)endl;/*歸約動(dòng)作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;/*出錯(cuò)else if(str1=error)coutERROR程序錯(cuò)誤，分析結(jié)束！endl;flag=false;/*分析成功else if(str1=acc)cout分析成功，終止程序endl;flag=false;int main() analyse(); return 0; 測(cè)試：i*i+i結(jié)果：五、實(shí)驗(yàn)總結(jié)此次課程設(shè)計(jì)中受益良多，從一開始的不知道從何入手，再到?jīng)Q定用的編程言、設(shè)計(jì)程序流程、調(diào)試，最后到程序運(yùn)行成功。較好的文法分析器是功能全面的能自動(dòng)構(gòu)造其項(xiàng)目集和轉(zhuǎn)換函