编译原理课程设计_算术表达式、for、while语句转换为四元式

1、.计算机与信息学院操作系统与编译原理联合课程设计报告专题：编译原理部分学生姓名：学号：专业班级：指导教师：2014年 7月.一、设计目标设计一个语法制导翻译器，将算术表达式、for语句、 while语句翻译成四元式。要求先确定一个定义算术表达式、for语句、 while语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的表达式，程序将其转换成四元式输出。二、设计思路开发平台： Visual C+ MFC解决这个问题的方案分为以下几个步骤：1. 将算数表达式、 for 语句、 while 语句转换为四元式的

2、第一步为对读入的表达式进行处理，即删除不必要的空格、回车、换行等，保证之后的步骤能够顺利进行。2. 分析算术表达式、 for 语句、 while 语句的文法。3. 通过词法分析判断语句中的每个字符的类型，如：数字、字母、符号等。4. 建立每种文法的 LR(0) 分析表，通过每个文法的 LR(0) 分析表对相应的表达式进行语法分析。5. 在语法分析正确的情况下，通过语法分析的中间过程的符号栈输出四元式，四元式的形式为：（ oparg1arg2result）。（一）算术表达式转换为四元式将算术表达式转换为四元式首先考虑了括号的问题，对于不同的算术表达式第一步进行词法分析，即确定各种符号的位置。而括

3、号中的式子是优先级最高的，应该最先进行处理。我使用了一个数组记录算术表达式中括号的位置，并且定义了first_cc和 first_jj函数对括号的乘除法和加减法分别进行处理。后将括号的式子以四元式的形式输出。通过以上转换，已将原算术表达式中的括号中的容使用大写字母A、 B 等代替（其中定义声明了change 函数，用来将括号部分替换为大写字母）。新的式子中， 只含有加减乘除以及赋值这四种运算，后根据优先级的不同，逐步生成四元式。其算法流程图如右图所示。（二） for语句转换为四元式1.For语句的文法如下：S-> f ( E ; F ; G ) H ;S-> f ( E ; X ;

4、 Y ) H ;E-> id = cF-> id < cG-> id + +X-> id > cY-> idH-> id 1 = id2 + id3.H-> id1 = id2 + cH-> id1 = c+ id2其中 c 表示常数const ，f 表示关键字for ， id表示一般标识符。for循环体部的表达式一般为算术表达式，而算术表达式转换为四元式的方法在第一部分已给出，此处 H 只考虑比较简单的情况。2.for语句的 LR(0) 分析表如下：3. 基本算法流程：本算法定义声明了两个结构体：一个是Node 结构体，其中char

5、 型的 type 中存储当前符号的类型， CString型的 sValue 中存储的为当前符号，int型的 eValue 只有在符号类型为数字的情况下才进行存储，存储数字的大小；另一个为stack 结构体， 这个结构体是实现语法分析中的符号栈和状态栈使用的，并未这两个栈分别定义了各自的pop 函数和 push 函.数。除此之外，本算法中的LR(0) 分析表通过二维数组存储。其中分为 action表和 goto 表。action表中的状态转换符号，用2-44 表示，规约的符号，用101-110 表示。具体的算法流程图如下：（三） while语句转换为四元式1.while语句的文法如下：(1)S-

6、>while(B)E(2)E->AE(3)E->A(4)A->iPA(5)A->i.(6)B->iTi(7)B->i其中 while 、( 、 ) 、 、 、P、 T 字母均为非终结符。 T 表示比较运算符，2.While语句的 LR(0) 分析表如下：、 ； 和 i 均为终结符，而 S、A、B、 E 这些大写 P 表示算术运算符， i 表示合法标识符。3. 基本算法流程：本算法的基本思想与for语句转换成四元式的思想比较相似，都是对读入的语句进行词法分析，后再通过LR(0) 分析表对语句进行语法分析，并同时输出四元式。与 for语句转换成四元式不同的

