语法分析—递归下降分析法

实验2语法分析——递归下降分析法一、实验目的1、通过该课程设计要学会用消除左递归的方法来使文法满足进行确定自顶向下分析的条件。2、学会用C/C++高级程序设计语言来设计一个递归下降分析法的语法分析器；3、通过该课程设计，加深对语法分析理论的理解，培养动手实践的能力。二、设计内容参考算数运算的递归子程序构造方法及代码，完成以下任务：构造布尔表达式的文法，并编写其递归子程序。程序设计语言中的布尔表达式有两个作用，一是计算逻辑值，更多的情况是二，用作改变控制流语句中条件表达式，如在if-then，if-then-else或是while-do语句中使用。布尔表达式是由布尔算符(and,or,not)施予布尔变量或关系运算表达式而成。为简单起见，以如下文法生成的布尔表达式作为设计对象：E→EandE|EorE|notE|iropi|true|falsei→标识符|数字rop→=||=||==|以上文法带有二义性，并且未消除左递归，请对之处理后，再构造递归下降程序。可适当减少工作量，暂时忽略id的定义，输入时直接用数字或字母表示。三、语法分析器的功能该语法分析器能够分析词法分析器的结果，即单词二元式。在输入单词二元式后，能输出分析的结果。四、算法分析1、语法分析的相关知识；2、递归子程序法的相关理论知识；3、根据递归子程序法相关理论，具体针对文法的每一条规则编写相应得递归子程序以及分析过程等。//在递归子程序的编写过程中，当要识别一个非终结符时，需时刻留意该非终结符的FIRST集与FOLLOW集。程序示例一：G：P→begind；XendG’：P→begind；XendX→d；X|YX→d；X|YY→Y；s|sY→sZZ→；sZ|ε相应的递归子程序设计如下：P（）{if（token==“begin“）{Read(token);If(token==’d’)Read(token);ElseERROR;If(token==’;’)Read(token);ElseERROR;If(token==’d’||‘s’)X();ElseERROR;If(token==’end’)OK;}ElseERROR;}X()//X→d；X|Y{if(token==’d’){read(token);if(token==’;’)read(token);elseERROR;If(token==’d’)X();Elseif(token==’s’)//注意：对Y的识别也可以是在X的过程中一开始就进行，所以在最外层分支中，加上一个token==s的分支Y();ElseERROR;}ElseERROR;}Y()//Y→sZ{if(token==’s’){read(token);If(token==’;’||‘end’)Z();ElseERROR;ElseERROR;}Z()//Z→；sZ|ε{if(token==’;’){read(token);If(token==’s’)Read(token);ElseERROR;If(token==’;’)Z()；Elseif(token==’end’)//类似的，这里对于读到end，也要最外层添加一个分支Return;ElseERROR;}ElseERROR;}程序示例二（参考代码）：构造文法G[E]：E→E+T|TT→T*F|FF→（E）|d的递归子程序（即语法分析器）。注：该文法消除左递归，得E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|d//E→TE'////E'→+TE'|ε////T→FT'////T'→*FT'|ε////F→(E)|d//////////源程序中E1、T1分别代替E'、T'//运行环境DevC++4.9.9.2#includeiostreamusingnamespacestd;#includeiomanip#includestring.h#defineERRORprintf(error./n);charA[51];//用于存放符号串,不能50个字符inti=0;//用于控制当前要判断的字符intn;booljudge=0;//用于判断输出合法或不合法voidE();//voidE1();//voidT();//为每个非终节符构造一个子程序E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|dvoidT1();//voidF();//voidmatch(int&k);//此程序只是此执行加1操作intmain(){cout请输入一个有待判断的符号串(以$结尾):\n;cout\n***************************************\n\n;cout;cinA;cout\n***************************************\n\n;n=strlen(A);E();if(judge==0)cout\n此输入串合法\n\n;elsecout\n此输入串不合法\n\n;system(pause);}voidE(){if(A[i]=='('||A[i]=='d'){T();if(A[i]=='+')E1();elseif(A[i]==')'||A[i]=='$'){judge=0;return;}}}voidE1(){if(A[i]=='+'){match(i);if(A[i]=='('||A[i]=='d'){T();if(A[i]=='+')E1();elseif(A[i]==')'||A[i]=='$')judge=0;return;}elsejudge=1;}}elseif(A[i]==')'||A[i]=='$')//判断当前输入符是否属于Follow(E1)return;elsejudge=1;}voidT(){if(A[i]=='('||A[i]=='d'){F();if(A[i]=='*')T1();elseif(A[i]=='+'||A[i]==')'|A[i]=='$')judge=0;return;elsejudge=1;}}voidT1(){if(A[i]=='*')//判断当前输入符是否属于First(*FT1){match(i);if(A[i]=='('||A[i]=='d'){F();if(A[i]=='*')T1();elseif(A[i]=='+'||A[i]==')'||A[i]=='$')judge=0;return;elsejudge=1;}}elseif(A[i]=='+'||A[i]==')'||A[i]=='$')//判断当前输入符是否属于Follow(T1)return;elsejudge=1;}voidF(){if(A[i]=='('){match(i);if(A[i]=='('||A[i]=='d')E();if(A[i]==')')match(i);}elseif(A[i]=='d')match(i);elsejudge=1;}voidmatch(int&k){k++;}五、实验报告编制并调试程序程序，运行通过后，书写实验报告，报告包括以下内容。1.实验题目与要求2.总的设计思想，及环境语言、工具等3.数据结构与模块说明(功能与框图)4.源程序(核心代码)5.运行结果与运行情况6.总结