實驗三LR(1)分析法

實驗學時：4

實驗類型:驗證

實驗規定:必修

一、實驗目的

構造LRQ)分析程序,運用它進行語法分析，判斷給出的符號串是否為該

文法辨認的句子，了解LR(K)分析方法是嚴格的從左向右掃描，和自底向上的

語法分析方法。

二、實驗內容

對下列文法，用LRQ)分析法對任意輸入的符號串進行分析:(產生式有誤,進行修

改)

(1)E-E+T

(2)E-E—T(E->T)

(3)T-T*F

(4)T-T/F(T->F)

(5)F-(E)

(6)F-i

三、實驗目的

1、編程時注意編程風格：空行的使用、注釋的使用、縮進的使用等。

2、假如碰到錯誤的表達式，應輸犯錯誤提醒信息。

3、程序輸入/輸出實例：

輸入一以#結束的符號串(涉及+—*/()i#)：在此位置輸入符號串

輸出過程如下：

環節狀態棧符號棧剩余輸入串動作

10#i+i*i#

移進

i+i*i的LR分析過程

環節狀態棧符號棧輸入動作說明

串

10#i+ACTION[0,i]=S5,狀態5入棧

i*i#

205#i+i*ir6：FT歸約,GOTO(0,F)=3入棧

#

303#F+i*i#r4:TTF歸約,GOTO(0,T)=3

入棧

402#T+i*i#r2:E-T歸約,GOTO。E)=l

入棧

501#E+iACTION[1,+]=S6,狀態6

*i#入棧

6016#E+i*i#ACTION[6,i]=S5,狀態5入棧

70165#E+i*i#r6：FT歸約,GOTO(6,F)=3入棧

80163#E+F*i#r4:T-F歸約,GOTO(6,T)=9入

棧

90169#E+T*i#ACTION[9/]=S7,狀態7入棧

1001697#E+T*i#ACTION[7,i]=S5,狀態5入棧

#

1101697#E+Tr6：FT歸約,GOT0(7,F)=1

5*i0入棧

12016#E+T#r3：T-*T*F歸約,GOTO(6,T)=9

9710*F入棧

130169#E+T#ri：ETE+T,GOTO(0,E)=l入棧

1401#E#Acc:分析成功

實驗報告正文的內容：

?描述LR(1)語法分析程序的設計思想：

?定義項目的一般形式是［A-a書，aiaoak］,這樣的一個項目稱為一個L

R(k)項目。項目中的aia2...ak稱為它的向前搜索符串(或展望串)，令K=L即

為LR⑴語法分析程序。在此,重新定義CLOSURE⑴的算法：

項目集I的閉包CLOSURE(I)構造方法：

1.I的任何項目都屬于CLOSURE⑴。

2.若項目［A-a+Bp,a］屬于CLOSURE(工)乃一匕是一個產生式,

那么，對于FIRST(ba)中的每個終結符6,假如［BT之句本來不在CLO

SUREQ)中，則把它加進去。

3.反復執行環節2,直至CLOSURE(I)不再增大為止。

GQ)的算法保持與LR語法分析程序同樣，通過以下方法構造文法分析表:

動作ACTION和狀態轉換GOTO構造如下：

1.若項目［A-a,aB,b］屬于工k且GO(Ik,a)=Ij,a為終結符，則

置ACT工ON［k,a］為句’。

2.若項目［A-wa］屬于工k,則置ACT］。N［k,a］為；其中假

定A-a為文法G，的第j個產生式。

3.若項目［SJ&,#］屬于Ik,則置ACTION［k,#］為"acc"。

4.若GO(工k,A)=Ij,則置GOTO。A］=jo

5.分析表中凡不能用規則1至4填入信息的空白欄均填上"犯錯標志"。

當具體面對輸入串時，通過查表進行分析該進行何種動作。

?程序結構描述：函數調用格式、參數含義、返回值描述、函數功能均在程序

源代碼出注釋出來,在此不再贅述，具體含義請參照源代碼Cpp文獻。

?具體的算法描述(程序執行流程圖)：

(1)總控程序，也可以稱為驅動程序。對所有的LR分析器總控程序都是相同

的。

(2)分析表或分析函數，不同的文法分析表將不同，同一個文法采用的LR分析器

不同時，分析表將不同，分析表又可以分為動作君ACTION)和狀態轉換(GOTO)

表兩個部分,它們都可用二維數組表達。

(3)分析棧，涉及文法符號棧和相應的狀態棧，它們均是先進后出棧。

分析器的動作就是由棧頂狀態和當前輸入符號所決定。

?LR分析器由三個部分組成：

