基于VC++的LL(1)語法分析器設(shè)計與實(shí)現(xiàn)

基于VC++的LL（1）語法分析器設(shè)計與實(shí)現(xiàn)學(xué)號：070108109第5頁共12頁基于VC++的LL（1）語法分析器設(shè)計與實(shí)現(xiàn)作者姓名：晏麗智指導(dǎo)老師：王一賓摘要：語法分析是編譯過程的核心部分，可以粗略的分為自上而下分析法和自下而上分析法。LL（1）文法是一類可以進(jìn)行確定的自上而下語法分析的文法。本文首先闡述了LL（1）文法的基本理論，然后著重討論了LL（1）語法分析器的設(shè)計，最后用VC++實(shí)現(xiàn)了LL（1）語法分析器。關(guān)鍵詞：LL（1）文法，F(xiàn)IRST集，F(xiàn)OLLOW集，預(yù)測分析表0引言語法分析是編譯過程的核心部分，它的任務(wù)是在詞法分析識別出單詞符號串的基礎(chǔ)上，分析并判定程序的語法結(jié)構(gòu)是否符合語法規(guī)則。LL（1）文法是一類可以進(jìn)行確定的自上而下語法分析的文法。本文討論了LL（1）語法分析器的工作原理和過程，重點(diǎn)說明了FIRST集、FOLLOW集以及預(yù)測分析表的構(gòu)造。1LL（1）語法分析器的基本理論1.1理論基礎(chǔ)語法分析是編譯過程的核心部分，它的任務(wù)是在詞法分析識別出單詞符號串的基礎(chǔ)上，分析并判定程序的語法結(jié)構(gòu)是否符合語法規(guī)則。語法分析器工作本質(zhì)：按文法的產(chǎn)生式，識別輸入符號串是否為一個句子，判斷是否能從文法的開始符號出發(fā)推導(dǎo)出這個輸入串。LL（1）文法是一類可以進(jìn)行確定的自上而下語法分析的文法。自上而下分析方法的基本思想是從文法的開始符號出發(fā)，向下推導(dǎo)，推出句子；即對任何輸入串，試圖用一切可能的辦法，從文法開始符號出發(fā)，自上而下地為輸入串建立一棵語法樹[1]。實(shí)現(xiàn)這種自上而下分析法存在許多困難，首先是遞歸問題，一個文法是含有左遞歸的，如果存在非終結(jié)符P，有PPa，則含有左遞歸的文法將使上述的自上而下的分析過程陷入無限循環(huán)。因此，使用自上而下分析法必須消除文法的左遞歸。其次是回溯問題。由于回溯造成的匹配虛假現(xiàn)象，把已經(jīng)做的一大堆語義工作推倒重來。這些事情既麻煩又費(fèi)時間，所以，最好應(yīng)設(shè)法消除回溯。1.2左遞歸的消除直接消除見諸于產(chǎn)生式中的左遞歸是比較容易的。假定關(guān)于非終結(jié)符P的規(guī)則為

