第一篇：自動(dòng)生成LR0分析表

編譯原理實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)名稱

實(shí)驗(yàn)時(shí)間2011年6月13日

院系計(jì)算機(jī)科學(xué)與技術(shù)

班級(jí)08計(jì)算機(jī)科技一班

學(xué)號(hào)E10814065

姓名王全鴻

1.試驗(yàn)?zāi)康妮斎耄喝我獾膲嚎s了的上下文無關(guān)文法。輸出：相應(yīng)的LR（0）分析表。

2.實(shí)驗(yàn)原理

在LR分析工作過程中的任何時(shí)候，棧里的文法符號(hào)（自棧底而上）X1X2…Xm應(yīng)該構(gòu)成活前綴，把輸入串的剩余部分配上之后即應(yīng)成為規(guī)范句型（如果整個(gè)輸入串確實(shí)構(gòu)成一個(gè)句子）。因此，只要輸入串的已掃描部分保持可歸約成一個(gè)活前綴，那就意味著所掃描過的部分沒有錯(cuò)誤。

構(gòu)造識(shí)別文法活前綴DFA有3種方法：

（1）根據(jù)形式定義求出活前綴的正則表達(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)系來得到識(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)k為初態(tài)。ACTION子表和GOTO子表可按如下方法構(gòu)造：

（1）若項(xiàng)目A→α.aβ屬于Ik且GO(Ik, a)= Ij, a為終結(jié)符，則置ACTION[k, a]為“把狀態(tài)j和符號(hào)a移進(jìn)?！?，簡記為“sj”；

（2）若項(xiàng)目A→α．屬于Ik，那么，對(duì)任何終結(jié)符a，置ACTION[k，a]為“用產(chǎn)生式A→α進(jìn)行規(guī)約”，簡記為“rj”；其中，假定A→α為文法G'的第j個(gè)產(chǎn)生式；（3）若項(xiàng)目S'→S．屬于Ik, 則置ACTION[k, #]為“接受”，簡記為“acc”；（4）若GO(Ik, A)= Ij, A為非終結(jié)符，則置GOTO[k, A]=j；

（5）分析表中凡不能用上述1至4填入信息的空白格均置上“出錯(cuò)標(biāo)志”。

按上述算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個(gè)入口不含多重定義，則稱它為文法G的一張LR(0)分析表。具有LR(0)表的文法G稱為一個(gè)LR（0）文法，LR(0)文法是無二義的。

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)：

typedef struct{SElemType *base,*top;int stacksize;}SqStack;

struct grammer{char **g;char vt[127];

};

char vn[27];char s;int line;

typedef struct prjset {int id;//項(xiàng)目集編號(hào)，從10000開始，與

項(xiàng)目編號(hào)（從0開始）區(qū)別

struct prjset *next;//指向下個(gè)項(xiàng)目集char

prjt[PROJECT_SET_SIZE+1];//PROJECT_SET_SIZE個(gè)單元,存儲(chǔ)項(xiàng)目的編號(hào),prjt[0]項(xiàng)目編號(hào)的個(gè)數(shù)

char pointafter[PROJECT_SET_SIZE+1];//

圓點(diǎn)后的字符,pointafter[0]字符個(gè)數(shù)struct prjset *actorgo[PROJECT_SET_SIZE];char pointbefore;}prjset,*pprjset;

4.實(shí)驗(yàn)心得

通過這次實(shí)驗(yàn)我對(duì)LR（0）語法分析有了一個(gè)更熟悉的掌握,對(duì)預(yù)先定義的文法規(guī)則，并集成詞法分析、符號(hào)表管理等程序來生成LR（0）分析表有了清醒的認(rèn)識(shí)，并且對(duì)高級(jí)程序語言一般結(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)))==

{

JoinSet(root.I->prjt, JoinSet(root.I->pointafter,project.gp[i][PROJECT_ID_POS]);project.gp[i][AFCHAR_POS]);

break;}//if

}//for

Closure(root.I);int pos;

for(q=root.I;q!=NULL;q=q->next){

for(i=1;i<=q->pointafter[0];i++){

NULL)exit(1);p->id = id;

p->next = NULL;p->prjt[0] = 0;

p->pointafter[0] = 0;p->pointbefore = '