LR分析器結構;

?其中：SP為棧指針，S[i]為狀態棧,X[i]為文法符號棧。狀態轉換表用G

0T0[i,X]=j表達，規定當棧頂狀態為i,碰到當前文法符號為X

時應轉向狀態j,X為終結符或非終結符。

?ACTION[i,a]規定了棧頂狀態為i時碰到輸入符號a應執行。動作有四

種也許：

(1)移進：

action[i,a]=Sj:狀態j移入到狀態棧，把a移入到文法符號棧，其中

i,j表達狀態號。

⑵歸約：

action[i,a]=rk:當在棧頂形成句柄時，則歸約為相應的非終結符A,

即文法中有A-B的產生式，若B的長度為R(即|B|=R),則從狀態棧和文法符

號棧中自頂向下去掉R個符號，即棧指針SP減去R,并把A移入文法符號棧內，

j=GOTO[i,A]移進狀態棧，其中i為修改指針后的棧頂狀態。

(3)接受acc:

當歸約到文法符號棧中只剩文法的開始符號S時，并且輸入符號串已結束即

當前輸入符是則為分析成功。

(4)報錯：

當碰到狀態棧頂為某一狀態下出現不該碰到的文法符號時，則報錯，說明輸

入端不是該文法能接受的符號串。

四、實驗規定

本程序原本的設計思想與實驗二相仿,但由于此種設計思想會導致程序靈

活性大大減少，故對設計思想進行優化，在此，不在對原程序設計思想進行

闡述，僅對改良后的程序設計思想進行闡述。

該文法的LR(1)分析表：

算術表達式文法的LR分析表

狀ACTIONGOTO

態i+*()#ETF

0s5s4123

acc

1s6

2「2S7「2「2

3「4「4「4「4

S4

4s5823

5「6「6「6「6

6S5S493

7S5S410

8s6Su

9riS7rir1

10「3「3r3「3

11「5r5r5r5

本程序根據給出的LR⑴文法分析表，構造string^0<Jaction[12]

nn

[6]={"S5"/0","0"/S4","O'VO",//ACTION表

nn

"0","S6"/"0",0/"0","acc",

"0","r2",nS7","0",72","r2",

"0n,nr4","r4","0","r4","r4n,

"S5","0","0"/"S4","0","0",

n

"0","r6r6","0","r6''lr6",

"S5",n0","0",nS4n,"0","0",

"S5",n0","0","S4","0","0",

"0","S6","0n,"0","Sil","0",

"0","r1","S7","0","r

"0","r3",nr3","0","r3n,nr3n,

"0"r5","r5","0r5","r5"};

int類的gotoarr[12][3]=

{1,2,3,//GOTO表

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},用以記錄LR(1)分析表的內容。

定義終結符集vt口，非終結符集vn[]產生式集合Production[]，狀態棧

status,用int類的數組Status記錄棧的內容，符號棧Stac

k,用string類的stacktd記錄棧的內容,定義移進函數Shift(),

Goto函數Goto(),歸約函數Reduction(),具體的分析函數Analyse

(),對于給定的字符串，讀取狀態棧的棧頂元素及字符串當前的首字母，先

通過函數Judge判斷符號棧棧頂元素是否在文法終結符集中，若不在,

則輸出Error,結束程序，若在其中，則返回字符串首字母在終結符vt[]

的下表，再通過查action表才丸行相相應的操作才丸行移進函數Shift()或

歸約函數Reduction(),同時若執行歸約操作，再通過查找Goto表判

斷應轉到的狀態，執行相應的Got。函數Goto()，反復進行以上環節，直至

分析執行至輸出acc或Error,程序結束。

?給出軟件的測試方法和測試結果:

根據程序的提醒，輸入一由該文法的終結符組成的字符串，程序即會進行分析,

具體的測試實例如下：

對的的輸入:

?.E:\study\PPT\洞譯原理\Debug*!l進2.exe*回漢

T->T*F

T->F

F-XE>

F->i

XXXXHXXXXXXXXXXXXXXXXLR<1>分析XXXXXXXXXXXXXXXXXXXXXXXXX

輸入字符串

i+i*i

xxxx*XXXXXXXXI啜進任如下分析”X***XXXM*XXXXXXXXXX*X*XX

步驟狀態棧符號棧動作說明…

10tti+i*ittnCTION[0,i]=S5,狀態5入棧

205#i+i*i#犬6：F->i歸約，GoToq0,F)=3入棧

303ttF?4：T->F歸約,GoTo〈0,T〉=2人;戔

402ttTA2：E->T歸約,GoTo40,E)=i入棧

501ttEACTION[1,+]=S6,狀態6人棧

