編譯原理課程設(shè)計(jì)算術(shù)表達(dá)式的LR分析過程

1、武漢理工大學(xué)華夏學(xué)院課 程 設(shè) 計(jì)課程名稱 編譯方法課程設(shè)計(jì) 題 目 算術(shù)表達(dá)式的LR分析過程 專 業(yè) 計(jì)算機(jī)應(yīng)用 班 級 1071班 學(xué) 號 姓 名 蔣夢琴 成 績 _ 指導(dǎo)教師 何九周 段學(xué)東 2009年6 月29日目 錄課程設(shè)計(jì)任務(wù)書-31設(shè)計(jì)目的-42設(shè)計(jì)要求-43設(shè)計(jì)內(nèi)容-431設(shè)計(jì)原則-432設(shè)計(jì)的題目-433在程序中表示文法-5331文法的輸入與讀取-5332文法的拓展-5333文法的保存格式-5334SLR(1)文法的定義-5335 SLR(1)_Action表的構(gòu)造-6336 SLR(1)_GoTo表的構(gòu)造-6337程序算法的設(shè)計(jì)-7124上機(jī)調(diào)試-134.1測試結(jié)果-135

2、心得體會(huì)-146參考文獻(xiàn)-14課程設(shè)計(jì)封底-15課程設(shè)計(jì)任務(wù)書設(shè)計(jì)題目：算術(shù)表達(dá)式的LR分析過程設(shè)計(jì)目的1. 鞏固和加深課堂所學(xué)知識；2. 學(xué)習(xí)掌握一般的軟硬件的設(shè)計(jì)方法和查閱、運(yùn)用資料的能力；3. 掌握高級語言詞法分析、語義分析、語法分析方法；4. 運(yùn)用高級語言編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序。設(shè)計(jì)任務(wù) （在規(guī)定的時(shí)間內(nèi)完成下列任務(wù)）1. 寫出符合該算術(shù)表達(dá)式的的文法和屬性文法描述；2. 按照算術(shù)表達(dá)式的LR分析過程給出分析方法的思想設(shè)計(jì)算術(shù)表達(dá)式文法；3. 完成算數(shù)表達(dá)式的LR分析的程序設(shè)計(jì)，用SLR（1）分析法實(shí)現(xiàn)對算術(shù)表達(dá)式的分析；4. 編制好分析程序后，設(shè)計(jì)若干用例，上機(jī)測試并通過所設(shè)計(jì)

3、的分析程序。時(shí)間安排 消化資料、系統(tǒng)調(diào)查 1天系統(tǒng)分析、總體設(shè)計(jì)，實(shí)施計(jì)劃、撰寫報(bào)告 3天演示、驗(yàn)收 1天具體要求1. 明確課程設(shè)計(jì)的目的和重要性，認(rèn)真領(lǐng)會(huì)課程設(shè)計(jì)的題目，讀懂課程設(shè)計(jì)指導(dǎo)書的要求，學(xué)會(huì)設(shè)計(jì)的基本方法與步驟，學(xué)會(huì)如何運(yùn)用前修知識與收集、歸納相關(guān)資料解決具體問題的方法。嚴(yán)格要求自己，要獨(dú)立思考，按時(shí)、獨(dú)立完成課程設(shè)計(jì)任務(wù)。2. 設(shè)計(jì)報(bào)告：要求層次清楚、整潔規(guī)范、不得相互抄襲，凡正文內(nèi)容有整段完全相同者一律以抄襲論處。設(shè)計(jì)報(bào)告正文字?jǐn)?shù)不少于0.2萬字（不包括附錄）。包含內(nèi)容：設(shè)計(jì)題目。目錄。正文：包括引言、需求分析、總體設(shè)計(jì)及開發(fā)工具的選擇，設(shè)計(jì)原則（給出語法分析方法及中間代碼形式

4、的描述、文法和屬性文法的設(shè)計(jì)），數(shù)據(jù)結(jié)構(gòu)與模塊說明（功能與流程圖）、詳細(xì)的算法設(shè)計(jì)、軟件調(diào)試、軟件的測試方法和結(jié)果、有關(guān)技術(shù)的討論、收獲與體會(huì)等。結(jié)束語。參考文獻(xiàn)（按公開發(fā)表的規(guī)范書寫）。附錄：軟件清單（或者附盤）。3. 軟件系統(tǒng)：界面友好，操作簡單；交付的軟件有必要的安裝、使用說明。指 導(dǎo) 教 師 簽 名： 2009年6月28日教研室主任（或責(zé)任教師）簽名： 2009年6月28日算術(shù)表達(dá)式的LR分析過程1.設(shè)計(jì)目的課程設(shè)計(jì)是對學(xué)生的一種全面綜合訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)。通常，設(shè)計(jì)題中的問題比平時(shí)的練習(xí)題要復(fù)雜，也更接近實(shí)際。編譯原理這門課程安排的課程設(shè)計(jì)

