1、一、實(shí)驗(yàn)?zāi)康?首先能讓用戶輸入一個(gè)文法，然后讓計(jì)算機(jī)自動(dòng)判斷是否是一個(gè)LL(1)文法，通過實(shí)驗(yàn)教學(xué)，加深學(xué)生對所學(xué)的關(guān)于編譯的理論知識(shí)的理解，增強(qiáng)學(xué)生對所學(xué)知識(shí)的綜合應(yīng)用能力，并通過實(shí)踐達(dá)到對所學(xué)的知識(shí)進(jìn)行驗(yàn)證。二、實(shí)驗(yàn)環(huán)境 供Windows系統(tǒng)的PC機(jī)，可用C+/C#/Java等編程工具編寫三、實(shí)驗(yàn)內(nèi)容 1、讓計(jì)算機(jī)接受一個(gè)文法，示例如：GS 為:SAB SbCA AbB BaDCAD CbDaS Dc1. 2、編程實(shí)現(xiàn)對上述文法是否是LL(1)文法的判斷，是則給出肯定回答，否則給出否定回答。2. 判別是否是LL(1)文法以鏈表或數(shù)組等數(shù)據(jù)結(jié)構(gòu)保存文法.求出能推出的非終結(jié)符.計(jì)算FIRST集

2、,FOLLOW集和SELECT集SELECT(A)SELECT(A)=?輸出肯定回答是輸出否定回答否實(shí)驗(yàn)流程圖如下：四、概要設(shè)計(jì)（1）、LL（1）文法的定義LL(1)分析法屬于確定的自頂向下分析方法。LL(1)的含義是：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串，第2個(gè)L表明分析過程中將使用最左推導(dǎo)，1表明只需向右看一個(gè)符號(hào)便可決定如何推導(dǎo)，即選擇哪個(gè)產(chǎn)生式(規(guī)則)進(jìn)行推導(dǎo)。LL(1)文法的判別需要依次計(jì)算FIRST集、FOLLOW集和SELLECT集,然后判斷是否為LL(1)文法,最后再進(jìn)行句子分析。需要預(yù)測分析器對所給句型進(jìn)行識(shí)別。即在LL(1)分析法中，每當(dāng)在符號(hào)棧的棧頂出現(xiàn)非終極符時(shí)

3、，要預(yù)測用哪個(gè)產(chǎn)生式的右部去替換該非終極符；當(dāng)出現(xiàn)終結(jié)符時(shí)，判斷其與剩余輸入串的第一個(gè)字符是否匹配，如果匹配，則繼續(xù)分析，否則報(bào)錯(cuò)。LL(1)分析方法要求文法滿足如下條件：對于任一非終極符A的兩個(gè)不同產(chǎn)生式Aàa,Aàb，都要滿足下面條件：SELECT(Aàa)SELECT(Aàb)=Æ（2）、預(yù)測分析表構(gòu)造LL(1)分析表的作用是對當(dāng)前非終極符和輸入符號(hào)確定應(yīng)該選擇用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)。它的行對應(yīng)文法的非終極符，列對應(yīng)終極符，表中的值有兩種：一是產(chǎn)生式的右部的字符串，一是null。若用M表示LL(1)分析表，則M可表示如下：M: VN

4、5;VTàPErrorM(A, t) = Aà，當(dāng)tÎselect(Aà) ，否則M(A, t) = Error其中P表示所有產(chǎn)生式的集合。（3）、語法分析程序構(gòu)造LL(1)分析中X為符號(hào)棧棧頂元素，a為輸入流當(dāng)前字符，E為給定測試數(shù)據(jù)的開始符號(hào)，#為句子括號(hào)即輸入串的括號(hào)。分析表用一個(gè)二位數(shù)組M表示，數(shù)組元素MA，a中的下標(biāo)A表示非終結(jié)符，a為終結(jié)符或句子括號(hào)#，二維數(shù)組中存放的是一條關(guān)于A 的產(chǎn)生式，表明當(dāng)非終結(jié)符A向下推導(dǎo)時(shí)，面臨輸入符a時(shí)，所采用的候選產(chǎn)生式，當(dāng)元素內(nèi)容無產(chǎn)生式時(shí)，則表明用A 的左部向下推導(dǎo)時(shí)出現(xiàn)了不該出現(xiàn)的符號(hào)，因此元素內(nèi)容轉(zhuǎn)向

5、出錯(cuò)處理的信息。LL(1)分析過程主要包括以下四個(gè)動(dòng)作：替換：當(dāng)XÎVN時(shí)選相應(yīng)產(chǎn)生式的右部b去替換X。此時(shí)X出棧，b逆序入棧。匹配：當(dāng)XÎVT時(shí)它與a進(jìn)行匹配，其結(jié)果可能成功，也可能失敗，如果成功則符號(hào)棧中將X退棧并將輸入流指針向前移動(dòng)一位，否則報(bào)錯(cuò)。接受：當(dāng)格局為（#，空#）時(shí)報(bào)告分析成功。報(bào)錯(cuò)：出錯(cuò)后，停止分析。并給出相應(yīng)的錯(cuò)誤提示信息。五、詳細(xì)設(shè)計(jì)【流程圖】1. 總體思路分析及流程圖給定一個(gè)正規(guī)文法G，在LL(1)預(yù)測分析中，必須先求出First集和Follow集，然后求出Select集，通過Select集判斷是否是LL1文法，如果是的話，構(gòu)造預(yù)測分析表。求出預(yù)測分

6、析表之后，再輸入一個(gè)字符串，依據(jù)LL1分析表單步輸出字符串的分析過程。功能模塊分解圖（1）主程序流程圖（2）核心算法流程圖 1.計(jì)算非終結(jié)符的First集的算法及流程：First集合的構(gòu)造算法：（1）若XVT，則First（X）=X。（2）若XVN，且有產(chǎn)生式Xa，則把a(bǔ)加入到First (X)中；若X也是一條產(chǎn)生式，則把也加到First (X)中。（3）若XY是一個(gè)產(chǎn)生式且YVN，則把First (Y)中的所有非-元素都加到First (X)中；若XY1Y2Yk是一個(gè)產(chǎn)生式，Y1，Yi-1都是非終結(jié)符，而且，對于任何j，1ji-1，F(xiàn)irst (Yj)都含有（即Y1Yi-1* ），則把Fir

7、st (Yj)中的所有非-元素都加到First (X)中；特別是，若所有的First (Yj)均含有，j=1,2,，k，則把加到First (X)中。連續(xù)使用上面的規(guī)則，直至每個(gè)集合First不再增大為止。2.計(jì)算非終結(jié)符的Follow集：Follow集合的具體構(gòu)造算法如下：（1）對于文法的開始符號(hào)S，置#于Follow(S)中；（2）若AB是一個(gè)產(chǎn)生式，則把First()|加至Follow(B)中；（3）若AB是一個(gè)產(chǎn)生式，或AB是一個(gè)產(chǎn)生式而 （即First()），則把Follow(A)加至Follow(B)中。連續(xù)使用上面的規(guī)則，直至每個(gè)集合Follow不再增大為止。六、結(jié)果分析 七、 實(shí)驗(yàn)感想本次實(shí)驗(yàn)用C語言操作判斷LL1型文法，判斷LL1型文法實(shí)驗(yàn)最主要的地方在于需要依