語(yǔ)法分析課程設(shè)計(jì)---編譯原理語(yǔ)法分析器的設(shè)計(jì)與實(shí)現(xiàn)

1、<p><b>　　摘 要</b></p><p>　　編譯程序一般由詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、目標(biāo)代碼生成程序、代碼優(yōu)化程序、表格管理程序和出錯(cuò)處理程序等成分構(gòu)成。在編譯原理的教學(xué)過(guò)程中，算法的講解都需要對(duì)算法進(jìn)行詳細(xì)的分析，包括算法條件的判斷，文法分析表的構(gòu)造過(guò)程，文法分析表的具體生成，針對(duì)文法的句子的分析過(guò)程等，這些過(guò)程往往需要占用大量時(shí)間

2、來(lái)分析、制表等。本軟件的主要任務(wù)就是利用程序來(lái)完成算法的上述相關(guān)過(guò)程，以達(dá)到高效，直觀的效果。本文旨在介紹語(yǔ)法分析方法中的一種自上而下的分析方法——LL(1)分析法。所謂LL(1)分析法是指語(yǔ)法分析是按自左至右的順序向前查看一個(gè)輸入字符串，并分析過(guò)程中產(chǎn)生句子的最左推導(dǎo)。</p><p>　　關(guān)鍵詞：編譯；語(yǔ)法分析；LL(1)算法；演示</p><p>　　、

3、 目錄</p><p>　　引言..... ............................................ .... ............ ...................................................................3</p><p><b>　　第一章、概述</b><

4、;/p><p>　　1.1設(shè)計(jì)目標(biāo)........................... .............................. ........................... ................... .............4</p><p>　　1.2設(shè)計(jì)理論基礎(chǔ)............... ............... ........

5、....... .............. ................ ........... ...................5</p><p><b>　　第二章、程序設(shè)計(jì)</b></p><p>　　2.1算法設(shè)計(jì)簡(jiǎn)介.............. ............................. ........... .........

6、............................................6</p><p>　　2.1.1自頂向下分析......... . ......................................................... .........................................6</p><p>　　2.1.2

7、LL（K）分析方法.................... . .................. .................................... .........................7</p><p>　　2.1.3 LL（1）分析方法....................................................................

8、....................................7</p><p>　　2.1.4 LL(1)分析表..................... ...... ................. ............. ..... ......................... ...................8</p><p>　　2.2系統(tǒng)流程圖..

9、.............. .................. .. ... .. ............................................. .. ....................9</p><p>　　第三章、設(shè)計(jì)的實(shí)現(xiàn).</p><p>　　3.1文件讀取模塊.........................................

10、......... ...................... ....................................10</p><p>　　3.1.1文件讀取使用的CommonDialog控件介紹............. .................. ................................10</p><p>　　3.1.2文法左

11、遞歸的判斷.................................................................... ..................................10</p><p><b>　　3.2算法分析模塊</b></p><p>　　3.2.1求select集.......... ............

12、........................................................... ...................................11</p><p>　　3.2.2求first集….......................................................................................

13、..............................12</p><p>　　3.2.1求follow集..... ............................................. .................................................................12.</p><p>　　3.3分析表構(gòu)造模

14、塊............. .......... ................ ................................................................13</p><p>　　3.3.1構(gòu)造文法分析表.. .........................................................................

15、.................................14</p><p>　　3.3.2 A::=aβ規(guī)則....................... ...................................................... .....................................14</p><p>　　3.3.3 A

16、::=Dβ規(guī)則.............................................................................. ....................................14</p><p>　　3.3.4A::=ε規(guī)則.............................................................

17、.........................................................14</p><p>　　3.4句子分子模塊......................................................................................... ......................15</p><

18、;p>　　3.4.1讀取句子............................... .........................................................................................16</p><p>　　3.4.2分析句子............................... ................

19、.........................................................................16</p><p>　　3.5系統(tǒng)模塊流程圖............... ............................................................................. .............17<

20、;/p><p>　　第四章、結(jié)構(gòu)測(cè)試........... ............................................................................. .............18</p><p>　　第五章、小結(jié)............,.............................................

21、.................................... ...................19</p><p>　　參考文獻(xiàn)............,................................................................................. ................. ............20</p&g

