編譯原理課程設(shè)計(jì)--構(gòu)造lr(0)分析法語法分析器

1、<p>　　太 原 學(xué) 院</p><p><b>　　課程設(shè)計(jì)報(bào)告書</b></p><p>　　課程名稱 編譯原理 </p><p>　　設(shè)計(jì)題目 構(gòu)造LR(0)分析法語法分析器 </p><p>　　專業(yè)班級(jí) 計(jì)

2、算機(jī)科學(xué)與技術(shù)13-4班 </p><p>　　學(xué) 號(hào) 20130905405 </p><p>　　姓 名 王芳芳 </p><p>　　指導(dǎo)教師 吳海麗 </p>&

3、lt;p>　　2016年 12 月 15日</p><p><b>　　目 錄</b></p><p><b>　　一、課題概述1</b></p><p><b>　　二、系統(tǒng)分析2</b></p><p>　　2．1 本課程設(shè)計(jì)的知識(shí)點(diǎn)2</p>&

4、lt;p>　　2.1.1 詞法編譯器功能2</p><p>　　2.1.2 詞法分析器的設(shè)計(jì)2</p><p>　　2.1.3 動(dòng)態(tài)模擬算法的基本功能2</p><p>　　2.1.4 LR分析器的構(gòu)成2</p><p>　　2. 2解決問題的基本思路3</p><p>　　2．3 需解決的關(guān)鍵技術(shù)3

5、</p><p>　　2．4 功能模塊框圖3</p><p><b>　　三、系統(tǒng)設(shè)計(jì)4</b></p><p>　　3．1 算法描述4</p><p>　　3. 2 實(shí)現(xiàn)方法6</p><p>　　3.2.1 構(gòu)造分析表6</p><p>　　3.2.2程序設(shè)計(jì)

6、關(guān)鍵6</p><p>　　3.2.3 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造6</p><p>　　3．3 詳細(xì)流程圖7</p><p><b>　　四、代碼編寫8</b></p><p>　　4. 1 生成分析表代碼8</p><p>　　4. 2分析句子代碼10</p>&l

7、t;p><b>　　五、調(diào)試分析14</b></p><p>　　六、運(yùn)行與調(diào)試15</p><p><b>　　總 結(jié) 17</b></p><p><b>　　參考文獻(xiàn)18</b></p><p><b>　　課題概述</b></

8、p><p>　　《編譯原理》是計(jì)算機(jī)專業(yè)的一門重要的專業(yè)課程，其中包含大量軟件設(shè)計(jì)思想。通過課程設(shè)計(jì)，實(shí)現(xiàn)一些重要的算法，或設(shè)計(jì)一個(gè)完整的編譯程序模型，能夠進(jìn)一步加深理解和掌握所學(xué)知識(shí)，對(duì)提高自己的軟件設(shè)計(jì)水平具有十分重要的意義。語法分析是編譯過程的第二階段，是編譯器前端的核心組成部分，在編譯系統(tǒng)中起到了至關(guān)重要的作用。自底向上的語法分析與自頂向下的語法分析相比，對(duì)將要分析的源程序有著更大的分析空間，從而受到了廣泛的

9、運(yùn)用。</p><p>　　本次課程設(shè)計(jì)的目標(biāo)即是利用所學(xué)過的編譯原理的知識(shí)，利用LR(0)分析法，用C語言寫出一個(gè)簡(jiǎn)單的LR(0)語法分析器。該語法分析器所要完成的功能是，對(duì)錄入的文法判斷它是否為L(zhǎng)R(0)文法，如果是輸出LR (0)分析表；在給定文法的情況下，能夠利用LR(0)分析表，對(duì)用戶輸入的一串字符串用LR(0)分析法進(jìn)行分析，判斷該字符串是否為符合給定文法的一個(gè)句子，建立文法及其LR分析表表

