编译原理实验4算符优先算法

一、实验目的与任务算术表达式和赋值语句的文法可以是（你可以根据需要适当改变）：S→i=EE→E+E|E-E|E*E|E/E|（E）|i根据算符优先分析法，将赋值语句进行语法分析，翻译成等价的一组基本操作，每一基本操作用四元式表示。二、实验涉及的相关知识点算符的优先顺序。三、实验内容与过程如参考C语言的运算符。输入如下表达式（以分号为结束）：（1）a=10;（2）b=a+20;注：此例可以进行优化后输出（不作要求）：(+,b,a,20)（3）c=(1+2)/3+4-(5+6/7);四、实验结果及分析（1）输出：(=,a,10,-)（2）输出：(=,r1,20,-)(+,r2,a,r1)(=,b,r2,-)（3）输出：(+,r1,1,2)(/,r2,r1,3)(/,r3,6,7)(+,r4,5,r3,)(+,r5,r2,4)(-,r6,r5,r4)(=,c,r6,-)五、实验有关附件（如程序、附图、参考资料，等）//程序功能：//根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确。//文法：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://这一步规约成功break;case2://规约全部完成returnTRUE;default://出错ErrMsg=规约错误。;returnFALSE;}break;case2://需要继续移进break;default://出错returnFALSE;}}}//规约，并判断是否完成//返回：-1出错，1这一步规约成功，2规约全部完成intGuiYue(){intn0,n;charr;//存优先关系n=FindPriorOp(-1);//取得堆栈中第一个终结符if(Peek(n).ch=='#')//出错或全部结束{if(IsOK())return2;elsereturn-1;}while(TRUE){n0=n;n=FindPriorOp(n0);//前一个终结符的堆栈位置if(n-n02)//出错（多个非终结符相邻）return-1;r=O_Table[Peek(n).No][Peek(n0).No];if(r=='')//寻找结束{if(!GuiYueN(n-1))//规约（从前一个后的字符开始）规约失败return-1;else//规约成功，还要判断是否全部完成{if(IsOK())return2;//规约全部完成elsereturn1;//这一步规约成功}}elseif(r=='=')//继续向前找{continue;}else//出错（r为或没有关系）return-1;}}//判断规约是否全部完成//返回：TRUE全部完成；FALSE没有完成boolIsOK(){//if(Peek(1)==NULL)returnFALSE;if(Peek(0).ch=='E'&&Peek(1).ch=='#'&&Token[ipToken].ch=='#')returnTRUE;elsereturnFALSE;}//返回：TRUE成功，FALSE失败boolGuiYueN(intn)//将堆栈中0~n单词规约{inti,j;boolk;for(i=0;iOG_NUMBER;i++)//将规约串和文法右部OG[][]每一个进行比较{for(j=n,k=FALSE;j=0;j--){if(OG[i][n-j]!=Peek(j).ch){k=TRUE;//TRUE表示规约串和文法右部不符，break;}}if(k)continue;//k==FALSE表示规约串判断完成if(OG[i][n+1]=='\0')//文法也判断完成，匹配成功{PopUp(n+1);//弹出规约串PushToken('E',O_IDENT);//压入左部“E”returnTRUE;}}returnFALSE;}//在堆栈中，从Begin开始，查找前一个终结符位置//如果从开始找，让Begin=-1intFindPriorOp(intBegin){intn;n=Begin+1;while(Peek(n).ch=='E'){n++;}returnn;}//移进，并判断是否需要规约//返回：-1出错，1需要规约，2可继续移进//1.单词结束（遇到“#”号），无法移进，需要规约，返回：1//2.单词没有结束，需判断是否可以移进//2-1.堆栈单词=单词：移进后返回：2//2-2.堆栈单词单词：不能移进，需要规约，返回：1//2