22、t;<p><b>　　引言</b></p><p>　　編譯原理是計(jì)算機(jī)專業(yè)中最難的一門課程,在理論上它要求學(xué)生掌握有關(guān)形勢(shì)語(yǔ)言和自動(dòng)機(jī)的抽象概念,在技術(shù)上要求學(xué)生能夠熟練地利用各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行編程。</p><p>　　編譯程序是現(xiàn)代計(jì)算機(jī)系統(tǒng)的基本組成部分之一。編譯程序一般由詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、目標(biāo)代碼生成程

23、序、代碼優(yōu)化程序、表格管理程序和出錯(cuò)處理程序等成分構(gòu)成。</p><p>　　在編譯原理的教學(xué)過(guò)程中，語(yǔ)法和語(yǔ)義分析階段關(guān)于算法的講解都需要對(duì)算法進(jìn)行詳細(xì)的分析，包括算法條件的判斷，文法分析表的構(gòu)造過(guò)程，文法分析表的具體生成，針對(duì)文法的句子的分析過(guò)程等。這些過(guò)程往往需要占用大量時(shí)間來(lái)分析、制表等。教學(xué)主要是對(duì)這些過(guò)程的講解和分析，沒有必要花這么多的時(shí)間來(lái)做這些工作。本軟件的主要任務(wù)就是利用程序來(lái)完成算法的上述相關(guān)

24、過(guò)程，節(jié)約教學(xué)時(shí)間。</p><p><b>　　第一章、概述</b></p><p><b>　　1,1設(shè)計(jì)目標(biāo)</b></p><p>　　《一個(gè)編譯原理語(yǔ)法分析器的設(shè)計(jì)與實(shí)現(xiàn)》</p><p>　　1.主要通過(guò)文本方式獲取相關(guān)文法，并實(shí)現(xiàn)以下相關(guān)操作：</p><p>

25、　　2.判斷文法是否符合LL（1）的要求</p><p>　　3.獲取文法的終結(jié)符和非終結(jié)符</p><p>　　4.求文法的select集（其中包括first集和follow集的求解）并判斷select集是否符合LL（1）算法的要求</p><p>　　5.根據(jù)文法和select集構(gòu)造文法分析表</p><p>　　6.根據(jù)文法分析表判斷輸

26、入的句子是否符合文法</p><p><b>　　1,2設(shè)計(jì)理論基礎(chǔ)</b></p><p>　　語(yǔ)法分析：逐一分析詞法分析所得的屬性字，檢查其中的語(yǔ)法錯(cuò)誤，如果沒有發(fā)現(xiàn)語(yǔ)法錯(cuò)誤， 則給出正確的語(yǔ)法結(jié)構(gòu)。</p><p>　　句子的分析：句子的分析實(shí)際就是分析源程序中的語(yǔ)句是否符合給定的文法。</p><p>　　文法：

27、對(duì)語(yǔ)言結(jié)構(gòu)的定義和描述，即在形式上用于描述和規(guī)定語(yǔ)言結(jié)構(gòu)。由若干條規(guī)則組成。</p><p>　　規(guī)則：為一個(gè)二元組，通常格式為U：：=x或U→x；其中U為規(guī)則的左部，是一個(gè)符號(hào)；x是規(guī)則的右部，是一貫有窮字符串。規(guī)則又稱為產(chǎn)生式。</p><p>　　BNF表示法：即巴科斯范式表示法，它引進(jìn)了符號(hào)“|”，符號(hào)“|”表示“或”。運(yùn)用符號(hào)“|”把相同左部的規(guī)則縮寫在一起，這樣顯得文法更為緊湊

28、。</p><p>　　文法G[Z]：規(guī)則的非空有窮集合，其中Z為文法的識(shí)別符號(hào)或開始符號(hào)，它至少要在一條規(guī)則的左部出現(xiàn)。</p><p>　　字匯表：在文法中，由全部規(guī)則的左部和右部中的所有符號(hào)組成的符號(hào)集。</p><p>　　非終結(jié)符：文法中出現(xiàn)在規(guī)則左部的符號(hào)，它們組成的集合稱為非終結(jié)符集。</p><p>　　終結(jié)符：文法中凡不屬于

29、非終結(jié)符集的符號(hào)，它們組成的集合稱為終結(jié)符集。</p><p>　　遞歸：同一操作或一組操作的連續(xù)重復(fù)，其實(shí)質(zhì)上是處理過(guò)程的性質(zhì)，在這種過(guò)程的每一步都要用到它自身的上一步或上幾步的結(jié)果。</p><p>　　遞歸定義：在定義某種事物時(shí)又用到其本身。</p><p>　　直接左遞歸規(guī)則：型如U：：=Uy的規(guī)則稱為直接左遞歸規(guī)則。</p><p>