5、的目的是旨在要求學(xué)生進(jìn)一步鞏固課堂上所學(xué)的理論知識，深化理解和靈活掌握教學(xué)內(nèi)容，選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)表示問題，然后編制算法和程序完成設(shè)計(jì)要求，從而進(jìn)一步培養(yǎng)學(xué)生獨(dú)立思考問題、分析問題、解決實(shí)際問題的動(dòng)手能力。通過設(shè)計(jì)調(diào)試詞法分析程序，實(shí)現(xiàn)從源程序中分出各種單詞的方法；加深對課堂教學(xué)的理解；提高詞法分析方法的實(shí)踐能力。2設(shè)計(jì)要求明確課程設(shè)計(jì)的目的和重要性，認(rèn)真領(lǐng)會(huì)課程設(shè)計(jì)的題目，讀懂課程設(shè)計(jì)指導(dǎo)書的要求，學(xué)會(huì)設(shè)計(jì)的基本方法與步驟，學(xué)會(huì)如何運(yùn)用前修知識與收集、歸納相關(guān)資料解決具體問題的方法。嚴(yán)格要求自己，要獨(dú)立思考，按時(shí)、獨(dú)立完成課程設(shè)計(jì)任務(wù)。深入理解所學(xué)的編譯原理相關(guān)知識，按照軟件工程的設(shè)計(jì)方

6、法進(jìn)行簡要的分析與概要設(shè)計(jì)，進(jìn)行總體設(shè)計(jì)，詳細(xì)設(shè)計(jì)、系統(tǒng)實(shí)施、調(diào)試。運(yùn)用程序設(shè)計(jì)語言實(shí)現(xiàn)算法，編寫相關(guān)程序。使用Visual C+編寫程序，并上機(jī)調(diào)試，確保程序能運(yùn)行正確。學(xué)會(huì)正確運(yùn)用語法規(guī)則，并能應(yīng)用優(yōu)先關(guān)系和結(jié)合性解決二義性和沖突問題，有效而正確的利用各種分析方法和思想，合理使用出錯(cuò)處理程序，上機(jī)調(diào)試通過。最后撰寫課程設(shè)計(jì)報(bào)告。3.設(shè)計(jì)內(nèi)容 3.1設(shè)計(jì)原則由于大多數(shù)適用的程序設(shè)計(jì)語言的文法不能滿足LR(0)文法的條件，即使是描述一個(gè)實(shí)數(shù)變量說明這樣簡單的文法也不一定是LR(0)文法。 現(xiàn)舉實(shí)型變量說明文法為例：實(shí)型變量說明 real標(biāo)識符表標(biāo)識符表標(biāo)識符表，i標(biāo)識符表i 3.2設(shè)計(jì)的題目

7、算術(shù)表達(dá)式的文法：E ® E +T | E T | T T ® T * F | T / F | F F ® i |（E） 設(shè)計(jì)算術(shù)表達(dá)式文法，用SLR（1）分析法實(shí)現(xiàn)對算術(shù)表達(dá)式的分析，給出一個(gè)具體句子的分析過程。3.3在程序中表示文法文法的輸入和讀取 為了程序讀取的方便，非/終結(jié)符相互間以空格分開。這里應(yīng)該輸入：E ® E +T | E T | T T ® T * F | T / F | F F ® i |（E） 文法的拓展 為了在LR分析時(shí)能夠指示分析器正確停止并接受輸入，一般在所有輸入文法前加上一個(gè)新的產(chǎn)生式，以上面文法為例，我

8、們要保存的文法應(yīng)該是如此：E ® E E ®E +T E ®ET E ®T T ® T * F T ®T / F T ® F F ® i F ®（E） 文法的保存格式設(shè)計(jì)一個(gè)類Grammar來對文法進(jìn)行各種處理。每一個(gè)項(xiàng)是一個(gè)2元組,記錄了終結(jié)符，和產(chǎn)生式右部。其中非終結(jié)符可以用字符串(string)類型表示，產(chǎn)生式右部可用字符串?dāng)?shù)組( vector<string > )表示。而在保存的同時(shí)又可記錄下文法的所有非終結(jié)符（因?yàn)槲姆ǖ漠a(chǎn)生式左部會(huì)出現(xiàn)所有的非終結(jié)符），然后再對已經(jīng)記錄的文法的產(chǎn)生式

