基于VC++的LL(1)語法分析器設計與實現

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

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

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

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

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）對輸入串進行分析下面用預測分析法的總控程序、分析棧和預測分析表對輸入串i+i*i進行分析，給出輸入串T的分析過程如表2所示：表2輸入串i+i*i的分析過程步驟分析棧（棧頂符號，當前輸入符）剩余輸入串所用產生式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）語法分析器的實現3.1總體設計該程序可分為如下幾步，流程圖如圖1：（1）讀入文法；（2）判斷正誤；（3）若無誤，判斷是否為LL(1)文法；（4）若是，構造分析表；（5）由總控算法判斷輸入符號串是否為該文法的句型。開始開始讀入文法讀入文法有效？有效？是LL(1)文法？ 是是LL(1)文法？ 是報錯判斷句型 報錯判斷句型 結束結束圖1程序流程圖主函數設計如下：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詳細設計主要的程序代碼說明：（1）文法的存儲類型intcount=0;/*分解的產生式的個數*/intnumber;/*所有終結符和非終結符的總數*/charstart;/*開始符號*/chartermin[50];/*終結符號*/charnon_ter[50];/*非終結符號*/charv[50];/*所有符號*/charfirst[50][50],follow[50][50];/*各產生式右部的FIRST和左部的FOLLOW集合*/charfirst1[50][50];/*所有單個符號的FIRST集合*/charselect[50][50];/*各單個產生式的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集合時使用*/文法的終結符和非終結符分別存放在termin[50]和non_ter[50]中，number是所有非終結符合終結符個數總和，start存放文法的開始符號，產生式個數存放在count中。（2）產生式存儲類型charleft[50];/*左部*/charright[50][50];/*右部*/文法產生式的左部非終結符存放在字符型數組left[50]中，產生式右部符號串存放在字符型數組right[50][50]中。讀入一個文法時將產生式放在P[50][50]數組中，傳值到形參point中，分解產生式時完整的產生式在point[]中。（3）FIRST和FOLLOW集的構造voidfirst2(inti)和voidFIRST(inti,char*p)分別是求單個符號的FIRST和各產生式右部的FIRST。這里因為前面已有一個first數組，而且又用first1數組存放所有單個符號的FIRST集合，為了避免重名，命名first2。求各產生式左部的FOLLOW用voidFOLLOW(inti)。其中i為符號在所有輸入符號中的序號。（4）LL（1）分析表的構造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]='#';/*將#加入終結符數組*/termin[i+1]='\0';for(i=0;i<=count-1;i++){for(m=0;;m++)if(non_ter[m]==left[i]) break;/*m為產生式左部非終結符的序號*/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為產生式右部終結符的序號*/M[m][k]=i; } } }}（4）其他函數設計voidrecur(char*point)用于分解含有左遞歸的產生式；voidemp(charc)是用于求所有能直接推出‘^’的符號；int_emp(charc)用于求某一符號能否推出‘^’，若能推出，返回1，否則返回0；intjudge()用于判斷讀入的文法是否正確；voidsyntax()是總控程序；3.3相關的運行界面截圖及說明本程序的運行壞境為VC++,執(zhí)行文件為LL(1).exe。進入程序后即提示信息：請輸入文法的非終結符，等待用戶輸入文法的所有非終結符，然后按enter彈出下一個提示信息，依次要用戶根據要求輸入。第一階段輸入到把產生式輸入完成即會出現相應的判斷命令。如圖2：圖2第一階段運行界面第二階段輸入的是句型，會出現相應的預測分析并判斷是否為該文法的句型。同時還有程序提示信息：是否繼續(xù)（yorn）,用戶輸入y則繼續(xù)執(zhí)行，否則程序結束。如圖3：圖3第二階段運行界面4結束語本文介紹了LL（1）語法分析器的設計與實現，其主體有三個部分組成，非終結符的首終結符集、后隨符號集和預測分析表，討論了LL（1）語法分析器的工作原理和過程，重點說明了FIRST集、FOLLOW集以及預測分析表的構造，最后對語法分析器的實現程序進行分析。致謝本文能夠順利的完成，我衷心地感謝指導老師王一賓老師的悉心指導！同時也對在論文撰寫參考文獻[1]陳火旺,劉春林,譚慶平,等.程序設計語言編譯原理[M].北京:國防工業(yè)出版社,2004

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

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

[4]Alfred

V.Aho,Ravi

Sethi,Jeffrey

D.Ullman.Compilers:principles,techniques,and

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

[5]Charles

N.Fischer,Richard

J.