30、;　　First集：首符號(hào)集。</p><p>　　Follow集：向前看集。</p><p>　　Select集：可選集。</p><p>　　LL（1）文法：對(duì)于文法G（S），其每個(gè)非終結(jié)符的不同規(guī)則具有不相交的Select集，則稱該文法為L(zhǎng)L（1）文法。</p><p><b>　　第二章、程序設(shè)計(jì)</b><

31、/p><p><b>　　2.1算法設(shè)計(jì)簡(jiǎn)介</b></p><p>　　2.1.1自頂向下分析</p><p>　　對(duì)于文法G[Z]，給頂一個(gè)待分析的句子(字符串)，自頂向下分析的基本思想是從識(shí)別符號(hào)Z開始，根據(jù)文法試著建立一個(gè)推導(dǎo)序列，若得到所給的句子，則句子得到識(shí)別，表明其結(jié)構(gòu)符合文法，如果經(jīng)過(guò)各種推導(dǎo)都不能得到所分析的句子，則該符號(hào)串不符合

32、文法?；蛘哒f(shuō)，從根結(jié)點(diǎn)出發(fā)，自上而下地建立一顆語(yǔ)法樹，其未端結(jié)點(diǎn)按從左到右的順序連接起來(lái)，構(gòu)成給定的符號(hào)串，則符號(hào)串得到識(shí)別。</p><p>　　例：設(shè)有文法G[N]和符號(hào)串25 N </p><p><b>　　N::=D|ND</b></p><p>　　D::=0

33、|1|2|…|9 </p><p><b>　　根據(jù)文法有：</b></p><p>　　NNDDD2D25； </p><p>　　因此我們說(shuō)25符合此文法

34、 </p><p>　　圖1 G[N]過(guò)程分析 </p><p>　　自頂向下分析的難點(diǎn)及解決辦法：</p><p>　　1>.自頂向下分析的難點(diǎn)</p><p>　　對(duì)于形如:U::=x1|x2|…|xn 的規(guī)則,可能需要對(duì)所有的規(guī)則都要試探。</p><p>　　2>.

35、難點(diǎn)的解決辦法</p><p>　　該解決辦法是把文法中每個(gè)非終結(jié)符號(hào)A的右部稱為A的候選式，對(duì)候選式的選擇，則根據(jù)當(dāng)前輸入符號(hào)來(lái)決定。</p><p><b>　　方法：</b></p><p>　　首先對(duì)文法的每個(gè)規(guī)則A::=求可選集 Select(A::=)。</p><p>　　當(dāng)時(shí)，則對(duì)于當(dāng)前輸入的符號(hào)a，若有

36、aFirst()，則可以選用規(guī)則A::=進(jìn)行推導(dǎo)。</p><p>　　若對(duì)于某非終止符號(hào)有n條規(guī)則（即有n個(gè)候選式）的處理方法：</p><p>　　A.首符號(hào)集不相同的解決辦法</p><p>　　對(duì)于文法，有A::=x1|x2|…|xn，其右部的n個(gè)候選式的首符號(hào)集均不相同:</p><p>　　即First(xi) ∩ First(x

37、j)= (ij)，對(duì)于待分析的符號(hào)串，如果最左的非終結(jié)符號(hào)為A，若其句子中對(duì)應(yīng)的下一個(gè)符號(hào)（當(dāng)前輸入符號(hào)）為a，且有aFirst(xk)，則選擇規(guī)則A::=xk來(lái)作為推導(dǎo)的候選式。</p><p>　　例：設(shè)有文法G[Z]，和句子bbabaax</p><p><b>　　Z::=aV|bZ</b></p><p><b>　　V::

38、=baZ|x</b></p><p>　　Select(Z ::=aV)={a};</p><p>　　Select(Z ::=bZ)=;</p><p>　　Select(V ::=baZ)=;</p><p>　　Select(V ::=x)={x};</p><p>　　Z bZ

39、 bbZ bbaV bbabaZ bbabaaVbbabaax</p><p>　　(babaax) (abaax) (baax) (ax) (x) </p><p>　　B.首符號(hào)相同的解決辦法</p><p>　　對(duì)于文法，有A::= x1|x2|…|xn，若有First(xi) ∩ First(xj) (ij)，采

