編譯原理-LR(1)算法源代碼

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一. 實(shí)驗(yàn)?zāi)康?掌握LR(1)分析法的基本原理2掌握LR(1)分析表的構(gòu)造方法3掌握LR(1)驅(qū)動(dòng)程序的構(gòu)造方法二. 實(shí)驗(yàn)內(nèi)容及要求構(gòu)造LR(1)分析程序，利用它進(jìn)行語(yǔ)法分析，判斷給出的符號(hào)串是否為該文法識(shí)別的句子，了解LR（K）分析方法是嚴(yán)格的從左向右掃描，和自底向上的語(yǔ)法分析方法。根據(jù)某一文法編制調(diào)試LR（1）分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。本次實(shí)驗(yàn)的目的主要是加深對(duì)LR（1）分析法的理解。程序輸入/輸出示例：對(duì)下列文法，用LR（1）分析法對(duì)任意輸入的符號(hào)串進(jìn)行分析：（1）E->E+T （2）E->ET （3）T->T*F（4）T-&g

2、t;T/F（5）F->(E)（6）F->i輸出的格式如下：(1)LR（1）分析程序，編制人：姓名，學(xué)號(hào)，班級(jí)(2)輸入一以#結(jié)束的符號(hào)串(包括+*/（）i#)：在此位置輸入符號(hào)串(3)輸出過(guò)程如下：步驟 狀態(tài)棧 符號(hào)棧 剩余輸入串動(dòng)作10#i+i*i#移進(jìn)(4)輸入符號(hào)串為非法符號(hào)串(或者為合法符號(hào)串)備注：(1)在“所用產(chǎn)生式”一列中如果對(duì)應(yīng)有推導(dǎo)則寫(xiě)出所用產(chǎn)生式；如果為匹配終結(jié)符則寫(xiě)明匹配的終結(jié)符；如分析異常出錯(cuò)則寫(xiě)為“分析出錯(cuò)”；若成功結(jié)束則寫(xiě)為“分析成功”。(2) 在此位置輸入符號(hào)串為用戶(hù)自行輸入的符號(hào)串。注意：1.表達(dá)式中允許使用運(yùn)算符（+-*/）、分割符（括號(hào)）、字符i

3、，結(jié)束符#；2.如果遇到錯(cuò)誤的表達(dá)式，應(yīng)輸出錯(cuò)誤提示信息（該信息越詳細(xì)越好）；3.對(duì)學(xué)有余力的同學(xué)，測(cè)試用的表達(dá)式事先放在文本文件中，一行存放一個(gè)表達(dá)式，同時(shí)以分號(hào)分割。同時(shí)將預(yù)期的輸出結(jié)果寫(xiě)在另一個(gè)文本文件中，以便和輸出進(jìn)行對(duì)照；4可采用的其它的文法。三. 實(shí)驗(yàn)過(guò)程1、使用LR(1)的優(yōu)點(diǎn)：(1)LR分析器能夠構(gòu)造來(lái)識(shí)別所有能用上下文無(wú)關(guān)文法寫(xiě)的程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)。(2)LR分析方法是已知的最一般的無(wú)回溯移進(jìn)-歸約方法，它能夠和其他移進(jìn)-歸約方法一樣有效地實(shí)現(xiàn)。(3)LR方法能分析的文法類(lèi)是預(yù)測(cè)分析法能分析的文法類(lèi)的真超集。(4)LR分析器能及時(shí)察覺(jué)語(yǔ)法錯(cuò)誤,快到自左向右掃描輸入的最大可能。

4、為了使一個(gè)文法是LR的，只要保證當(dāng)句柄出現(xiàn)在棧頂時(shí)，自左向右掃描的移進(jìn)-歸約分析器能夠及時(shí)識(shí)別它便足夠了。當(dāng)句柄出現(xiàn)在棧頂時(shí)，LR分析器必須要掃描整個(gè)棧就可以知道這一點(diǎn)，棧頂?shù)臓顟B(tài)符號(hào)包含了所需要的一切信息。如果僅知道棧內(nèi)的文法符號(hào)就能確定棧頂是什么句柄。LR分析表的轉(zhuǎn)移函數(shù)本質(zhì)上就是這樣的有限自動(dòng)機(jī)。不過(guò)，這個(gè)有限自動(dòng)機(jī)不需要根據(jù)每步動(dòng)作讀棧，因?yàn)?，如果這個(gè)識(shí)別句柄的有限自動(dòng)機(jī)自底向上讀棧中的文法符號(hào)的話(huà)，它達(dá)到的狀態(tài)正是這時(shí)棧頂?shù)臓顟B(tài)符號(hào)所表示的狀態(tài)，所以，LR分析器可以從棧頂?shù)臓顟B(tài)確定它需要從棧中了解的一切。2、LR分析器由三個(gè)部分組成：(1)總控程序，也可以稱(chēng)為驅(qū)動(dòng)程序。對(duì)所有的LR分