10、示的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)LR(0)的分析器。編譯器設(shè)計(jì)的編譯程序涉及到編譯五個(gè)階段中的三個(gè)，即詞法分析器、語法分析器和中間代碼生成器。編譯程序的輸出結(jié)果包括詞法分析后的二元式序列、變量名表、狀態(tài)棧分析過程顯示及四元式序列程序。整個(gè)編譯程序分為三部分：詞法分析部分、語法分析處理及四元式生成部分、輸出顯示部分。一個(gè)程序設(shè)計(jì)語言就是一個(gè)記號(hào)系統(tǒng)，如同自然語言一樣，它的完整的定義應(yīng)包括語法和語義兩個(gè)方面。所謂一個(gè)語言的語法是指一組規(guī)則，用它

11、可以形成和產(chǎn)生一個(gè)合適的程序。目前廣泛使用的手段是上下文無關(guān)文法，即用上下文無關(guān)文法作為程序設(shè)計(jì)語言語法的描述工具。LR分析法正是給出一種能根據(jù)當(dāng)前分析棧中的符號(hào)串（通常以狀態(tài)表示）</p><p><b>　　二、系統(tǒng)分析</b></p><p>　　2.1 本課程設(shè)計(jì)涉及的知識(shí)點(diǎn)</p><p>　　2.1.1 詞法編譯器功能</p&

12、gt;<p>　?。?）導(dǎo)入任意文法，也可以自己輸入。</p><p>　?。?）輸出文法的分析過程，以及判斷是否為L(zhǎng)R (0)文法，輸出分析表。</p><p>　?。?）輸入句子，進(jìn)行語法分析。</p><p><b>　?。?）輸出結(jié)構(gòu)樹。</b></p><p>　　2.1.2 詞法分析器

13、的設(shè)計(jì)</p><p>　　(1)寫出該語言的詞法規(guī)則。</p><p>　　(2)把詞法規(guī)則轉(zhuǎn)換為相應(yīng)的狀態(tài)轉(zhuǎn)換圖。</p><p>　　(3)把各轉(zhuǎn)換圖的初態(tài)連在一起，構(gòu)成識(shí)別該語言的自動(dòng)機(jī)。</p><p>　　(4)設(shè)計(jì)掃描器；把掃描器作為語法分析的一個(gè)過程，當(dāng)語法分析需要一個(gè)單詞時(shí)，就調(diào)用掃描器。掃描器從初態(tài)出發(fā)，當(dāng)識(shí)別一個(gè)單詞后便

14、進(jìn)入終態(tài)，送出二元式。</p><p>　　2.1.3 動(dòng)態(tài)模擬算法的基本功能</p><p>　　（1）輸入LR分析表和一個(gè)句子。</p><p>　?。?）輸出LR總控程序。</p><p>　　（3）輸出依據(jù)句子構(gòu)對(duì)應(yīng)的語法樹的過程。</p><p>　　（4）設(shè)計(jì)一個(gè)給定LR分析表，輸入一個(gè)句子，能由依據(jù)LR分

15、析表輸出與句子對(duì)應(yīng)的語法樹，能對(duì)語法樹生成過程進(jìn)行模擬。</p><p>　　（5）輸入句子：bccd#。</p><p>　?。?）根據(jù)文法產(chǎn)生的LR分析表。</p><p><b>　?。?）輸出結(jié)果</b></p><p>　　2.1.4 LR分析器的構(gòu)成</p><p>　　一個(gè)LR分析器

16、由３個(gè)部分組成</p><p>　　（1）總控程序，也可以稱為驅(qū)動(dòng)程序。對(duì)所有的LR分析器，總控程序都是相同的。</p><p>　?。?）分析表或分析函數(shù)。不同的文法分析表將不同，同一個(gè)文法采用的LR</p><p>　　分析器不同時(shí)，分析表也不同，分析表又可以分為動(dòng)作（ACTION）表和狀態(tài)（GOTO）表兩個(gè)部分，它們都可用二維數(shù)組表示。</p>