6016ttE+i*i#ACTION[6,i]=S5,狀態5人棧

70165ttE+i*ittx6：F->i歸約,GoTo<6,F)=3入棧

80163ttE+F*i#r4：T->F歸約，GoTo46,T〉=9入棧

90169ttE+T*ittACTION19,?]=S7,狀態7入棧

1001697#E*T*illACTI0NC7,i]=S5,狀態5人棧

11016975ttE+T*ittN6：F->i歸約，GoTo<7,F>?10At

120169710ttE+T*Ftti*3：T-X*F歸約，GOTO<6,T>=9A

130169#E+Ttt￡：E->E+T歸約2GoTo<0,E〉=l入

1401ttEttacc分淅破功

是否繼續分析，丫或y繼續

*'E:\study\PPT\編譯^^\Debug\2^2.exe"回漢「

tLR<i>分析，

XXXXMXXXXXXXXMXXXXXXXX

八J

狀態棧符號棧泰

A4態4W

0tt<i>tt<]=s毒

5態

oN[ij=s5

約

，

04tt<.4,入

i>#^戌

->1G>

，

約<4*

045tt<i>tt?GOTO人

T->F<4T>戌

，*

4-約OTO

043tt<F>#2歸G=3

1r'E>T<4E>入

OTO燒

-喘

=2戌

042tt<T>#AC”=s1

約

IoN[a11=8棧

入

048tt<E；歸*

>#GTo<0入

>*

04811tt<E>，=3

戌

入

tt4T>F3約GT<0T>

r>"OTO<0*F>

03#Ftt，

3=2入a

相

2E>T舄GOTOE>

r:功

02#TItc*=1

ac

-h

01ttEU乂

錯誤的輸

入：

A

■,"E\study\PPT\^i^J^^\Debug\3^2.exe"-回SS

5042#<T>#F2：E->T歸約，GoTo<4,E〉=8人棧.

6048tt<E>ttACTIONS，.狀態11人棧

704811#<E>n歸約，GoTo<0,F)=3入棧

803ttFn￡4：T->F歸綱，GoTo<0,T>=2入核

902ttlUi*2：E->T歸納，GoTo<0,E)=：L入棧

1001#Ettacc分析成功

是否繼續分析，丫或y繼續

y

輸入字符串

<1>*<>

************************現進彳丁如下分析XXXXXXXXXXXWX-MWMXXXXXXX

步驟狀態棧符號棧薊余輸入電動作說明

10#ACTION[0-<]=S4,狀態4人棧

204#<ACTI0N[4,i]=S5,狀態5人棧

3045#<i>*<>#歸約，GoTo44,F)=3入福

4043#<F>*<>?犬4：T->F歸約，GoTo<4,T〉=2人或

5042tt<T>*<>?r2：E-X歸約，GoTo〈4,E)=8人棧

6048tt<E>*<>?ACTIONmQUSll,狀態11?入棧

704811#<E>*<>ttf5：F-XE)歸約，GoTo<0,F)=3人棧

803ttF*<>tti、4：T-〉F歸約，GoTo<0,T〉=2入棧

902#T*<>#ACTI0N[2,*]=S7,狀態7入榜

10027#T*OUACTI0N[7,<J=S4>狀態4人棧

是否繼續與荒丫或y繼續

?實驗總結(設計的特點、局限性、收獲與體會):

本程序摒棄了原設計思想，改使用構造action口及Goto□表來存儲L

R(1)分析表的內容，對于不同的產生式，只需修改其相應的action表，

G。t。表，終結符及非終結符表即可，大大提高了程序分析的靈活性，但由

于時間有限，測試實例局限性，程序也許存在未知錯誤，在此需進一步改

善,通過本次實驗，進一步加深了對于LR(1)分析法的理解與應用，同時關

于本次實驗，有幾點深刻的體會：程序的設計思想是程序的靈魂,在程序

編寫之前，一定要仔細閱讀實驗規定，對的理解實驗規定，并綜合考慮程序

的算法優化，靈活性等諸多方面，作出對的的設計思想。程序的實際編寫

工作是一門細致的工作,編寫過程中一定要認真仔細，由于程序中的一個

小錯誤也許會引起一連串的錯誤，同時編寫時務必具體仔細，避免程序的邏

輯錯誤，由于程序的邏輯錯誤調試是們十分復雜耗時的工作,對于程序編寫

中的一個小的邏輯錯誤，需要花費大量時間調試，而本實驗在編寫完畢后,

即消耗接近兩天的時間進行調試，所以程序的編寫務求認真、仔細、準確。