P→Pα|?其中，?不以P開頭。那么我們可以把P的規(guī)則改寫為如下的非直接左遞歸形式：P→?P’P’→αP’|ε(ε為空字)這種形式和原來的形式是等價的，也就是說，從P推出的符號串是相同的。一般而言，假定關(guān)于P的全部產(chǎn)生式是P→Pα1|Pα2|…|Pαm|β1|β2|…βn其中α都不等于ε，且每個β不以P開頭。則改寫后為P→β1P′|β2P′|…|βnP′P′→α1P′|α2P′|…|αmP′|ε使用這個方法，我們?nèi)菀装岩娭T于表面的所有直接左遞歸都消除掉，也就是說，把直接左遞歸都改成直接右遞歸。對于間接左遞歸的消除可以采用代人法把間接左遞歸變成直接左遞歸[2]。下面給出消除左遞歸的算法：如果一個文法不含回路,也不含以ε為右部的產(chǎn)生式。(1)排序把文法G的所有非終結(jié)符按任一種順序排列P1、P2、…、Pn按序執(zhí)行。(2)代入及消除左遞歸for(i=1;i<=n;i++)for(j=1;j<=i－1;j++)把形如Pi→Pjγ的規(guī)則改寫為Pi→δ1γ|δ2γ|…|δkγ(其中Pj→δ1|δ2|…|δk是關(guān)于Pj的所有規(guī)則)消除關(guān)于Pi規(guī)則的直接左遞歸性(3)化簡化簡由（2）所得文法，即去除那些從開始符號出發(fā)永遠(yuǎn)無法到達(dá)的非終結(jié)符的產(chǎn)生式規(guī)則。1.3消除回溯、提左因子為了消除回溯就必須保證：對文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時，能夠根據(jù)它所面臨的輸入符號準(zhǔn)確地指派它的一個候選去執(zhí)行任務(wù)，并且次候選的工作結(jié)果是確信無疑的。也就是說，若此候選獲得成功匹配，那么，這種匹配不會是虛假的；若此候選無法完成任務(wù)，則任何其它候選也肯定也無法完成任務(wù)。換句話說，假定現(xiàn)在輪到非終結(jié)符A去執(zhí)行匹配任務(wù)，A共有n個候選α1，α2，……αn,即A→α1|α2|……αn。A能夠根據(jù)不同的輸入符號指派相應(yīng)的αi作為全權(quán)代表去執(zhí)行任務(wù)，那就肯定無需回溯了。在這里A已不再是讓某個候選去試探地執(zhí)行任務(wù)，而是根據(jù)所面臨的輸入符號α準(zhǔn)確地指派唯一的一個候選。其次，被指派候選的工作成敗也完全代表了A[3]。假定關(guān)于A的規(guī)則是A→δβ1|δβ2|……|δβn|γ1|γ2|……|γm(其中γi不以δ開頭)，提取公共左因子,改寫為A→δA′|γ1|γ2|……|γmA′→β1|β2|……|βn2LL（1）語法分析器的設(shè)計首先判別一個文法是否是LL（1）文法，如果不是LL（1）文法則需要轉(zhuǎn)化為LL（1）文法。要判別一個文法是否為LL（1）文法，首先需要給出FIRST集合、FOLLOW集合。2.1構(gòu)造FIRST集根據(jù)定義：FIRST（α）={a|αa...，a∈VT}，特別是，若α=>ε，則規(guī)定ε∈FIRST（α）。對于文法符號串X∈(VN∪VT)＊，其辦法是連續(xù)使用下面的規(guī)則，直至沒個集合不在增大為止。（1）若X∈VT，則FIRST（X）={X}。（2）

若X∈VN，且有產(chǎn)生式X→a…,則把a(bǔ)加入到FIRST(X)中；若X→ε也是一條產(chǎn)生式則把ε也加到FIRST（X）中。（3）

若X->Y…是一個產(chǎn)生式且Y∈VN,則把FIRST(Y)中的所有非ε元素都加到FIRST(X)中；若X表1LL（1）預(yù)測分析表

i+*（)#EE->TEˊ

E->TEˊ

Eˊ

Eˊ->+TEˊ

Eˊ->εEˊ->εTT->FTˊ

T->FTˊ

Tˊ

Tˊ->εTˊ->*FTˊ

Tˊ->εTˊ->εFF->i

F->(E)

（3）對輸入串進(jìn)行分析下面用預(yù)測分析法的總控程序、分析棧和預(yù)測分析表對輸入串i+i*i進(jìn)行分析，給出輸入串T的分析過程如表2所示：表2輸入串i+i*i的分析過程步驟分析棧（棧頂符號，當(dāng)前輸入符）剩余輸入串所用產(chǎn)生式1#E（E，i）

查表i+i*i#E->TEˊ2#EˊT（T，i）

查表i+i*i#T->FTˊ3#EˊTˊF（F，i）查表i+i*i#F->i4#EˊTˊi（i，i）i匹配i+i*i#