17、<p>　?。?）分析棧，包括文法符號(hào)和相應(yīng)的狀態(tài)棧。它們均是先進(jìn)后出棧。分析器的動(dòng)作由棧頂狀態(tài)和當(dāng)前輸入符號(hào)所決定（LR(0)分析器不需向前查看輸入符號(hào)）。</p><p>　　2.2解決問題的基本思路</p><p>　　1、用構(gòu)造一個(gè)狀態(tài)轉(zhuǎn)換函數(shù)實(shí)現(xiàn)狀態(tài)轉(zhuǎn)換。</p><p>　　2、再通過函數(shù)構(gòu)造一個(gè)移進(jìn)－歸約函數(shù)實(shí)現(xiàn)移進(jìn)規(guī)約動(dòng)作。</p&g

18、t;<p>　　3、采用構(gòu)造一個(gè)打印LR分析器的工作過程函數(shù)實(shí)現(xiàn)輸出。</p><p>　　在規(guī)范規(guī)約的過程中，一方面記住已移進(jìn)和規(guī)約出的整個(gè)符號(hào)串，另一方面根據(jù)所用的產(chǎn)生式推測(cè)可能碰到的輸入符號(hào)。每一項(xiàng)ACTION(s，a)所規(guī)定的動(dòng)作不外是下述四種可能之一：（1）移進(jìn)（2）規(guī)約（3）接受（4）報(bào)錯(cuò)。</p><p>　　2.3 需解決的關(guān)鍵技術(shù)</p>&l

19、t;p><b>　?。?）詞法編譯器。</b></p><p>　?。?）交互式面向?qū)ο蟮脑~法編譯器基本功能是。</p><p>　?。?）根據(jù)規(guī)約規(guī)則對(duì)字符進(jìn)行歸約。</p><p>　?。?）符合條件時(shí)采取移進(jìn)動(dòng)作。</p><p>　　2.4 功能模塊框圖</p><p><b&

20、gt;　　圖1 功能模塊框圖</b></p><p><b>　　三、系統(tǒng)設(shè)計(jì)</b></p><p><b>　　3.1 算法描述</b></p><p><b>　　1、已知文法G</b></p><p><b>　　(1) E→E+T</b&g

21、t;</p><p><b>　　(2) E→T</b></p><p><b>　　(3) T→T*F</b></p><p><b>　　(4) T→F</b></p><p><b>　　(5) F→(E)</b></p><p&

22、gt;<b>　　(6) F→i</b></p><p>　　2、LR(0)分析表的構(gòu)造算法如下：</p><p>　　假設(shè)已構(gòu)造出LR(0)項(xiàng)目集規(guī)范族為：C={I0,I1, … , In}，其中Ik為項(xiàng)目集的名字，k為狀態(tài)名，令包含S′→·S項(xiàng)目的集合Ik的下標(biāo)k為分析器的初始狀態(tài)。那么分析表的ACTION表和GOTO表構(gòu)造步驟為：</p>

23、<p>　　(1) 若項(xiàng)目A→α·aβ屬于Ik且轉(zhuǎn)換函數(shù)GO(Ik,a)= Ij，當(dāng)a為終結(jié)符時(shí)則置ACTION[k,a]為Sj，其動(dòng)作含意為將終結(jié)符a移進(jìn)符號(hào)棧，狀態(tài)j進(jìn)入狀態(tài)棧，(相當(dāng)狀態(tài)k時(shí)遇a轉(zhuǎn)向狀態(tài)j)。</p><p>　　(2) 若項(xiàng)目A→α· 屬于Ik，則對(duì)任何終結(jié)符a 和'#'號(hào)置ACTION[k,a]和ACTION[k,#]為"rj&q

24、uot;，j為在文法G′中某產(chǎn)生式A→α的序號(hào)。rj動(dòng)作的含義是把當(dāng)前文法符號(hào)棧頂?shù)姆?hào)串α歸約為A，并狀態(tài)棧指針從棧頂向下移動(dòng)|α|的長(zhǎng)度 , 文法符號(hào)棧從棧頂彈出|α|個(gè)符號(hào)，非終結(jié)符A變?yōu)楫?dāng)前面臨的符號(hào)。</p><p>　　(3) 若GO(Ik,A)＝Ij，則置GOTO[k,A]為"j"，其中A為非終結(jié)符，表示當(dāng)前狀態(tài)為"k"時(shí)，遇文法符號(hào)A時(shí)狀態(tài)應(yīng)轉(zhuǎn)向j，因此A移

