1、精選優(yōu)質(zhì)文檔-傾情為你奉上LR分析器一、 目的和要求通過設(shè)計(jì)、編制、調(diào)試一個典型的語法分析程序，實(shí)現(xiàn)對詞法分析程序所提供的單詞序列進(jìn)行語法檢查和結(jié)構(gòu)分析，進(jìn)一步掌握常用的語法分析方法。1、選擇最有代表性的語法分析方法，如LL(1) 語法分析程序、算符優(yōu)先分析程序和LR分析分析程序，并至少完成兩個題目。2、選擇對各種常見程序語言都用的語法結(jié)構(gòu)，如賦值語句（尤指表達(dá)式）作為分析對象，并且與所選語法分析方法要比較貼切。 實(shí)驗(yàn)前的準(zhǔn)備按實(shí)驗(yàn)的目的和要求，編寫語法分析程序，同時考慮相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。 調(diào)試調(diào)試?yán)討?yīng)包括符合語法規(guī)則的算術(shù)表達(dá)式，以及分析程序能夠判別的若干錯例。 輸出對于所輸入的算術(shù)表達(dá)式，

2、不論對錯，都應(yīng)有明確的信息告訴外界。 擴(kuò)充有余力的同學(xué)，可適當(dāng)擴(kuò)大分析對象。譬如： 算術(shù)表達(dá)式中變量名可以是一般標(biāo)識符，還可含一般常數(shù)、數(shù)組元素、函數(shù)調(diào)用等等。 除算術(shù)表達(dá)式外，還可擴(kuò)充分析布爾、字符、位等不同類型的各種表達(dá)式。加強(qiáng)語法檢查，盡量多和確切地指出各種錯誤。 編寫上機(jī)實(shí)習(xí)報(bào)告。二、背景知識 自下而上分析技術(shù)LR(K)方法LR(K)方法是一種自下而上的語法分析方法，是當(dāng)前最廣義的無回溯的“移進(jìn)- 歸約”方法。它根據(jù)棧中的符號串和向前查看的k(k³0)個輸入符號，就能唯一確定分析器的動作是移進(jìn)還是歸約，以及用哪個產(chǎn)生式進(jìn)行歸約。優(yōu)點(diǎn)：文法適用范圍廣；識別效率高；查錯能力強(qiáng)；可

3、自動構(gòu)造。邏輯組成：總控程序LR分析表LR分析器的結(jié)構(gòu)：一個LR分析器實(shí)際是一個帶先進(jìn)后出存儲器（棧）的確定下推自動機(jī)，它由一個輸入串、一個下推棧和一個帶有分析表的總控程序組成。棧中存放著由“歷史”和“展望”材料抽象而來的各種“狀態(tài)”。任何時候，棧頂?shù)臓顟B(tài)都代表了整個的歷史和已推測出的展望。為了有助于明確歸約手續(xù)，我們把已歸約出的文法符號串也同時放進(jìn)棧里。LR分析器的每一動作都由棧頂狀態(tài)和當(dāng)前輸入符號所唯一確定。 LR分析器模型圖分析器的任何一次移動都是根據(jù)棧頂狀態(tài)Sm和當(dāng)前輸入符號ai，去查看ACTION表并執(zhí)行ACTION（ Sm，ai）規(guī)定的動作，直至分析成功或失敗。LR分析表有兩個部分

4、：動作部分ACTION和狀態(tài)轉(zhuǎn)換部分GOTO。ACTIONS,a表明當(dāng)前狀態(tài)S面臨輸入符號a時應(yīng)該采取的動作：1、移入：將S,y的下一個狀態(tài)S以及當(dāng)前符號入棧。2、歸約：對棧頂?shù)姆柎凑漳硞€規(guī)則進(jìn)行歸約。3、接受：宣布輸入符號串為一個句子。4、報(bào)錯：宣布輸入符號串不是句子。GOTOS,U表示當(dāng)前狀態(tài)S和非終結(jié)符號匹配的時候所轉(zhuǎn)換到的下一個狀態(tài)。LR總控程序：LR總控程序示意圖LR分析器的工作過程是由總控程序根據(jù)分析表，使得分析器構(gòu)型從一種構(gòu)型向另一種構(gòu)型變化的過程。初始構(gòu)型：（S0，a1a2an $）， S0為分析器的初態(tài)，$為輸入串的括號。分析過程的每步結(jié)果可表示為：（S0X1S1XmSm

