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

魏陈强23020232204168实验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 →expr<expr| 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;}}对应的推导过程为：programblock{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、对于空选择，如何处理？一开始的时候，我选择暂时忽略。五、实验代码#include<stdio.h>#include<string.h>#include<ctype.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;i<8;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(finaltable[final_num],"="); finaltableint[final_num++]=5; ungetc(ch,stdin); } } break; case'(': strcpy(otherchartable[otherchar_num++],"("); strcpy(finaltable[final_num],"("); finaltableint[final_num++]=6;//(6 break; case')': strcpy(otherchartable[otherchar_num++],")"); strcpy(finaltable[final_num],")"); finaltableint[final_num++]=7;//)7 break; case';': strcpy(otherchartable[otherchar_num++],";"); strcpy(finaltable[final_num],";"); finaltableint[final_num++]=8; //;8 break; case'{': strcpy(otherchartable[otherchar_num++],"{"); strcpy(finaltable[final_num],"{"); finaltableint[final_num++]=9; //{9 break; case'}': strcpy(otherchartable[otherchar_num++],"}"); strcpy(finaltable[final_num],"}"); finaltableint[final_num++]=10; //}10 break; case'||': strcpy(otherchartable[otherchar_num++],"||"); strcpy(finaltable[final_num],"||"); finaltableint[final_num++]=11; //||11 break; case'&&': strcpy(otherchartable[otherchar_num++],"&&"); strcpy(finaltable[final_num],"&&"); finaltableint[final_num++]=12; //&&12 break; case'+': strcpy(otherchartable[otherchar_num++],"+"); strcpy(finaltable[final_num],"+"); finaltableint[final_num++]=13; //+13 break; case'-': strcpy(otherchartable[otherchar_num++],"-"); strcpy(finaltable[final_num],"-"); finaltableint[final_num++]=19; //-19 break; case'>': { ch=getchar(); if(ch=='=') { strcpy(otherchartable[otherchar_num++],">="); strcpy(finaltable[final_num],">="); finaltableint[final_num++]=14; } //>=14 else { strcpy(otherchartable[otherchar_num++],">"); strcpy(finaltable[final_num],">"); finaltableint[final_num++]=15; //>15 ungetc(ch,stdin); } } break; case'<': { ch=getchar(); if(ch=='=') { strcpy(otherchartable[otherchar_num++],"<="); strcpy(finaltable[final_num],"<="); finaltableint[final_num++]=16; } //<=16 else { strcpy(otherchartable[otherchar_num++],"<"); strcpy(finaltable[final_num++],"<"); finaltableint[final_num++]=17; //<17 ungetc(ch,stdin); } } break; case'*': strcpy(finaltable[final_num],"*"); finaltableint[final_num++]=18; //*18 break; default: error();break; }}voiderror(){ flag_error=1; printf("出现错误,中止分析!\n");}voidinitialize(){ inti; for(i=0;i<20;i++) { word[i]='\0'; }}voidcheck(){ inti,j,flag; strcpy(re_keywordtable[0],keywordtable[0]); for(i=1;i<keyword_num;i++) { flag=0; for(j=0;j<rekeyword_num;j++) { if(strcmp(keywordtable[i],re_keywordtable[j])==0) { flag=1; break; } } if(flag==0) strcpy(re_keywordtable[rekeyword_num++],keywordtable[i]); } strcpy(re_digittable[0],digittable[0]); for(i=1;i<digit_num;i++) { flag=0; for(j=0;j<redigit_num;j++) { if(strcmp(digittable[i],re_digittable[j])==0) { flag=1; break; } } if(flag==0) strcpy(re_digittable[redigit_num++],digittable[i]); } strcpy(re_otherchartable[0],otherchartable[0]); for(i=1;i<otherchar_num;i++) { flag=0; for(j=0;j<reotherchar_num;j++) { if(strcmp(otherchartable[i],re_otherchartable[j])==0) { flag=1; break; } } if(flag==0) strcpy(re_otherchartable[reotherchar_num++],otherchartable[i]); } strcpy(re_idtable[0],idtable[0]); for(i=1;i<id_num;i++) { flag=0; for(j=0;j<reid_num;j++) { if(strcmp(idtable[i],re_idtable[j])==0) { flag=1; break; } } if(flag==0) strcpy(re_idtable[reid_num++],idtable[i]); }}voidnote(){ charch; inti=0; ch=getchar(); while(1) { if(ch=='*') { ch=getchar(); if(ch=='/') break; else { ungetc(ch,stdin); word[i++]=ch; } } else { word[i++]=ch; } ch=getchar(); } strcpy(notetable[note_num++],word);}voidprint(){ inti; //printf("Keywords:\n"); if(keyword_num!=0) for(i=0;i<rekeyword_num;i++) printf("<%s,>\n",re_keywordtable[i]); //printf("\nDigits:\n"); if(digit_num!=0) for(i=0;i<redigit_num;i++) printf("<number,%s>\n",re_digittable[i]); //printf("\nOtherchars:\n"); if(otherchar_num!=0) for(i=0;i<reotherchar_num;i++) printf("<comparison,%s>\n",re_otherchartable[i]); //printf("\nId:\n"); if(id_num!=0) for(i=0;i<reid_num;i++) printf("<id,%s>\n",re_idtable[i]); if(note_num!=0) { printf("注释:\n"); for(i=0;i<note_num;i++) printf("%s\n",notetable[i]); } printf("词法分析完成!\n");}voidprin(){ inti;finaltableint[final_num]='\0'; printf("语法分析结果如下：\n"); for(i=0;i<final_num;i++) printf("%s",finaltable[i]); printf("\n语法分析过程如下:\n");}voidprogram(){ printf("program-->block\n"); block(); if(flagerror==1) { error(); return; }}voidblock(){ if(flagerror==1) { return; } printf("block-->{stmts}\n"); match("{"); stmts(); match("}");}voidstmts(){ if(flagerror==1) { return; } if(finaltableint[finalnum]==10) { printf("stmts-->null\n"); return; } printf("stmts-->{stmtstmts}\n"); stmt(); stmts();}voidstmt(){ if(flagerror==1) { return; } switch(finaltableint[finalnum]){ case1: printf("stmt-->id=expr\n"); match("id"); match("="); expr(); match(";"); break; case100: match("if"); match("("); Bool(); match(")"); stmt(); if(strcmp(finaltable[finalnum],"else")==0) { printf("stmt-->if(bool)stmtelsestmt\n"); match("else"); stmt(); break; } else { printf("stmt-->{if(bool)stmt\n"); break; } case400: printf("stmt-->while(bool)stmt\n"); match("while"); match("("); Bool(); match(")"); stmt(); break; case500: printf("stmt-->dostmtwhile(bool)\n"); match("do"); stmt(); match("while"); match("("); Bool(); match(")"); match(";"); break; case800: printf("stmt-->break;\n"); match("break"); match(";"); break; default: printf("stmt-->block\n"); block(); break; }}voidBool(){ if(flagerror==1) { return; } expr(); switch(finaltableint[finalnum]){ case17: printf("bool-->expr<expr\n"); match("<"); expr(); break; case16: printf("bool-->expr<=expr\n"); match("<="); expr(); break; case15: printf("bool-->expr>expr\n"); match(">"); expr(); break; case14: printf("bool-->expr>=expr\n"); match(">="); expr(); break; default: printf("bool-->expr\n"); expr(); break; }}voidexpr(){ if(flagerror==1) { return; } printf("expr-->termexpr1\n"); term(); expr1();}voidexpr1(){ if(flagerror==1) { return; } switch(finaltableint[finalnum]){ case13: printf("expr1-->+termexpr1\n"); match("+"); term(); expr1(); break; case19: printf("expr1-->-termexpr1\n"); match("-"); term(); expr1(); break; default: printf("expr1-->null\n"); return; }}voidterm(){ if(flagerror==1) { return; } printf("term-->factorterm1\n"); factor(); term1();}voidterm1(){ if(flagerror==1) { return; } switch(finaltableint[finalnum]){ case18: printf("term1-->*factorterm1\n"); match("*"); factor(); term1(); break; case2: printf("term1-->/factorterm1\n"); match("/"); factor(); term1(); break; default: printf("term1-->null\n"); return; }}voidfactor(){ if(flagerror==1) { return; } switch(finaltableint[finalnum]){ case6: printf("fatcor-->(expr)\n"); match("("); expr(); match(")"); break; case1: printf("factor-->id\n"); match("id"); break; case99: printf("factor-->num\n"); match("num"); break; default: flagerror=1; break; }}voidmatch(char*t){ if(strcmp(finaltable[finalnum],t)==0) ; else { flagerror=1; return; } finalnum++;}六、实验结果对于正确的语句：{i=2;while(i<=100){sum=sum+i;i=i+2;}}结果：对于不正确的语句：(while之后多了一个；){i=2;while(i<=100);i=i+2;}结果：七、实验总结遇到的问题1：定义字符串的时候出错，写成chart;解决方法：正确的定义：Char*t;遇到的问题2：我使用词法分析所得的每一个词素作为语法分析的单位，但是这些都是字符串，而switch()case语句只能用int型的。解决方法：对应于存放词素的fina