魏陈强 23020092204168实验3 递归下降法的语法分析器一、实验目的学习用递归下降法构造语法分析器的原理，掌握递归下降法的编程方法。

二、实验内容用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。

这里只要求实现部分产生式，文法的开始符号为program。

（完整的源语言的文法定义见教材附录 A.1，p394）program→ blockblock→{stmts }stmts→stmt stmts |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| expr >= expr| exprexpr→ expr + term| expr - term| termterm→ term * factor| term / factor| factorfactor→ ( e xpr ) | 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(e xpr<= 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 }⇒．．．．．．．四、实验思路之前编写的词法分析器，能够将语句中的每一个词素都识别出来，因此，在此基础上，定义一个二维字符串数组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)stmt else stmt，否则匹配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"}; char keywordtable[20][20],re_keywordtable[20][20];char digittable[20][20],re_digittable[20][20];char otherchartable[20][20],re_otherchartable[20][20];char idtable[20][20],re_idtable[20][20];char notetable[20][20];char finaltable[100][20];int finaltableint[100];char word[20];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();}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");}}void alpha(){int i=1,flag;char ch;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;}}void digit(){int i=1,flag;char ch;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;}}void otherchar(){char ch;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;} // >= 14else{strcpy(otherchartable[otherchar_num++],">");strcpy(finaltable[final_num],">");finaltableint[final_num++]=15; // > 15ungetc(ch,stdin);}}break;case '<':{ch=getchar();if(ch=='='){strcpy(otherchartable[otherchar_num++],"<=");strcpy(finaltable[final_num],"<=");finaltableint[final_num++]=16;} // <= 16else{strcpy(otherchartable[otherchar_num++],"<");strcpy(finaltable[final_num++],"<");finaltableint[final_num++]=17; //< 17ungetc(ch,stdin);}}break;case '*':strcpy(finaltable[final_num],"*");finaltableint[final_num++]=18; // * 18break;default:error();break;}}void error(){flag_error=1;printf("出现错误,中止分析!\n");}void initialize(){int i;for(i=0;i<20;i++){word[i]='\0';}}void check(){int i,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]);}}void note(){char ch;int i=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);}void print(){int i;//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");}void prin(){int i;finaltableint[final_num]='\0';printf("语法分析结果如下：\n");for(i=0;i<final_num;i++)printf("%s",finaltable[i]);printf("\n语法分析过程如下:\n");}void program(){printf("program-->block\n");block();if(flagerror==1){error();return;}}void block(){if(flagerror==1){return;}printf("block-->{stmts}\n");match("{");stmts();match("}");}void stmts(){if(flagerror==1){return;}if(finaltableint[finalnum]==10){printf("stmts-->null\n");return;}printf("stmts-->{stmt stmts}\n");stmt();stmts();}void stmt(){if(flagerror==1){return;}switch(finaltableint[finalnum]){case 1:printf("stmt-->id=expr\n");match("id");match("=");expr();match(";");break;case 100:match("if");match("(");Bool();match(")");stmt();if(strcmp(finaltable[finalnum],"else")==0){printf("stmt-->if(bool) stmt else stmt\n");match("else");stmt();break;}else{printf("stmt-->{if(bool) stmt\n");break;}case 400:printf("stmt-->while(bool) stmt\n");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(";");case 800:printf("stmt-->break;\n");match("break");match(";");break;default:printf("stmt-->block\n");block();break;}}void Bool(){if(flagerror==1){return;}expr();switch(finaltableint[finalnum]){case 17:printf("bool-->expr<expr\n");match("<");expr();break;case 16:printf("bool-->expr<=expr\n");match("<=");expr();break;case 15:printf("bool-->expr>expr\n");match(">");expr();break;case 14:printf("bool-->expr>=expr\n");match(">=");expr();break;default:printf("bool-->expr\n");expr();}}void expr(){if(flagerror==1){return;}printf("expr-->term expr1\n");term();expr1();}void expr1(){if(flagerror==1){return;}switch(finaltableint[finalnum]){case 13:printf("expr1-->+term expr1\n");match("+");term();expr1();break;case 19:printf("expr1-->-term expr1\n");match("-");term();expr1();break;default:printf("expr1-->null\n");return;}}void term(){if(flagerror==1){}printf("term-->factor term1\n");factor();term1();}void term1(){if(flagerror==1){return;}switch(finaltableint[finalnum]){case 18:printf("term1-->*factor term1\n");match("*");factor();term1();break;case 2:printf("term1-->/factor term1\n");match("/");factor();term1();break;default:printf("term1-->null\n");return;}}void factor(){if(flagerror==1){return;}switch(finaltableint[finalnum]){case 6:printf("fatcor-->(expr)\n");match("(");expr();match(")");case 1:printf("factor-->id\n");match("id");break;case 99:printf("factor-->num\n");match("num");break;default:flagerror=1;break;}}void match(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：定义字符串的时候出错，写成char t;解决办法：正确的定义：Char *t;遇到的问题2：我使用词法分析所得的每一个词素作为语法分析的单位，但是这些都是字符串，而switch()case 语句只能用int型的。