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

计算机与信息学院《操作系统与编译原理联合课程设计报告》2014年7月专题：编译原理部分学生姓名：学号：专业班级：指导教师：一、设计目标设计一个语法制导翻译器，将算术表达式、for语句、while语句翻译成四元式。要求先确定一个定义算术表达式、for语句、while语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的表达式，程序将其转换成四元式输出。二、设计思路开发平台：VisualC++MFC解决这个问题的方案分为以下几个步骤：1.将算数表达式、for语句、while语句转换为四元式的第一步为对读入的表达式进行处理，即删除不必要的空格、回车、换行等，保证之后的步骤能够顺利进行。2.分析算术表达式、for语句、while语句的文法。3.通过词法分析判断语句中的每个字符的类型，如：数字、字母、符号等。4.建立每种文法的LR(0)分析表，通过每个文法的LR(0)分析表对相应的表达式进行语法分析。5.在语法分析正确的情况下，通过语法分析的中间过程的符号栈输出四元式，四元式的形式为：（oparg1arg2result）。（一）算术表达式转换为四元式将算术表达式转换为四元式首先考虑了括号的问题，对于不同的算术表达式第一步进行词法分析，即确定各种符号的位置。而括号中的式子是优先级最高的，应该最先进行处理。我使用了一个数组记录算术表达式中括号的位置，并且定义了first_cc和first_jj函数对括号内的乘除法和加减法分别进行处理。后将括号内的式子以四元式的形式输出。通过以上转换，已将原算术表达式中的括号中的内容使用大写字母’A’、’B’……等代替（其中定义声明了change函数，用来将括号部分替换为大写字母）。新的式子中，只含有加减乘除以及赋值这四种运算，后根据优先级的不同，逐步生成四元式。其算法流程图如右图所示。（二）for语句转换为四元式1.For语句的文法如下：S-f(E;F;G){H;}S-f(E;X;Y){H;}E-id=cF-idcG-id++X-idcY-id––H-id1=id2+id3H-id1=id2+cH-id1=c+id2其中c表示常数const，f表示关键字for，id表示一般标识符。for循环体内部的表达式一般为算术表达式，而算术表达式转换为四元式的方法在第一部分已给出，此处H只考虑比较简单的情况。2.for语句的LR(0)分析表如下：3.基本算法流程：本算法定义声明了两个结构体：一个是Node结构体，其中char型的type中存储当前符号的类型，CString型的sValue中存储的为当前符号，int型的eValue只有在符号类型为数字的情况下才进行存储，存储数字的大小；另一个为stack结构体，这个结构体是实现语法分析中的符号栈和状态栈使用的，并未这两个栈分别定义了各自的pop函数和push函数。除此之外，本算法中的LR(0)分析表通过二维数组存储。其中分为action表和goto表。action表中的状态转换符号，用2-44表示，规约的符号，用101-110表示。具体的算法流程图如下：（三）while语句转换为四元式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均为终结符，而S、A、B、E这些大写字母均为非终结符。T表示比较运算符，P表示算术运算符，i表示合法标识符。2.While语句的LR(0)分析表如下：3.基本算法流程：本算法的基本思想与for语句转换成四元式的思想比较相似，都是对读入的语句进行词法分析，后再通过LR(0)分析表对语句进行语法分析，并同时输出四元式。与for语句转换成四元式不同的是，while语句转换为四元式在结构体定义等方面做了改进。首先是LR(0)分析表的存储方式进行了改进，本算法中为LR(0)分析表定义了一个table的结构体，将action和goto两个部分全部存入table的结构体中，是查表的时候更加方便。除此之外，还定义了obj结构体，此结构体主要是为了存储所要输出的四元式，定义了此结构体之后，程序的调理变得更为清晰了。本算法中符号栈以及状态栈的部分主要调用了c++中原有的stack结构体，使用其本身定义的pop函数以及push函数，简化的代码。以下为算法的流程图：（四）输入、输出以及界面设计1.输入：本程序的输入均为语句或表达式，若每次测试程序均输入表达式，则会输入大量式子，浪费时间。所以本程序采用文件读入的形式，只需要在指定位置输入文件名即可。2.输出：本程序输出的四元式全部在MFC界面的文本框中显示。可以复制，方便之后的使用。3.界面设计：本程序为了方便使用以及界面美观，使用了MFC中的TabControl控件，界面设计如下：图中当前标签为“while语句”，显示的界面为“while语句转换为四元式”。通过若点击其他标签按钮，界面也会切换到相应的界面。每个界面都是一个对话框，如下图所示：（1）CompilerDesignDlg.cpp作为主要的文件，去调用其他的对话框。首先对每一个对话框（IDD_DIALOG1-3）进行设置，样式：下层；边框：无。如下图所示：（2）后在CompilerDesignDlg.h文件中添加每个对话框的头文件，以及申明每个对话框，代码如下：#includeDlg1.h#includeDlg2.h#includeDlg3.hCDlg1page1;CDlg2page2;CDlg3page3;（3）在初始化函数CCompilerDesignDlg::OnInitDialog()中编写相关代码：m_tabCtrl.InsertItem(0,算术表达式);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);CRectrc;m_tabCtrl.GetClientRect(&rc);rc.top+=22;rc.bottom-=3;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控件，创建函数，函数内代码实现如下：voidCCompilerDesignDlg::OnSelchangeTab1(NMHDR*pNMHDR,LRESULT*pResult){intCurSel=m_tabCtrl.GetCurSel();switch(CurSel){case0:page1.ShowWindow(true);page2.ShowWindow(false);page3.ShowWindow(false);break;case1:page1.ShowWindow(false);page2.ShowWindow(true);page3.ShowWindow(false);break;case2:page1.ShowWindow(false);page2.ShowWindow(false);page3.ShowWindow(true);break;}*pResult=0;}三、核心代码（一）算术表达式转化为四元式1.first_cc函数：对括号中的乘除法进行处理。voidCDlg1::first_cc(inti,intm){i++;for(;i=m-1;i++)//处理乘除运算{if(str[i]=='*'||str[i]=='/'){CStringstr00;CStringstrget;GetDlgItemText(IDC_OUT,strget);CStringstr01=str[i];CStringstr02=str[i-1];CStringstr03=str[i+1];CStringstr04=JG;str00=str0+str01+str1+str02+str1+str03+str1+str04+str2;SetDlgItemText(IDC_OUT,strget+str00);change(i-1);str[i-1]=str[i]=str[i+1]=JG;sum--;JG=(char)(int)JG++;}}}2.first_jj函数：对括号内的加减法进行处理。voidCDlg1::first_jj(intj,intm){j++;for(;j=m-1;j++)//处理加减运算{if(str[j]=='+'||str[j]=='-'){CStringstr00;CStringstrget;GetDlgItemText(IDC_OUT,strget);CStringstr01=str[j];CStringstr02=str[j-1];CStringstr03=str[j+1];CStringstr04=JG;str00=str0+str01+str1+str02+str1+str03+str1+str04+str2;SetDlgItemText(IDC_OUT,strget+str00);change(j-1);str[j-1]=str[j]=str[j+1]=JG;sum--;JG=(char)(int)JG++;}}}3.scan函数：用于从文件中读入表达式，并处理空格、回车、换行等。并对表达式中的括号进行处理。voidCDlg1::scan(FILE*fin){intp[MAX];charch='a';intc=-1,q=0;while(ch!=EOF){ch=getc(fin);while(ch==''||ch=='\n'||ch=='\t')ch=getc(fin);//消除空格和换行符str[m++]=ch;if(ch=='='||ch=='+'||ch=='-'||ch=='*'||ch=='/')//统计含有以上字符的符号sum++;elseif(ch=='('){p[++c]=m-1;}elseif(ch==')'){q=m-1;first_cc(p[c],q);//从左括号处理到又括号first_jj(p[c],q);JG=(char)(int)JG--;str[p[c]]=str[m-1]=JG;c--;JG=(char)(int)JG++;}}}4.tans_simple函数：用于处理经过scan函数处理后的式子，根据其优先级的不同分别处理，并输出四元式。voidCDlg1::trans_simple(){for(inti=0;i=m-1;i++)//处理乘除运算{if(str[i]=='*'||str[i]=='/'){CStringstr00;CStringstrget;GetDlgItemText(IDC_OUT,strget);CStringstr01=str[i];CStringstr02=str[i-1];CStringstr03=str[i+1];CStringstr04=JG;str00=str0+str01+str1+str02+str1+str03+str1+str04+str2;SetDlgItemText(IDC_OUT,strget+str00);change(i-1);str[i-1]=str[i]=str[i+1]=J