編譯原理課程設(shè)計(jì)——算術(shù)表達(dá)式、for、while語句轉(zhuǎn)換為四元式資料

1、計(jì)算機(jī)與信息學(xué)院操作系統(tǒng)與編譯原理聯(lián)合課程設(shè)計(jì)報告專題：編譯原理部分 學(xué)生姓名： 學(xué) 號：專業(yè)班級： 指導(dǎo)教師：2014 年 7 月一、設(shè)計(jì)目標(biāo)設(shè)計(jì)一個語法制導(dǎo)翻譯器，將算術(shù)表達(dá)式、for語句、while語句翻譯成四元式。要求先確定一個定義算術(shù)表達(dá)式、for語句、while語句的文法，為其設(shè)計(jì)一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實(shí)現(xiàn)翻譯程序。對用戶輸入的任意一個正確的表達(dá)式，程序?qū)⑵滢D(zhuǎn)換成四元式輸出。二、設(shè)計(jì)思路開發(fā)平臺：Visual C+ MFC解決這個問題的方案分為以下幾個步驟：1.將算數(shù)表達(dá)式、for語句、while語句轉(zhuǎn)換為四元式的第一步為

2、對讀入的表達(dá)式進(jìn)行處理，即刪除不必要的空格、回車、換行等，保證之后的步驟能夠順利進(jìn)行。2.分析算術(shù)表達(dá)式、for語句、while語句的文法。3.通過詞法分析判斷語句中的每個字符的類型，如：數(shù)字、字母、符號等。4.建立每種文法的LR(0)分析表，通過每個文法的LR(0)分析表對相應(yīng)的表達(dá)式進(jìn)行語法分析。5.在語法分析正確的情況下，通過語法分析的中間過程的符號棧輸出四元式，四元式的形式為：（op arg1 arg2 result）。（一）算術(shù)表達(dá)式轉(zhuǎn)換為四元式將算術(shù)表達(dá)式轉(zhuǎn)換為四元式首先考慮了括號的問題，對于不同的算術(shù)表達(dá)式第一步進(jìn)行詞法分析，即確定各種符號的位置。而括號中的式子是優(yōu)先級最高的，應(yīng)

3、該最先進(jìn)行處理。我使用了一個數(shù)組記錄算術(shù)表達(dá)式中括號的位置，并且定義了first_cc和first_jj函數(shù)對括號內(nèi)的乘除法和加減法分別進(jìn)行處理。后將括號內(nèi)的式子以四元式的形式輸出。通過以上轉(zhuǎn)換，已將原算術(shù)表達(dá)式中的括號中的內(nèi)容使用大寫字母A、B等代替（其中定義聲明了change函數(shù)，用來將括號部分替換為大寫字母）。新的式子中，只含有加減乘除以及賦值這四種運(yùn)算，后根據(jù)優(yōu)先級的不同，逐步生成四元式。其算法流程圖如右圖所示。（二）for語句轉(zhuǎn)換為四元式1.For語句的文法如下：S- f ( E ; F ; G ) H ;S- f ( E ; X ; Y ) H ;E- id = cF- id id

4、 + +X- id cY- id H- id1 = id2 + id3H- id1 = id2 + cH- id1 = c+ id2 其中c 表示常數(shù)const，f表示關(guān)鍵字for， id表示一般標(biāo)識符。for循環(huán)體內(nèi)部的表達(dá)式一般為算術(shù)表達(dá)式，而算術(shù)表達(dá)式轉(zhuǎn)換為四元式的方法在第一部分已給出，此處H只考慮比較簡單的情況。2.for語句的LR(0)分析表如下：3. 基本算法流程：本算法定義聲明了兩個結(jié)構(gòu)體：一個是Node結(jié)構(gòu)體，其中char型的type中存儲當(dāng)前符號的類型，CString型的sValue中存儲的為當(dāng)前符號，int型的eValue只有在符號類型為數(shù)字的情況下才進(jìn)行存儲，存儲數(shù)字的大

5、??；另一個為stack結(jié)構(gòu)體，這個結(jié)構(gòu)體是實(shí)現(xiàn)語法分析中的符號棧和狀態(tài)棧使用的，并未這兩個棧分別定義了各自的pop函數(shù)和push函數(shù)。除此之外，本算法中的LR(0)分析表通過二維數(shù)組存儲。其中分為action表和goto表。action表中的狀態(tài)轉(zhuǎn)換符號，用2-44表示，規(guī)約的符號，用101-110表示。具體的算法流程圖如下：（三）while語句轉(zhuǎn)換為四元式1.while語句的文法如下：(1)S-while(B)E(2)E-AE(3)E-A(4)A-iPA (5)A-i(6)B-iTi(7)B-i其中while、( 、) 、 、 、P、T 、 ； 和i均為終結(jié)符，而S、A、B、E這些大寫字母均