40、用試探法：即從首字符中有輸入符號(hào)的多個(gè)候選式中任選一個(gè)來(lái)試探，如果不成功，就換另一個(gè)接著試。試探法有可能形成回溯現(xiàn)象。對(duì)于回溯現(xiàn)象，可以通過(guò)“左提因子方法”對(duì)文法進(jìn)行修改來(lái)消除。</p><p>　　2.1.2LL（K）分析方法</p><p>　　LL(K)分析方法是一種自頂向下的分析技術(shù)。這種分析方法從左到右掃描源程序（輸入串），同時(shí)從識(shí)別符號(hào)開始生成句子的最左推導(dǎo)（規(guī)范推導(dǎo)），向前看

41、K個(gè)符號(hào)，便能確定當(dāng)前應(yīng)選擇怎樣的規(guī)則。</p><p>　　當(dāng)K=1時(shí)，既是LL（1）分析方法。</p><p>　　2.1.3 LL（1）分析方法</p><p>　　1.LL（1）方法的思想：根據(jù)輸入串的當(dāng)前輸入符號(hào)，確定用某規(guī)則進(jìn)行推導(dǎo)，當(dāng)推導(dǎo)的第一個(gè)符號(hào)與輸入串的當(dāng)前符號(hào)匹配時(shí)，就把輸入串的下一個(gè)字符作為當(dāng)前輸入字符，直到推導(dǎo)出輸入串。根據(jù)輸入串向前的1個(gè)

42、符號(hào)來(lái)確定推導(dǎo)規(guī)則時(shí)，就是LL（1）方法。</p><p>　　2.LL(1)分析方法的邏輯結(jié)構(gòu)</p><p>　　圖2 LL(1)分析方法的邏輯結(jié)構(gòu)</p><p>　　2.1.4LL(1)分析表</p><p>　　LL(1)分析表是分析方法的核心,它確定了推導(dǎo)所使用的規(guī)則。</p><p>　　A.LL(1)分

43、析過(guò)程</p><p>　　假設(shè)分析過(guò)程中當(dāng)前句型的右端部分為：x1x2…xm，(xiV)</p><p>　　輸入流（待分析串）的右端部分為：y1y2…yn，(yiVt)</p><p>　　此時(shí)有以下3種情況：</p><p>　　(1)當(dāng)x1Vn，則根據(jù)當(dāng)前輸入符號(hào)y1選擇相應(yīng)的規(guī)則去替換x1;</p><p>

44、　　(2)當(dāng)x1Vt時(shí)，則查看x1與y1是否相同，若x1與y1相同，則分別刪去x1和y1，然后繼續(xù)向前分析；不相同表示不相配，為出錯(cuò)。</p><p>　　(3)若上述兩個(gè)字符串均為空，則表示全部匹配，輸入串被識(shí)別。</p><p>　　現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使x1成為棧頂，利用分析棧，當(dāng)棧頂符號(hào)與輸入串當(dāng)前符號(hào)相匹配時(shí)，則從棧頂刪除該符號(hào)。然后再把相應(yīng)的規(guī)則逆向壓

45、入棧頂，替換原棧頂?shù)姆墙K結(jié)符。 </p><p>　　B.LL(1)分析表的構(gòu)造</p><p>　　LL(1)分析表：它是用來(lái)反映分析棧中的元素與輸入串中元素的一種匹配關(guān)系。如果分析棧中的元素為A，輸入元素為a，則其匹配關(guān)系記為L(zhǎng)L(A,a)</p><p>　　LL(1)分析矩陣：一種用來(lái)反映這種匹配關(guān)系的矩陣表示，該矩陣稱為L(zhǎng)L(1)分析矩陣。首先進(jìn)行介紹與L

46、L(1)分析有關(guān)的3個(gè)操作約定：</p><p>　　(1)N表示繼續(xù)下一個(gè)符號(hào)；</p><p>　　(2)P表示重讀當(dāng)前符號(hào)，也即不讀入下一符號(hào)；</p><p>　　(3)R()表示用的逆串替換棧頂符號(hào)。</p><p>　　構(gòu)造LL(1)分析表的方法如下：</p><p>　　a.對(duì)于A::=a，(aVt)，則

47、</p><p>　　令 LL(A,a)=R()/N </p><p>　　**R()/N：表示用的逆串替換Ａ后，繼續(xù)讀入下一個(gè)符號(hào)。</p><p>　　當(dāng)為時(shí)，即：A::=a，有：LL(A,a)=R()/N </p><p>　　b.對(duì)于A::=D，(DVn)，且有 Select(A::=D)={b1,b2,…,bn} ，</p&g

