带出错处理的算符优先分析算法的程序实现.doc

目 录第一章 概述.11.1设计内容.11.2设计要求.1第二章 设计的基本原理.22.1算法分析. .22.2错误处理. .3第三章 程序设计.43.1总体方案设计.43.2各模块设计.6第四章 程序测试.7 第五章 结论.11附录 程序清单.11第一章 概述1.1设计内容 该课程设计题目是：对文法G：EE+T|T TT*F|F F(E)|i实现带出错处理的算符优先分析算法，程序显示输出“移进-归约”的步骤。 优先关系表如下：优先关系表(包括出错处理子程序)+*()i#+*(=e2e2ie2e2#e3 a DOBEGINREPEATQ:=Sj;IF Sj-1 THEN j:j-1 ELSE j:j-2UNTIL Sj Q;把Sj+1Sk归约为某个N；k:=j+1;Sk:=N;END OF WHILE;IF Sj a OR sj = a THENBEGIN k:=k+1; Sk:=a ENDELSE ERROR /* 调用出错诊察程序 */UNTIL a = #在上述算法的工作过程中，若出现j减1后的值小于等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：# N #算法优先分析一般并不等价于规范归约。在算法优先归约过程中，我们无法用那些右部仅含一个一个非终结符的产生式进行归约。对该文法G的句子i+i，按算法优先分析法，归约过程是：先把第一个i归为F，然后把第二个i也归约为F，最后把F+F直接归约为E。在此过程中，单非产生式对归约没有发挥作用。2.2 错误处理算符优先分析中的出错处理：(1) 如 + 或 * 被归约，则检查其两端是否出现非终结符。否则，打印错误信息：“缺表达式”。(2) 如i被归约，则检查其左端或右端是否有非终结符。如果有，则给出信息：“表达式间无运算符联结”。(3) 如()被归约，则检查是否在括号间有一非终结符。如果没有，则给出信息：“括号间无表达式”。根据优先关系表中的e1，e2，e3，e4可以调用错误处理子程序。(1) e1： /*当表达式以左括号结尾时，调用此程序*/ 将(从栈顶移去；给出错误信息：非法左括号。(2) e2： /*当i或)后跟i或(时，调用此程序*/ 在输入端插入+；给出错误信息：缺少运算符。(3) e3： /*当表达式以右括号开始时，调用此程序*/ 从输入端删除)；给出错误信息：非法右括号。(4) e4： 若栈顶有非终结符E，则表达式分析完毕。 若为空，则在输入端插入i；给出错误信息：缺少表达式。第三章 程序设计3.1总体方案设计先将优先关系表保存在一个二维数组Vtchart66里面，利用函数int Vttoint(char ch)将算符数字化，这样利于后面判断，以确定两个算符之间在Vtchart数组里面的关系。在设计的程序中，就是利于函数void OperatorFun(string s)进行综合处理，该函数就是算符优先算法的体现。在此函数里面有一个循环，直到分析完毕则结束，在处理过程中调用各个处理函数以及错误处理函数。利用函数bool isVn(char ch)和函数bool isVt(char ch)判断符号串是否是非终结符和终结符。在已归约串里面找到第一个终结符和输入串进行比较，若是Vtchartm1m2 = | Vtchartm1m2 = =即已归约串里面的第一个终结符和输入串的终结符的优先关系为即它们的关系是则进行归约，在归约过程中，可能会遇到错误，这就要在归约函数里面进行处理了；然后其他的情况即遇到a，b，c，d即优先关系表中的e1，e2，e3，e4，则程序就会调用错误处理子程序，在错误处理子程序里面进行相关处理。就这样进行循环，直到分析完毕。这个综合函数的流程图如下：Vtchartm1m2,a,b,c,d?归约移进错误处理用第一个产生式归约用第二个产生式归约用第三个产生式归约用第四个产生式归约用第一个错误处理程序用第二个错误处理程序用第三个错误处理程序用第四个错误处理程序或=a,b,c,d +* ) ia bc d3.2 各模块设计由于无法用那些右部仅含一个一个非终结符的产生式进行归约，第一个产生式EE+T|T可以只用EE+T代替，第二个产生式TT*F|F可以用TT*F代替，第三个产生式为F(E)，第四个产生式为Fi。如果+或*被归约，则检查其两端是否出现非终结符。若缺左表达式，则归约串添加E；若缺右表达式，则归约串添加E；若缺左右表达式，则归约串添加两个E。检查()中间是否有非终结符，若没有，则添加E。若i被归约，检查其左端或右端是否有非终结符即检查已归约串i的左右两边的字符是否是非终结符，这可以利用函数bool isVn(char ch)，如果有，则表明表达式间无运算符联结，则添加运算符+。若出现e1错误，则将(从已归约串的栈顶移去，即pop();，当然首先找到(的位置；若出现e2错误，在输入端加入+， index-; str2index = +; 可以实现，index是分析到的输入串位置；若出现e3错误，从输入端删除)， index+; 就可实现，即分析的输入串向后移动一个位置。若出现e4错误，若已归约串的栈顶是非终结符E，则分析完毕。若为空，即栈顶为#，则在输入串插入i，index-; str2index = i; 即可实现。每分析一步，则向文件输出一个步骤，有函数void outputfile()实现输出到文件。第四章 程序测试运行程序，则出现下面窗口：即提示用户输入一符号串。这个输入的符号串可以以#结束，也可以不以#结束，这在程序里面已经处理好了，即if(str2lenofstr2-1 != #) str2 += #;，就是如果不以#结束，就直接在符号串后面加上#。输入符号串，假如是：ii+) 则在文件里面产生一个文件reduction.txt文件里面是符号串“移进归约”的步骤，在有错误的步骤后面有错误原因以及解决方法。可以在运行程序的窗口里面显示结果，选择Y或y就可进行显示。如果选择N或n，则会显示如下信息：如果输入的是其他错误选择：第五章 结论经过学习实现了算符优先算法，能够对输入的符号串进行算符优先分析，并且能够处理分析过程中遇到的错误。经过这次课程设计的练习，我感觉自己的编程能力得到了很好的锻炼，是一次很好的实践活动，对以后的学习也有很大的帮助。【附录】 程序清单主程序：（main.cpp）17#include #include analysis.husing namespace std;int lenofstr2;ifstream infile(reduction.txt,ios:in);char ch;char choice;int main()cout-endl;coutstr2;lenofstr2 = str2.length();if(str2lenofstr2-1 != #)str2 += #;OperatorFun(str2);cout-endl;coutchoice;if(choice = y |choice = Y)if(!infile)cerropen error!endl;exit(1);while(infile.get(ch)cout.put(ch);coutendl;infile.close();else if(choice = n|choice = N)coutYou can see the result in the file.endl;elsecoutYour choice is Wrong!endlYou can see the result in the file.endl;cout-endl;return 0;头文件：（analysis.h）#include #include #include #include using namespace std;int length(0),index(0),number(0);int m1,m2;char str1100;string str2;char Vtchart66 = ,=,b,b,b,b,c, 0)k+;n = n/10;return k;/输出到文件void outputfile()outfilenumbersetiosflags(ios:left)setw(25-MedianofNum(number);for(int i = 0; i length; +i)outfilestr1i;outfilesetw(25-length)setiosflags(ios:right);for(int i = index; str2i != #; +i)outfilestr2i;outfile#;number+;/第一个产生式EE+T|Tvoid Reduction_1()/用第一个产生式归约if(str1length-2 = + & isVn(str1length-1) & isVn(str1length-3) for(int i = 0; i 3; +i)pop();push(E);outputfile();outfileendl;return;/缺左表达式else if(str1length-2 = + & isVn(str1length-1) & isVt(str1length-3)for(int i = 0; i 2; +i)str1length-i = str1length-i-1;str1length-2 = E;length+;outputfile();outfilesetiosflags(ios:right)setw(35)缺左表达式-归约串添加Eendl;Reduction_1();/缺右表达式else if(str1length-1 = + & isVn(str1length-2)push(E);outputfile();outfilesetiosflags(ios:right)setw(35)缺右表达式-归约串添加Eendl;Reduction_1();/缺左右表达式else if(str1length-1 = + & isVt(str1length-2)pop();push(E);push(+);push(E);outputfile();outfilesetiosflags(ios:right)setw(35)缺左右表达式-归约串添加两个Eendl;Reduction_1();/第二个产生式TT*F|Fvoid Reduction_2()/用第二个产生式归约if(str1length-2 = * & isVn(str1length-1) & isVn(str1length-3)for(int i = 0; i 3; +i)pop();push(T);outputfile();outfileendl;return;/缺左表达式else if(str1length-2 = * & isVn(str1length-1) & isVt(str1length-3)for(int i = 0; i 2; +i)str1length-i = str1length-i-1;str1length-2 = F;length+;outputfile();outfilesetiosflags(ios:right)setw(35)缺左表达式-归约串添加Fendl;Reduction_1();/缺右表达式else if(str1length-1 = * & isVn(str1length-2)push(F);outputfile();outfilesetiosflags(ios:right)setw(35)缺右表达式-归约串添加Fendl;Reduction_1();/缺左右表达式else if(str1length-1 = * & isVt(str1length-2)pop();push(F);push(*);push(F);outputfile();outfilesetiosflags(ios:right)setw(35)缺左右表达式-归约串添加两个Fendl;Reduction_1();/第三个产生式F(E)void Reduction_3()int t = findVtReduce();/用第三个产生式归约if(str1t = ) & str1t-2 = ( & isVn(str1t-1)for(int i = 0; i 3; +i)pop();push(F);outputfile();outfileendl;return;/括号间无表达式else if(str1t = ) & str1t-1 = ()for(int i = 0; i length-t; +i)str1length-i = str1length-i-1;str1t = E;length+;outputfile();outfilesetiosflags(ios:right)setw(35)括号间无表达式-归约串在括号间添加E= 0 & isVn(str1t-1) = false)pop();push(F);outputfile();outfileendl;if(t length-1 & isVn(str1t+1)str1length = str1length-1;str1length-1 = +;length+;outputfile();bl = false;outfilesetiosflags(ios:right)setw(35)表达式见无运算符联结-添加一个+= 0 & isVn(str1t-1)for(int i = 0; i length-t; +i)str1length-i = str1length-i-1;str1t = +;length+;outputfile();if(bl)outfilesetiosflags(ios:right)setw(35)表达式间无运算符联结-添加一个+endl;/出错诊断程序void errorOf1()if(str1length-1 = ()pop();outputfile();outfilesetiosflags(ios:right)setw(35)非法左括号-将(从栈顶移去endl;else if(str1length-2 = ()str1length-2 = str1length-1;length-;outputfile();outfilesetiosflags(ios:right)setw(35)非法左括号-将(从栈顶移去endl;/出错诊断程序void errorOf2()index-;str2index = +;outputfile();outfilesetiosflags(ios:right)setw(35)缺少运算符-在输入端插入+endl;/出错诊断程序void errorOf3()index+;outputfile();outfilesetiosflags(ios:right)setw(35)非法右括号-从输入端删除)endl;/出错诊断程序void errorOf4()if(length = 1)index-;str2index = i;outputfile();outfilesetiosflags(ios:right)setw(35)缺少表达式-在输入端插入iendl;elseoutputfile();outfileset