实验三递归下降法的语法分析器.doc

魏陈强 23020092204168实验3 递归下降法的语法分析器一、实验目的学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。二、实验内容用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。这里只要求实现部分产生式，文法的开始符号为program。（完整的源语言的文法定义见教材附录 A.1，p394）program blockblock stmts stmts stmt stmts | e stmt id = expr ; |if ( bool ) stmt|if ( bool) stmt else stmt|while (bool) stmt |do stmt while (bool ) ; |break ; |blockbool expr expr | expr expr | expr = expr | exprexpr expr + term | expr - term | termterm term * factor | term / factor | factorfactor ( expr ) | id | num三、实验要求个人完成，提交实验报告。实验报告中给出采用测试源代码片断，及其对应的最左推导过程（形式可以自行考虑）。测试程序片断：i = 2;while (i =100)sum = sum + i;i = i + 2; 对应的推导过程为：program block stmts stmt stmts id = expr ; stmts id = num; stmts id = num; stmt stmts id = num; while (bool) stmt stmts id = num; while (expr= expr) stmt stmts id = num; while (id = expr) stmt stmts id = num; while (id = num) stmt stmts id = num; while (id = num) block stmts id = num; while (id = num) stmts stmts 四、实验思路之前编写的词法分析器，能够将语句中的每一个词素都识别出来，因此，在此基础上，定义一个二维字符串数组finaltable10020，用于存放由词法分析器提取出来的每个词素，比如，i=2，则finaltable0=”id”，finaltable1=”=”，finaltable2=”num”。并且，为了以后能够方便使用switch() case 语句，另外再定义一个一维整型数组finaltableint100，用于存放一个数字和finaltable10020中的字符串对应。这里，我们定义if=100，for=200，else=300，while=400，do=500，float=600，int=700，break=800， = 17， = 15，= = 14，+ = 13，&=12，|=11，=10，=9，；=8；)=7，(=6，= = 5，= = 4，!= =3，/=2，id =1，keyword=0，num=99，*=18，- = 19。然后依据语法分析的正则表达式，参照实验一类似中缀改后缀的写法以及课本40页的伪代码编写。相比词法分析器，词法分析的时候，是以单个字符为一个单位，而语法分析，我们以字符串为单位，这些字符串即finaltable10020中的字符串。编写的过程中涉及几个问题，1、如何把每一步的迭代都显示出来？对于这个问题，可以在每个非终结符函数的开头输出对应的迭代即可。2、在应用文法的时候，应该首先消除左递归，这是至关重要的，该实验我们只要消除expr()和term()的左递归即可。3、if语句二义性处理。对于这个问题，我们只要再往后看一个字符串，看其是否是else，如果是，则匹配if ( bool) stmt else stmt，否则匹配if ( bool ) stmt。4、对于空选择，如何处理？一开始的时候，我选择暂时忽略。五、实验代码#include#include#include /* if=100，for=200，else=300，while=400，do=500，float=600，int=700，break=800， = 17， = 15，= = 14，+ = 13，&=12，|=11，=10，=9，；=8；)=7，(=6，= = 5，= = 4，!= =3，/=2，id =1，keyword=0，num=99，*=18，- = 19*/char *keyword8=if,for,else,while,do,float,int,break;char keywordtable2020,re_keywordtable2020;char digittable2020,re_digittable2020;char otherchartable2020,re_otherchartable2020;char idtable2020,re_idtable2020;char notetable2020;char finaltable10020;int finaltableint100;char word20;void initialize();void alpha();void digit();void error();void otherchar();void note();void print();void prin();void check();void program();void block();void stmts();void stmt();void Bool();void expr();void expr1();void term();void term1();void factor();void match(char *t);int digit_num=0,keyword_num=0,otherchar_num=0,id_num=0,note_num=0; int redigit_num=1,rekeyword_num=1,reotherchar_num=1,reid_num=1; int final_num=0,finalnum=0;int flag_error=0;int flagerror=0;char lookahead;void main()printf(请输入要分析的语句:n);initialize();lookahead=getchar();while(1)if(isalpha(lookahead)alpha();initialize();else if(isdigit(lookahead)digit();initialize();else if(lookahead=t|lookahead= );else if(lookahead=n)break;else if(lookahead=/)lookahead=getchar();if(lookahead=*)note();initialize();elseungetc(lookahead,stdin);strcpy(finaltablefinal_num,/);strcpy(otherchartableotherchar_num+,/);finaltableintfinal_num+=2;initialize();elseotherchar();initialize();lookahead=getchar();check();if(flag_error=0)printf(词法分析结果如下:n);print();prin();program();if(finalnum=final_num)printf(语法分析完成!n);void alpha()int i=1,flag;char ch;ch=lookahead;word0=ch;ch=getchar();while(isalpha(ch)|isdigit(ch)wordi+=ch;ch=getchar();ungetc(ch,stdin);flag=0;for(i=0;i8;i+)if(strcmp(word,keywordi)=0)flag=1;if(flag=1)strcpy(keywordtablekeyword_num+,word);strcpy(finaltablefinal_num,word);if(strcmp(word,if)=0)finaltableintfinal_num+=100;if(strcmp(word,for)=0)finaltableintfinal_num+=200;if(strcmp(word,else)=0)finaltableintfinal_num+=300;if(strcmp(word,while)=0)finaltableintfinal_num+=400;if(strcmp(word,do)=0)finaltableintfinal_num+=500;if(strcmp(word,float)=0)finaltableintfinal_num+=600;if(strcmp(word,int)=0)finaltableintfinal_num+=700;if(strcmp(word,break)=0)finaltableintfinal_num+=800;elsestrcpy(idtableid_num+,word);strcpy(finaltablefinal_num,id);finaltableintfinal_num+=1;void digit()int i=1,flag;char ch;ch=lookahead;word0=ch;ch=getchar();while(isalpha(ch)|isdigit(ch)wordi+=ch;ch=getchar();ungetc(ch,stdin);flag=0;for(i=0;wordi!=0;i+)if(wordi9)flag=1;if(flag=1)strcpy(idtableid_num+,word);strcpy(finaltablefinal_num,id);finaltableintfinal_num+=1;elsestrcpy(digittabledigit_num+,word);strcpy(finaltablefinal_num,num);finaltableintfinal_num+=99;void otherchar()char ch;ch=lookahead;switch(ch)case !:ch=getchar();if(ch=)strcpy(otherchartableotherchar_num+,!=);strcpy(finaltablefinal_num,!=);finaltableintfinal_num+=3;elseungetc(ch,stdin);error();break;case =:ch=getchar();if(ch=)strcpy(otherchartableotherchar_num+,=);strcpy(finaltablefinal_num,=);finaltableintfinal_num+=4;elsestrcpy(otherchartableotherchar_num+,=);strcpy(finaltablefinal_num,=);finaltableintfinal_num+=5;ungetc(ch,stdin);break;case (:strcpy(otherchartableotherchar_num+,();strcpy(finaltablefinal_num,();finaltableintfinal_num+=6; / ( 6break;case ):strcpy(otherchartableotherchar_num+,);strcpy(finaltablefinal_num,);finaltableintfinal_num+=7; / ) 7break;case ;:strcpy(otherchartableotherchar_num+,;);strcpy(finaltablefinal_num,;);finaltableintfinal_num+=8;/ ; 8break;case :strcpy(otherchartableotherchar_num+,);strcpy(finaltablefinal_num,);finaltableintfinal_num+=9;/ 9break;case :strcpy(otherchartableotherchar_num+,);strcpy(finaltablefinal_num,);finaltableintfinal_num+=10;/ 10break;case |:strcpy(otherchartableotherchar_num+,|);strcpy(finaltablefinal_num,|);finaltableintfinal_num+=11;/ | 11break;case &:strcpy(otherchartableotherchar_num+,&);strcpy(finaltablefinal_num,&);finaltableintfinal_num+=12;/& 12break;case +:strcpy(otherchartableotherchar_num+,+);strcpy(finaltablefinal_num,+);finaltableintfinal_num+=13;/ + 13break;case -:strcpy(otherchartableotherchar_num+,-);strcpy(finaltablefinal_num,-);finaltableintfinal_num+=19;/ - 19break;case :ch=getchar();if(ch=)strcpy(otherchartableotherchar_num+,=);strcpy(finaltablefinal_num,=);finaltableintfinal_num+=14;/ = 14elsestrcpy(otherchartableotherchar_num+,);strcpy(finaltablefinal_num,);finaltableintfinal_num+=15;/ 15ungetc(ch,stdin);break;case :ch=getchar();if(ch=)strcpy(otherchartableotherchar_num+,=);strcpy(finaltablefinal_num,=);finaltableintfinal_num+=16;/ = 16elsestrcpy(otherchartableotherchar_num+,);strcpy(finaltablefinal_num+,);finaltableintfinal_num+=17;/ 17ungetc(ch,stdin);break;case *:strcpy(finaltablefinal_num,*);finaltableintfinal_num+=18;/ * 18break;default:error();break;void error()flag_error=1;printf(出现错误,中止分析!n);void initialize()int i;for(i=0;i20;i+)wordi=0;void check()int i,j,flag;strcpy(re_keywordtable0,keywordtable0);for(i=1;ikeyword_num;i+)flag=0;for(j=0;jrekeyword_num;j+)if(strcmp(keywordtablei,re_keywordtablej)=0)flag=1;break;if(flag=0)strcpy(re_keywordtablerekeyword_num+,keywordtablei);strcpy(re_digittable0,digittable0);for(i=1;idigit_num;i+)flag=0;for(j=0;jredigit_num;j+)if(strcmp(digittablei,re_digittablej)=0)flag=1;break;if(flag=0)strcpy(re_digittableredigit_num+,digittablei);strcpy(re_otherchartable0,otherchartable0);for(i=1;iotherchar_num;i+)flag=0;for(j=0;jreotherchar_num;j+)if(strcmp(otherchartablei,re_otherchartablej)=0)flag=1;break;if(flag=0)strcpy(re_otherchartablereotherchar_num+,otherchartablei);strcpy(re_idtable0,idtable0);for(i=1;iid_num;i+)flag=0;for(j=0;jreid_num;j+)if(strcmp(idtablei,re_idtablej)=0)flag=1;break;if(flag=0)strcpy(re_idtablereid_num+,idtablei);void note()char ch;int i=0;ch=getchar();while(1)if(ch=*)ch=getchar();if(ch=/)break;elseungetc(ch,stdin);wordi+=ch;elsewordi+=ch;ch=getchar();strcpy(notetablenote_num+,word);void print()int i;/printf(Keywords:n);if(keyword_num!=0)for(i=0;irekeyword_num;i+)printf(n,re_keywordtablei);/printf(nDigits:n);if(digit_num!=0)for(i=0;iredigit_num;i+)printf(n,re_digittablei);/printf(nOtherchars:n);if(otherchar_num!=0)for(i=0;ireotherchar_num;i+)printf(n,re_otherchartablei);/printf(nId:n);if(id_num!=0)for(i=0;ireid_num;i+)printf(n,re_idtablei);if(note_num!=0)printf(注释:n);for(i=0;inote_num;i+)printf(%sn,notetablei);printf(词法分析完成!n);void prin()int i; finaltableintfinal_num=0;printf(语法分析结果如下：n);for(i=0;iblockn);block();if(flagerror=1)error();return;void block()if(flagerror=1)return;printf(block-stmtsn);match();stmts();match();void stmts()if(flagerror=1)return;if(finaltableintfinalnum=10)printf(stmts-nulln);return;printf(stmts-stmt stmtsn);stmt();stmts();void stmt()if(flagerror=1)return;switch(finaltableintfinalnum)case 1:printf(stmt-id=exprn);match(id);match(=);expr();match(;);break;case 100:match(if);match();Bool();match();stmt();if(strcmp(finaltablefinalnum,else)=0)printf(stmt-if(bool) stmt else stmtn);match(else);stmt();break;elseprintf(stmt-if(bool) stmtn);break;case 400:printf(stmt-while(bool) stmtn);match(while);match();Bool();match();stmt();break;case 500:printf(stmt-do stmt while(bool)n);match(do);stmt();match(while);match();Bool();match();match(;);break;case 800:printf(stmt-break;n);match(break);match(;);break;default:printf(stmt-blockn);block();break;void Bool()if(flagerror=1)return;expr();switch(finaltableintfinalnum)case 17:printf(bool-exprexprn);match(expr=exprn);match(exprexprn);match();expr();break;case 14:printf(bool-expr=exprn);match(=);expr();break;default:printf(bool-exprn);expr();break;void expr()if(flagerror=1)return;printf(expr-term expr1n);term();expr1();void expr1()if(flagerror=1)return;switch(finaltableintfinalnum)case 13:printf(expr1-+term expr1n);match(+);term();expr1();break;case 19:printf(expr1-term expr1n);match(-);term();expr1();break;default:printf(expr1-nulln);return;void term()if(flagerror=1)return;printf(term-factor term1n);factor();term1();void term1()if(flagerror=1)return;switch(finaltableintfinalnum)case 18:printf(term1-*factor term1n);match(*);factor();term1();break;case 2:printf(term1-/factor term1n);match(/);factor();term1();break;default:printf(term1-nulln);return;void factor()if(flagerror=1)return;switch(finaltableintfinalnum)case 6:printf(fatcor-(expr)n);match();expr();match();break;case 1:printf