48、t;<p>　　則 LL(A,bi)=R(D)/P，(i=1,2,…,n)</p><p>　　**R(D)/P：表示用D的逆串替換A后，重讀當(dāng)前符號(hào)</p><p>　　c.對(duì)于A::=，且有 Select(A::=)= {b1,b2,…,bn}</p><p>　　則 LL(A, bi)=R()/P</p><p>　　d.

49、對(duì)于每一個(gè)aVt，a不出現(xiàn)于規(guī)則右部的首部，</p><p>　　則令 LL(a,a)=R()/N</p><p>　　e.對(duì)于#，令LL(#,#)=acc 表示分析結(jié)束，輸入串得到識(shí)別。</p><p>　　f.非上述5種情況，則置出錯(cuò)，分析表中用空白表示。</p><p><b>　　2.2系統(tǒng)流程圖</b><

50、/p><p><b>　　第三章，設(shè)計(jì)的實(shí)現(xiàn)</b></p><p><b>　　3.1文件讀取模塊</b></p><p>　　本模塊通過(guò)調(diào)用VB中CommonDialog控件的ShowOpen方法啟動(dòng)打開文件對(duì)話框，獲取需要讀取的文件的路徑，再調(diào)用Open命令打開文件，將文件中保存的文法讀入內(nèi)存，用二維數(shù)組進(jìn)行保存。<

51、;/p><p>　　3.1.1文件讀取使用的CommonDialog控件介紹</p><p>　　CommonDialog 控件提供諸如打開和保存文件、設(shè)置打印選項(xiàng)、選擇顏色和字體等操作的一組標(biāo)準(zhǔn)對(duì)話框。調(diào)用打開文件對(duì)話框的具體代碼如下：</p><p>　　Dim p_name As String ' 文件路徑</p><p>　　Fo

52、rm1.CommonDialog1.CancelError = True</p><p>　　On Error GoTo err</p><p>　　Form1.CommonDialog1.Filter = "Text(*.txt)|*.txt"</p><p>　　Form1.CommonDialog1.FilterIndex = 1</

53、p><p>　　Form1.CommonDialog1.ShowOpen ' 用 ShowOpen 方法顯示對(duì)話框</p><p>　　p_name = Form1.CommonDialog1.FileName ' 用 FileName 屬性獲取選定文件的名稱</p><p>　　3.1.2文法左遞歸的判斷</p><p>　　文

54、法中使用遞歸規(guī)則以后，可以用有限的規(guī)則刻劃無(wú)限語(yǔ)言，但不利的是對(duì)與具有左遞歸性的文法，不能采用自頂向下的分析算法。一般含有左遞歸規(guī)則的文法形式為U::=xUy，</p><p>　　若x=, 則有U::=Uy，即為左遞歸規(guī)則。由于消除左遞歸算法的復(fù)雜性和畢業(yè)設(shè)計(jì)時(shí)間所限，所以本軟件沒有這項(xiàng)功能，只是對(duì)直接左遞歸進(jìn)行錯(cuò)誤判斷。</p><p>　　Do While WF(j, 0) <

55、> Empty ' 判斷文法是否有左遞歸</p><p>　　If WF(j, 0) = WF(j, 1) Then</p><p>　　MsgBox "！錯(cuò)誤！文法有左遞歸存在，不符合LL(1)的要求", vbApplicationModal, "錯(cuò)誤"</p><p><b>　　Exit Sub&

56、lt;/b></p><p><b>　　End If</b></p><p><b>　　j = j + 1</b></p><p><b>　　Loop</b></p><p><b>　　3.2算法分析模塊</b></p><

57、;p>　　本模塊首先獲取文法的終結(jié)符集和非終結(jié)符集，分別用一維數(shù)組進(jìn)行保存；然后在對(duì)文法的每一條規(guī)則求select集，并將select集保存到二維數(shù)組中；最后對(duì)select集做相關(guān)判斷，以確定所讀入的文法是否符合LL（1）文法的規(guī)則。程序中所用到的公有數(shù)據(jù)成員有：</p><p>　　Public hs As Integer ' 文法的行數(shù)</p><p>　　Publ

58、ic zj As Integer ' 終結(jié)符的個(gè)數(shù)</p><p>　　Public nz As Integer ' 非終結(jié)符的個(gè)數(shù)</p><p>　　Public SLT(50, 50) As String ' select集</p><p>　　Dim F(50) As String ' 用與臨時(shí)存