25、入文法符號(hào)棧，j移入狀態(tài)棧。</p><p>　　(4) 若項(xiàng)目S′→S·屬于Ik，則置ACTION[k,#]為"acc"，表示接受。</p><p>　　(5) 凡不能用上述方法填入的分析表的元素，均應(yīng)填上"報(bào)錯(cuò)標(biāo)志"。為了表的清晰我們僅用空白表示錯(cuò)誤標(biāo)志。</p><p>　　根據(jù)這種方法構(gòu)造的LR(0)分析表不

26、含多重定義時(shí)，稱這樣的分析表為L(zhǎng)R(0)分析表，能用LR(0)分析表的分析器稱為L(zhǎng)R(0)分析器，能構(gòu)造LR(0)分析表的文法稱為L(zhǎng)R(0)文法。</p><p>　　產(chǎn)生如下所示的LR分析表 </p><p>　　表 1 LR分析表</p><p>　　這張分析表包括兩個(gè)部分，一是“動(dòng)作”（ACTION）表，另一是

27、“狀態(tài)轉(zhuǎn)換”（GOTO）表。ACTION(S,a)規(guī)定了當(dāng)狀態(tài)S面臨輸入符號(hào)a時(shí)應(yīng)采取什么動(dòng)作。GOTO（S，X）規(guī)定了狀態(tài)S面對(duì)文法符號(hào)X（終結(jié)符或非終結(jié)符）時(shí)下一狀態(tài)是什么。顯然，GOTO(S，X)定義了一個(gè)以文法符號(hào)為字母表的DFA。其中，S0為分析器的初態(tài)；＃為句子的左括號(hào)；a1a2……an為輸入串；其后的＃為結(jié)束符（句子右括號(hào)）。分析過程每步的結(jié)果可表示為：（S0S1……Sm，#X1X2……Xm ai, ai+1……an#）。

28、</p><p><b>　　3.2 實(shí)現(xiàn)方法</b></p><p>　　3.2.1 構(gòu)造分析表</p><p>　　LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器（棧）的確定有限狀態(tài)自動(dòng)機(jī)。LR分析器的每一步工作是由棧頂狀態(tài)和現(xiàn)行輸入符號(hào)所唯一決定的。構(gòu)造一個(gè)int型二維數(shù)組table[13][9],用于存放LR分析表。并初始化。作者這樣規(guī)定：&l

29、t;/p><p>　　0～11 表示 狀態(tài)Sj，其中0對(duì)應(yīng)S0，1對(duì)應(yīng)S1……</p><p>　　21～26 表示 規(guī)約Rj，其中21對(duì)應(yīng)R1，22對(duì)應(yīng)R2……</p><p>　　12 表示 “接受”。</p><p>　　-1 表示 規(guī)約出錯(cuò)，報(bào)錯(cuò)。</p><p>　　3.2.2程

30、序設(shè)計(jì)關(guān)鍵</p><p>　?。?）在輸入串(句子)輸入的過程中，涉及到一個(gè)壓棧的問題。但是輸入串壓入的字符順序剛好與原理中的字符串模型剛好相反，這樣需要先彈出的反而在棧底。為了既要保證字符串輸入，又要讓輸入的字符串存儲(chǔ)順序與輸入的字符串相反。采取以下措施：</p><p>　　先將輸入的字符串壓入符號(hào)棧symbol中，然后符號(hào)棧彈出的字符再壓入輸入串棧instr中，這樣實(shí)現(xiàn)了輸入串的倒

31、序存儲(chǔ)。</p><p>　?。?）狀態(tài)棧和符號(hào)棧輸出（遍歷）過程均采取自棧底到棧頂?shù)捻樞?，而輸入串棧則是采取自棧頂?shù)綏５椎捻樞蜉敵觥?lt;/p><p>　　3.2.3 LR(0)項(xiàng)目集規(guī)范族的構(gòu)造</p><p>　　識(shí)別活前輟的NFA我們可以利用子集法將其確定化。對(duì)確定化后的DFA如果把每個(gè)子集中所含狀態(tài)集對(duì)應(yīng)的項(xiàng)目寫在新的狀態(tài)中。對(duì)于構(gòu)成識(shí)別一個(gè)文法活前綴的DF

