編譯原理課設(shè).doc

編譯技術(shù)課程設(shè)計(jì)班 級(jí) 學(xué) 號(hào) 姓 名 指導(dǎo)老師 2015年 6月目錄一、目的2二、題目2三、要求21.詞法分析22.語(yǔ)法分析23.代碼生成24.錯(cuò)誤處理2四、實(shí)驗(yàn)環(huán)境31.開(kāi)發(fā)環(huán)境:32.程序語(yǔ)言:3五、系統(tǒng)實(shí)現(xiàn)31.詞法分析32.語(yǔ)法分析43.中間代碼64.錯(cuò)誤處理7六、程序運(yùn)行結(jié)果81.連乘82.連加93.加乘混合94.帶括號(hào)105.常數(shù)106.錯(cuò)誤的算術(shù)表達(dá)式11七、總結(jié)12一、目的是理論與實(shí)踐并重的課程，而其課程設(shè)計(jì)要綜合運(yùn)用一、二年級(jí)所學(xué)的多門(mén)課程的內(nèi)容，用來(lái)完成一個(gè)小型編譯程序。從而鞏固和加強(qiáng)對(duì)詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼生成和報(bào)錯(cuò)處理等理論的認(rèn)識(shí)和理解；培養(yǎng)學(xué)生對(duì)完整系統(tǒng)的獨(dú)立分析和設(shè)計(jì)的能力，進(jìn)一步培養(yǎng)學(xué)生的獨(dú)立編程能力。二、題目題目1 表達(dá)式的小型編譯器三、要求1.詞法分析產(chǎn)生語(yǔ)言的單詞序列 2.語(yǔ)法分析能識(shí)別由加+ 乘* 括號(hào)（）操作數(shù)（變量或常數(shù)）所組成的算術(shù)表達(dá)式，其文法如下：EE+T|TTT*F|FF(E)|i 使用的分析方法可以是：遞歸下降分析法或LR分析法。 3.代碼生成 產(chǎn)生上述算術(shù)表達(dá)式的中間代碼4.錯(cuò)誤處理給出錯(cuò)誤信息輸入：算術(shù)表達(dá)式輸出：符號(hào)表，常數(shù)表。 歸下降分析法：遞歸調(diào)用過(guò)程/ LR分析法：語(yǔ)義棧和符號(hào)棧四元式序列四、實(shí)驗(yàn)環(huán)境1.開(kāi)發(fā)環(huán)境: Visual Studio 20132.程序語(yǔ)言: C+五、系統(tǒng)實(shí)現(xiàn)1.詞法分析（1）單詞符號(hào)表（2）狀態(tài)轉(zhuǎn)換圖 （3）數(shù)據(jù)結(jié)構(gòu) （4）函數(shù)說(shuō)明void getonechar() /*從輸入的算數(shù)表達(dá)式中讀取一個(gè)字符*/void concatenation()/*將token中的字符串與character中的字符并作為token中新的字符串*/bool letter() /*判斷character中的字符是否為字母的布爾函數(shù),是則返回true,否側(cè)返回false*/bool digit()/*判斷character中的字符是否為數(shù)字的布爾函數(shù),是則返回true,否側(cè)返回false */void retract()/*掃描指針回退一個(gè)字符,同時(shí)將character置為空白*/int reserve() /*將token中的字符查找保留字?jǐn)?shù)組,若是保留字就返回它的種別編碼,否則返回0*/void buildlist1()/*將標(biāo)識(shí)符登錄到符號(hào)表中(value2)*/void buildlist2()/*將常數(shù)登錄到常數(shù)表中(value1)*/void resolve()/*詞法分析的主要函數(shù),每次識(shí)別一個(gè)單詞,將種別編碼放入cf中,填入對(duì)應(yīng)的value1和value*/void cffx()/*詞法分析,讀入輸入的算數(shù)表達(dá)式,循環(huán)執(zhí)行resolve(),直到所有單詞識(shí)別完畢*/2.語(yǔ)法分析（1）分析方法說(shuō)明 本程序采用LR分析法,存在4種動(dòng)作:移進(jìn):使(s,a)的下一個(gè)狀態(tài)s= ACTIONs,a和輸入符號(hào)a進(jìn)棧,下一輸入符號(hào)變成現(xiàn)行輸入符號(hào).規(guī)約: 指用某一產(chǎn)生式A進(jìn)行規(guī)約,假若的長(zhǎng)度為,則規(guī)約動(dòng)作是去掉棧頂?shù)膫€(gè)棧,即是狀態(tài)Sm-變成棧頂狀態(tài),然后使(Sm-,A)的下一狀態(tài)s=GOTOSm-,A和文法符號(hào)A進(jìn)棧.規(guī)約的動(dòng)作不改變現(xiàn)行輸入符號(hào),執(zhí)行規(guī)約的動(dòng)作意味著呈現(xiàn)于棧頂?shù)姆?hào)串Xm-+1Xm是一個(gè)相對(duì)于A的句柄.接受: 宣布分析成功,停止分析器工作.報(bào)錯(cuò): 報(bào)告發(fā)現(xiàn)源程序含有錯(cuò)誤,調(diào)用錯(cuò)誤處理程序.（2）文法（3）數(shù)據(jù)結(jié)構(gòu)#include /*引入c+標(biāo)準(zhǔn)庫(kù)*/stack status;/*狀態(tài)棧*/stack sign; /*符號(hào)棧*/（4）函數(shù)說(shuō)明Void initYffx() /*語(yǔ)法分析初始化,狀態(tài)棧放0,符號(hào)棧放#,語(yǔ)義棧放_(tái)*/Void showLR()/*遍歷狀態(tài)棧,符號(hào)棧,語(yǔ)義棧,并顯示出來(lái)*/Void yffxSolve() /*查action二維數(shù)組,進(jìn)行移進(jìn),規(guī)約處理*/Void yyfx()/*循環(huán)執(zhí)行yffxSolve(),直到分析成功或出現(xiàn)錯(cuò)誤*/Void showBlm()/*顯示變量名表*/Void showCsb()/*顯示常數(shù)表*/3.中間代碼（1）屬性文法 移進(jìn)時(shí): 如果輸入的是終結(jié)符,語(yǔ)義棧就移進(jìn)”_”,如果是非終結(jié)符,則語(yǔ)義棧移進(jìn)對(duì)應(yīng)的常數(shù)或變量名.規(guī)約時(shí): 如果規(guī)約對(duì)應(yīng)的文法是(4)Ei時(shí)語(yǔ)義棧不變,對(duì)應(yīng)其他文法時(shí),先pop出棧頂3個(gè)元素,再如果是(3)E(E)文法時(shí),語(yǔ)義棧push剛才出棧的第二個(gè)元素,如果是(1)EE+E文法時(shí),判斷剛才出棧的第一個(gè)和第三個(gè)元素是否是常數(shù),是則push兩個(gè)常數(shù)的和,否則push臨時(shí)變量Tn;如果是(1)EE*E文法時(shí),判斷剛才出棧的第一個(gè)和第三個(gè)元素是否是常數(shù),是則push兩個(gè)常數(shù)的積,否則push臨時(shí)變量Tn;（2）數(shù)據(jù)結(jié)構(gòu)#include /*引入c+標(biāo)準(zhǔn)庫(kù)*/stack yuyi;/*語(yǔ)義棧*/string v1,v2,v3,v4;/*分別表示四元式的參數(shù)1,參數(shù)2,參數(shù)3,參數(shù)4*/（3）函數(shù)說(shuō)明語(yǔ)義棧和四元式的產(chǎn)生是在語(yǔ)法分析一起的,在yffxSolve().void yffxSolve()stack tempYuyiPush;showLR();int i = -1;if (cfm = 6 | cfm = 7)i = 0;if (cfm = 8)i = 1;if (cfm = 10)i = 2;if (cfm = 14)i = 3;if (cfm = 15)i = 4;if (cfm = 16)i = 5;if (i = -1) cout 輸入了錯(cuò)誤的種別編碼 0)if (actionstatus.top()i 100)if (actionstatus.top()i = 1000)cout acc endl;system(pause);exit(0);/*規(guī)約*/cout gy endl;int s = actionstatus.top()i - 100;for (int j = 0; j gyLens - 1; j+)if (s != 4)tempYuyiPush.push(yuyi.top();yuyi.pop();status.pop();sign.pop();status.push(actionstatus.top()6);sign.push(E);if (s = 4)else v2 = tempYuyiPush.top();tempYuyiPush.pop();string v2plus5 = tempYuyiPush.top();tempYuyiPush.pop();v3 = tempYuyiPush.top();tempYuyiPush.pop();if (isdigit(v2) & isdigit(v3)if (s = 1)v4 = intToStr(strToInt(v2) + strToInt(v3);if (s = 2)v4 = intToStr(strToInt(v2) * strToInt(v3);yuyi.push(v4);else if (v2 = _ & isdigit(v2plus5) & v2 = _)v4 = v2plus5;yuyi.push(v4);else string tempNum = intToStr(yuyiNum);string tempS = T + tempNum;yuyiNum+;yuyi.push(tempS);v4 = tempS;if (s = 1)v1 = +;if (s = 2)v1 = *;else/*移近*/cout yj endl;status.push(actionstatus.top()i);sign.push(inputSigni);if (cfm = 6 | cfm = 7)if (cfm = 6)yuyi.push(value2m);else string tempVal = intToStr(value1m);yuyi.push(tempVal);else yuyi.push(_);m+;elseint err = actionstatus.top()i;cout 第 m 個(gè)單詞后 showErrerr + 12endl;system(pause);exit(0);lrNum+;（4）流程圖4.錯(cuò)誤處理（1）數(shù)據(jù)結(jié)構(gòu)string showErr12 = FOUND ERROR: +前缺少變量或常量 ,/*0,e1*/ FOUND ERROR: *前缺少變量或常量 ,/*1,e2*/ FOUND ERROR: )前缺少對(duì)應(yīng)( ,/*2,e3*/ FOUND ERROR: 連續(xù)的變量或常量,缺少+/* ,/*3,e4*/ FOUND ERROR: (前缺少+/* ,/*4,e5*/ FOUND ERROR: (后缺少常量或變量 ,/*5,e6*/ FOUND ERROR: ()內(nèi)無(wú)表達(dá)式 ,/*6,e7*/ FOUND ERROR: +后缺少變量或常量 ,/*7,e8*/ FOUND ERROR: *后缺少變量或常量 ,/*8,e9*/ FOUND ERROR: 算數(shù)表達(dá)式為空 ,/*9,e10*/ FOUND ERROR: 缺少對(duì)應(yīng)) ,/*10,e11*/ FOUND ERROR: 語(yǔ)法分析錯(cuò)誤 /*11,e12*/; （2）函數(shù)說(shuō)明yffxSolve()中,查action數(shù)組時(shí),遇到e時(shí)輸出錯(cuò)誤位置和錯(cuò)誤信息,跳過(guò)此單詞,繼續(xù)進(jìn)行語(yǔ)法分析.六、程序運(yùn)行結(jié)果1.連乘2.連加3.加乘混合4.帶括號(hào)5.常數(shù)6.錯(cuò)誤的算術(shù)表達(dá)式1)缺少操作符2)缺少操作數(shù)3)不完整的()七、總結(jié)通過(guò)課程設(shè)計(jì)更加深入地理解了LR分析法對(duì)算數(shù)表達(dá)式處理的過(guò)程,熟悉了編譯的四個(gè)階段:詞法分析,語(yǔ)法分析,語(yǔ)義分析和中間代碼,以及錯(cuò)誤處理.在運(yùn)用c+編寫(xiě)程序時(shí),也熟悉了c+標(biāo)準(zhǔn)庫(kù)中stack的使用.程序是一段一段寫(xiě)下來(lái)的,整個(gè)程序沒(méi)有整體的規(guī)劃,定義的變量又多又亂,造成許多變量需要不斷的修改,而且不利于程序的理解.在對(duì)棧處理的時(shí)候,發(fā)現(xiàn)標(biāo)準(zhǔn)庫(kù)定義的stack的函數(shù)太少,只有pop,push,empty,top,size,沒(méi)有遍歷,需要自己寫(xiě).程序需要不斷修改才能完成.檢查時(shí)發(fā)現(xiàn):顯示錯(cuò)誤處理時(shí)沒(méi)有給出錯(cuò)誤位置;當(dāng)出現(xiàn)多個(gè)錯(cuò)誤時(shí),只能顯示第一個(gè)錯(cuò)誤.完整代碼:#include #include #include #include #include using namespace std;string str;/*源程序*/char character;/*源程序當(dāng)前字符*/int p = -1;/*源程序游標(biāo)*/string token = ;string blz5 = while, if, else, switch, case ;int c; /*標(biāo)示符種類編碼*/int length;/*輸入源程序的長(zhǎng)度*/int statue = 0;/*判斷詞法分析完成*/int cf50;/*詞法分析后的種類編碼數(shù)組*/int value150;/*cf對(duì)應(yīng)常數(shù)*/string value250;/*cf對(duì)應(yīng)變量名*/int q = 0;/*cf創(chuàng)建的游標(biāo)*/int m = 0;/*cf語(yǔ)法分析的游標(biāo)*/string blmb50;/*變量名表*/int a = 0;/*變量名表的游標(biāo)*/string csb50;/*常數(shù)表*/int b = 0;/*常數(shù)表的游標(biāo)*/static int action107 = 3, -12, -11, 2, -10, -3, 1 , -9, 4, 5, -8, -10, 1000, -1 , 3, -7, -7, 2, -6, -2, 6 , -9, 104, 104, -8, 104, 104, -1 , 3, -5, -5, 2, -10, -5, 7 , 3, -4, -4, 2, -10, -4, 8 , -9, 4, 5, -9, 9, -2, -1 , -9, 101, 5, -9, 101, 101, -1 , -9, 102, 102, -9, 102, 102, -1 , -9, 103, 103, -9, 103, 103, -1 ;stack status;stack sign;stack yuyi;int lrNum = 0;/*分析表步驟號(hào)*/char inputSign7 = i, +, *, (, ), #, E ;/*進(jìn)棧符號(hào)*/int gyLen4 = 3, 3, 3, 1 ;int yuyiNum = 1;/*語(yǔ)義臨時(shí)變量序號(hào)*/string v1, v2, v3, v4;string showErr12 = 發(fā)現(xiàn)錯(cuò)誤: +前缺少變量或常量 ,/*0,e12*/ 發(fā)現(xiàn)錯(cuò)誤: *前缺少變量或常量 ,/*1,e11*/ 發(fā)現(xiàn)錯(cuò)誤: )前缺少對(duì)應(yīng)( ,/*2,e10*/ 發(fā)現(xiàn)錯(cuò)誤: 連續(xù)的變量或常量,缺少+/* ,/*3,e9*/ 發(fā)現(xiàn)錯(cuò)誤: (前缺少+/* ,/*4,e8*/ 發(fā)現(xiàn)錯(cuò)誤: (后缺少常量或變量 ,/*5,e7*/ 發(fā)現(xiàn)錯(cuò)誤: ()內(nèi)無(wú)表達(dá)式 ,/*6,e6*/ 發(fā)現(xiàn)錯(cuò)誤: +后缺少變量或常量 ,/*7,e5*/ 發(fā)現(xiàn)錯(cuò)誤: *后缺少變量或常量 ,/*8,e4*/ 發(fā)現(xiàn)錯(cuò)誤: 算數(shù)表達(dá)式為空 ,/*9,e3*/ 發(fā)現(xiàn)錯(cuò)誤: 缺少對(duì)應(yīng)) ,/*10,e2*/ 發(fā)現(xiàn)錯(cuò)誤: 語(yǔ)法分析錯(cuò)誤 /*11,e1*/;void getonechar()/*if (p = length)system(pause);exit(0);*/p+;while (strp = & strp + 1 = )p+;character = (char)strp;void concatenation()token += character;bool letter()if (character = a & character = A & character = 0 & character = 9)return true;elsereturn false;int reserve()for (int i = 0; i 5; i+)if (token = blzi)return i + 1;return 0;void retract()p-;/*變量名表*/void buildlist1(string token)int i;for (i = 0; i a; i+)if (token = blmbi)break;if (i = a)blmba = token;a+;value2q = token;/*常數(shù)表*/void buildlist2(string token)int i;for (i = 0; i b; i+)if (token = csbi)break;if (i = b)csbb = token;b+;stringstream ss;ss num;value1q = num;void resolve()token = ;getonechar();switch (character)case a:case b:case c:case d:case e:case f:case g:case h:case i:case j:case k:case l:case m:case n:case o:case p:case q:case r:case s:case t:case u:case v:case w:case x:case y:case z:while (letter() | digit()concatenation();getonechar();retract();c = reserve();if (c = 0)buildlist1(token);cout (6, token ) endl;cfq = 6;q+;elsecout ( c , blzc - 1 ) endl;cfq = c;q+;break;case 0:case 1:case 2:case 3:case 4:case 5:case 6:case 7:case 8:case 9:while (digit()concatenation();getonechar();retract();buildlist2(token);cfq = 7;q+;cout (7, token ) endl;break;case +:cfq = 8;q+;cout (8, +) endl;break;case -:cfq = 9;q+;cout (9, -) endl;break;case (:cfq = 14;q+;cout (14, () endl;break;case ):cfq = 15;q+;cout (15, ) endl;break;case *:cfq = 10;q+;cout (10, *) endl;break;case :getonechar();if (character = =)cfq = 11;q+;cout (11, LE) endl;elseretract();cfq = 11;q+;cout (11, LT) endl;break;case =:getonechar();if (character = =)cfq = 11;q+;cout (11, EQ) endl;elseretract();cfq = 12;q+;cout (12, =) endl;break;case ;:cfq = 12;q+;cout (13, ;) endl;break;case #:cfq = 16;statue = 1;break;case 0:statue = 1;break;case :break;default:cfq = 16;q+;cout 詞法分析 FOUND ERROR endl;break;void cffx()cout 請(qǐng)輸入源程序: endl;statue = 0;getline(cin, str);cout *詞法分析結(jié)果* endl;while (true)if (statue = 1)break;resolve();void initYffx()sign.push(#);status.push(0);yuyi.push(_);void showLR()/*棧遍歷 先pop再push*/string tempSign;string tempStatus;string tempYuyi;string tempFour;stack tempSi;stack tempSt;stack tempYu;int tempLen1 = sign.size();int tempLen2 = status.size();int tempLen3 = yuyi.size();for (int i = 0; i tempLen1; i+)tempSign = tempSign + sign.top();tempSi.push(sign.top();sign.pop();for (int i = 0; i tempLen2; i+)tempStatus = tempStatus + (char)(status.top()+48);tempSt.push(status.top();status.pop();for (int i = 0; i tempLen3; i+)tempYuyi = tempYuyi + yuyi.top();tempYu.push(yuyi.top();yuyi.pop();if (v1 = )tempFour = ;else tempFour = ( + v1 + , + v2 + , + v3 + , + v4 + );cout setw(2) lrNum setw(15) tempSign setw(15) tempStatus setw(15) tempYuyi setw(15) tempFour endl;for (int i = 0; i tempLen1; i+)sign.push(tempSi.top();tempSi.pop();for (int i = 0; i tempLen2; i+)status.push(tempSt.top();tempSt.pop();for (int i = 0; i tempLen3; i+)yuyi.push(tempYu.top();tempYu.pop();v1 = ;bool isdigit(string str)for (int i = 0; i 9) | (str.at(i) 0)return false;return true;int strToInt(string str)stringstream s;s tempInt;return tempInt;string intToStr(int inter)stringstream s;s tempStr;return tempStr;void yffxSolve()stack tempYuyiPush;showLR();int i = -1;if (cfm = 6 | cfm = 7)i = 0;if (cfm = 8)i = 1;if (cfm = 10)i = 2;if (cfm = 14)i = 3;if (cfm = 15)i = 4;if (cfm = 16)i = 5;if (i = -1) cout 輸入了錯(cuò)誤的種別編碼 0)if (actionstatus.top()i 100)if (actionstatus.top()i = 1000)cout acc endl;system(pause);exit(0);/*規(guī)約*/cout gy endl;int s = actionstatus.top()i - 100;for (int j = 0; j gyLens - 1; j+)if (s != 4)tempYuyiPush.push(yuyi.top();yuyi.pop();status.pop();sign.pop();status.push(actionstatus.top()6);sign.push(E);if (s = 4)else v2 = tempYuyiPush.top();tempYuyiPush.pop();string v2plus5 = tempYuyiPush.top();tempYuyiPush.pop