7、是，while语句转换为四元式在结构体定义等方面做了改进。首先是LR(0) 分析表的存储方式进行了改进，本算法中为LR(0) 分析表定义了一个table 的结构体，将 action 和 goto 两个部分全部存入 table 的结构体中，是查表的时候更加方便。除此之外， 还定义了obj 结构体， 此结构体主要是为了存储所要输出的四元式，定义了此结构体之后，程序的调理变得更为清晰了。本算法中符号栈以及状态栈的部分主要调用了c+中原有的 stack结构体， 使用其本身定义的 pop 函数以及push 函数，简化的代码。以下为算法的流程图：.（四）输入、输出以及界面设计1. 输入：本程序的输入均为语

8、句或表达式，若每次测试程序均输入表达式，则会输入大量式子，浪费时间。所以本程序采用文件读入的形式，只需要在指定位置输入文件名即可。2. 输出：本程序输出的四元式全部在MFC界面的文本框中显示。可以复制，方便之后的使用。3. 界面设计：本程序为了方便使用以及界面美观，使用了MFC中的 TabControl 控件，界面设计如下：.图中当前标签为“ while 语句”，显示的界面为“ while 语句转换为四元式”。通过若点击其他标签按钮，界面也会切换到相应的界面。每个界面都是一个对话框，如下图所示：（ 1）CompilerDesignDlg.cpp 作为主要的文件， 去调用其他的对话框。 首先对每

9、一个对话框（ IDD_DIALOG1-3）进行设置，样式：下层；边框：无。如下图所示：（ 2）后在 CompilerDesignDlg.h 文件中添加每个对话框的头文件， 以及申明每个对话框，代码如下：#include "Dlg1.h"#include "Dlg2.h"#include "Dlg3.h"CDlg1 page1;CDlg2 page2;CDlg3 page3;（ 3）在初始化函数 CCompilerDesignDlg:OnInitDialog()中编写相关代码：m_tabCtrl.InsertItem(0, "

10、算术表达式 ");.m_tabCtrl.InsertItem(1, "for语句 ");m_tabCtrl.InsertItem(2, "while语句 ");page1.Create(IDD_DIALOG1, &m_tabCtrl);page2.Create(IDD_DIALOG2, &m_tabCtrl);page3.Create(IDD_DIALOG3, &m_tabCtrl);CRect rc;m_tabCtrl.GetClientRect(&rc);rc.top += 22;rc.bottom -= 3

11、;rc.left += 2;rc.right -= 3;/ 设置子对话框尺寸并移动到指定位置page1.MoveWindow(&rc);page2.MoveWindow(&rc);page3.MoveWindow(&rc);page1.ShowWindow(true);page2.ShowWindow(false);page3.ShowWindow(false);m_tabCtrl.SetCurSel(0);（ 4）填写按钮响应函数， 即实现点击按钮切换到相应界面的功能， 双击 Tab控件，创建函数，函数代码实现如下：void CCompilerDesignDlg:On

12、SelchangeTab1(NMHDR* pNMHDR, LRESULT* 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

13、.ShowWindow(false);page3.ShowWindow(true);break;*pResult = 0;.三、核心代码（一）算术表达式转化为四元式1.first_cc函数：对括号中的乘除法进行处理。void CDlg1:first_cc(int i, int m)i+;for (; i <= m - 1; i+)/处理乘除运算if (stri = '*' | stri = '/')CString str00;CString strget;GetDlgItemText(IDC_OUT, strget);CString str01 = str

14、i;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 - 1);stri - 1 = stri = stri + 1 = JG;sum-;JG = (char)(int)JG+;2.first_jj函数：对括号的加减法进行处理。void CDlg1:first_j

15、j(int j, int m)j+;for (; j <= m - 1; j+)/处理加减运算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 + str1 + str02 + str1 + str03 + st