59、放select集中元素的數(shù)組</p><p>　　Public ZJF(50) As String ' 終結(jié)符集</p><p>　　Public NZJ(250) As String ' 非終結(jié)符集</p><p>　　3.2.1求select集</p><p>　　設(shè)有文法G[S]，并有規(guī)則A::=，則該規(guī)則的可選

60、集為：</p><p>　　Select(A::=)= </p><p><b>　　具體實(shí)現(xiàn)代碼如下：</b></p><p>　　If WF(a, 0) = Empty Then</p><p><b>　　Exit For</b></p><p>　　ElseIf WF

61、(a, 1) = "ε" Then 'ε為空字符串</p><p>　　Call follow(a, fo)</p><p><b>　　i = 0</b></p><p>　　Do While F(i) <> Empty</p><p>　　SLT(a, i) = F(i)<

62、;/p><p>　　F(i) = Empty</p><p><b>　　i = i + 1</b></p><p>　　SLT(a, i) = Empty</p><p><b>　　Loop</b></p><p><b>　　Else</b></

63、p><p>　　Call first(a, fo) </p><p>　　3.2.2求first集</p><p>　　首符號(hào)集既求解文法每條規(guī)則右邊的第一個(gè)符號(hào)并且必須是終結(jié)符，因?yàn)槲姆ㄊ褂脭?shù)組存放，所以既求文法每行規(guī)則的第2個(gè)字符既可；如果規(guī)則左邊第一個(gè)字符為非終結(jié)符，則通過(guò)循環(huán)對(duì)該非終結(jié)符再求首符號(hào)集。</p><p>　　For i

64、= 0 To zj</p><p>　　If WF(a, 1) = ZJF(i) Then '判斷第a條規(guī)則右邊的首符號(hào)是否是終結(jié)符</p><p>　　For p = 0 To fo '判斷WF(i,j+1)在F()中是否已經(jīng)存在</p><p>　　If WF(a, 1) = F(p) Then</p><p><b

65、>　　b = 1</b></p><p><b>　　Exit For</b></p><p><b>　　End If</b></p><p><b>　　Next p</b></p><p>　　If b = 1 Then</p><p

66、><b>　　b = 0</b></p><p><b>　　Else</b></p><p>　　F(fo) = WF(a, 1)</p><p>　　fo = fo + 1</p><p>　　F(fo) = Empty</p><p><b>　　End

67、 If </b></p><p>　　3.2.3求follow集</p><p>　　求向前看集主要分兩種情況，一種是可以直接循環(huán)推導(dǎo)出終結(jié)符；第二種是推出的還是非終結(jié)符的，如果推出的還是非終結(jié)符的就循環(huán)對(duì)該非終結(jié)符再求向前看集；第三種情況是不能對(duì)該非終結(jié)符求向前看集，但是可以通過(guò)對(duì)該非終結(jié)符推導(dǎo)出的第二個(gè)非終結(jié)符求向前看集的方法求出終結(jié)符。</p><p

68、>　　c = 0: b = 0</p><p>　　If WF(a, 0) = WF(0, 0) Then '判斷是不是對(duì)文法起始符求follow集</p><p>　　For p = 0 To fo '判斷WF(i,j+1)在F()中是否已經(jīng)存在</p><p>　　If F(p) = "#" Then</p>

69、;<p><b>　　b = 1</b></p><p><b>　　Exit For</b></p><p><b>　　End If</b></p><p><b>　　Next p</b></p><p>　　If b = 1 Then

70、</p><p><b>　　b = 0</b></p><p><b>　　Else</b></p><p>　　F(fo) = "#"</p><p>　　fo = fo + 1</p><p>　　F(fo) = Empty</p>&

71、lt;p><b>　　End If</b></p><p><b>　　End If</b></p><p>　　For i = 0 To hs</p><p><b>　　j = 1</b></p><p>　　Do While WF(i, j) <> Em

72、pty</p><p>　　If WF(a, 0) = WF(i, j) Then</p><p>　　If WF(i, j + 1) = Empty And a <> i Then</p><p>　　Call follow(i, fo)</p><p><b>　　Else</b></p>

73、<p>　　For m = 0 To zj '判斷WF(i,j+1)是不是終結(jié)符</p><p>　　If WF(i, j + 1) = ZJF(m) Then</p><p>　　For p = 0 To fo '判斷WF(i,j+1)在F()中是否已經(jīng)存在</p><p>　　If WF(i, j + 1) = F(p) Then&l

74、t;/p><p><b>　　b = 1</b></p><p><b>　　Exit For</b></p><p><b>　　End If</b></p><p><b>　　Next p</b></p><p>　　If b =

