自動(dòng)生成LR0分析表

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

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

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

4、算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個(gè)入口不含多重定義，則稱它為文法G的一張LR(0)分析表。具有LR(0)表的文法G稱為一個(gè)LR（0）文法，LR(0)文法是無(wú)二義的。3. 實(shí)驗(yàn)內(nèi)容(1) 實(shí)現(xiàn)計(jì)算閉包c(diǎn)losure（I）的算法；(2) 實(shí)現(xiàn)轉(zhuǎn)向函數(shù)Go（q，a）的算法；(3)構(gòu)造文法項(xiàng)目集函數(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;/項(xiàng)目集編號(hào)，從10000開始，與項(xiàng)目編號(hào)（從0開始）區(qū)別struct prjset *next;/指向下個(gè)項(xiàng)目集char prjtPROJECT_SET_SIZE+1;/PROJECT_SET_SIZE個(gè)單元,存儲(chǔ)項(xiàng)目的編號(hào),prjt0項(xiàng)目編號(hào)的個(gè)數(shù)char pointafterPROJECT_SET_SIZE+1;/圓點(diǎn)后的字符,pointafter0字符個(gè)數(shù)struct prjset *actorgoPROJECT_SET_SIZE;char pointbefore;prjset,*pprjset;

6、4.實(shí)驗(yàn)心得通過(guò)這次實(shí)驗(yàn)我對(duì)LR（0）語(yǔ)法分析有了一個(gè)更熟悉的掌握,對(duì)預(yù)先定義的文法規(guī)則，并集成詞法分析、符號(hào)表管理等程序來(lái)生成LR（0）分析表有了清醒的認(rèn)識(shí)，并且對(duì)高級(jí)程序語(yǔ)言一般結(jié)構(gòu)和主要共同特征有了全面的認(rèn)識(shí)和理解.5.實(shí)驗(yàn)代碼void CreateProjectSet()/構(gòu)造文法的項(xiàng)目集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指向的項(xiàng)目集是否已存在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相同的項(xiàng)目集，刪除*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 為項(xiàng)目的編號(hào)，prjset指向項(xiàng)目集int i;int j;int rk;for(i=

12、1; i<=pset->prjt0; i+)rk = pset->prjti;if(IsInSet(g.vn, project.gprkAFCHAR_POS)/若圓點(diǎn)后字符為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為項(xiàng)目編號(hào)，將rk的去向加入prjset指向的項(xiàng)目集中,返回項(xiàng)目編號(hào)，若無(wú)返回-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);/將項(xiàng)目加入項(xiàng)目集if(project.gpiAFCHAR_POS != '0')JoinSet(prjset