編譯原理課程設計

1、編譯原理課程設計報告太 原 學 院課程設計報告書課程名稱 編譯原理 設計題目 構造LR(0)分析法語法分析器 專業(yè)班級 計算機科學與技術13-4班 學 號 20130905405 姓 名 王芳芳 指導教師 吳海麗 2016年 12 月 15日1目 錄一、課題概述1二、系統(tǒng)分析221 本課程設計的知識點22.1.1 詞法編譯器功能22.1.2 詞法分析器的設計22.1.3 動態(tài)模擬算法的基本功能22.1.4 LR分析器的構成22. 2解決問題的基本思路323 需解決的關鍵技術324 功能模塊框圖3三、系統(tǒng)設計431 算法描述43. 2 實現方法63.2.1 構造分析表63.2.2程序設計關鍵63

2、.2.3 LR(0)項目集規(guī)范族的構造633 詳細流程圖7四、代碼編寫8 4. 1 生成分析表代碼8 4. 2分析句子代碼10五、調試分析14六、運行與調試15總 結 17參考文獻181、 課題概述 編譯原理是計算機專業(yè)的一門重要的專業(yè)課程，其中包含大量軟件設計思想。通過課程設計，實現一些重要的算法，或設計一個完整的編譯程序模型，能夠進一步加深理解和掌握所學知識，對提高自己的軟件設計水平具有十分重要的意義。語法分析是編譯過程的第二階段，是編譯器前端的核心組成部分，在編譯系統(tǒng)中起到了至關重要的作用。自底向上的語法分析與自頂向下的語法分析相比，對將要分析的源程序有著更大的分析空間，從而受到了廣泛的

3、運用。 本次課程設計的目標即是利用所學過的編譯原理的知識，利用LR(0)分析法，用C語言寫出一個簡單的LR(0)語法分析器。該語法分析器所要完成的功能是，對錄入的文法判斷它是否為LR(0)文法，如果是輸出LR (0)分析表；在給定文法的情況下，能夠利用LR(0)分析表，對用戶輸入的一串字符串用LR(0)分析法進行分析，判斷該字符串是否為符合給定文法的一個句子，建立文法及其LR分析表表示的數據結構，設計并實現一個LR(0)的分析器。編譯器設計的編譯程序涉及到編譯五個階段中的三個，即詞法分析器、語法分析器和中間代碼生成器。編譯程序的輸出結果包括詞法分析后的二元式序列、變量名表、狀態(tài)棧分析

4、過程顯示及四元式序列程序。整個編譯程序分為三部分：詞法分析部分、語法分析處理及四元式生成部分、輸出顯示部分。一個程序設計語言就是一個記號系統(tǒng)，如同自然語言一樣，它的完整的定義應包括語法和語義兩個方面。所謂一個語言的語法是指一組規(guī)則，用它可以形成和產生一個合適的程序。目前廣泛使用的手段是上下文無關文法，即用上下文無關文法作為程序設計語言語法的描述工具。LR分析法正是給出一種能根據當前分析棧中的符號串（通常以狀態(tài)表示）和向右順序查看輸人串的k個(k>=0)符號就可惟一地確定分析器的動作是移進還是歸約和用哪個產生式歸約，因而也就能惟一地確定句柄。LR分析法的歸約過程是規(guī)范推導的逆過程，所以LR

5、分析過程是一種規(guī)范歸約過程。 二、系統(tǒng)分析2.1 本課程設計涉及的知識點2.1.1 詞法編譯器功能（1）導入任意文法，也可以自己輸入。（2）輸出文法的分析過程，以及判斷是否為LR (0)文法，輸出分析表。（3）輸入句子，進行語法分析。（4）輸出結構樹。2.1.2 詞法分析器的設計(1)寫出該語言的詞法規(guī)則。(2)把詞法規(guī)則轉換為相應的狀態(tài)轉換圖。(3)把各轉換圖的初態(tài)連在一起，構成識別該語言的自動機。(4)設計掃描器；把掃描器作為語法分析的一個過程，當語法分析需要一個單詞時，就調用掃描器。掃描器從初態(tài)出發(fā)，當識別一個單詞后便進入終態(tài)，送出二元式。2.1.3 動態(tài)模擬算法的基本功能（1

