DOWHILE循環(huán)語(yǔ)句的翻譯程序設(shè)計(jì)（簡(jiǎn)單優(yōu)先法、輸出四元式）.doc

武漢理工大學(xué)編譯原理課程設(shè)計(jì)說明書學(xué) 號(hào)： 0120910340521課 程 設(shè) 計(jì)題 目DO-WHILE循環(huán)語(yǔ)句的翻譯程序設(shè)計(jì)（簡(jiǎn)單優(yōu)先法、輸出四元式）學(xué) 院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專 業(yè)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)班 級(jí)計(jì)算機(jī)0905姓 名馮 強(qiáng)指導(dǎo)教師楊克儉2012年01月04日課程設(shè)計(jì)任務(wù)書學(xué)生姓名： 馮 強(qiáng) 專業(yè)班級(jí)： 計(jì)算機(jī)0905班 指導(dǎo)教師： 楊克儉 工作單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題目: DO-WHILE循環(huán)語(yǔ)句的翻譯程序設(shè)計(jì)（簡(jiǎn)單優(yōu)先法、輸出四元式）初始條件：理論：學(xué)完編譯課程，掌握一種計(jì)算機(jī)高級(jí)語(yǔ)言的使用。實(shí)踐：計(jì)算機(jī)實(shí)驗(yàn)室提供計(jì)算機(jī)及軟件環(huán)境。如果自己有計(jì)算機(jī)可以在其上進(jìn)行設(shè)計(jì)。要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）（1） 寫出符合給定的語(yǔ)法分析方法的文法及屬性文法。（2） 完成題目要求的中間代碼四元式的描述。（3） 寫出給定的語(yǔ)法分析方法的思想，完成語(yǔ)法分析和語(yǔ)義分析程序設(shè)計(jì)。（4） 編制好分析程序后，設(shè)計(jì)若干用例，上機(jī)測(cè)試并通過所設(shè)計(jì)的分析程序。（5） 設(shè)計(jì)報(bào)告格式按附件要求書寫。課程設(shè)計(jì)報(bào)告書正文的內(nèi)容應(yīng)包括：1 系統(tǒng)描述（問題域描述）；2 文法及屬性文法的描述；3 語(yǔ)法分析方法描述及語(yǔ)法分析表設(shè)計(jì)；4 按給定的題目給出中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計(jì)；5 編譯系統(tǒng)的概要設(shè)計(jì)；6 詳細(xì)的算法描述（流程圖或偽代碼）；7 軟件的測(cè)試方法和測(cè)試結(jié)果；8 研制報(bào)告（研制過程，本設(shè)計(jì)的評(píng)價(jià)、特點(diǎn)、不足、收獲與體會(huì)等）；9 參考文獻(xiàn)（按公開發(fā)表的規(guī)范書寫）。時(shí)間安排：設(shè)計(jì)安排一周：周1、周2：完成系統(tǒng)分析及設(shè)計(jì)。周3、周4：完成程序調(diào)試及測(cè)試。周5：撰寫課程設(shè)計(jì)報(bào)告。設(shè)計(jì)驗(yàn)收安排：設(shè)計(jì)周的星期五第1節(jié)課開始到實(shí)驗(yàn)室進(jìn)行上機(jī)驗(yàn)收。設(shè)計(jì)報(bào)告書收取時(shí)間：設(shè)計(jì)周的次周星期一上午10點(diǎn)。指導(dǎo)教師簽名： 2011年 11月 23日系主任（或責(zé)任教師）簽名： 2011年 11月 23日DO-WHILE語(yǔ)句的翻譯程序設(shè)計(jì)(簡(jiǎn)單優(yōu)先法,輸出四元式)1問題描述輸入一個(gè)DO-WHILE的語(yǔ)句,進(jìn)行詞法分析,詞法分析器利用超前搜索,狀態(tài)轉(zhuǎn)換等方法,將源程序轉(zhuǎn)化成為一個(gè)一個(gè)的單詞符號(hào)二元式,如果詞法分析無(wú)誤,則進(jìn)入語(yǔ)法分析部分,使用簡(jiǎn)單優(yōu)先法進(jìn)行文法分析,為每個(gè)終極符與非終極符之間定義優(yōu)先關(guān)系,利用優(yōu)先關(guān)系進(jìn)行移進(jìn)-規(guī)約,如果能規(guī)約到文法的開始符,則文法分析成功,輸出四元式.2文法及屬性文法的描述2.1文法描述G(s): S-do B while E,B-c:=a+1,E-ab2.2屬性文法描述G(s): S-do B while E, S.begin:=newlabel; B.next:=S.begin; E.true:=newlabel; E.false:= S.next; S.code:=gen(S.begin:) B.code E.code gen(E.true:) gen(gotoS.begin) B-c:=a+1 B.code:= c:=a+1 E-ab E.code=gen(ifabgoto E.true) Gen(goto E.false) E-true E.code:=gen(goto E.true) E-false E.code:=gen(goto E.false) 3語(yǔ)法分析方法及中間代碼形式的描述3.1語(yǔ)法分析方法描述3.1.1簡(jiǎn)單優(yōu)先法的定義一個(gè)文法G，若它不含e產(chǎn)生式，也不含任何右部相同的不同產(chǎn)生式，并且它的任何符號(hào)對(duì)(X,Y)，或者沒有關(guān)系，或者存在下述三種關(guān)系：=、之一，則稱該文法是一個(gè)簡(jiǎn)單優(yōu)先文法。 A)X=Y當(dāng)且僅當(dāng)G中含有形如PXY的產(chǎn)生式 B)XY當(dāng)且僅當(dāng)Y為G的終結(jié)符，G中含有形如PQR的產(chǎn)生式，其中Q，R為非終結(jié)符，且Q X，YFirst(R)D)對(duì)任何X，若文法開始符號(hào)SX，則#。3.1.2簡(jiǎn)單優(yōu)先法的基本思想根據(jù)優(yōu)先關(guān)系的定義，將簡(jiǎn)單優(yōu)先文法中各文法符號(hào)之間的這種關(guān)系用一個(gè)矩陣表示，稱作簡(jiǎn)單優(yōu)先矩陣。PDA讀入一個(gè)單詞后，比較棧頂符號(hào)和該單詞的優(yōu)先級(jí)，若棧頂符號(hào)優(yōu)先級(jí)低于該單詞，繼續(xù)讀入；若棧頂符號(hào)優(yōu)先級(jí)高于或等于讀入符號(hào)，則找句柄進(jìn)行歸約，找不到句柄就繼續(xù)讀入。直到最后棧內(nèi)只剩下開始符號(hào)，輸入串讀到“”為止。此時(shí)識(shí)別正確?？煞贮c(diǎn)描述如下:1、對(duì)句型中相鄰的文法符號(hào)規(guī)定優(yōu)先關(guān)系，以尋找句型中的句柄; 2、規(guī)定句柄內(nèi)各相鄰符號(hào)之間具有相同的優(yōu)先級(jí); 3、規(guī)定句柄兩端符號(hào)優(yōu)先級(jí)要比位于句柄之外而又和句柄相鄰的符號(hào)的優(yōu)先級(jí)高，以先歸約句柄; 4、對(duì)于文法中所有符號(hào)，只要它們可能在某個(gè)句型中相鄰，就要為它們規(guī)定相應(yīng)的優(yōu)先關(guān)系，若某兩個(gè)符號(hào)永遠(yuǎn)不可能相鄰，則它們之間就無(wú)關(guān)系.3.1.3簡(jiǎn)單優(yōu)先矩陣用于表示文法符號(hào)之間的簡(jiǎn)單優(yōu)先關(guān)系的矩陣。3.1.4簡(jiǎn)單優(yōu)先法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：技術(shù)簡(jiǎn)單缺點(diǎn)：適用范圍小，分析表尺寸太大。3.2中間代碼形式描述四元式是一種比較普遍采用的中間代碼形式。四元式的四個(gè)組成成分是：算符op，第一和第二運(yùn)算對(duì)象ARG1和ARG2及運(yùn)算結(jié)果RESULT。運(yùn)算對(duì)象和運(yùn)算結(jié)果有時(shí)指用戶自己定義的變量，有時(shí)指編譯程序引進(jìn)的臨時(shí)變量。例如:輸入字符串 do c=a+1 while ab 則輸出四元式 (1) (+,a,1,c) (2) (,a,b,t0) (3) (=,t0,true,1)(4) (-,-,-,-)4簡(jiǎn)要的分析與概要設(shè)計(jì)整個(gè)工程分為5個(gè)文件：Main.c - 程序的入口點(diǎn)，輸入待分析的字符串后先進(jìn)行詞法分析，然后調(diào)用兩個(gè)函數(shù)進(jìn)行語(yǔ)法分析及產(chǎn)生中間代碼。Global.h - 定義了一些全局變量及宏P(guān)arse.h - 語(yǔ)法分析器的主要算法Prece.h - 定義和實(shí)現(xiàn)了一些關(guān)于優(yōu)先級(jí)的操作Stack.h - 定義和實(shí)現(xiàn)了一個(gè)棧及其操作5詳細(xì)的算法描述5.1 Main的主要算法void InputString()/輸入字符串 int len = 0; printf(表達(dá)式文法為: ); printf(GRAMMAR); printf(n Please input any string to parse:n); scanf(%s, Buff);/輸入字符串 len = strlen(Buff);/取字符串長(zhǎng)度 Bufflen = #;Bufflen+1 = 0; void main()/主程序 printf( DO-WHILE循環(huán)語(yǔ)句的翻譯n ); printf(循環(huán)語(yǔ)句的格式為：DO WHILE n ); printf(翻譯的語(yǔ)句:do c=a+1 while abn );cifa();/調(diào)用詞法分析程序,對(duì)輸入字符串進(jìn)行詞法分析InputString();/再次輸入待分析字符串以便進(jìn)行語(yǔ)法分析 Parse();/調(diào)用語(yǔ)法分析,對(duì)輸入字符串進(jìn)行語(yǔ)法分析 getch();void cifa()/詞法分析 char str; printf( * 詞法分析器 *n); if (fp=fopen(lj.txt,r)=NULL)/如果文件無(wú)法打開 printf(源程序無(wú)法打開！n); else str =fgetc(fp); while (str!=EOF) if (isalpha(str)!=0)/判斷是否為字符 str=letterprocess(str);/調(diào)用字符處理 else if (isdigit(str)!=0)判斷是否為數(shù)字 str=numberprocess(str);/調(diào)用數(shù)字處理 else/其它 str=otherprocess(str); /調(diào)用其它處理 ; printf(詞法分析結(jié)束！n); 5.2 Global的主要算法typedef enum false=0, true bool;#define GRAMMAR G(s): S-do B while E,B-c:=a+1,E=ab/定義文法#define BUFFSIZE 100#define STACKSIZE 1005.3 Parse的主要算法void error()/規(guī)約不成功 printf(The input string doesnt match the grammar!);void succeed()/規(guī)約成功 printf(Succeed! The input match the grammar.);char Reduce(const char* c) /將終極符或非終極符規(guī)約為非終極符 if (*c = d) return S; else if (*c = c ) return B; else if (*c = a) return E; bool Parse()/簡(jiǎn)單優(yōu)先語(yǔ)法分析 char c; /保存棧頂元素char t; /保存最有可能彈出的終極符int ip = 0; /指向輸入緩沖區(qū)的指針 InitStack(); /初始化棧 while (true) TopValue(&c); if (c=S & Buffip=#)/如果棧頂為S或#,規(guī)約成功 succeed(); return true; else switch (GetPrecedence(&c, &Buffip) /如果優(yōu)先符是小于或等于則壓棧,否則進(jìn)棧 case LT: case EQ: Push(&Buffip+);/壓棧 PrintStack(); break; case GT: Pop(&c);/出棧 do t = c; Pop(&c); while (GetPrecedence(&c, &t) != LT); Push(&c); t = Reduce(&t); Push(&t); PrintStack(); break; default: error(); return false; 5.4 Prece的主要算法/定義優(yōu)先關(guān)系Prece PreTable1818 = /* S d o B w h i l e E a = + 1 b c # */* S */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* d */ NO, NO, EQ, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* o */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, LT, GT ,/* B */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* w */ NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* h */ NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* i */ NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* l */ NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* e */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, LT, NO, NO, NO, NO, NO, NO, GT ,/* E */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* a */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, EQ, NO, GT ,/* = */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, NO, GT ,/* + */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, GT ,/* 1 */ NO, NO, NO, NO, NO, GT, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, GT ,/* b */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, GT ,/* c */ NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, NO, EQ, NO, NO, NO, NO, NO, GT ,/* # */ LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, LT, EQ ,;int CharToIndex(const char* c)/定義矩陣switch (*c)case S: return 0;case d: return 1;case o: return 2;case B: return 3;case w: return 4;case h: return 5;case i: return 6;case l: return 7;case e: return 8;case E: return 9;case a: return 10;case =: return 11;case +: return 12; case 1: return 13; case : return 14;case b: return 15;case c: return 16;case #: return 17;default: return -1;Prece GetPrecedence(const char* c1, const char* c2) /取優(yōu)先關(guān)系 int i, j;i = CharToIndex(c1);/棧頂元素j = CharToIndex(c2);/輸入符號(hào)流第一個(gè)元素if (i!=-1 & j!=-1) return PreTableij; else return ND;/否則沒有優(yōu)先關(guān)系 5.5 Stack的主要算法void InitStack()/初始化符號(hào)棧 char c = #;StackTop = 0;Push(&c); bool Push(const char* c)/壓棧 if (StackTop = 0) *c = TheStack-StackTop; return true; else return false; bool TopValue(char* c)/取棧頂元素值 if (StackTop 0)/* not null */ *c = TheStackStackTop-1;return true; else return false; void PrintStack()/打印棧的元素 int i;for (i=0; iStackTop; i+) printf(%c, TheStacki); printf(n);6軟件的測(cè)試方法和測(cè)試結(jié)果6.1測(cè)試方法在visual c+ 6.0 下調(diào)試并通過.6.2測(cè)試結(jié)果7設(shè)計(jì)的特點(diǎn),不足,收獲與體會(huì)這次編譯原理課程設(shè)計(jì)的題目是用簡(jiǎn)單優(yōu)先分析法進(jìn)行DO-WHILE循環(huán)語(yǔ)句的語(yǔ)法分析,并輸出四元式.設(shè)計(jì)