6、為非終結(jié)符。T表示比較運(yùn)算符，P表示算術(shù)運(yùn)算符，i表示合法標(biāo)識符。2.While語句的LR(0)分析表如下：3.基本算法流程：本算法的基本思想與for語句轉(zhuǎn)換成四元式的思想比較相似，都是對讀入的語句進(jìn)行詞法分析，后再通過LR(0)分析表對語句進(jìn)行語法分析，并同時輸出四元式。與for語句轉(zhuǎn)換成四元式不同的是，while語句轉(zhuǎn)換為四元式在結(jié)構(gòu)體定義等方面做了改進(jìn)。首先是LR(0)分析表的存儲方式進(jìn)行了改進(jìn)，本算法中為LR(0)分析表定義了一個table的結(jié)構(gòu)體，將action和goto兩個部分全部存入table的結(jié)構(gòu)體中，是查表的時候更加方便。除此之外，還定義了obj結(jié)構(gòu)體，此結(jié)構(gòu)體主要是為了存儲

7、所要輸出的四元式，定義了此結(jié)構(gòu)體之后，程序的調(diào)理變得更為清晰了。本算法中符號棧以及狀態(tài)棧的部分主要調(diào)用了c+中原有的stack結(jié)構(gòu)體，使用其本身定義的pop函數(shù)以及push函數(shù)，簡化的代碼。以下為算法的流程圖：（四）輸入、輸出以及界面設(shè)計(jì)1.輸入：本程序的輸入均為語句或表達(dá)式，若每次測試程序均輸入表達(dá)式，則會輸入大量式子，浪費(fèi)時間。所以本程序采用文件讀入的形式，只需要在指定位置輸入文件名即可。2.輸出：本程序輸出的四元式全部在MFC界面的文本框中顯示?？梢詮?fù)制，方便之后的使用。3.界面設(shè)計(jì)：本程序?yàn)榱朔奖闶褂靡约敖缑婷烙^，使用了MFC中的TabControl控件，界面設(shè)計(jì)如下：圖中當(dāng)前標(biāo)簽為“

8、while語句”，顯示的界面為“while語句轉(zhuǎn)換為四元式”。通過若點(diǎn)擊其他標(biāo)簽按鈕，界面也會切換到相應(yīng)的界面。每個界面都是一個對話框，如下圖所示：（1）作為主要的文件，去調(diào)用其他的對話框。首先對每一個對話框（IDD_DIALOG1-3）進(jìn)行設(shè)置，樣式：下層；邊框：無。如下圖所示：（2）后在CompilerDesignDlg.h文件中添加每個對話框的頭文件，以及申明每個對話框，代碼如下：#include Dlg1.h#include Dlg2.h#include Dlg3.hCDlg1 page1;CDlg2 page2;CDlg3 page3;（3）在初始化函數(shù)CCompilerDesign

9、Dlg:OnInitDialog()中編寫相關(guān)代碼：m_tabCtrl.InsertItem(0, 算術(shù)表達(dá)式);m_tabCtrl.InsertItem(1, for語句);m_tabCtrl.InsertItem(2, while語句);page1.Create(IDD_DIALOG1, &m_tabCtrl);page2.Create(IDD_DIALOG2, &m_tabCtrl);reate(IDD_DIALOG3, &m_tabCtrl);CRect rc;m_tabCtrl.GetClientRect(&rc);rc.top += 22;rc.bottom -= 3;rc.lef

10、t += 2;rc.right -= 3;/設(shè)置子對話框尺寸并移動到指定位置page1.MoveWindow(&rc);page2.MoveWindow(&rc);page3.MoveWindow(&rc);page1.ShowWindow(true);page2.ShowWindow(false);Window(false);m_tabCtrl.SetCurSel(0);（4）填寫按鈕響應(yīng)函數(shù)，即實(shí)現(xiàn)點(diǎn)擊按鈕切換到相應(yīng)界面的功能，雙擊Tab控件，創(chuàng)建函數(shù)，函數(shù)內(nèi)代碼實(shí)現(xiàn)如下：void CCompilerDesignDlg:OnSelchangeTab1(NMHDR* pNMHDR, LRES

11、ULT* pResult) int CurSel = m_tabCtrl.GetCurSel();switch (CurSel)case 0:page1.ShowWindow(true);page2.ShowWindow(false);page3.ShowWindow(false);break;case 1:page1.ShowWindow(false);page2.ShowWindow(true);page3.ShowWindow(false);break;case 2:page1.ShowWindow(false);page2.ShowWindow(false);page3.ShowWin