75、 1 Then</p><p><b>　　b = 0</b></p><p><b>　　Else</b></p><p>　　F(fo) = WF(i, j + 1)</p><p>　　fo = fo + 1</p><p>　　F(fo) = Empty</p&

76、gt;<p><b>　　End If</b></p><p><b>　　c = 1</b></p><p><b>　　Exit For</b></p><p><b>　　End If</b></p><p><b>　　Ne

77、xt m</b></p><p>　　If c = 1 Then</p><p><b>　　c = 0</b></p><p><b>　　Else</b></p><p>　　For n = 0 To hs '查找WF(i,j+1)對(duì)應(yīng)的非終結(jié)符在文法的第幾行</p&g

78、t;<p>　　If WF(i, j + 1) = WF(n, 0) Then</p><p>　　Call first(n, fo) </p><p>　　3.3分析表構(gòu)造模塊</p><p>　　在已經(jīng)得到文法select集的前提下，以次為依據(jù)，對(duì)文法的三種類型的規(guī)則：A::=aβ型、A::=Dβ型、A::=ε型分別構(gòu)造分析表，并

79、用一個(gè)三維數(shù)組保存。形如FXB（y，x，z），其中，y表示分析表的第y行，x表示第x列，z表示第y行第x列所對(duì)應(yīng)的格子中的第z個(gè)數(shù)據(jù)。</p><p>　　3.3.1構(gòu)造文法分析表</p><p>　　在求解Select集完成后，結(jié)果按照非終結(jié)符放入分析表Y軸，沒有出現(xiàn)在對(duì)應(yīng)規(guī)則右部首部的終結(jié)符放入分析表Y軸，終結(jié)符放入分析表X軸等規(guī)則放置。如圖5。</p><p>

80、;　　圖5 分析表構(gòu)造流程</p><p>　　3.3.2A::=aβ規(guī)則</p><p>　　對(duì)于A::=a，(aVt)，則</p><p>　　令 LL(A,a)=R()/N </p><p>　　**R()/N：表示用的逆串替換Ａ后，繼續(xù)讀入下一個(gè)符號(hào)。</p><p>　　當(dāng)為時(shí)，即：A::=a，有：LL(A,

81、a)=R()/N </p><p>　　3.3.3A::=Dβ規(guī)則</p><p>　　對(duì)于A::=D，(DVn)，且有 Select(A::=D)={b1,b2,…,bn} ，</p><p>　　則 LL(A,bi)=RD)/P，(i=1,2,…,n)</p><p>　　**R(D)/P：表示用D的(逆串替換A后，重讀當(dāng)前符號(hào)</

82、p><p>　　3.3.4A::=ε規(guī)則</p><p>　　對(duì)于A::=，且有 Select(A::=)= {b1,b2,…,bn}</p><p>　　則 LL(A, bi)=R()/P</p><p><b>　　3.4句子分析模塊</b></p><p>　　本部分主要通過(guò)VB中的InputB

83、ox對(duì)話框讀入待分析句子，并與分析表進(jìn)行對(duì)照，逐步分析所輸入的句子是否符合文法。分析過(guò)程均用一維數(shù)組進(jìn)行保存。</p><p><b>　　相關(guān)程序片段如下：</b></p><p>　　程序中所用到的公有數(shù)據(jù)成員有：</p><p>　　Dim FXZ(50) As String '存放句子分析過(guò)程中的分析棧</p>

84、<p>　　Dim FHZ(50) As String '存放句子分析過(guò)程中的輸入符號(hào)棧</p><p><b>　　3.4.1讀取句子</b></p><p>　　Public Sub juzi_read(str As String) '讀取句子</p><p>　　FHZ(0) = Empty</p>

85、;<p><b>　　i = 0</b></p><p>　　a = Mid(str, 1, 1)</p><p>　　Do While a <> Empty</p><p>　　FHZ(i) = a</p><p>　　a = Mid(str, i + 2, 1)</p><

86、;p><b>　　i = i + 1</b></p><p>　　FHZ(i) = Empty</p><p><b>　　Loop</b></p><p>　　If FHZ(0) = Empty Then</p><p><b>　　Exit Sub</b></p

87、><p><b>　　End If</b></p><p>　　FHZ(i) = "#"</p><p>　　FHZ(i + 1) = Empty</p><p>　　Call fenxi_chr</p><p><b>　　End Sub</b></p

88、><p><b>　　3.4.2分析句子</b></p><p>　　現(xiàn)在我們把句型的右端部分逆向放入一分析堆棧中，使x1成為棧頂，利用分析棧，當(dāng)棧頂符號(hào)與輸入串當(dāng)前符號(hào)相匹配時(shí)，則從棧頂刪除該符號(hào)。然后再把相應(yīng)的規(guī)則逆向壓入棧頂，替換原棧頂?shù)姆墙K結(jié)符。 </p><p>　　Do While fenxibiao.FXB(i, j, k) <

