编译原理实验-四

实验四算符优先文法处理算术表达式与赋值语句一、实验目的算术表达式和赋值语句的文法可以是（你可以根据需要适当改变）：S→i=EE→E+E|E-E|E*E|E/E|（E）|i根据算符优先分析法，将赋值语句进行语法分析，翻译成等价的一组基本操作，每一基本操作用四元式表示。二、估计实验时间1.课余准备15小时；2.上机三次6小时；3.完成实验报告5小时。三、实验过程和指导（一）准备：1.阅读课本有关章节，花一周时间确定算术表达式的文法，设计出算符优先关系表；2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。（二）上课上机：上机调试，发现错误，分析错误，再修改完善。教师根据学生的设计方案与学生进行探讨，以修改方案和代码。（三）程序要求：程序输入/输出示例：如参考C语言的运算符。输入如下表达式（以分号为结束）和输出结果：（1）a=10;输出：(=,a,10,-)（2）b=a+20;输出：(=,r1,20,-)(+,r2,a,r1)(=,b,r2,-)注：此例可以进行优化后输出（不作要求）：(+,b,a,20)（3）c=(1+2)/3+4-(5+6/7);输出：(+,r1,1,2)(/,r2,r1,3)(/,r3,6,7)(+,r4,5,r3,)(+,r5,r2,4)(-,r6,r5,r4)(=,c,r6,-)注：输出格式有多种，如上面第二个括号可改为(/,r1,r1,3)以节约变量（当然后面相应的变量引用也要改变）。注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、常量（无符号整数）和变量；2只要能表达正确的计算过程，任何输出方式都可以；3.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；4.测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；5.其中临时变量名可不用r1,r2，也可用别的形式代替，如r[1],r[2]等。6.为了降低难度，文法可适当降低要求，如只处理含有+-()的表达式，也可只处理+-*/的表达式；7.对学有余力的同学，可增加一个函数来计算四元式，最后输出被赋值变量的值（如果表达式中含有变量，则设它为0），计算过程用浮点表示，但要注意不要被0除。程序思路（仅供参考）：1.借用实验二的结果，可将其中的取字符函数几乎原封不动地移植过来，其中的分割和分析单词的方法可借用过来分割现在这个实验的运算符、常量和变量。2.模块结构：（1）初始化：设立算符优先关系表（或优先函数）、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；（2）控制部分：将一个表达式从文件中读出；（3）词法分析：将表达式分割成单词序列；（4）利用算符优先文法进行表达式处理：根据算符优先关系表（或优先函数）对表达式单词序列进行堆栈（或其他）操作，得到并保存四元组，如果遇到错误则显示错误信息；（5）输出四元组。（四）练习该实验的目的和思路：程序相当复杂，需要利用到大量的编译原理，也用到了大量编程技巧和数据结构，通过这个练习可大大提高软件开发能力。程序规模大概为400行。本实验的结果可作为课程设计的基础。通过练习，掌握对表达式进行处理的一种方法。（五）为了能设计好程序，主意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用、变量合理命名等。四、上交1.程序源代码（主文件名为by3）；2.已经测试通过的测试数据10组（全部存在test3.txt文件中，以“第一组输入/输出/第二组输入/输出/第三组输入/输出……”的格式存放）；3.实验报告：（1）功能描述：该程序具有什么功能？（2）程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图、程序总体执行流程图（参考课本第二章）。（3）实验过程记录：出错次数、出错严重程度、解决办法摘要。（4）实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？五、参考源代码//程序功能：//根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确。//文法：E→E+E|E-E|E*E|E/E|(E)|i//其中i为无符号整数////例：//输入：10;//输出：正确//输入：1+2;//输出：正确//输入：(1+2)/3+4-(5+6/7);//输出：正确//输入：((1-2)/3+4;//输出：错误////输入测试数据保存在同目录的文本文件testin.txt中，保存格式：//表达式行;//表达式行;//.....//预期的输出保存在同目录的文本文件testout.txt中，保存格式：//表达式行;//正确/错误//表达式行;//正确/错误//...../////////////////////////////////////////////////////////////////#includestdio.h#includestdlib.h#defineTRUE1#defineFALSE0//文件信息：#defineTESTIN_FILENAMEtestin.txt#defineTESTOUT_FILENAMEtestout.txtFILE*fTestIn;FILE*fTestOut;//打开文件后的柄//运算符定义：#defineO_NUMBER8//运算符个数，+-*/()i##defineO_PLUS0//加+#defineO_MINUS1//减-#defineO_TIMES2//乘*#defineO_SLASH3//除/#defineO_L_PAREN4//左括号(parenthesis)#defineO_R_PAREN5//右括号#defineO_IDENT6//标识符#defineO_NUL7//语法界符#//表达式缓冲区：由专门函数操作（ReadFormula(),GetChar()）#defineBUFFER_SIZE1000//表达式缓冲区大小charBuffer[BUFFER_SIZE];//表达式缓冲区，以'\0'表示结束intipBuffer=0;//表达式缓冲区当前位置序号//算符优先关系表：charO_Table[O_NUMBER][O_NUMBER]={{'','','','','','','',''},{'','','','','','','',''},{'','','','','','','',''},{'','','','','','','',''},{'','','','','','=','','-'},{'','','','','-','','-',''},{'','','','','-','','-',''},{'','','','','','-','','='}};//优先关系表：八个字符分别是+-*/()i#,其中'-'表示出错//文法：#defineOG_NUMBER6//文法个数charOG[OG_NUMBER][4]={E+E,E-E,E*E,E/E,(E),i};//文法右部//单词序列存放格式定义：#defineTOKEN_MAX_LENTH100//最大的单词长度+1typedefstruct{charch;//存放字符：+-*/()i#EintNo;//存放算符优先关系表中的序号//doubleValue;//当ch==i时，且为数值时，存放值的大小}SToken;#defineMAX_TOKEN_NUMBER1000//在一个表达式中允许最大的单词个数STokenToken[MAX_TOKEN_NUMBER];//单词序列，最后一个以“#”结束intTokenNumber=0;//单词序列中包含的单词个数intipToken=0;//进行“移进-规约”时的位置指示//堆栈：由专门的函数操作（PopUp(),Push(),…）#defineSTACK_MAX_SIZE1000//堆栈最大存储量STokenStack[STACK_MAX_SIZE];//堆栈intipStack=0;//堆栈指针，指向栈顶（下一个空位置）//词法分析专用全局变量：charch;//存放取得的一个字符//charAToken[TOKEN_MAX_LENTH];//存放组成的单词，存放时以\0为结束//intipAToken;//用于读字符时，指向下一个AToken[]的位置，便于组成单词//错误信息：char*ErrMsg;//出错信息//函数声明：boolJudge();//利用算符优先关系表判断单词序列是否正确intGuiYue();//规约，并判断是否完成boolIsOK();//判断规约是否全部完成boolGuiYueN(intn);//将堆栈中0~n单词规约intFindPriorOp(intBegin);//在堆栈中，从Begin开始，查找前一个终结符位置intMoveIn();//移进，并判断是否需要规约voidJudgeInit();//（利用算符优先关系表判断单词序列是否正确）判断前的初始化STokenPeek(intn);//窥视堆栈boolPopUp(intn);//弹出堆栈voidPushToken(charch,intO_No);//压栈（以字符形式）voidPush(STokenToken);//压栈boolInit();//全局初始化voidEnd();//程序退出前作善后处理voidOutPut(char*Formula,char*Result);//将结果输出到文件boolReadFormula();//从文件中读出一个表达式存于表达式缓冲区Buffer[]中，以'\0'结束，并置ipBuffer=0；boolChangeToTokens();//将表达式分割成单词序列charGetFirstChar();//从表达式缓冲区中取到下面第一个非空字符charGetChar();//从表达式缓冲区取一个字符，返回该字符的同时将它存于全局变量ch中boolMakeErr(char*ErrMassage);//生成错误信息，错误信息存于全局变量ErrMsg中///////////////////////////////////////voidmain(){if(!Init())//初始化{printf(初始化失败！程序不能继续。错误信息如下：\n%s\n,ErrMsg);exit(0);}while(ReadFormula())//从文件中读表达式成功{if(ChangeToTokens())//将表达式分割成单词序列{if(Judge())//利用算符优先关系表判断表达式（单词序列）是否正确OutPut(Buffer,正确！);elseOutPut(Buffer,ErrMsg);//输出错误信息}else//出错{OutPut(Buffer,ErrMsg);//输出错误信息}}End();//程序退出前作善后处理}//利用算符优先关系表判断单词序列是否正确//返回：TRUE正确；FALSE错误，且错误信息存于ErrMsg//本函数的实现思路：//将单词序列进行“移进-规约”操作，最后判断是否能全部完成//使用到：堆栈（STokenStack[]）、文法（charOG[][]）、算符优先关系表（charO_Table[][]）等boolJudge(){JudgeInit();PushToken('#',O_NUL);//将“#”号置栈底while(TRUE)//进行“移进-规约”操作{switch(MoveIn()){case1://需要规约switch(GuiYue())//规约{case1://这一步规约成功brea