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

魏陈强23020092204168实验3递归下降法的语法分析器一、实验目的学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。二、实验内容用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。这里只要求实现部分产生式，文法的开始符号为program。（完整的源语言的文法定义见教材附录A.1，p394）program→blockblock→{stmts}stmts→stmtstmts|stmt→id=expr;|if(bool)stmt|if(bool)stmtelsestmt|while(bool)stmt|dostmtwhile(bool);|break;|blockbool→exprexpr|expr=expr|exprexpr|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}{stmtstmts}{id=expr;stmts}{id=num;stmts}{id=num;stmtstmts}{id=num;while(bool)stmtstmts}{id=num;while(expr=expr)stmtstmts}{id=num;while(id=expr)stmtstmts}{id=num;while(id=num)stmtstmts}{id=num;while(id=num)blockstmts}{id=num;while(id=num){stmts}stmts}．．．．．．．四、实验思路之前编写的词法分析器，能够将语句中的每一个词素都识别出来，因此，在此基础上，定义一个二维字符串数组finaltable[100][20]，用于存放由词法分析器提取出来的每个词素，比如，i=2，则finaltable[0]=”id”，finaltable[1]=”=”，finaltable[2]=”num”。并且，为了以后能够方便使用switch()case语句，另外再定义一个一维整型数组finaltableint[100]，用于存放一个数字和finaltable[100][20]中的字符串对应。这里，我们定义if=100，for=200，else=300，while=400，do=500，float=600，int=700，break=800，=17，==16，=15，==14，+=13，&&=12，||=11，}=10，{=9，；=8；)=7，(=6，==5，===4，!==3，/=2，id=1，keyword=0，num=99，*=18，-=19。然后依据语法分析的正则表达式，参照实验一类似中缀改后缀的写法以及课本40页的伪代码编写。相比词法分析器，词法分析的时候，是以单个字符为一个单位，而语法分析，我们以字符串为单位，这些字符串即finaltable[100][20]中的字符串。编写的过程中涉及几个问题，1、如何把每一步的迭代都显示出来？对于这个问题，可以在每个非终结符函数的开头输出对应的迭代即可。2、在应用文法的时候，应该首先消除左递归，这是至关重要的，该实验我们只要消除expr()和term()的左递归即可。3、if语句二义性处理。对于这个问题，我们只要再往后看一个字符串，看其是否是else，如果是，则匹配if(bool)stmtelsestmt，否则匹配if(bool)stmt。4、对于空选择，如何处理？一开始的时候，我选择暂时忽略。五、实验代码#includestdio.h#includestring.h#includectype.h/*if=100，for=200，else=300，while=400，do=500，float=600，int=700，break=800，=17，==16，=15，==14，+=13，&&=12，||=11，}=10，{=9，；=8；)=7，(=6，==5，===4，!==3，/=2，id=1，keyword=0，num=99，*=18，-=19*/char*keyword[8]={if,for,else,while,do,float,int,break};charkeywordtable[20][20],re_keywordtable[20][20];chardigittable[20][20],re_digittable[20][20];charotherchartable[20][20],re_otherchartable[20][20];charidtable[20][20],re_idtable[20][20];charnotetable[20][20];charfinaltable[100][20];intfinaltableint[100];charword[20];voidinitialize();voidalpha();voiddigit();voiderror();voidotherchar();voidnote();voidprint();voidprin();voidcheck();voidprogram();voidblock();voidstmts();voidstmt();voidBool();voidexpr();voidexpr1();voidterm();voidterm1();voidfactor();voidmatch(char*t);intdigit_num=0,keyword_num=0,otherchar_num=0,id_num=0,note_num=0;intredigit_num=1,rekeyword_num=1,reotherchar_num=1,reid_num=1;intfinal_num=0,finalnum=0;intflag_error=0;intflagerror=0;charlookahead;voidmain(){printf(请输入要分析的语句:\n);initialize();lookahead=getchar();while(1){if(isalpha(lookahead)){alpha();initialize();}elseif(isdigit(lookahead)){digit();initialize();}elseif(lookahead=='\t'||lookahead==''){;}elseif(lookahead=='\n')break;elseif(lookahead=='/'){lookahead=getchar();if(lookahead=='*'){note();initialize();}else{ungetc(lookahead,stdin);strcpy(finaltable[final_num],/);strcpy(otherchartable[otherchar_num++],/);finaltableint[final_num++]=2;initialize();}}else{otherchar();initialize();}lookahead=getchar();}check();if(flag_error==0){printf(词法分析结果如下:\n);print();prin();program();if(finalnum==final_num)printf(语法分析完成!\n);}}voidalpha(){inti=1,flag;charch;ch=lookahead;word[0]=ch;ch=getchar();while(isalpha(ch)||isdigit(ch)){word[i++]=ch;ch=getchar();}ungetc(ch,stdin);flag=0;for(i=0;i8;i++){if(strcmp(word,keyword[i])==0)flag=1;}if(flag==1){strcpy(keywordtable[keyword_num++],word);strcpy(finaltable[final_num],word);if(strcmp(word,if)==0)finaltableint[final_num++]=100;if(strcmp(word,for)==0)finaltableint[final_num++]=200;if(strcmp(word,else)==0)finaltableint[final_num++]=300;if(strcmp(word,while)==0)finaltableint[final_num++]=400;if(strcmp(word,do)==0)finaltableint[final_num++]=500;if(strcmp(word,float)==0)finaltableint[final_num++]=600;if(strcmp(word,int)==0)finaltableint[final_num++]=700;if(strcmp(word,break)==0)finaltableint[final_num++]=800;}else{strcpy(idtable[id_num++],word);strcpy(finaltable[final_num],id);finaltableint[final_num++]=1;}}voiddigit(){inti=1,flag;charch;ch=lookahead;word[0]=ch;ch=getchar();while(isalpha(ch)||isdigit(ch)){word[i++]=ch;ch=getchar();}ungetc(ch,stdin);flag=0;for(i=0;word[i]!='\0';i++){if(word[i]'0'||word[i]'9')flag=1;}if(flag==1){strcpy(idtable[id_num++],word);strcpy(finaltable[final_num],id);finaltableint[final_num++]=1;}else{strcpy(digittable[digit_num++],word);strcpy(finaltable[final_num],num);finaltableint[final_num++]=99;}}voidotherchar(){charch;ch=lookahead;switch(ch){case'!':{ch=getchar();if(ch=='='){strcpy(otherchartable[otherchar_num++],!=);strcpy(finaltable[final_num],!=);finaltableint[final_num++]=3;}else{ungetc(ch,stdin);error();}}break;case'=':{ch=getchar();if(ch=='='){strcpy(otherchartable[otherchar_num++],==);strcpy(finaltable[final_num],==);finaltableint[final_num++]=4;}else{strcpy(otherchartable[otherchar_num++],=);strcpy(finaltab