12、dow(true);break;*pResult = 0;三、核心代碼（一）算術(shù)表達(dá)式轉(zhuǎn)化為四元式1.first_cc函數(shù)：對括號中的乘除法進(jìn)行處理。void CDlg1:first_cc(int i, int m)i+;for (; i = m - 1; i+)/處理乘除運(yùn)算if (stri = * | stri = /)CString str00;CString strget;GetDlgItemText(IDC_OUT, strget);CString str01 = stri;CString str02 = stri - 1;CString str03 = stri + 1;CStri

13、ng str04 = JG;str00 = str0 + str01 + str1 + str02 + str1 + str03 + str1 + str04 + str2;SetDlgItemText(IDC_OUT, strget + str00);change(i - 1);stri - 1 = stri = stri + 1 = JG;sum-;JG = (char)(int)JG+;2.first_jj函數(shù)：對括號內(nèi)的加減法進(jìn)行處理。void CDlg1:first_jj(int j, int m)j+;for (; j = m - 1; j+)/處理加減運(yùn)算if (strj = +

14、 | strj = -)CString str00;CString strget;GetDlgItemText(IDC_OUT, strget); CString str01 = strj;CString str02 = strj - 1;CString str03 = strj + 1;CString str04 = JG;str00 = str0 + str01 + str1 + str02 + str1 + str03 + str1 + str04 + str2;SetDlgItemText(IDC_OUT, strget + str00);change(j - 1);strj - 1