6、）輸入LR分析表和一個句子。（2）輸出LR總控程序。（3）輸出依據句子構對應的語法樹的過程。（4）設計一個給定LR分析表，輸入一個句子，能由依據LR分析表輸出與句子對應的語法樹，能對語法樹生成過程進行模擬。（5）輸入句子：bccd#。（6）根據文法產生的LR分析表。（7）輸出結果2.1.4 LR分析器的構成一個LR分析器由個部分組成（1）總控程序，也可以稱為驅動程序。對所有的LR分析器，總控程序都是相同的。（2）分析表或分析函數。不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表也不同，分析表又可以分為動作（ACTION）表和狀態(tài)（GOTO）表兩個部分，它們都可用二維數組表示。（

7、3）分析棧，包括文法符號和相應的狀態(tài)棧。它們均是先進后出棧。分析器的動作由棧頂狀態(tài)和當前輸入符號所決定（LR(0)分析器不需向前查看輸入符號）。2.2解決問題的基本思路1、用構造一個狀態(tài)轉換函數實現狀態(tài)轉換。2、再通過函數構造一個移進歸約函數實現移進規(guī)約動作。3、采用構造一個打印LR分析器的工作過程函數實現輸出。 在規(guī)范規(guī)約的過程中，一方面記住已移進和規(guī)約出的整個符號串，另一方面根據所用的產生式推測可能碰到的輸入符號。每一項ACTION(s，a)所規(guī)定的動作不外是下述四種可能之一：（1）移進（2）規(guī)約（3）接受（4）報錯。2.3 需解決的關鍵技術（1）詞法編譯器。（2）交互式面向對象的詞法編譯