32、A項(xiàng)目集(狀態(tài))的全體稱為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族，我們可以分析每個(gè)狀態(tài)中項(xiàng)目集的構(gòu)成，不難發(fā)現(xiàn)如下規(guī)律：</p><p>　　若狀態(tài)中包含形如A→α·Bβ的項(xiàng)目，則形如B→·γ的項(xiàng)目也在此狀態(tài)內(nèi)。例如：0狀態(tài)中項(xiàng)目集為{S′→·E，E→·aA, E→·bB}。</p><p>　　回顧由NFA確定化到DFA時(shí)，E→·aA

33、和E→·bB正是屬于S′→·E的閉包中。因而，可引入閉包函數(shù)(CLOSURE)來求DFA一個(gè)狀態(tài)的項(xiàng)目集。</p><p>　　若文法G已拓廣為G′，而S為文法G的開始符號(hào)，拓廣后增加產(chǎn)生式S′→S。如果I是文法G′的一個(gè)項(xiàng)目集，定義和構(gòu)造I的閉包CLOSURE(I)如下：</p><p>　　(1) I的項(xiàng)目均在CLOSURE(I)中。</p><

34、p>　　(2) 若A→α·Bβ屬于CLOSURE(I)，則每一形如B→·γ的項(xiàng)目也屬于</p><p>　　CLOSURE(I)。</p><p>　　(3) 重復(fù)(2)直到不出現(xiàn)新的項(xiàng)目為止。即CLOSURE(I)不再擴(kuò)大。</p><p>　　由此，我們可以很容易構(gòu)造出初態(tài)的閉包，即S′→·S屬于I，再按上述三點(diǎn)求其閉包。&l

35、t;/p><p><b>　　3.3 詳細(xì)流程圖</b></p><p>　　圖3.1 LR分析器設(shè)計(jì)流程圖</p><p>　　圖2 LR分析器設(shè)計(jì)流程圖</p><p><b>　　四、代碼編寫</b></p><p>　　4.1 生成分析表代碼</p>&l