5、，aiai+1an$）。分析器的下一次動作是由棧頂狀態(tài)Sm和當(dāng)前輸入符號ai所唯一確定的，即：執(zhí)行ACTIONSm，ai規(guī)定的動作。經(jīng)執(zhí)行各種可能的動作后，分析器的構(gòu)型可如下變化：1、若ACTION(Sm，ai)=“移進(jìn)S”，則分析器構(gòu)型變?yōu)椋⊿0X1S1XmSmaiS，ai+1an$）。 2、若ACTION(Sm，ai)=“歸約A ”，則分析器構(gòu)型變?yōu)椋⊿0X1S1Xm-rSm-rAS，aiai+1an$）,其中SGOTO(Sm-r，A)，|=r 。 3、若ACTION(Sm，ai)=“接受”，則分析成功，正常停止。4、若ACTION(Sm，ai)=“ERROR”，語法出錯，進(jìn)行出錯處理。L

6、R分析表的構(gòu)造：LR(0)項(xiàng)目的定義：文法的每一個產(chǎn)生式的右部添加一個圓點(diǎn)（·），則構(gòu)成文法的一個LR(0)項(xiàng)目。設(shè)I是文法G的任一項(xiàng)目集，則定義和構(gòu)造CLOSURE(I)的規(guī)則如下：1、屬于I的任何項(xiàng)目也屬于CLOSURE(I)；2、若A ·B 屬于CLOSURE(I)，那么，對于任何關(guān)于B的產(chǎn)生式B ,項(xiàng)目B· 也屬于CLOSURE(I)；3、重復(fù)執(zhí)行以上兩步，直到CLOSURE(I)不再增大為止。構(gòu)成識別一個文法活前綴的DFA的項(xiàng)目集（狀態(tài)）的全體稱為這個文法的LR(0) 項(xiàng)目集規(guī)范族。構(gòu)成過程如下：1、文法拓廣；2、構(gòu)造拓廣文法的LR(0)項(xiàng)目集規(guī)范族3、

7、由初始項(xiàng)目出發(fā)，利用CLOSURE和goto函數(shù)；4、將LR(0)項(xiàng)目集規(guī)范族中的每個項(xiàng)目集作為FA的狀態(tài)，將goto函數(shù)作為狀態(tài)轉(zhuǎn)換函數(shù)，構(gòu)造出的FA即為所求。項(xiàng)目集I的閉包CLOSURE(I)：設(shè)I是文法G的任一項(xiàng)目集，則定義和構(gòu)造CLOSURE(I)的規(guī)則如下：1、屬于I的任何項(xiàng)目也屬于CLOSURE(I)；2、若A .B 屬于CLOSURE(I)，那么，對于任何關(guān)于B的產(chǎn)生式B ,項(xiàng)目B . 也屬于CLOSURE(I)；3、重復(fù)執(zhí)行以上兩步，直到CLOSURE(I)不再增大為止。LR(0) 文法的判定：如果文法G的項(xiàng)目集規(guī)范族的每個項(xiàng)目集中不存在下述沖突項(xiàng)目：1、移進(jìn)項(xiàng)目和歸約項(xiàng)目并存

8、，2、多個歸約項(xiàng)目并存，則稱文法G為LR(0)文法。只有對于LR(0)文法，才能構(gòu)造它的LR(0)分析表。構(gòu)造LR(0)分析表的步驟如下：1、若項(xiàng)目A.a Ii且goto(Ii,a)=Ij,其中a為終結(jié)符，置ACTIONi,a=“把狀態(tài)j和符號a移進(jìn)棧”，簡記為“sj”;2、若項(xiàng)目A. Ii ,則對于任何輸入符a或結(jié)束符$，置ACTIONi,a=“用產(chǎn)生式 A進(jìn)行歸約”，簡記為“rj”(假定A是文法G的第j條產(chǎn)生式);3、若項(xiàng)目SS. Ii ,則置ACTIONi,$=“接收”，簡記為acc；4、若goto(I,A)=Ij,A 為非終結(jié)符，則置GOTO(i,A)=j5、分析表中凡不能用規(guī)則1 4