15、= strj = strj + 1 = JG;sum-;JG = (char)(int)JG+;3.scan函數(shù)：用于從文件中讀入表達(dá)式，并處理空格、回車、換行等。并對表達(dá)式中的括號進(jìn)行處理。void CDlg1:scan(FILE *fin)int pMAX;char ch = a;int c = -1, q = 0;while (ch != EOF)ch = getc(fin);while (ch = | ch = n | ch = t)ch = getc(fin);/消除空格和換行符strm+ = ch;if (ch = = | ch = + | ch = - | ch = * | ch

16、 = /) /統(tǒng)計(jì)含有以上字符的符號sum+;else if (ch = ()p+c = m - 1;else if (ch = )q = m - 1;first_cc(pc, q);/從左括號處理到又括號first_jj(pc, q);JG = (char)(int)JG-;strpc = strm - 1 = JG;c-;JG = (char)(int)JG+;4.tans_simple函數(shù)：用于處理經(jīng)過scan函數(shù)處理后的式子，根據(jù)其優(yōu)先級的不同分別處理，并輸出四元式。void CDlg1:trans_simple()for (int i = 0; i = m - 1; i+)/處理乘除

17、運(yùn)算if (stri = * | stri = /)CString str00;CString strget;GetDlgItemText(IDC_OUT, strget); CString str01 = stri;CString str02 = stri - 1;CString str03 = stri + 1;CString str04 = JG;str00 = str0 + str01 + str1 + str02 + str1 + str03 + str1 + str04 + str2;SetDlgItemText(IDC_OUT, strget + str00);change(i

18、- 1);stri - 1 = stri = stri + 1 = JG;sum-;JG = (char)(int)JG+;for (int j = 0; j = m - 1; j+)/處理加減運(yùn)算if (strj = + | strj = -)CString str00;CString strget;GetDlgItemText(IDC_OUT, strget); CString str01 = strj;CString str02 = strj - 1;CString str03 = strj + 1;CString str04 = JG;str00 = str0 + str01 + st

19、r1 + str02 + str1 + str03 + str1 + str04 + str2;SetDlgItemText(IDC_OUT, strget + str00);change(j - 1);strj - 1 = strj = strj + 1 = JG;sum-;JG = (char)(int)JG+;for (int k = 0; k in_c; zf=in_c; SetDlgItemText(IDC_DISPLAY,zf);getSym(zf, i);r = nodeSize;CString str_cf;CString str_c;CString str_i;int cou

20、nt=0;for (i = 0; ir; i+)sti = nodei.type;if(sti=f)GetDlgItemText(IDC_CF,str_cf);CString temp_str3=關(guān)鍵字：forrn;SetDlgItemText(IDC_CF,str_cf+temp_str3);else if (sti=i)CString temp_str3=nodei.sValue;str_i=str_i+temp_str3+ ;else if(sti=c)CString temp_str3=nodei.sValue;str_c=str_c+temp_str3+ ;numbercount+=

21、nodei.sValue;GetDlgItemText(IDC_CF,str_cf);SetDlgItemText(IDC_CF,str_cf+符號：+str_i+rn+常數(shù)：+str_c+rn);for (i = 0; i0 & action(q, 14, y)100 & action(q, 14, y) = 110)CString strget;GetDlgItemText(IDC_YF,strget);SetDlgItemText(IDC_YF,strget+進(jìn)行規(guī)約rn);switch (zh)case 101: for (i = 0; i12; i+)pop(s, &y); pop2

22、(t, &x);push(s, S);pop2(t, &e);push2(t, e);go(e, 7, S); /查詢GOTO表push2(t, sh); /替換后的數(shù)字index-;break;case 102:for (i = 0; i12; i+)pop(s, &y); pop2(t, &x);push(s, S);pop2(t, &e);push2(t, e);go(e, 7, S);push2(t, sh);index-;break;case 103:char a3; h = h + 1;for (i = 0; i3; i+)ai = pop(s, &y);pop2(t, &x);p

23、ush(s, E);pop2(t, &e);push2(t, e);go(e, 7, E);push2(t, sh); CString str00; CString strget; GetDlgItemText(IDC_OUT, strget); CString str01 = a1; CString str02 = a0; CString str03 = a2; str00 = str0 + str01 + str1 + number0 + str1 + str1 + str1 + str03 + str2+l:rn; SetDlgItemText(IDC_OUT, strget + str

24、00);index-;break;case 104:char b3; h = h + 1;for (i = 0; i= + str03 + +number1+ over)rn; SetDlgItemText(IDC_OUT, strget + str00);index-;break;case 105:h = h + 1; char c3;for (i = 0; i3; i+)ci = pop(s, &y); pop2(t, &x);push(s, G);pop2(t, &e);push2(t, e);go(e, 7, G);push2(t, sh); CString str00; CStrin

25、g strget; GetDlgItemText(IDC_OUT, strget); CString str02 = c0; CString str03 = c2; str00 = str0 + str02 + str1 + str03 + str1 + 1 + str1 + t1 +str2; SetDlgItemText(IDC_OUT, strget + str00); GetDlgItemText(IDC_OUT, strget); str00 = str0 + = + str1 + t1 + str1 + str1 + str1 + str03 +str2; SetDlgItemTe

26、xt(IDC_OUT, strget + str00);index-;break;case 106:h = h + 1; char d3;for (i = 0; i3; i+)di = pop(s, &y); pop2(t, &x);push(s, X);pop2(t, &e);push2(t, e);go(e, 7, X);push2(t, sh); CString str00; CString strget; GetDlgItemText(IDC_OUT, strget); CString str02 = d0; CString str03 = d2; str00 = (j= + str0

27、3 + +number1 + over)rn; SetDlgItemText(IDC_OUT, strget + str00);index-;break;case 107:h = h + 1; char f3;for (i = 0; i3; i+)fi = pop(s, &y); pop2(t, &x);push(s, Y);pop2(t, &e);push2(t, e);go(e, 7, Y);push2(t, sh); CString str00; CString strget; GetDlgItemText(IDC_OUT, strget); CString str02 = f0; CS

28、tring str03 = f2; str00 = str0 + str02 + str1 + str03 + str1 + 1 + str1 + t1 +str2; SetDlgItemText(IDC_OUT, strget + str00); GetDlgItemText(IDC_OUT, strget); str00 = str0 + = + str1 + t1 + str1 + str1 + str1 + str03 +str2; SetDlgItemText(IDC_OUT, strget + str00);index-;break;case 108: h = h + 1; cha

29、r g5;for (i = 0; i5; i+)gi = pop(s, &y); pop2(t, &x);push(s, H);pop2(t, &e);push2(t, e);go(e, 7, H);push2(t, sh); CString str00; CString strget; GetDlgItemText(IDC_OUT, strget); CString str01 = g1; CString str02 = g0; CString str03 = g2; CString str04 = g3; CString str05 = g4; str00 = str0 + str01 +

30、 str1 + str03 + str1 + number2 + str1 + t2+ 101010+str2; SetDlgItemText(IDC_OUT, strget + str00);GetDlgItemText(IDC_OUT, strget); str00 = str0 + str04 + str1 + t2 + str1 + str1 + str1 + str05+ str2+ goto lrnover11 11 11 11rn; SetDlgItemText(IDC_OUT, strget + str00);index-;break;case 109:h = h + 1; c

31、har j5;for (i = 0; i5; i+)ji = pop(s, &y); pop2(t, &x);push(s, H);pop2(t, &e);push2(t, e);go(e, 7, H);push2(t, sh);/coutendl; CString str00; CString strget; GetDlgItemText(IDC_OUT, strget); CString str01 = j1; CString str02 = j0; CString str03 = j2; CString str04 = j3; CString str05 = j4; str00 = st

32、r0 + str01 + str1 + str03 + str1 + number2 + str1 + t2+str2; SetDlgItemText(IDC_OUT, strget + str00);GetDlgItemText(IDC_OUT, strget); str00 = str0 + str04 + str1 + t2 + str1 + str1 + str1 + str05+ str2+ goto lrnoverrn; SetDlgItemText(IDC_OUT, strget + str00);index-;break;case 110: h = h + 1; char l5

33、;for (i = 0; i5; i+)li = pop(s, &y); pop2(t, &x);push(s, H);pop2(t, &e);push2(t, e);go(e, 7, H);push2(t, sh); CString str00; CString strget; GetDlgItemText(IDC_OUT, strget); CString str01 = l1; CString str02 = l0; CString str03 = l2; CString str04 = l3; CString str05 = l4; SetDlgItemText(IDC_OUT, st

34、rget + str00);GetDlgItemText(IDC_OUT, strget); str00 = str0 + str04 + str1 + t2 + str1 + str1 + str1 + str05+ str2+ goto over1551515151rn; SetDlgItemText(IDC_OUT, strget + str00);index-; break; if (k1 = 45)MessageBox(轉(zhuǎn)化成功);ok = 0;else if (u = 0) MessageBox(轉(zhuǎn)化出錯); break; （三）while語句轉(zhuǎn)換為四元式1.LR函數(shù)：主要用于通過

35、LR(0)分析表，對表達(dá)式進(jìn)行語法分析。void CDlg3:LR()int Tai50, len = 1;int i, j, k, l, m, tmp_n = 0, num = 0;int X;char temp;char fuhao50 = # ;char*W = 7, SW(B)E, EAE, EA, AiPA, Ai;, BiTi, Bi ;num = strlen(shuru);Tai0 = 0;for (i = 0; inum;)j = Tailen - 1;temp = shurui;switch (temp)case +:case -:case *:case /:case =:

36、 temp = P; break;case : temp = T; break;if (temp != P&temp != T&temp != w)if (temp = 0&temp = a&temp = A&temp = Z)temp = i;switch (temp)case w: k = 0; break;case (: k = 1; break;case ): k = 2; break;case : k = 3; break;case : k = 4; break;case i: k = 5; break;case P: k = 6; break;case T: k = 7; brea

37、k;case ;: k = 8; break;case #: k = 9; break;if (actionj.act_0k = s) int row = m_list.GetItemCount(); m_list.InsertItem(row, );/couty!i! ;/Tailen+ = actionj.act_1k;tmp_n = strlen(fuhao) - 1;fuhao+tmp_n = shurui+;CString str00=; for (l = 0; llen; l+) CString temp_str1; temp_str1.Format(%d,Tail); str00

38、=str00+temp_str1; m_list.SetItemText(row, 0, str00); CString str11=fuhao;m_list.SetItemText(row, 1, str11);CString str22=; for (l = i; lnum; l+) CString temp_str2=shurul; str22=str22+temp_str2; m_list.SetItemText(row, 2, str22);else if (actionj.act_0k = r) int row = m_list.GetItemCount(); m_list.Ins

39、ertItem(row, );X = strlen(Wactionj.act_1k) - 1;len -= X;for (m = len; mlen + X; m+)fuhaom = 0;fuhaolen = Wactionj.act_1k0;switch (Wactionj.act_1k0)case S:l = 0;break;case E:l = 1;break;case B:l = 2;break;case A:l = 3;break;len += 1;Tailen - 1 = actionTailen - 2.gol;CString str00=;for (l = 0; llen; l

40、+) CString temp_str1; temp_str1.Format(%d,Tail); str00=str00+temp_str1; m_list.SetItemText(row, 0, str00); CString str11=fuhao;m_list.SetItemText(row, 1, str11);CString str22=;for (l = i; lnum; l+) CString temp_str2=shurul; str22=str22+temp_str2; m_list.SetItemText(row, 2, str22);else if (actionj.act_0k = Z)break;duce_obj函數(shù)：主要用于操作符號棧，并且輸出四元式。void CDlg3:produce_obj(char c,int count)stack sf;stack s1;stack s;int i, j = 0;sf.push(;);char t5 = ABCD ;for (i = 0; i)str00=(j= +temp_str2+ +temp_str3+ over)rnl:rn;else if(temp