編譯原理課程設(shè)計LL(1)文法分析

編譯原理課程設(shè)計——LL(1)語法分析

課題綜述算法介紹人員分工程序流程目錄課題綜述

語法分析是編譯程序的核心部分。語法分析的作用是識別由詞法分析給出的單詞符號序列是否是給定的文法的正確句子。目前語法分析常用的方法右自頂向下分析和自底向上分析兩大類。

確定的自頂向下方法，是從文法的開始符號，考慮如何根據(jù)當(dāng)前的輸入符號（單詞）唯一的確定選用哪個產(chǎn)生式替換相應(yīng)非終結(jié)符往下推導(dǎo)。LL(1)文法是一種確定的自頂向下的分析方法。

LL(1)的含義是：第一個L表明自頂向下分析從左向右掃描輸入串，第二個L表明分析過程中將用最左推導(dǎo)，1表明只需向右看一個符號便可以決定如何推導(dǎo)即選擇哪個產(chǎn)生式（即規(guī)則）進行推導(dǎo)。

算法介紹1、在對輸入序列進行LL(1)文法分析之前，首先要對文法進行判別，看文法是不是LL(1)文法。這個文法應(yīng)該滿足無二義性，無左遞歸，無公因子。具體的判別過程是，求出能推出ε的非終結(jié)符，求出FIRST集，求出FOLLOW集，求出SELLECT集，看相同左部的產(chǎn)生式的SELLECT集是否有交集，有就不是LL（1）文法。2、如果輸入文法不是LL(1)文法，可以進行轉(zhuǎn)換，轉(zhuǎn)換一般有兩種方法：提取左公因子法和消除左遞歸法。3、構(gòu)造預(yù)測分析表，設(shè)二維矩陣M。4、預(yù)測分析。人員分工負(fù)責(zé)MFC界面制作，程序總控，各個非終結(jié)符能否推出ε的計算,判斷是否LL(1),以及人員分工。消除左遞歸的實現(xiàn)提取公因子的實現(xiàn)求FIRST集求FOLLOW集求SELLECT集構(gòu)造預(yù)測分析表，分析輸入的句子程序流程程序開始InitAndConvertPt();//讀入文法、消除左遞歸、提取公因子InitArray();//初始化N[]數(shù)組VnRefresh(Pt);//構(gòu)造非終結(jié)符集VtRefresh(Pt);//構(gòu)造終結(jié)符集Create_N_Table();//判斷哪些非終結(jié)符可以推出空,存入N[]FirstVt();//求FIRST集FollowVt();//求Follow集SelectVt();//求Select集是不是LL(1)輸出不是LL（1）文法NOyes構(gòu)造預(yù)測分析表分析表達式界面輸出提取公因子

使產(chǎn)生式右部沒有公共因子。若產(chǎn)生式右部有左公因子，則反復(fù)提取，直到引進的新非終結(jié)符的有關(guān)的產(chǎn)生式再無左公共因子為止。

消除左遞歸左遞歸分為直接左遞歸和間接左遞歸。（1）直接左遞歸的處理

我們利用引入新非終結(jié)符的方法來消除左遞歸：

如：

U→Ux|y（其中x,yV+，y不以U開頭），引入一個新的非終結(jié)符U’后，可以等價地改寫成為：

U→yU’

U’→x

U’|ε