Ps:實驗源代碼請參照cpp文獻。

#inc1ude<iostream>

#include<stack>

#include<string>

usingnamespacestd;

stringaction[l2][6]={"S5","0","0","S4","0","0",

“ACTION表

"0","S6","000","acc",

。。

"0","r2","S7","0","r2","r2"f

????"0","r4","r4","0","r4","r4",

??"S5","0","0","S4","0","0",

。。。。"0","r6","r6","0","r6","r6",

?o"S5","0","0"f"S4","0","0",

?。。。"S5","0","0","S4","0","0",

。"0","S6","0","0","Sll","0",

。。。"0","rl","S7"0","rl","r1",

"0","r3","r3","0","r3","r3",

。。。。"0","r5","r5","0","r5","r5");

intgotoarr[l2][3]={1,2,3,/

/GOTO表

0,0,0,

?0,0,0,

。0,0,0,

???8,2,31

??0,0,0,

???0,9,3,

???0,0,10,

???0,0,0,

???0,0,0,

??0,0,0,

????0,0,0};

charvt[6]={'i');//存放終結符

charvn[3]={'E'f'T'；F');/陌放非終結符

stringProduction[6]={"E->E+T"f"E">T","T->T*F","T->F","F->

(E)"，“F->i"};〃產生式集合

intcount=0;〃記錄當前進行解決的輸入字符串字符位置

intline=l;〃記錄解決的環節數

boolflag=fa1se;

intStatusNumber=1;//棧中狀態數

stringstacktd="#";〃記錄符號棧中內容

intStatus[50]={0};〃記錄狀態棧

stack<char>Stack;//創建一個■棧

stack<int>status;〃創建一個狀態棧

voidJudge(int&i,intj,chararr[],charch,strings){//

判斷輸入串是否由文法終結符組成

fIag=faIse;

?for(int1=0;l<j;1++){

?if(ch==arr[l]){

?Iag=true;

?i=l;

??break;

Odd}

0}

?if(flag==fa1se){

cout<<"\tError"<<endl;

?count=s.size();

。}

)

voidOutputstatus(){//輸出狀態集

?for(inti=0;i<StatusNumber;i++)

?cout<<Status[i];

}

voidOutputstring(strings){/圖I出未解決的字符串

?for(inti=count;i<s.size();i++)

cout<<s.at(i);

)

voidOutput(strings){//輸出環節、狀態集、符號集、輸入串

cout<<line<<"\t";

OutputstatusQ;

cout<<"\t"<<stacktd<<"\t";

Outputstring(s);

cout<<"\t\t";

1ine++;

)

voidShift(inti,strings){//移進函數S

?Output(s);

cout<<"ACTION["<<status.top()<<","<<s.at(count)

<<"]=S"<<i<狀態"<<i<<"A^"<<endl;

status.push(i);〃將狀態i壓進狀態棧

Status[StatusNumber]=i;//Status記錄狀態棧的內容

Stack.push(s.at(count));〃將當前面臨的輸入串符號壓進符號

棧

stacktd=stacktd+s.at(count);//stacktd記錄符號棧的內容

count++;//當前面臨的輸入串字符往后移一位

StatusNumber++;//狀態數加一

)

voidGoto(stack<int>stl.stack<char>st2,strings)

{〃GoT。語句

intj=-1;

intchl=st1.top();

?charch2=st2.top();

Judge(j,3,vn,ch2,s);//求得ch2在mE終結瞳中的位置

if(gotoarr[chl][j]==0){

?cout<<"\tError"<<endl;

count=s.size();

)

?e1se{

??status.push(gotoarr[chl][j]);〃新狀態進棧

Status[StatusNumber]=gotoarr[ch1][j];

StatusNumber++;

4

}

voidReduction(inti,strings){〃歸約函數R

Output(s);

cout<<"r"<<i<<?'："<<production[i-1]<<“歸約,GoTo(";

?intN=Production[i-1].length()-3;

for(intj=0;j<N;j++){//消除要歸約的狀態及符號

?status.pop();

Stack.pop();

StatusNumber--;

??stacktd.erase(stacktd.length()-1);

)

?cout<<status.top()<<"f"<<Production[i-1].at(O)<<")=";

Stack.push(Production[i-1].at(O));//符號進棧

stacktd=stacktd+Stack.top();

Goto(status,Stack,s);

cout<<status.top()<<"<<end1;

Status[StatusNumber]=status.top();

)

voidAnalyse(strings){〃具體分析函數

oStack.push”');〃初始化

status.push(0);

s=s+"#";

?intt=-l;〃記錄ch在數組vt的位置

while(count<s.size()){

??inti=status.top