递归下降分析法实验

实验二递归下降分析法一、实验目的（1）掌握自上而下语法分析的要求与特点。（2）掌握递归下降语法分析的基本原理和方法。二、实验环境Windows7操作系统MicrosoftVisualC++三、实验内容递归下降分析法是确定的自上而下分析法，它要求文法是LL(1)文法。它的基本思想是：对文法中的每个非终结符编写一个函数或子程序，每个函数或子程序的功能是识别由该非终结符所表示的语法成分。1.递归下降分析法的功能词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。2.递归下降分析法的前提改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法，3.递归下降分析法实验设计思想及算法为G的每个非终结符号U构造一个递归过程。U的产生式的右边指出这个过程的代码结构：(1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。(2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现。四、实验步骤1.阅读课本有关章节；2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。4.将源代码拷贝到机上调试，发现错误，再修改完善，直到调试通过为止。5.系统流程图6.程序代码#includeiostreamusingnamespacestd;chara[80];//字符串的存入charsym;//单个的判断字符inti=0;//字符串下标voidE();//功能识别函数voidE2();//功能识别函数voidE3();//功能识别函数voidT();//功能识别函数voidT2();//功能识别函数voidT3();//功能识别函数结束输出正确提示信息判断是否为正确表达式是否输入表达式输出错误提示信息开始voidF();//功能识别函数voidinput();//输入函数voidadvance();//字符串小标进一函数voidmain(){while(1){input();advance();E();//从首个推导式E开始if(sym=='#')couta为合法符号串endl;elsecout非法的符号串!endl;i=0;//重新输入时，下标置0}}voidE(){T();E2();E3();}voidE2(){if(sym=='+'){advance();T();E2();}elseif(sym!=')'&&sym!='#'&&sym!='-'){cout非法的符号串!endl;exit(0);}}voidE3(){if(sym=='-'){advance();T();E3();}elseif(sym!=')'&&sym!='#'&&sym!='+'){cout非法的符号串!endl;exit(0);}}voidT(){F();T2();T3();}voidT2(){if(sym=='*'){advance();F();T2();}elseif(sym!='+'&&sym!=')'&&sym!='#'&&sym!='-'&&sym!='/'){cout非法的符号串!endl;exit(0);}}voidT3(){if(sym=='/'){advance();F();T3();}elseif(sym!='+'&&sym!=')'&&sym!='#'&&sym!='-'&&sym!='*'){cout非法的符号串!endl;exit(0);}}voidF(){if(sym=='('){advance();E();if(sym==')')advance();else{cout非法的符号串!endl;exit(0);}}elseif(sym=='i'||sym=='I'){advance();}else{cout非法的符号串!endl;exit(0);}}voidinput(){cout请输入一以#结束的符号串(包括+-*/()i#):endl;cina;}voidadvance(){sym=a[i];i++;}五、运行结果1.输入正确的表达式的运行结果如下图所示：2.输入错误的运行结果如下图所示：六、实验总结在试验的过程中，遇到了一些问题，都是粗心大意而造成，并非是对文法分析和编程的熟悉问题，说明了我再以后的试验中应该更细心的编写程序的每一步，对于本次试验所出现的马虎，应该牢记，以后不再犯同样的错误。本次实验主要出现了以下两次重要错误：（1）算式匹配时候，如果输入字符串中只有“（”时，仍然是能够正确匹配；解决方案：由于没有考虑括号匹配是成对存在的问题，添加右括号匹配代码就可以解决了。（2）调用非终结符E()执行完以后，则对于一些非法的算式还是成功输出例如i-、i*等；解决方案：在主函数main()中需要对调用非终结符E()执行完以后的ch进行判断，如果ch为“#”则算式匹配成功，否则算式匹配失败。通过本次试验实践使我掌握了递归下降语法分析的基本原理和方法。运用递归下降分析法完成了本试验的语法分析构造，并且成功的分析出每种正确的句子和错误的句子。函数的构造是根据文法分析的递归过程，所编写每个函数的功能，以文法的右部为函数名，对应的左部为相应分析过程。此分析法简单，直观，易构造分析程序，但是不适于文法过于复杂的，不易检查出错误。