（2）間接左遞歸的處理對于間接左遞歸的消除需要通過產(chǎn)生式非終結(jié)符置換，將間接左遞歸變?yōu)橹苯幼筮f歸，然后按直接左遞歸消除。終結(jié)符推出ε的計算分為三步：1、將數(shù)組N中對應(yīng)每一非終結(jié)符的標(biāo)記置初值為“未定”2、掃描文法中的產(chǎn)生式。1）刪除所有右部含有終結(jié)符的產(chǎn)生式，若這使得以某一非終結(jié)符為左部的所有產(chǎn)生式都被刪除，則將數(shù)組中對應(yīng)該非終結(jié)符的標(biāo)記值改為“否”，說明該非終結(jié)符不能推出ε。2）若某一非終結(jié)符的某一產(chǎn)生式右部為ε，則將數(shù)組中對應(yīng)該非終結(jié)符的標(biāo)志置為“是”，并從文法中刪除該非終結(jié)符的所有產(chǎn)生式。3、掃描產(chǎn)生式右部的每一個符號。1）若所掃描到的非終結(jié)符號在數(shù)組中對應(yīng)的標(biāo)志是"是"，則刪去該非終結(jié)符，若這使產(chǎn)生式右部為空，則對產(chǎn)生式左部的非終結(jié)符在數(shù)組中對應(yīng)的標(biāo)志改"是"，并刪除該非終結(jié)符為左部的所有產(chǎn)生式。2）若所掃描到的非終結(jié)符號在數(shù)組中對應(yīng)的標(biāo)志是"否"，則刪去該產(chǎn)生式，若這使產(chǎn)生式左部非終結(jié)符的有關(guān)產(chǎn)生式都被刪去，則把在數(shù)組中該非終結(jié)符對應(yīng)的標(biāo)志改成"否"。4、重復(fù)3，直到掃描完一遍文法的產(chǎn)生式，數(shù)組中非終結(jié)符對應(yīng)的特征再沒有改變?yōu)橹?。FIRST集合的計算FIRST集合的構(gòu)造算法：（1）若X∈VT，則FIRST（X）={X}。（2）若X∈VN，且有產(chǎn)生式X→a……，則把a加入到FIRST(X)中；若X→ε也是一條產(chǎn)生式，則把ε也加到FIRST(X)中。（3）若X→Y……是一個產(chǎn)生式且Y∈VN，則把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中；若X→Y1Y2…Yk是一個產(chǎn)生式，Y1，…，Yi-1都是非終結(jié)符，而且，對于任何j，1≤j≤i-1，F(xiàn)IRST(Yj)都含有ε（即Y1…Yi-1*ε），則把FIRST(Yj)中的所有非ε-元素都加到FIRST(X)中；特別是，若所有的FIRST(Yj)均含有ε，j=1,2,…，k，則把ε加到FIRST(X)中。連續(xù)使用上面的規(guī)則，直至每個集合FIRST不再增大為止。FOLLOW集的計算FOLLOW集合的構(gòu)造算法：（1）對于文法的開始符號S，置#于FOLLOW(S)中；（2）若A→αBβ是一個產(chǎn)生式，則把FIRST(β)|{ε}加至FOLLOW(B)中；（3）若A→αB是一個產(chǎn)生式，或A→αBβ是一個產(chǎn)生式而βε（即ε∈FIRST(β)），則把FOLLOW(A)加至FOLLOW(B)中。連續(xù)使用上面的規(guī)則，直至每個集合FOLLOW不再增大為止。

SELLECT集的計算對某一產(chǎn)生式Ａ－＞ＢＣ，若產(chǎn)生式右部可以推出ε，則ＳＥＬＬＥＣＴ（Ａ）＝｛ＦＩＲＳＴ（ＢＣ）－｛ε｝｝ＵＦＯＬＬＯＷ（Ａ）若產(chǎn)生式右部推不出ε，則ＳＥＬＬＥＣＴ（Ａ）＝ＦＩＲＳＴ（ＢＣ）判斷是否LL(1)文法對當(dāng)前的產(chǎn)生式左部，查找后面的具有相同左部的其他產(chǎn)生式，并比較SELLECT集，若有重合，則不是LL(1)文法。構(gòu)造預(yù)測分析表在確定的自頂向下分析方法中，又有遞歸子程序法和預(yù)測分析方法，我們采用的是預(yù)測分析的方法。一個預(yù)測分析器由三部分組成：（1）預(yù)測分析程序（2）先進后出棧（3）預(yù)測分析表其中，只有預(yù)測分析表與文法有關(guān)。分析表可用矩陣M表示。M（A，a）中的下標(biāo)A表示非終結(jié)符，a為終結(jié)符或括號，矩陣元素M（A，a）中的內(nèi)容是一條關(guān)于A的產(chǎn)生式，表明當(dāng)用非終結(jié)符A往下推導(dǎo)時，面臨輸入符A時，所應(yīng)采取的候選產(chǎn)生式，元素內(nèi)容無產(chǎn)生式時，則表明出錯。為便于辨認(rèn)，我們令M數(shù)組為

Analyze數(shù)組。預(yù)測分析過程#為文法的括號；