自動生成LR0分析表

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 編譯原理實驗報告實驗名稱 自動生成LR（0）分析表 實驗時間 2011年6月13日 院系 計算機(jī)科學(xué)與技術(shù) 班級 08計算機(jī)科技一班 學(xué)號 E 姓名 王全鴻 1. 試驗?zāi)康妮斎耄喝我獾膲嚎s了的上下文無關(guān)文法。輸出：相應(yīng)的LR（0）分析表。2. 實驗原理在LR分析工作過程中的任何時候，棧里的文法符號（自棧底而上）X1X2Xm應(yīng)該構(gòu)成活前綴，把輸入串的剩余部分配上之后即應(yīng)成為規(guī)范句型（如果整個輸入串確實構(gòu)成一個句子）。因此，只要輸入串的已掃描部分保持可歸約成一個活前綴，那就意味著所掃描過的部分沒有錯誤。構(gòu)造識別文法活前綴DFA有3種方法：（1）根據(jù)形式定義求出活前綴的正

2、則表達(dá)式，然后由此正則表達(dá)式構(gòu)造NFA再確定為DFA；（2）求出文法的所有項目，按一定規(guī)則構(gòu)造識別活前綴的NFA再確定化為DFA；（3）使用閉包函數(shù)（CLOSURE）和轉(zhuǎn)向函數(shù)(GO(I,X)構(gòu)造文法G的LR(0)的項目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系來得到識別活前綴的DFA。對于LR（0）文法，我們可以直接從它的項目集規(guī)范族C和活前綴識別自動機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)GO構(gòu)造出LR分析表。下面是構(gòu)造LR（0）分析表的算法。假定C=I0, I1,，In，令每個項目集Ik的下標(biāo)k為分析器的一個狀態(tài)，因此，G'的LR(0)分析表含有狀態(tài)0，1，n。令那個含有項目S'S的Ik的下標(biāo)

3、k為初態(tài)。ACTION子表和GOTO子表可按如下方法構(gòu)造：（1）若項目A.a屬于Ik且GO (Ik, a)= Ij, a為終結(jié)符，則置ACTIONk, a為“把狀態(tài)j和符號a移進(jìn)?！保営洖椤皊j”；（2）若項目A屬于Ik，那么，對任何終結(jié)符a，置ACTIONk，a為“用產(chǎn)生式A進(jìn)行規(guī)約”，簡記為“rj”；其中，假定A為文法G'的第j個產(chǎn)生式；（3）若項目S'S屬于Ik, 則置ACTIONk, #為“接受”，簡記為“acc”；（4）若GO (Ik, A)= Ij, A為非終結(jié)符，則置GOTOk, A=j；（5）分析表中凡不能用上述1至4填入信息的空白格均置上“出錯標(biāo)志”。按上述

4、算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個入口不含多重定義，則稱它為文法G的一張LR(0)分析表。具有LR(0)表的文法G稱為一個LR（0）文法，LR(0)文法是無二義的。3. 實驗內(nèi)容(1) 實現(xiàn)計算閉包closure（I）的算法；(2) 實現(xiàn)轉(zhuǎn)向函數(shù)Go（q，a）的算法；(3)構(gòu)造文法項目集函數(shù)CreateProjectSet（）；定義數(shù)據(jù)結(jié)構(gòu)：專心-專注-專業(yè)typedef struct SElemType *base,*top; int stacksize; SqStack;struct grammer char *g; char vt127; char vn27;

5、char s; int line;typedef struct prjsetint id;/項目集編號，從10000開始，與項目編號（從0開始）區(qū)別struct prjset *next;/指向下個項目集char prjtPROJECT_SET_SIZE+1;/PROJECT_SET_SIZE個單元,存儲項目的編號,prjt0項目編號的個數(shù)char pointafterPROJECT_SET_SIZE+1;/圓點后的字符,pointafter0字符個數(shù)struct prjset *actorgoPROJECT_SET_SIZE;char pointbefore;prjset,*pprjset;