89、> Empty</p><p>　　Select Case fenxibiao.FXB(i, j, k)</p><p>　　Case "acc"</p><p><b>　　Exit Sub</b></p><p><b>　　Case "ε"</b>

90、</p><p>　　FXZ(a) = Empty</p><p><b>　　Case "/N"</b></p><p>　　FHZ(b) = " "</p><p><b>　　b = b + 1</b></p><p><b

91、>　　a = a - 1</b></p><p><b>　　Exit For</b></p><p><b>　　Case "/P"</b></p><p><b>　　a = a - 1</b></p><p><b>　　E

92、xit For</b></p><p><b>　　Case Else</b></p><p>　　FXZ(a) = fenxibiao.FXB(i, j, k)</p><p><b>　　a = a + 1</b></p><p>　　FXZ(a) = Empty</p>

93、<p>　　End Select</p><p><b>　　k = k + 1</b></p><p><b>　　Loop</b></p><p>　　3.5系統(tǒng)模塊流程圖</p><p><b>　　第四章、結(jié)果測(cè)試</b></p><p

94、>　　在設(shè)計(jì)完成后，對(duì)設(shè)計(jì)各個(gè)功能做了詳細(xì)的測(cè)試，對(duì)于正確的文法，系統(tǒng)能正常的演示整個(gè)文法分析的每一個(gè)過(guò)程；對(duì)于預(yù)設(shè)置的錯(cuò)誤處理，系統(tǒng)也能給出正確的判斷，指出文法的錯(cuò)誤類型。</p><p><b>　　測(cè)試錯(cuò)誤文法</b></p><p>　　句子錯(cuò)誤有2種情況：</p><p>　　1．句子不符合文法，錯(cuò)誤提示如圖所示：</p&

95、gt;<p>　　句子不符合文法（1）</p><p>　　2．句子中有終結(jié)符以外的字符，錯(cuò)誤提示如下圖所示：</p><p>　　句子不符合文法（2）</p><p><b>　　第五章、小結(jié)</b></p><p>　　編譯原理是計(jì)算機(jī)專業(yè)中最難的一門課程,在理論上我們只能掌握有關(guān)形勢(shì)語(yǔ)言和自動(dòng)機(jī)的抽象

96、概念,在技術(shù)上很難能夠熟練地利用各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行編程。尤其對(duì)于向前看集的算法實(shí)現(xiàn)，我覺得是最難的一部分，因?yàn)樯婕暗降那闆r太多，循環(huán)和選擇句型的嵌套使用如果不仔細(xì)分析就容易出現(xiàn)錯(cuò)誤。在數(shù)據(jù)的處理上我采用各模塊全數(shù)組操作，并且將最終結(jié)果通過(guò)字符串方式保存，通過(guò)字符串來(lái)向其他模塊傳送數(shù)據(jù)，這種新的嘗試也讓我的程序帶有個(gè)人的風(fēng)格，讓我對(duì)編程的多樣化有了更深的了解和認(rèn)識(shí)。</p><p>　　通過(guò)語(yǔ)法分析器的設(shè)計(jì)的使用，在

97、編譯原理的學(xué)習(xí)中起到幫助，更好的了解LL（1）算法的整個(gè)過(guò)程。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 錢煥延.編譯技術(shù)第2版[M].南京：東南大學(xué)出版社出版，2002。</p><p>　　[2] 康慕寧.編譯原理[M].西安：西北工業(yè)大學(xué)出版社出版，2003。</p><p>　　[

98、3] 賀世娟，陳冀川.Visual Basic 6.0 程序設(shè)計(jì)[M].北京：中國(guó)水利水電出版社出版，2002.8。</p><p>　　[4] 楊克玉.VB6.0程序設(shè)計(jì)實(shí)訓(xùn)教程[M].北京：機(jī)械工業(yè)出版社出版，2005.2。</p><p>　　[5] 陳明.Visual Basic教程[M].北京：人民郵電出版社，2002.8。</p><p>　　[6] 徐