语法分析程序的设计与实现

语法分析程序的设计与实现一、实验目的及要求1、目的（1）进一步理解和掌握语法分析中的递归下降分析法。（2）进一步掌握对文法消除左递归和公共左因子使之成为LL(1)文法的方法。（3）学习用自己熟悉的程序语言如C/C++等实现对较简单语言的语法分析程序。2、要求（1）把原文法改写为LL(1)文法。（2）采用递归下降分析法设计本程序。二、实验使用的主要设备（含软件系统）WindowsXP、VisualC++6.0三、实验内容假设待分析的简单语言的语法：（1）程序→begin语句表end（2）语句表→语句表;语句|语句（3）语句→赋值语句（4）赋值语句→id:=表达式（5）表达式→表达式+项|表达式-项|项（6）项→项*因子|项/因子|因子（7）因子→id|num|(表达式)编制程序，对以下语句进行分析：（1）begina:=9;x:=2*3;b:=a+xend（正确）（2）x:=a+b*cend（错误）如果是文法正确的句子，则输出成功信息，显示“success！”；否则，输出错误信息，显示“error!”四、实验过程1、将原文法简化为方便起见，将原文法用字母简化表示，用P代表程序，用L代表语句表，用S代表语句，用d代表end，用A代表赋值语句，用E代表表达式，用T代表项，用F代表因子，用i代表id，用n代表num（数据）。则将文法简化为G[P]：（1）P→bLd（2）L→L;S|S（3）S→A（4）A→i:=E（5）E→E+T|E-T|T（6）T→T*F|T/F|F（7）F→i|n|(E)2、将文法G[P]改写为LL(1)文法由于递归下降分析法要求文法为LL(1)文法，而在文法G[P]中（2）、（5）、（6）产生式含有左递归（无公共左因子），需要消除左递归。改写后的文法G’[P]：（1）P→bLd（2）L→SL’（3）L’→;SL’|ε（4）S→A（5）A→i:=E（6）E→TE’（7）E’→+TE’|-TE’|ε（8）T→FT’（9）T’→*FT’|/FT’|ε（10）F→i|n|(E)五、编程思路假设所分析的语言已经过词法分析后为正确的单词序列，并将各单词以单词值（所有标识符的值用字符“i”表示、数据用字符“n”表示、begin用字符“b”表示、end用字符“d”表示）。这样，程序begina:=9;x:=2*3;b:=a+xend经词法分析后，生成的单词表如下：b,i:=,n,;,i:=,n,*,n,;,i:=,i,+,i,d。把上述单词表存放于一个数组str中，str中的字符串就是要分析的语言。为每个非终结符构造一个子程序，每个子程序的函数体按非终结符的候选式分情况展开，遇到终结符直接匹配，遇到非终结符就调用相应非终结符的子程序，直到所有非终结符都展开为终结符并得到匹配为止，若达到这一步表明分析成功，否则有语法错误。六、程序流程图1、主程序图1主程序流程图从单词表取下一个单词进行匹配（调用match()函数）是begin?调用语句表函数L()匹配成功?从单词表取下一个单词是end?分析成功，输出success结束语法错误，输出errorYNYNYN（其他函数的程序流程图略）七、实验参考程序（自编）//parser.c（递归下降分析程序）#includestdio.h#includestdlib.h#includestring.h#includeiostream.h//全局变量inti=0;//用于数组str的下标char*lookahead;//用于存放所取到的单词（向前看单词）//声明函数char*getnexttoken();voidL();voidS();voidLL();voidA();voidT();voidE();voidEE();voidTT();voidF();voiderror();voidmatch(char*ch);/*假设词法分析后,句子各单词正确。直接形成单词表，用数组str存放单词的值。其中：b代表begin，i代表标识符id，n代表数据num，d代表end。*///char*str[100]={i:=,i,+,i,*,i,d,#};//对应句子：x:=a+b*cend#//对应句子：begina:=9;x=2*3;b:=a+xend#char*str[100]={b,i:=,n,;,i:=,n,*,n,;,i:=,i,+,i,d,#};voidmain(){lookahead=getnexttoken();//取下一个单词if(lookahead==b)//b代表begin{match(b);L();//调用语句列表函数if(lookahead==d)//d代表endprintf(success!\n);elseerror();}elseerror();}//各个函数的实现char*getnexttoken(){returnstr[i++];}voidL(){S();LL();}voidS(){A();}voidLL(){if(lookahead==;){match(;);S();LL();//递归调用}}voidA(){if(lookahead==i:=){match(i:=);//匹配成功E();}}voidE(){T();EE();}voidEE(){if(lookahead==+){match(+);T();EE();//递归调用}elseif(lookahead==-){match(-);T();EE();//递归调用}}voidT(){F();TT();}voidTT(){if(lookahead==*){match(*);F();TT();//递归调用}elseif(lookahead==/){match(/);F();TT();}}voidF(){if(lookahead==(){match(();E();if(lookahead==))match());elseerror();}elseif(lookahead==i)match(i);elseif(lookahead==n)match(n);elseerror();}voiderror(){printf(error!\n);exit(1);}voidmatch(char*ch){if(ch==lookahead)//与当前符号相同，即匹配{lookahead=getnexttoken();//取下一个符号//return;}elseerror();//不匹配,进行出错处理}测试//对应句子：begina:=9;x=2*3;b:=a+xend#//char*str[100]={b,i:=,n,;,i:=,n,*,n,;,i:=,i,+,i,d,#};char*str[100]={i:=,i,+,i,*,i,d,#};//对应句子：x:=a+b*cend#