9、右部再掃描一遍，記錄下所有的終結(jié)符。在本程序中，我雖然記錄了原始的符號串，但是在具體過程處理時(shí)使用的是符號串對應(yīng)的下標(biāo)來進(jìn)行的，因此再對原始形式的文法再掃描一遍，生成對應(yīng)的以下標(biāo)形式保存的文法。同時(shí)我對終結(jié)符號和非終結(jié)符號的保存位于不同的數(shù)組中，于是下標(biāo)就會(huì)產(chǎn)生沖突，我采用方式是建立一個(gè)下標(biāo)數(shù)據(jù)結(jié)構(gòu) Index 來保存下標(biāo):struct Index int index; / 非終結(jié)符或者終結(jié)符的下標(biāo) bool teminal; / 為真表示該下標(biāo)保存的是終結(jié)符 bool is_nonteminal(); / 返回! terminal SLR（1）文法的定義（1）若狀態(tài)s 包含了格式A a.Xb

10、 的任意項(xiàng)目，其中X 是一個(gè)終結(jié)符，且X 是輸入串中的下一個(gè)記號，則動(dòng)作將當(dāng)前的輸入記號移進(jìn)到棧中，且被壓入到棧中的新狀態(tài)是包含了項(xiàng)目A aX.b 的狀態(tài)。（2）若狀態(tài)s 包含了完整項(xiàng)目A g.，則輸入串中的下一個(gè)記號是在 Follow (A) 中，所以動(dòng)作是用規(guī)則A g 歸約。用規(guī)則S&cent; S 歸約與接受等價(jià)，其中S 是開始狀態(tài)；只有當(dāng)下一個(gè)輸入記號是$時(shí)，這才會(huì)發(fā)生。在所有的其他情況中，新狀態(tài)都是如下計(jì)算的：刪除串a(chǎn) 和所有它的來自分析棧中的對應(yīng)狀態(tài)。相對應(yīng)地，DFA 回到a 開始構(gòu)造的狀態(tài)。通過構(gòu)造，這個(gè)狀態(tài)必須包括格式B g. Ab 的一個(gè)項(xiàng)目。將A 壓入到棧中，并將包