36、t;p>　　void CLR0ForWinDlg::OnGtable() </p><p><b>　　{</b></p><p>　　CTableDlg dlg;</p><p>　　dlg.SetControlInfo(IDC_EXPLORER1, RESIZE_BOTH);</p><p>　　dlg.Set

37、ControlInfo(IDOK, ANCHORE_BOTTOM | ANCHORE_RIGHT);</p><p>　　dlg.SetControlInfo(IDC_EXPORT, ANCHORE_BOTTOM | ANCHORE_RIGHT);</p><p>　　dlg.SetControlInfo(IDC_ANALYZE, ANCHORE_BOTTOM | ANCHORE_RIGH

38、T);</p><p>　　string temp = "";</p><p>　　CString t;</p><p>　　for(int i = 0; i < m_vtlist.GetCount(); i++)</p><p><b>　　{</b></p><p>

39、　　m_vtlist.GetText(i,t);</p><p>　　//temp.push_back(t.GetAt(0));</p><p>　　temp += t.GetAt(0);</p><p><b>　　}</b></p><p>　　dlg.g.SetVt(temp);</p><p&

40、gt;　　temp = "";</p><p>　　for(i = 0; i < m_vnlist.GetCount(); i++)</p><p><b>　　{</b></p><p>　　m_vnlist.GetText(i,t);</p><p>　　//temp.push_back(t

41、.GetAt(0));</p><p>　　temp += t.GetAt(0);</p><p><b>　　}</b></p><p>　　dlg.g.SetVn(temp);</p><p>　　m_startedit.GetWindowText(t);</p><p>　　if (t ==

42、 "")</p><p><b>　　{</b></p><p>　　MessageBox("輸入的文法有誤，請(qǐng)檢查！", "錯(cuò)誤",MB_OK | MB_ICONSTOP);</p><p><b>　　return;</b></p><p&

43、gt;<b>　　}</b></p><p>　　dlg.g.SetStart(t.GetAt(0));</p><p>　　temp = "";</p><p>　　for(i = 0; i < m_plist.GetCount(); i++)</p><p><b>　　{<

44、/b></p><p>　　temp = "";</p><p>　　m_plist.GetText(i,t);</p><p>　　for(int j = 0; j < t.GetLength(); j ++)</p><p>　　//temp.push_back(t.GetAt(j));</p>

45、<p>　　temp += t.GetAt(j);</p><p>　　dlg.g.AddPrecept(temp);</p><p><b>　　}</b></p><p>　　if(dlg.g.IsGrammarLegal())</p><p><b>　　{</b></p&

46、gt;<p>　　dlg.g.GenerateLR0Table();</p><p>　　dlg.DoModal();</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p>

47、<p>　　MessageBox("輸入的文法有誤，請(qǐng)檢查！", "錯(cuò)誤",MB_OK | MB_ICONSTOP);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　4.2分析句子代碼</

48、b></p><p>　　void CAnalyzeDlg::OnButton1() </p><p><b>　　{</b></p><p>　　// TODO: Add your control notification handler code here</p><p>　　UpdateData(TRUE);

49、</p><p>　　m_pTree->m_tree.DeleteAllItems();</p><p>　　for(int i = 0; i < m_input.GetLength(); i ++)</p><p><b>　　{</b></p><p>　　if (!m_g.IsInVt(m_input.

50、GetAt(i)))</p><p><b>　　{</b></p><p>　　MessageBox("輸入的句子不全部由終結(jié)符組成", "錯(cuò)誤", MB_OK | MB_ICONSTOP);</p><p><b>　　return;</b></p><p&g

51、t;<b>　　}</b></p><p><b>　　}</b></p><p>　　assert(TreeStack.empty());</p><p>　　m_input += "#";</p><p>　　char szTempPath[MAX_PATH]; </p

52、><p>　　char szTempName[MAX_PATH]; </p><p>　　if (m_strTempFilename != "")</p><p>　　::DeleteFile(m_strTempFilename.c_str());</p><p>　　::GetTempPath(100,szTempPath)

53、;</p><p>　　::GetTempFileName(szTempPath,"LR0",0,szTempName);</p><p>　　m_strTempFilename = szTempName;</p><p>　　CStdioFile out;</p><p>　　out.Open(szTempName, C

54、File::modeCreate | CFile::modeWrite);</p><p>　　out.WriteString("<html>\n");</p><p>　　out.WriteString("<head>\n");</p><p>　　out.WriteString("<

55、title>Untitled Document</title>\n");</p><p>　　out.WriteString("<meta http-equiv=\"Content-Type\" content=\"text/html; charset=gb2312\">\n");</p><p

56、>　　out.WriteString("</head>\n");</p><p>　　out.WriteString("<body bgcolor=\"#FFFFFF\" text=\"#000000\">\n");</p><p>　　out.WriteString("

57、<table border=\"1\" cellpadding=\"0\" cellspacing=\"0\" style=\"border-collapse: collapse\" bordercolor=\"#111111\">\n");</p><p>　　out.WriteStrin

58、g("<tr>\n<td nowrap>&nbsp;步驟&nbsp;</td>\n<td nowrap>&nbsp;狀態(tài)棧</td>\n<td nowrap>&nbsp;符號(hào)棧&nbsp;</td>\n<td nowrap>&nbsp;輸入串&nbsp;</td>\

59、n<td nowrap>&nbsp;ACTION&nbsp;</td>\n<td nowrap >&nbsp;GOTO&nbsp;</td>\n </tr>\n");</p><p>　　vector <int> Status;</p><p>　　vector <cha

60、r> Symbol;</p><p>　　int iStep = 1;</p><p>　　int iPos = 0;</p><p>　　Status.push_back(0);</p><p>　　Symbol.push_back('#');</p><p>　　Pair ToDo;</

61、p><p>　　bool bErrorFlag = false;</p><p>　　bool bGoOn = true;</p><p>　　while ((bGoOn) && (!bErrorFlag))</p><p><b>　　{</b></p><p>　　assert(i

62、Pos < m_input.GetLength());</p><p>　　assert(Status.size() == Symbol.size());</p><p>　　ToDo = m_g.GetAction(Status.back(), m_input.GetAt(iPos));</p><p><b>　　int i, j;</b&

63、gt;</p><p>　　switch (ToDo.one)</p><p><b>　　{</b></p><p><b>　　case 'S':</b></p><p>　　out.WriteString(GetStepInfo(iStep, Status, Symbol, m

64、_input.Right(m_input.GetLength() - iPos), ToDo, -1));</p><p>　　Symbol.push_back(m_input.GetAt(iPos));</p><p>　　Status.push_back(ToDo.two);</p><p><b>　　iPos++;</b></p&

65、gt;<p><b>　　break;</b></p><p><b>　　case 'R':</b></p><p>　　j = m_g.GetGoTo(Status[Status.size()-m_g.GetPrecept(ToDo.two).GetRight().length()-1], m_g.GetPrec

66、ept(ToDo.two).GetLeft()[0]);</p><p>　　assert(j != -1);</p><p>　　out.WriteString(GetStepInfo(iStep, Status, Symbol, m_input.Right(m_input.GetLength() - iPos), ToDo, j));</p><p>　　for

67、(i = 0; i < m_g.GetPrecept(ToDo.two).GetRight().length(); i++)</p><p><b>　　{</b></p><p>　　Status.pop_back();</p><p>　　Symbol.pop_back();</p><p><b>

68、　　}</b></p><p>　　Symbol.push_back(m_g.GetPrecept(ToDo.two).GetLeft()[0]);</p><p>　　Status.push_back(j);</p><p>　　TreeStack.push(ToDo.two);</p><p><b>　　break

69、;</b></p><p><b>　　case 'a':</b></p><p>　　if (m_input.GetAt(iPos) == '#')</p><p><b>　　{</b></p><p>　　out.WriteString(GetSte

70、pInfo(iStep, Status, Symbol, m_input.Right(m_input.GetLength() - iPos), ToDo, -1));</p><p>　　bGoOn = false;</p><p><b>　　}</b></p><p><b>　　else</b></p>

71、<p>　　bErrorFlag = true;</p><p><b>　　break;</b></p><p><b>　　case 0:</b></p><p>　　bErrorFlag = true;</p><p><b>　　break;</b><

72、/p><p><b>　　default:</b></p><p>　　assert(false);</p><p><b>　　}</b></p><p><b>　　iStep++;</b></p><p><b>　　}</b>&

73、lt;/p><p>　　out.WriteString("</table>");</p><p>　　if (bErrorFlag)</p><p><b>　　{</b></p><p>　　out.WriteString("<p><font color=\&qu

74、ot;#FF3300\">分析失敗，輸入的字符串是不符合預(yù)定文法的！</font></p>\n");</p><p>　　//m_pTree->m_tree.DeleteAllItems();</p><p>　　while(!TreeStack.empty())</p><p>　　TreeStack.pop

75、();</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　out.WriteString("<p><font color=\"#009900\&

76、quot;>分析完成，輸入的字符串是預(yù)定文法的句子</font></p>\n");</p><p>　　//HTREEITEM h = m_pTree->m_tree.GetRootItem();</p><p>　　//ExpandTree(h);</p><p>　　MakeTree();</p>&l

77、t;p><b>　　}</b></p><p>　　out.WriteString("</body>\n</html>");</p><p>　　out.Close();</p><p>　　m_web.Navigate(szTempName,NULL,NULL,NULL,NULL);</

78、p><p>　　m_edit1.SetFocus();</p><p>　　m_edit1.SetSel(0, -1);</p><p><b>　　}</b></p><p><b>　　五、調(diào)試分析</b></p><p>　　編完自己的程序，然后在將其他組員的程序整合起來后

79、就進(jìn)行了,首先將所有的程序進(jìn)行測(cè)試和編譯檢查有沒有錯(cuò)誤，有錯(cuò)誤的話先修改正確，在調(diào)試的過程中，先輸入字符串，進(jìn)行規(guī)約，要注意的是一定要輸入可以規(guī)約的字符串且要在字符串的最后輸入一個(gè)“#”號(hào)作為規(guī)約的結(jié)束標(biāo)志，如果沒有加上“#”結(jié)束符號(hào)，導(dǎo)致系統(tǒng)認(rèn)為用戶的輸入串并沒有結(jié)束，不斷的進(jìn)行規(guī)約，并且在規(guī)約的時(shí)候要特別注意各棧的值的情況，因?yàn)樽詈笠敵鼋Y(jié)果，如果輸入的是不可規(guī)約的字符串那系統(tǒng)就會(huì)出錯(cuò)不能完成規(guī)約。</p><p

80、><b>　　六、運(yùn)行與調(diào)試</b></p><p><b>　　圖3 導(dǎo)入文法界面</b></p><p>　　圖4 生成分析表界面</p><p><b>　　圖5 分析句子界面</b></p><p>　　圖6 生成語法樹界面</p><p&g

81、t;<b>　　總 結(jié)</b></p><p>　　編譯原理是一門很重要的課程。我們平常寫小的C語言程序會(huì)感到困難，而編譯原理則是關(guān)于編寫編譯器的技術(shù)，難度之大可想而知。編譯器的編寫一直被認(rèn)為是十分困難的事情，難怪第一Fortran的編譯器據(jù)說花了18年的時(shí)間才完成。當(dāng)然編譯原理和編譯技術(shù)并不是相同的，編譯原理更注重理論方面的知識(shí)，編譯技術(shù)更注重實(shí)際編寫編譯器過程中用到的技術(shù)。在編程序的過

82、程中，有時(shí)會(huì)和一個(gè)小小的錯(cuò)誤較上半天的勁，等到最后才發(fā)現(xiàn)只是由于語法用的不正確，算法是可行的。這樣在一個(gè)小小的語法錯(cuò)誤上浪費(fèi)許多時(shí)間是很不值得，所以在今后的語言學(xué)習(xí)中，我會(huì)重視語法的細(xì)節(jié)。另外在程序設(shè)計(jì)上，以前自己傾向于直接寫程序，很少使用流程圖。后來發(fā)現(xiàn)先設(shè)計(jì)出流程圖，那么程序的結(jié)構(gòu)就會(huì)清晰的多，編寫的時(shí)候也會(huì)更節(jié)省時(shí)間。在整個(gè)程序中，我認(rèn)為其中逆波蘭式的構(gòu)造和自動(dòng)機(jī)的構(gòu)造都是比較難的，是通過對(duì)基礎(chǔ)知識(shí)的詳細(xì)深入回顧得出，特別是自動(dòng)機(jī)

83、的確定化過程煩鎖又耗時(shí)，采用了鄰接表進(jìn)行存儲(chǔ)。上機(jī)的調(diào)試時(shí)間也不是很長(zhǎng)，但程序的最大問題就是可讀性不強(qiáng)，雖基本功能能達(dá)到理想的效果。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　1、陳意云．編譯原理和技術(shù)．中國(guó)科技大學(xué)出版社，1997</p><p>　　2、金成植．編譯程序構(gòu)造原理和實(shí)現(xiàn)技術(shù)．高等教育出版社，2006&l