8、器基本功能是。（3）根據規(guī)約規(guī)則對字符進行歸約。 （4）符合條件時采取移進動作。2.4 功能模塊框圖運行程序給出該程序所運用的文法和LR分析表用戶輸入字符串程序給出結果圖1 功能模塊框圖三、系統(tǒng)設計3.1 算法描述1、已知文法G(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fi2、LR(0)分析表的構造算法如下：假設已構造出LR(0)項目集規(guī)范族為：C=I0,I1, , In，其中Ik為項目集的名字，k為狀態(tài)名，令包含S·S項目的集合Ik的下標k為分析器的初始狀態(tài)。那么分析表的ACTION表和GOTO表構造步驟為：(1) 若項目A·a屬于I

9、k且轉換函數GO(Ik,a)= Ij，當a為終結符時則置ACTIONk,a為Sj，其動作含意為將終結符a移進符號棧，狀態(tài)j進入狀態(tài)棧，(相當狀態(tài)k時遇a轉向狀態(tài)j)。(2) 若項目A· 屬于Ik，則對任何終結符a 和'#'號置ACTIONk,a和ACTIONk,#為"rj"，j為在文法G中某產生式A的序號。rj動作的含義是把當前文法符號棧頂的符號串歸約為A，并狀態(tài)棧指針從棧頂向下移動|的長度 , 文法符號棧從棧頂彈出|個符號，非終結符A變?yōu)楫斍懊媾R的符號。(3) 若GO(Ik,A)Ij，則置GOTOk,A為"j"，其中A為非終結

10、符，表示當前狀態(tài)為"k"時，遇文法符號A時狀態(tài)應轉向j，因此A移入文法符號棧，j移入狀態(tài)棧。(4) 若項目SS·屬于Ik，則置ACTIONk,#為"acc"，表示接受。(5) 凡不能用上述方法填入的分析表的元素，均應填上"報錯標志"。為了表的清晰我們僅用空白表示錯誤標志。根據這種方法構造的LR(0)分析表不含多重定義時，稱這樣的分析表為LR(0)分析表，能用LR(0)分析表的分析器稱為LR(0)分析器，能構造LR(0)分析表的文法稱為LR(0)文法。3、 產生如下所示的LR分析表 STATEACTIONGOTOabcd#ET

11、F0S2S311acc2S4S1063S5S474S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6 表 1 LR分析表這張分析表包括兩個部分，一是“動作”（ACTION）表，另一是“狀態(tài)轉換”（GOTO）表。ACTION(S,a)規(guī)定了當狀態(tài)S面臨輸入符號a時應采取什么動作。GOTO（S，X）規(guī)定了狀態(tài)S面對文法符號X（終結符或非終結符）時下一狀態(tài)是什么。顯然，GOTO(S，X)定義了一個以文法符號為字母表的DFA。其中，S0為分析器的初態(tài)；為句子的左括號；a1a2an為輸入串；其

12、后的為結束符（句子右括號）。分析過程每步的結果可表示為：（S0S1Sm，#X1X2Xm ai, ai+1an#）。3.2 實現方法3.2.1 構造分析表LR分析器實質上是一個帶先進后出存儲器（棧）的確定有限狀態(tài)自動機。LR分析器的每一步工作是由棧頂狀態(tài)和現行輸入符號所唯一決定的。構造一個int型二維數組table139,用于存放LR分析表。并初始化。作者這樣規(guī)定：011 表示 狀態(tài)Sj，其中0對應S0，1對應S12126 表示 規(guī)約Rj，其中21對應R1，22對應R212 表示 “接受”。-1 表示 規(guī)約出錯，報錯。3.2.2程序設計關鍵（1）在輸入串(句子)輸入的過程中，涉及到一個壓棧的問題

13、。但是輸入串壓入的字符順序剛好與原理中的字符串模型剛好相反，這樣需要先彈出的反而在棧底。為了既要保證字符串輸入，又要讓輸入的字符串存儲順序與輸入的字符串相反。采取以下措施：先將輸入的字符串壓入符號棧symbol中，然后符號棧彈出的字符再壓入輸入串棧instr中，這樣實現了輸入串的倒序存儲。（2）狀態(tài)棧和符號棧輸出（遍歷）過程均采取自棧底到棧頂的順序，而輸入串棧則是采取自棧頂到棧底的順序輸出。3.2.3 LR(0)項目集規(guī)范族的構造識別活前輟的NFA我們可以利用子集法將其確定化。對確定化后的DFA如果把每個子集中所含狀態(tài)集對應的項目寫在新的狀態(tài)中。對于構成識別一個文法活前綴的DFA項目集(狀態(tài))

14、的全體稱為這個文法的LR(0)項目集規(guī)范族，我們可以分析每個狀態(tài)中項目集的構成，不難發(fā)現如下規(guī)律：若狀態(tài)中包含形如A·B的項目，則形如B·的項目也在此狀態(tài)內。例如：0狀態(tài)中項目集為S·E，E·aA, E·bB?；仡櫽蒒FA確定化到DFA時，E·aA和E·bB正是屬于S·E的閉包中。因而，可引入閉包函數(CLOSURE)來求DFA一個狀態(tài)的項目集。若文法G已拓廣為G，而S為文法G的開始符號，拓廣后增加產生式SS。如果I是文法G的一個項目集，定義和構造I的閉包CLOSURE(I)如下：(1) I的項目均在CLOSURE

15、(I)中。(2) 若A·B屬于CLOSURE(I)，則每一形如B·的項目也屬于CLOSURE(I)。(3) 重復(2)直到不出現新的項目為止。即CLOSURE(I)不再擴大。由此，我們可以很容易構造出初態(tài)的閉包，即S·S屬于I，再按上述三點求其閉包。3.3 詳細流程圖初始化狀態(tài)棧，符號棧，輸入串棧輸入串各字符壓棧 求下一狀態(tài)符號ii = goto_char(status_p,instr_p)規(guī)約出錯！異常中止！i = = -1 ?規(guī)約成功！退出i = = 12 ?規(guī)約動作：1 求出i對應規(guī)約規(guī)則右部字符串長度x = ri-21.y2 在符號棧和狀態(tài)棧中彈出x個字符

16、。然后將該規(guī)約規(guī)則左部壓入輸入串棧i>0 && i<=11 移進動作：1 將現狀態(tài)i壓棧push(status_p,i)2 將當前輸入串字符壓入符號棧a = pop(instr_p)push(symbol_p,a)打印該步工作過程圖3.1 LR分析器設計流程圖圖2 LR分析器設計流程圖四、代碼編寫4.1 生成分析表代碼void CLR0ForWinDlg:OnGtable() CTableDlg dlg;dlg.SetControlInfo(IDC_EXPLORER1, RESIZE_BOTH);dlg.SetControlInfo(IDOK, ANCHORE_BO

17、TTOM | ANCHORE_RIGHT);dlg.SetControlInfo(IDC_EXPORT, ANCHORE_BOTTOM | ANCHORE_RIGHT);dlg.SetControlInfo(IDC_ANALYZE, ANCHORE_BOTTOM | ANCHORE_RIGHT);string temp = ""CString t;for(int i = 0; i < m_vtlist.GetCount(); i+)m_vtlist.GetText(i,t);/temp.push_back(t.GetAt(0);temp += t.GetAt(0);d

18、lg.g.SetVt(temp);temp = ""for(i = 0; i < m_vnlist.GetCount(); i+)m_vnlist.GetText(i,t);/temp.push_back(t.GetAt(0);temp += t.GetAt(0);dlg.g.SetVn(temp);m_startedit.GetWindowText(t);if (t = "")MessageBox("輸入的文法有誤，請檢查！", "錯誤",MB_OK | MB_ICONSTOP);return;dlg.g.

19、SetStart(t.GetAt(0);temp = ""for(i = 0; i < m_plist.GetCount(); i+)temp = ""m_plist.GetText(i,t);for(int j = 0; j < t.GetLength(); j +)/temp.push_back(t.GetAt(j);temp += t.GetAt(j);dlg.g.AddPrecept(temp);if(dlg.g.IsGrammarLegal()dlg.g.GenerateLR0Table();dlg.DoModal();elseMe

20、ssageBox("輸入的文法有誤，請檢查！", "錯誤",MB_OK | MB_ICONSTOP);4.2分析句子代碼void CAnalyzeDlg:OnButton1() / TODO: Add your control notification handler code hereUpdateData(TRUE);m_pTree->m_tree.DeleteAllItems();for(int i = 0; i < m_input.GetLength(); i +)if (!m_g.IsInVt(m_input.GetAt(i)Mess

21、ageBox("輸入的句子不全部由終結符組成", "錯誤", MB_OK | MB_ICONSTOP);return;assert(TreeStack.empty();m_input += "#"char szTempPathMAX_PATH; char szTempNameMAX_PATH; if (m_strTempFilename != ""):DeleteFile(m_strTempFilename.c_str();:GetTempPath(100,szTempPath);:GetTempFileName(

22、szTempPath,"LR0",0,szTempName);m_strTempFilename = szTempName;CStdioFile out;out.Open(szTempName, CFile:modeCreate | CFile:modeWrite);out.WriteString("<html>n");out.WriteString("<head>n");out.WriteString("<title>Untitled Document</title>n&qu

23、ot;);out.WriteString("<meta http-equiv="Content-Type" content="text/html; charset=gb2312">n");out.WriteString("</head>n");out.WriteString("<body bgcolor="#FFFFFF" text="#000000">n");out.WriteString("<tabl

24、e border="1" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111">n");out.WriteString("<tr>n<td nowrap>&nbsp;步驟&nbsp;</td>n<td nowrap>&nbsp;狀態(tài)棧</td>n<td nowr

25、ap>&nbsp;符號棧&nbsp;</td>n<td nowrap>&nbsp;輸入串&nbsp;</td>n<td nowrap>&nbsp;ACTION&nbsp;</td>n<td nowrap >&nbsp;GOTO&nbsp;</td>n </tr>n");vector <int> Status;vector <char> Symbol;int iStep = 1;int iPos =

26、 0;Status.push_back(0);Symbol.push_back('#');Pair ToDo;bool bErrorFlag = false;bool bGoOn = true;while (bGoOn) && (!bErrorFlag)assert(iPos < m_input.GetLength();assert(Status.size() = Symbol.size();ToDo = m_g.GetAction(Status.back(), m_input.GetAt(iPos);int i, j;switch (ToDo.one)c

27、ase 'S':out.WriteString(GetStepInfo(iStep, Status, Symbol, m_input.Right(m_input.GetLength() - iPos), ToDo, -1);Symbol.push_back(m_input.GetAt(iPos);Status.push_back(ToDo.two);iPos+;break;case 'R':j = m_g.GetGoTo(StatusStatus.size()-m_g.GetPrecept(ToDo.two).GetRight().length()-1, m_g

28、.GetPrecept(ToDo.two).GetLeft()0);assert(j != -1);out.WriteString(GetStepInfo(iStep, Status, Symbol, m_input.Right(m_input.GetLength() - iPos), ToDo, j);for(i = 0; i < m_g.GetPrecept(ToDo.two).GetRight().length(); i+)Status.pop_back();Symbol.pop_back();Symbol.push_back(m_g.GetPrecept(ToDo.two).Ge

29、tLeft()0);Status.push_back(j);TreeStack.push(ToDo.two);break;case 'a':if (m_input.GetAt(iPos) = '#')out.WriteString(GetStepInfo(iStep, Status, Symbol, m_input.Right(m_input.GetLength() - iPos), ToDo, -1);bGoOn = false;elsebErrorFlag = true;break;case 0:bErrorFlag = true;break;default

30、:assert(false);iStep+;out.WriteString("</table>");if (bErrorFlag)out.WriteString("<p><font color="#FF3300">分析失敗，輸入的字符串是不符合預定文法的！</font></p>n");/m_pTree->m_tree.DeleteAllItems();while(!TreeStack.empty()TreeStack.pop();elseout.WriteString("<p><font color="#009900">分析完成，輸入的字符串是預定文法的句子</font></p>n");/HTREEITEM h = m_pTree->m_tree.GetRootItem();/ExpandTree(h);MakeTree();out.WriteString("</body>n</html>