11、含了項(xiàng)目B aA.b 的狀態(tài)壓入。（3）若下一個(gè)輸入記號都不是上面兩種情況所提到的，則聲明一個(gè)錯(cuò)誤。若上述的 SLR(1) 分析規(guī)則并不導(dǎo)致二義性，則文法為 SLR(1) 文法(SLR(1) grammar)。SLR(1)文法的投影函數(shù)1定義如下：G1：StateSet ´ (VT#) 2WG1 (S,a) = Reduce j |Bp·ÎS,aÎFollow(B),Bp ÎP (if存在Xa·abÎS且aÎVT then Shift) 如果LRSM0中的每個(gè)狀態(tài)S，對任意 aÎVT，使得|G1(S,a)

12、|£1，則稱相應(yīng)文法為SLR(1)文法。 SLR(1)_Action表的構(gòu)造若G1(S,#)=Shift Action( S, # )=Accept若G1(S,a)=Shift 且a¹# Action( S, a) =Shift若G1(S,a)=Reduce j Action( S, a) =Reduce j若G1(S,a)=Æ Action( S, a) = Error SLR(1)_GoTo表的構(gòu)造GoTo( S, X) = S ¢ ， 當(dāng)LRSM0中有S S¢ GoTo( S, X) = error，否則 合并的SLR(1)分析表，合并方

13、法: Action¢( S, a) = Shift i , 當(dāng)Action¢(S, a)= Shift且GoTo(S,a)=Si GoTo¢( S, X) = Si , 當(dāng)GoTo(S,X)=Si 且XÎVN程序算法設(shè)計(jì)#include<stdio.h>#include<string.h>char *action126="S5#",NULL,NULL,"S4#",NULL,NULL, /*ACTION表*/ NULL,"S6#",NULL,NULL,NULL,"

14、acc", NULL,"r2#","S7#", NULL,"r2#","r2#", NULL,"r4#","r4#", NULL,"r4#","r4#", "S5#",NULL,NULL, "S4#",NULL,NULL, NULL,"r6#","r6#", NULL,"r6#","r6#", "S

15、5#",NULL,NULL, "S4#",NULL,NULL, "S5#",NULL,NULL, "S4#",NULL,NULL, NULL,"S6#",NULL, NULL,"S11#",NULL, NULL,"r1#","S7#", NULL,"r1#","r1#", NULL,"r3#","r3#", NULL,"r3#","r3#

16、", NULL,"r5#","r5#", NULL,"r5#","r5#"int goto1123=1,2,3, /*QOTO表*/ 0,0,0, 0,0,0, 0,0,0, 8,2,3, 0,0,0, 0,9,3, 0,0,10, 0,0,0, 0,0,0, 0,0,0, 0,0,0;char vt6='i','+','*','(',')','#' /*存放終結(jié)符*/char vn3='E',

17、'T','F' /*存放非終結(jié)符*/char*LR7="M->E#","E->E+T#","E->T#","T->T*F#","T->F#","F->(E)#","F->i#" /*存放產(chǎn)生式*/int a20;/數(shù)組a實(shí)現(xiàn)狀態(tài)棧char b20,c20,c1;/數(shù)組b實(shí)現(xiàn)符號棧，數(shù)組c存放輸入的字符串int top1,top2,top3,top,m,n;void main() in

18、t g,h,i,j,k,l,p,y,z,count; char x,copy20,copy120; top1=0;top2=0;top3=0;top=0; a0=0;y=a0;b0='#' count=0;z=0; /輸入要識別的字符串 printf("請輸入表達(dá)式n"); do scanf("%c",&c1); ctop3=c1; /字符數(shù)組c10存放輸入的字符串 top3=top3+1;/最后top3=5 while(c1!='#'); /輸出分析結(jié)果 printf("步驟t狀態(tài)棧tt符號棧tt輸入串

19、ttACTIONtGOTOn"); do y=z;m=0;n=0; /*y,z指向狀態(tài)棧棧頂*/ g=top;j=0;k=0; x=ctop; /將輸入符號賦給x count+; printf("%dt",count);/輸出步驟序號 while(m<=top1) /*輸出狀態(tài)棧*/ printf("%d",am); m=m+1; printf("tt"); while(n<=top2) /*輸出符號棧*/ printf("%c",bn); n=n+1; printf("tt&quo

20、t;); while(g<=top3) /*輸出輸入串*/ printf("%c",cg); g=g+1; printf("tt"); while(x!=vtj&&j<=5) /獲取當(dāng)前x對應(yīng)j的值 j+; if(j=5&&x!=vtj)/如果x不是終結(jié)符則報(bào)錯(cuò) printf("errorn"); return; if(actionyj=NULL)/？ printf("errorn"); return; else strcpy(copy,actionyj); if(cop

21、y0='S') /*處理移進(jìn)*/ z=copy1-'0'/因?yàn)闋顟B(tài)從0開始 top1=top1+1; top2=top2+1; atop1=z;/數(shù)組a實(shí)現(xiàn)狀態(tài)棧 btop2=x;/數(shù)組b實(shí)現(xiàn)符號棧 top=top+1;/輸入符號串?dāng)?shù)組c的頂 i=0; while(copyi!='#')/例 "S3#" 輸出ACTION printf("%c",copyi); i+; printf("n"); if(copy0='r') /*處理歸約*/ i=0; while(copyi

22、!='#')/例 "S3#" 輸出ACTION printf("%c",copyi); i+; h=copy1-'0'/因?yàn)闋顟B(tài)從0開始 strcpy(copy1,LRh); while(copy10!=vnk) /獲取當(dāng)前k值 k+; l=strlen(LRh)-4; top1=top1-l+1; top2=top2-l+1; y=atop1-1; p=goto1yk; atop1=p; btop2=copy10; z=p; printf("t"); printf("%dn",p)

23、; while(actionyj!="acc"); printf("accn");4上機(jī)調(diào)試41測試結(jié)果5.心得體會(huì)通過該課程設(shè)計(jì)，掌握了什么是編譯程序，編譯程序工作的基本過程及其各階段的基本任務(wù)，熟悉了編譯程序總流程框圖，了解了編譯程序的生成過程、構(gòu)造工具及其相關(guān)的技術(shù)對課本上的知識有了更深的理解，課本上的知識師機(jī)械的，表面的。通過把該算法的內(nèi)容，算法的執(zhí)行順序在計(jì)算機(jī)上實(shí)現(xiàn)，把原來以為很深?yuàn)W的書本知識變的更為簡單，對實(shí)驗(yàn)原理有更深的理解。 通過把該算法的內(nèi)容，算法的執(zhí)行順序在計(jì)算機(jī)上實(shí)現(xiàn)，知道和理解了該理論在計(jì)算機(jī)中是怎樣執(zhí)行的，對該理論在實(shí)踐中的應(yīng)用有深刻的理解。通過該課程設(shè)計(jì)，全面系統(tǒng)的理解了編譯原理程序構(gòu)造的一般原理和基本實(shí)現(xiàn)方法。把死板的課本知識變得生動(dòng)有趣，激發(fā)了學(xué)習(xí)的積極性。把學(xué)過的計(jì)算機(jī)編譯原理的知識強(qiáng)化，能夠把課堂上學(xué)的知識通過自己設(shè)計(jì)的程序表示出來，加深了對理論知識的理解。以前對與計(jì)算機(jī)操 在這次課程設(shè)計(jì)中，我就是按照實(shí)驗(yàn)指導(dǎo)的