16、r1 + str04 + str2; SetDlgItemText(IDC_OUT, strget + str00);.change(j - 1);strj - 1 = strj = strj + 1 = JG;sum-;JG = (char)(int)JG+;3.scan 函数：用于从文件中读入表达式，并处理空格、回车、换行等。并对表达式中的括号进行处理。void CDlg1:scan(FILE *fin)int pMAX;char ch = 'a'int c = -1, q = 0;while (ch != EOF)ch = getc(fin);while (ch = &#

17、39; ' | ch = 'n' | ch = 't')ch = getc(fin);/消除空格和换行符strm+ = ch;if (ch = '=' | ch = '+' | ch = '-' | ch = '*' | ch = '/') /统计含有以上字符的符号sum+;else if (ch = '(')p+c = m - 1;else if (ch = ')')q = m - 1;first_cc(pc, q);/从左括号处理到又括号f

18、irst_jj(pc, q);JG = (char)(int)JG-;strpc = strm - 1 = JG;c-;JG = (char)(int)JG+;4.tans_simple函数：用于处理经过scan 函数处理后的式子，根据其优先级的不同分别处理，并输出四元式。void CDlg1:trans_simple()for (int i = 0; i <= m - 1; i+)/处理乘除运算.if (stri = '*' | stri = '/')CString str00;CString strget;GetDlgItemText(IDC_OUT,

19、 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 - 1);stri - 1 = stri = stri + 1 = JG;sum-;JG = (char)(int)JG+;for (int j = 0;

20、 j <= m - 1; j+)/处理加减运算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 + str1 + str02 + str1 + str03 + str1 + str04 + str2; SetDl

21、gItemText(IDC_OUT, strget + str00); change(j - 1);strj - 1 = strj = strj + 1 = JG;sum-;JG = (char)(int)JG+;for (int k = 0; k <= m - 1; k+)/处理赋值运算if (strk = '=')JG = (char)(int)-JG;CString str00;CString strget;.GetDlgItemText(IDC_OUT, strget);CString str01 = strk;CString str02 = strk - 1;C

22、String str03 = strk + 1;str00 = str0 + str01 + str1 + str03 + str1 + str1 + str1 + str02 + str2; SetDlgItemText(IDC_OUT, strget + str00);sum-;change(k + 1);strk - 1 = JG;（二） for 语句转换为四元式work 函数：主要用于根据LR(0) 分析表进行语法分析，并输出四元式。void CDlg2: work()CString str0 = "( "CString str1 = ""CSt

23、ring str2 = " )rn"CString zf;char ch, y;int x, e, u, ok = 1;int i = 0, index = 0;int h = 0;int r;int k1 = 0;char st40;CString ah40;stack s;stack t;SetDlgItemText(IDC_OUT,"");CString in_s;char in_c100;GetDlgItemText(IDC_FILENAME,in_s);ifstream iii(in_s);iii>>in_c;zf=in_c;Set

24、DlgItemText(IDC_DISPLAY,zf);getSym(zf, i);r = nodeSize;CString str_cf;CString str_c;CString str_i;int count=0;.for (i = 0; i<r; i+)sti = nodei.type;if(sti='f')GetDlgItemText(IDC_CF,str_cf);CString temp_str3="关键字： forrn"SetDlgItemText(IDC_CF,str_cf+temp_str3);else if (sti='i&

25、#39;)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+=nodei.sValue;GetDlgItemText(IDC_CF,str_cf);SetDlgItemText(IDC_CF,str_cf+"符号： "+str_i+"rn"+"常数： "

26、+str_c+"rn");for (i = 0; i<r; i+)ahi = nodei.sValue;/测试Initstack(s);Initstack(t);push(s, '#');push2(t, 0);SetDlgItemText(IDC_YF,"动作符号GOTOrn");while (ok = 1)ch = stindex;index+;y = ch;if (ch = '')y = '#'k1 = action(1, 14, y);pop2(t, &q);push2(t, q);u

27、 = action(q, 14, y);if (action(q, 14, y)>0 && action(q, 14, y)<45).CString strget;GetDlgItemText(IDC_YF,strget);CString str00;push(s, ch);push2(t, zh);CString temp_str1=ch;CString temp_str2;temp_str2.Format("%d",zh);str00="移进"+temp_str1+""+temp_str2+"

28、rn"SetDlgItemText(IDC_YF,strget+str00);if (action(q, 14, y)>100 && action(q, 14, y) <= 110)CString strget;GetDlgItemText(IDC_YF,strget);SetDlgItemText(IDC_YF,strget+"进行规约 rn");switch (zh)case 101:for (i = 0; i<12; i+)pop(s, &y); pop2(t, &x);push(s, 'S'

29、);pop2(t, &e);push2(t, e);go(e, 7, 'S'); /查询 GOTO表push2(t, sh); /替换后的数字index-;break;case 102:for (i = 0; i<12; 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; i&

30、lt;3; i+).ai = pop(s, &y);pop2(t, &x);push(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+

31、 str03+ str2+"l:rn"SetDlgItemText(IDC_OUT, strget + str00);index-;break;case 104:char b3; h = h + 1;for (i = 0; i<3; i+)bi = pop(s, &y); pop2(t, &x);push(s, 'F');pop2(t, &e);push2(t, e);go(e, 7, 'F');push2(t, sh);CString str00;CString strget;GetDlgItemText(ID

32、C_OUT, strget);CString str02 = b0;CString str03 = b2;str00 = "(j>=" + str03 + ""+number1+"over)rn"SetDlgItemText(IDC_OUT, strget + str00);index-;break;case 105:h = h + 1; char c3;.for (i = 0; i<3; i+)ci = pop(s, &y); pop2(t, &x);push(s, 'G');pop2(t

33、, &e);push2(t, e);go(e, 7, 'G');push2(t, sh);CString str00;CString strget;GetDlgItemText(IDC_OUT, strget);CString str02 = c0;CString str03 = c2;str00= str0+ str02+ str1+ str03+ str1+ "1"+ str1SetDlgItemText(IDC_OUT, strget + str00);GetDlgItemText(IDC_OUT, strget);str00= str0+ &

34、quot;="+ str1+ "t1"+ str1+ str1+ str1SetDlgItemText(IDC_OUT, strget + str00);index-;break;case 106:h = h + 1; char d3;for (i = 0; i<3; 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 s

35、trget;GetDlgItemText(IDC_OUT, strget);CString str02 = d0;CString str03 = d2;str00 = "(j<= " + str03 + " "+number1 + " over)rn" SetDlgItemText(IDC_OUT, strget + str00);index-;break;case 107:+ "t1" +str2;+ str03 +str2;.h = h + 1; char f3;for (i = 0; i<3; i

36、+)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;CString str03 = f2;str00= str0+ str02+ str1+ str03+ str1+ "1"+ str1+ "t1"+str

37、2;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; char g5;for (i = 0; i<5; i+)gi = pop(s, &y); pop2(t, &x);push(s

38、, '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+ str1+ str03+ str1+ number2+ str1+ "t2&quo

39、t;+"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; char j5;f

40、or (i = 0; i<5; i+)ji = pop(s, &y); pop2(t, &x);push(s, 'H');pop2(t, &e);push2(t, e);go(e, 7, 'H');push2(t, sh);/cout<<endl;CString str00;CString strget;GetDlgItemText(IDC_OUT, strget);CString str01 = j1;CString str02 = j0;CString str03 = j2;CString str04 = j3;CS

41、tring str05 = j4;str00 = str0 + 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,

42、 strget + str00);index-;break;case 110:h = h + 1; char l5;for (i = 0; i<5; 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 = l

43、0;CString str03 = l2;CString str04 = l3;CString str05 = l4;str00 = str0 + str01 + str1 + str03 + str1 + str02 + str1 + "t2"+"4"+str2;SetDlgItemText(IDC_OUT, strget + str00);GetDlgItemText(IDC_OUT, strget);str00 = str0 + str04 + str1 + "t2" + str1 + str1 + str1 + str05+

44、str2+ "goto over1551515151rn"SetDlgItemText(IDC_OUT, strget + str00);index-;break;if (k1 = 45)MessageBox(" 转化成功 ");ok = 0;else if (u = 0) MessageBox("转化出错 ");break;（三） while 语句转换为四元式1.LR 函数：主要用于通过LR(0) 分析表，对表达式进行语法分析。void CDlg3:LR()int Tai50, len = 1;int i, j, k, l, m,

45、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; i<num;)j = Tailen - 1;temp = shurui;switch (

46、temp)case '+':case '-':case '*':case '/':case '=': temp = 'P' break;case '<':case '>':temp = 'T' break;if (temp != 'P'&&temp != 'T'&&temp != 'w')if (temp >= '0'&&t

47、emp <= '9' | temp >= 'a'&&temp <= 'z' | 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

48、= 4;break;case 'i':k = 5;break;case 'P':k = 6;break;case 'T':k = 7;break;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; l<len; l+)CString temp_str1;temp_str1.Format("%d",Tail);str00=str00+temp_str1;m_list.SetItemText(row, 0, str00);.CString str11