5、析器總控程序都是相同的。(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)所決定。LR分析器結(jié)構(gòu)：輸入串XXX# 總控程序n1。10Xn。X1#ACTION表GOTO 表輸出其中: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é)符。ACTIONi

6、，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減去R，并把A移入文法符號(hào)棧內(nèi)，j=GOTOi,A移進(jìn)狀態(tài)棧，其中i為修改指針后的棧頂狀態(tài)。(3)接受acc:當(dāng)歸約到文法符號(hào)棧中只剩文法的開(kāi)始符號(hào)S時(shí)，并且輸入符號(hào)串已結(jié)束即當(dāng)前輸入符是'#'，則為分析成功。

7、(4)報(bào)錯(cuò):當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號(hào)時(shí)，則報(bào)錯(cuò)，說(shuō)明輸入端不是該文法能接受的符號(hào)串。3、LL（1）分析法實(shí)驗(yàn)設(shè)計(jì)思想及算法否否是是否是0，#分別入狀態(tài)棧和符號(hào)棧置ip指向w#的第一個(gè)符號(hào)令s是狀態(tài)棧棧頂，a是ip所指向的符號(hào)actions，a=Ssactions,a=reduce A->把a(bǔ)和s分別推入符號(hào)棧和狀態(tài)棧；使ip前進(jìn)到下一個(gè)字符分別從棧頂彈出|個(gè)符號(hào)，令s是當(dāng)前棧頂狀態(tài)，把a(bǔ)和gotos,A先后推入棧中，輸出產(chǎn)生式A->ActionA,a=accept結(jié)束出錯(cuò)處理4.實(shí)驗(yàn)的源程序代碼如下：#include<stdio.h>#inclu

8、de<string.h>char *action103="S3#","S4#",NULL, /*ACTION表*/ NULL,NULL,"acc", "S6#","S7#",NULL, "S3#","S4#",NULL, "r3#","r3#",NULL, NULL,NULL,"r1#", "S6#","S7#",NULL, NULL,NULL,

9、"r3#", "r2#","r2#",NULL, NULL,NULL,"r2#"int goto1102=1,2, /*QOTO表*/ 0,0, 0,5, 0,8, 0,0, 0,0, 0,9, 0,0, 0,0, 0,0;char vt3='a','b','#' /*存放非終結(jié)符*/char vn2='S','B' /*存放終結(jié)符*/char *LR4="E->S#","S->BB#"

10、;,"B->aB#","B->b#"/*存放產(chǎn)生式*/int a10;char b10,c10,c1;int top1,top2,top3,top,m,n;void main()int g,h,i,j,k,l,p,y,z,count;char x,copy10,copy110;top1=0;top2=0;top3=0;top=0;a0=0;y=a0;b0='#'count=0;z=0;printf("請(qǐng)輸入表達(dá)式n");doscanf("%c",&c1);ctop3=c1;top

11、3=top3+1;while(c1!='#');printf("步驟t狀態(tài)棧tt符號(hào)棧tt輸入串ttACTIONtGOTOn");doy=z;m=0;n=0; /*y,z指向狀態(tài)棧棧頂*/g=top;j=0;k=0;x=ctop;count+;printf("%dt",count);while(m<=top1) /*輸出狀態(tài)棧*/printf("%d",am); m=m+1;printf("tt");while(n<=top2) /*輸出符號(hào)棧*/printf("%c"

12、;,bn); n=n+1;printf("tt");while(g<=top3) /*輸出輸入串*/printf("%c",cg); g=g+1;printf("tt");while(x!=vtj&&j<=2) j+;if(j=2&&x!=vtj) printf("errorn"); return; if(actionyj=NULL)printf("errorn");return;elsestrcpy(copy,actionyj);if(copy0=&

13、#39;S') /*處理移進(jìn)*/z=copy1-'0' top1=top1+1;top2=top2+1;atop1=z;btop2=x;top=top+1;i=0;while(copyi!='#')printf("%c",copyi);i+;printf("n");if(copy0='r') /*處理歸約*/i=0;while(copyi!='#')printf("%c",copyi);i+;h=copy1-'0'strcpy(copy1,LRh);while(copy10!=vnk) k+;l=strlen(LRh)-4;top1=top1-l+1;top2=top2-l+1;y=atop1-1;p=goto1yk;atop1=p;btop2=copy10;z=p;printf("t");printf("%dn",p);while