9、添入信息的元素均置上ERROR。三、實(shí)驗(yàn)內(nèi)容要求：給定分析對象的LR分析表和一個分析對象的句子，輸出該句子分析的結(jié)果。否否是是否是0，#分別入狀態(tài)棧和符號棧置ip指向w#的第一個符號令s是狀態(tài)棧棧頂，a是ip所指向的符號actions，a=Ssactions,a=reduce A->把a(bǔ)和s分別推入符號棧和狀態(tài)棧；使ip前進(jìn)到下一個字符分別從棧頂彈出|個符號，令s是當(dāng)前棧頂狀態(tài)，把a(bǔ)和gotos,A先后推入棧中，輸出產(chǎn)生式A->ActionA,a=accept結(jié)束出錯處理程序輸入/輸出示例：對下列文法，用LR（1）分析法對任意輸入的符號串進(jìn)行分析：（1）E->E+T （2）E

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

11、符i，結(jié)束符#；2.如果遇到錯誤的表達(dá)式，應(yīng)輸出錯誤提示信息（該信息越詳細(xì)越好）；3.對學(xué)有余力的同學(xué)，測試用的表達(dá)式事先放在文本文件中，一行存放一個表達(dá)式，同時以分號分割。同時將預(yù)期的輸出結(jié)果寫在另一個文本文件中，以便和輸出進(jìn)行對照；四、設(shè)計(jì)思路模塊結(jié)構(gòu)：（1）定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。（2）初始化：設(shè)立LR(1)分析表、初始化變量空間（包括堆棧、結(jié)構(gòu)體、數(shù)組、臨時變量等）；（3）控制部分：從鍵盤輸入一個表達(dá)式符號串；（4）利用LR(1)分析算法進(jìn)行表達(dá)式處理：根據(jù)LR(1)分析表對表達(dá)式符號串進(jìn)行堆棧（或其他）操作，輸出分析結(jié)果，如果遇到錯誤則顯示錯誤信息。五、相關(guān)代碼 

12、;#include<stdio.h> #include<string.h>  char *action103="S3#","S4#",NULL, NULL,NULL,"acc",  "S6#","S7#",NULL, "S3#","S4#",NULL,    "r3#","r3#&qu

13、ot;,NULL, NULL,NULL,"r1#",  "S6#","S7#",NULL, NULL,NULL,"r3#",  "r2#","r2#",NULL,   NULL,NULL,"r2#" int goto1102=1,2,    0,0,     

14、  0,5,       0,8,       0,0,       0,0,       0,9,       0,0,       0,0, &#

15、160;  0,0; char vt3='a','b','#'                       /*存放非終結(jié)符*/ char vn2='S','B'     

16、0;                  char *LR4="E->S#","S->BB#","B->aB#","B->b#"/*存放產(chǎn)生式*/  int a10; char b10,c10,c1; int top1,top2,top3

17、,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("請輸入表達(dá)式n");  do  scanf("%c

18、",&c1);   ctop3=c1;   top3=top3+1;  while(c1!='#');  printf("步驟t狀態(tài)棧tt符號棧tt輸入串ttACTIONtGOTOn");  do   y=z;m=0;n=0;              &

19、#160;       /*y,z指向狀態(tài)棧棧頂*/   g=top;j=0;k=0;   x=ctop;   count+;   printf("%dt",count);   while(m<=top1)            &#

20、160;       /*輸出狀態(tài)棧*/  printf("%d",am);             m=m+1;      printf("tt");   while(n<=top2)     

21、;               /*輸出符號棧*/   printf("%c",bn);             n=n+1;      printf("tt");  &

22、#160;while(g<=top3)                    /*輸出輸入串*/  printf("%c",cg);             g=g+1;    

23、60; printf("tt");   while(x!=vtj&&j<=2) j+;   if(j=2&&x!=vtj)     printf("errorn");       return;    if(actionyj=NULL)    

24、;printf("errorn");    return;      else    strcpy(copy,actionyj);   if(copy0='S')                   &#

25、160;  /*處理移進(jìn)*/  z=copy1-'0'             top1=top1+1;    top2=top2+1;    atop1=z;    btop2=x;    top=top+1;   

26、60;i=0;    while(copyi!='#')     printf("%c",copyi);     i+;        printf("n");      if(copy0='r')                      /*處理