5#EˊTˊ（Tˊ，+）查表+i*i#Tˊ->ε6#Eˊ（Eˊ，+）查表+i*i#Eˊ->+TEˊ7#EˊT+（+，+）+匹配+i*i#

8#EˊT（T，i）查表i*i#T->FTˊ9#EˊTˊF（F，i）查表i*i#F->i10#EˊTˊi（i，i）i匹配i*i#

11#EˊTˊ（Tˊ，*）查表*i#Tˊ->*FTˊ12#EˊTˊF*（*，*）*匹配*i#

13#EˊTˊF（F，i）查表i#F->i14#EˊTˊi（i，i）i匹配i#

15#EˊTˊ（Tˊ，#）查表#Tˊ->ε16#Eˊ(Eˊ,#)查表#Eˊ->ε17###3LL（1）語法分析器的實(shí)現(xiàn)3.1總體設(shè)計該程序可分為如下幾步，流程圖如圖1：（1）讀入文法；（2）判斷正誤；（3）若無誤，判斷是否為LL(1)文法；（4）若是，構(gòu)造分析表；（5）由總控算法判斷輸入符號串是否為該文法的句型。開始開始讀入文法讀入文法有效？有效？是LL(1)文法？ 是是LL(1)文法？ 是報錯判斷句型 報錯判斷句型 結(jié)束結(jié)束圖1程序流程圖主函數(shù)設(shè)計如下：voidmain(){ inti,j; start=grammer(termin,non_ter,left,right);/*讀入一個文法*/printf("count=%d",count); printf("\nstart:%c",start); strcpy(v,non_ter); strcat(v,termin); printf("\nv:%s",v); printf("\nnon_ter:%s",non_ter);printf("\ntermin:%s",termin); printf("\nright:"); for(i=0;i<=count-1;i++) printf("%s",right[i]);printf("\nleft:"); for(i=0;i<=count-1;i++) printf("%c",left[i]);if(validity==1) validity=judge();printf("\nvalidity=%d",validity); if(validity==1) {printf("\n文法有效"); ll=ll1(); printf("\nll=%d",ll); if(ll==0) printf("\n該文法不是一個LL1文法！"); else { MM();printf("\n"); for(i=0;i<=19;i++) for(j=0;j<=19;j++) if(M[i][j]>=0) printf("M[%d][%d]=%d",i,j,M[i][j]); printf("\n"); menu(); } }}3.2詳細(xì)設(shè)計主要的程序代碼說明：（1）文法的存儲類型intcount=0;/*分解的產(chǎn)生式的個數(shù)*/intnumber;/*所有終結(jié)符和非終結(jié)符的總數(shù)*/charstart;/*開始符號*/chartermin[50];/*終結(jié)符號*/charnon_ter[50];/*非終結(jié)符號*/charv[50];/*所有符號*/charfirst[50][50],follow[50][50];/*各產(chǎn)生式右部的FIRST和左部的FOLLOW集合*/charfirst1[50][50];/*所有單個符號的FIRST集合*/charselect[50][50];/*各單個產(chǎn)生式的SELECT集合*/charf[50],F[50];/*記錄各符號的FIRST和FOLLOW是否已求過*/charempty[20];/*記錄可直接推出^的符號*/charTEMP[50];/*求FOLLOW時存放某一符號串的FIRST集合*/intvalidity=1;/*表示輸入文法是否有效*/intll=1;/*表示輸入文法是否為LL(1)文法*/intM[20][20];/*分析表*/charchoose;/*用戶輸入時使用*/charempt[20];/*求_emp()時使用*/charfo[20];/*求FOLLOW集合時使用*/文法的終結(jié)符和非終結(jié)符分別存放在termin[50]和non_ter[50]中，number是所有非終結(jié)符合終結(jié)符個數(shù)總和，start存放文法的開始符號，產(chǎn)生式個數(shù)存放在count中。（2）產(chǎn)生式存儲類型charleft[50];/*左部*/charright[50][50];/*右部*/文法產(chǎn)生式的左部非終結(jié)符存放在字符型數(shù)組left[50]中，產(chǎn)生式右部符號串存放在字符型數(shù)組right[50][50]中。讀入一個文法時將產(chǎn)生式放在P[50][50]數(shù)組中，傳值到形參point中，分解產(chǎn)生式時完整的產(chǎn)生式在point[]中。（3）FIRST和FOLLOW集的構(gòu)造voidfirst2(inti)和voidFIRST(inti,char*p)分別是求單個符號的FIRST和各產(chǎn)生式右部的FIRST。這里因為前面已有一個first數(shù)組，而且又用first1數(shù)組存放所有單個符號的FIRST集合，為了避免重名，命名first2。求各產(chǎn)生式左部的FOLLOW用voidFOLLOW(inti)。其中i為符號在所有輸入符號中的序號。（4）LL（1）分析表的構(gòu)造voidMM(){inti,j,k,m; for(i=0;i<=19;i++)for(j=0;j<=19;j++)M[i][j]=-1;i=strlen(termin);termin[i]='#';/*將#加入終結(jié)符數(shù)組*/termin[i+1]='\0';for(i=0;i<=count-1;i++){for(m=0;;m++)if(non_ter[m]==left[i]) break;/*m為產(chǎn)生式左部非終結(jié)符的序號*/for(j=0;j<=strlen(select[i])-1;j++){ if(in(select[i][j],termin)==1){ for(k=0;;k++) if(termin[k]==select[i][j]) break;/*k為產(chǎn)生式右部終結(jié)符的序號*/M[m][k]=i; } } }}（4）其他函數(shù)設(shè)計voidrecur(char*point)用于分解含有左遞歸的產(chǎn)生式；voidemp(charc)是用于求所有能直接推出‘^’的符號；int_emp(charc)用于求某一符號能否推出‘^’，若能推出，返回1，否則返回0；intjudge()用于判斷讀入的文法是否正確；voidsyntax()是總控程序；3.3相關(guān)的運(yùn)行界面截圖及說明本程序的運(yùn)行壞境為VC++,執(zhí)行文件為LL(1).exe。進(jìn)入程序后即提示信息：請輸入文法的非終結(jié)符，等待用戶輸入文法的所有非終結(jié)符，然后按enter彈出下一個提示信息，依次要用戶根據(jù)要求輸入。第一階段輸入到把產(chǎn)生式輸入完成即會出現(xiàn)相應(yīng)的判斷命令。如圖2：圖2第一階段運(yùn)行界面第二階段輸入的是句型，會出現(xiàn)相應(yīng)的預(yù)測分析并判斷是否為該文法的句型。同時還有程序提示信息：是否繼續(xù)（yorn）,用戶輸入y則繼續(xù)執(zhí)行，否則程序結(jié)束。如圖3：圖3第二階段運(yùn)行界面4結(jié)束語本文介紹了LL（1）語法分析器的設(shè)計與實(shí)現(xiàn)，其主體有三個部分組成，非終結(jié)符的首終結(jié)符集、后隨符號集和預(yù)測分析表，討論了LL（1）語法分析器的工作原理和過程，重點(diǎn)說明了FIRST集、FOLLOW集以及預(yù)測分析表的構(gòu)造，最后對語法分析器的實(shí)現(xiàn)程序進(jìn)行分析。致謝本文能夠順利的完成，我衷心地感謝指導(dǎo)老師王一賓老師的悉心指導(dǎo)！同時也對在論文撰寫參考文獻(xiàn)[1]陳火旺,劉春林,譚慶平,等.程序設(shè)計語言編譯原理[M].北京:國防工業(yè)出版社,2004

[2]陳意云,張昱.編譯原理[M].北京:高等教育出版社,2003

[3]呂映芝,張素琴,蔣維杜.編譯原理[M].北京:清華大學(xué)出版社,2000

[4]Alfred

V.Aho,Ravi

Sethi,Jeffrey

D.Ullman.Compilers:principles,techniques,and

tools[M].北京.人民郵電出版社,2002

[5]Charles

N.Fischer,Richard

J.