6、4.實驗心得通過這次實驗我對LR（0）語法分析有了一個更熟悉的掌握,對預(yù)先定義的文法規(guī)則，并集成詞法分析、符號表管理等程序來生成LR（0）分析表有了清醒的認(rèn)識，并且對高級程序語言一般結(jié)構(gòu)和主要共同特征有了全面的認(rèn)識和理解.5.實驗代碼void CreateProjectSet()/構(gòu)造文法的項目集int i;int j;int k;int id = ID;pprjset p,q;root.I = root.tail = NULL;if(p = (pprjset)malloc(sizeof(prjset) = NULL) exit(1);p->id = id;p->next = NU

7、LL;p->prjt0 = 0;p->pointafter0 = 0;p->pointbefore = '0'for(j=0; j<PROJECT_SET_SIZE; j+)p->actorgoj = NULL;for(j=0; j<PROJECT_SET_SIZE; j+)p->actorgoj = NULL;root.I = p;root.tail = p;root.size = 1;for(i=0; i<project.line; i+)if(project.s=project.gpiGRAMMER_START_CHAR_P

8、OS&&DOT= project.gpiGRAMMER_START_CHAR_POS+1)JoinSet(root.I->prjt, project.gpiPROJECT_ID_POS);JoinSet(root.I->pointafter, project.gpiAFCHAR_POS);break;/if/forClosure(root.I);int pos;for(q=root.I; q!=NULL; q=q->next)for(i=1; i<=q->pointafter0; i+)pos = i;pos-;if(p = (pprjset)ma

9、lloc(sizeof(prjset) = NULL) exit(1);p->next = NULL;p->prjt0 = 0;p->pointafter0 = 0;p->pointbefore = q->pointafteri;for(j=0; j<PROJECT_SET_SIZE; j+)p->actorgoj = NULL;for(j=1; j<=q->prjt0; j+)if(project.gpq->prjtjAFCHAR_POS = p->pointbefore)go(q->prjtj, p);/forClos

10、ure(p);/判斷p指向的項目集是否已存在pprjset ptr;int flag;int flagsame;flagsame = 1;flag = 1;for(ptr=root.I; ptr!=NULL; ptr=ptr->next)flag = 1;if(p->prjt0 = ptr->prjt0)for(k=1; k<=p->prjt0; k+)if(!IsInSet(ptr->prjt, p->prjtk)flag = 0;break;/if/for/ifelseflag = 0;/elseif(flag = 0)flagsame = 0;e

11、lseflagsame = 1;break;/forif(flagsame)/flagsame = 1 , 有與*p相同的項目集，刪除*pq->actorgoi-1 = ptr;free(p);else/將p掛到root.tailq->actorgoi-1 = p;p->id = +id;root.tail->next = p;root.tail = p;root.size+;/for/for/CreateProjectSetvoid Closure(prjset *pset)/rk 為項目的編號，prjset指向項目集int i;int j;int rk;for(i=

12、1; i<=pset->prjt0; i+)rk = pset->prjti;if(IsInSet(g.vn, project.gprkAFCHAR_POS)/若圓點后字符為vnfor(j=0; j<project.line; j+) if(project.gpjGRAMMER_START_CHAR_POS=project.gprkAFCHAR_POS && project.gpjGRAMMER_START_CHAR_POS+1 = DOT)JoinSet(pset->prjt, project.gpjPROJECT_ID_POS);JoinSet

13、(pset->pointafter, project.gpjAFCHAR_POS);/if/for/if/for/Closureint go(int rk, pprjset prjset)/rk為項目編號，將rk的去向加入prjset指向的項目集中,返回項目編號，若無返回-1int i;int j;int rksize;char rkS;char rkpointafter;if(rkpointafter = project.gprkAFCHAR_POS) = '0')return -1;int pointpos;pointpos = IsInSet(&projec

14、t.gprkPROJECT_LEN_POS, DOT);pointpos += PROJECT_LEN_POS;rksize = project.gprkPROJECT_LEN_POS;rkS = project.gprkGRAMMER_START_CHAR_POS;for(i=0; i<project.line; i+) if(project.gpiGRAMMER_START_CHAR_POS=rkS&&project.gpiPROJECT_LEN_POS = rksize && project.gpiBFCHAR_POS = rkpointafter)int flag;flag = 1;for(j=pointpos+2;j<=project.gpiPROJECT_LEN_POS+PROJECT_LEN_POS; j+)if(project.gpij != project.gprkj)flag = 0;break;/forif(flag)JoinSet(prjset->prjt, project.gpiPROJECT_ID_POS);/將項目加入項目集if(project.gpiAFCHAR_POS != '0')JoinSet(prjset