内容：

实现以下语法的递归下降分析：

示例：

对于以下代码给出其递归下降语法分析过程：

{i=2;while(i<=100){sum=sum+i;i=i+2;}
}

具体实现：

• 首先对上下文无关文法进行检查，消除左递归和左公共因子，从逻辑上检测避免死循环和低效率处理。
• 采用每个产生式的左边的文法符号对应一个函数或过程的形式，编写程序实现一个递归下降分析器。
• 语法分析是在词法分析的基础上进行的（关于词法分析的实现，具体参见我的上篇博客->【编译原理与技术】词法分析器（C++实现））。

C++代码：

#include<cstdio>
#include<cstring>
#include<ctype.h>
#include<iostream>
using namespace std;
char prog[1000],ch,ch1,token[1000],filename[30];
int p=0,sym=0,n,line=1;
FILE *fpin;
const char *keyword[22]={"if","else","while","do","main","int","float","for""double","return","const","void","continue","break","char","signed","enum","long","switch","case","auto","unsigned"};
char keywordtable[20][20];                 //存放保留字
char digittable[20][20];                   //存放数字
char otherchartable[20][20];           		//存放其他字符
char 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 program();
void block();
void stmts();
void stmt();
void Bool();
void expr();
void expr1();
void term();
void term1();
void factor();
void YufaBegin();
void CifaBegin();
void GetToken();
void match(string str);
int digit_num=0,keyword_num=0,otherchar_num=0,id_num=0,note_num=0;
int final_num=0,finalnum=0;
int flag_error=0;                                  //0表示没有错误，1表示有错误 
int flagerror=0;int main()
{cout<<"请输入源文件名:";while(1){cin>>filename;if((fpin=fopen(filename,"r"))!=NULL)//只读	{ 	break;}		elsecout<<"文件输入错误！请输入源文件名：";	}//将文件内容存储到prog中 do{ch=fgetc(fpin);prog[p++]=ch;}while(ch!=EOF);//调用词法分析部分 printf("-----------------\n");printf("词法分析结果如下:\n");rewind(fpin);ch=fgetc(fpin);CifaBegin();//调用语法分析部分rewind(fpin); ch=fgetc(fpin);		initialize();YufaBegin();return 0;
}  
void YufaBegin(){p=0;while(1){	ch=prog[p++];  if(ch==EOF) break;            if(isalpha(ch)||ch=='_')                    //a-z或A-Z时返回非零值(不一定是1)，否则返回零 {alpha();initialize();}else if(isdigit(ch))               //用来判断字符lookahead是否为数字 {digit();initialize();}else if(ch=='\t'||ch==' '||ch=='\n'){continue;}else if(ch=='/'){ch=prog[p++];if(ch=='*'||ch=='/'){note();initialize();}else{p--;                          					//把一个字符退回到输入流中//lookahead是写入的字符，stdin是文件流指针 strcpy(finaltable[final_num],"/");                //将"/"放到终结符号表中 strcpy(otherchartable[otherchar_num++],"/");      //将"/"放到其他符号表中 finaltableint[final_num++]=2;                     //"/"的序号是2 initialize();}}/*else if(ch=='#'){break;}*/else{otherchar();initialize();}}if(flag_error==0){finaltableint[final_num]='\0';printf("--------------------");printf("\n语法分析过程如下:\n");program();if(finalnum==final_num)printf("语法分析完成！");		}
}  
void alpha()
{int i=0,flag;word[i++]=ch;ch=prog[p++];while(isalpha(ch)||isdigit(ch))                                //将标识符放到word数组中 {word[i++]=ch;ch=prog[p++];}	p--;flag=0;for(i=0;i<21;i++){if(strcmp(word,keyword[i])==0){flag=1;break;}}//在这里我只实现了部分保留字，大家可根据要求自行增删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 initialize()
{for(int i=0;i<20;i++){word[i]='\0';}
}
void digit()
{int i=0,flag;word[i++]=ch;ch=prog[p++];while(isdigit(ch)){word[i++]=ch;ch=prog[p++];}	p--;strcpy(digittable[digit_num++],word);strcpy(finaltable[final_num],"num");//数字数组，序号为99 finaltableint[final_num++]=99;}	
void note()
{int i=0;while(1){if(ch=='*'){ch=prog[p++];if(ch=='/')break;else{p--;word[i++]=ch;	}  }else if(ch=='\n'){break;}else{word[i++]=ch;}ch=prog[p++];}strcpy(notetable[note_num++],word);//将注释的内容放入注释表 
}
void otherchar()
{switch(ch){case '!':{ch=prog[p++];if(ch=='='){strcpy(otherchartable[otherchar_num++],"!=");strcpy(finaltable[final_num],"!=");finaltableint[final_num++]=3;}else{p--;error();}}break;case '=':{ch=prog[p++];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;p--;}}break;case '(':strcpy(otherchartable[otherchar_num++],"(");strcpy(finaltable[final_num],"(");finaltableint[final_num++]=6;break;case ')':strcpy(otherchartable[otherchar_num++],")");strcpy(finaltable[final_num],")");finaltableint[final_num++]=7;break;case ';':strcpy(otherchartable[otherchar_num++],";");strcpy(finaltable[final_num],";");finaltableint[final_num++]=8;break;case '{':strcpy(otherchartable[otherchar_num++],"{");strcpy(finaltable[final_num],"{");finaltableint[final_num++]=9;break;case '}':strcpy(otherchartable[otherchar_num++],"}");strcpy(finaltable[final_num],"}");finaltableint[final_num++]=10;break;case '|':{ch=prog[p++];if(ch=='|'){strcpy(otherchartable[otherchar_num++],"||");strcpy(finaltable[final_num],"||");finaltableint[final_num++]=11;}else{p--;error();}} break;case '&':{ch=prog[p++];if(ch=='&'){strcpy(otherchartable[otherchar_num++],"&&");strcpy(finaltable[final_num],"&&");finaltableint[final_num++]=12;}else{p--;error();}} break;case '+':strcpy(otherchartable[otherchar_num++],"+");strcpy(finaltable[final_num],"+");finaltableint[final_num++]=13;break;case '-':strcpy(otherchartable[otherchar_num++],"-");strcpy(finaltable[final_num],"-");finaltableint[final_num++]=19;break;case '>':{ch=prog[p++];if(ch=='='){strcpy(otherchartable[otherchar_num++],">=");strcpy(finaltable[final_num],">=");finaltableint[final_num++]=14;}else{strcpy(otherchartable[otherchar_num++],">");strcpy(finaltable[final_num],">");finaltableint[final_num++]=15;p--;}}break;case '<':{ch=prog[p++];if(ch=='='){strcpy(otherchartable[otherchar_num++],"<=");strcpy(finaltable[final_num],"<=");finaltableint[final_num++]=16;}else{strcpy(otherchartable[otherchar_num++],"<");strcpy(finaltable[final_num],"<");finaltableint[final_num++]=17;p--;}}break;case '*':strcpy(otherchartable[otherchar_num++],"*");strcpy(finaltable[final_num],"*");finaltableint[final_num++]=18;break;default:error();break;}
}
void error()
{flag_error=1;printf("出现错误，停止分析！\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;}//cout<<"stmts():"<<finaltableint[finalnum]<<endl;if(finaltableint[finalnum]==10){printf("stmts-->null\n");return;}printf("stmts-->stmt stmts\n");stmt();stmts();
}
void stmt()
{if(flagerror==1){return;}//cout<<"stmt():"<<finaltableint[finalnum]<<endl;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(")");break;case 800:printf("stmt-->break\n");match("break");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();break;}
}
void expr()
{if(flagerror==1){return;}printf("expr-->term expr1\n");term();expr1();
}
void expr1()
{if(flagerror==1){return;}//cout<<"expr1():"<<finaltableint[finalnum]<<endl;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){return;}printf("term-->factor term1\n");factor();term1();
} 
void term1()
{if(flagerror==1){return;}//cout<<"term1():"<<finaltableint[finalnum]<<endl;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;}//cout<<"factor():"<<finaltableint[finalnum]<<endl;switch(finaltableint[finalnum]){case 6:printf("factor-->(expr)\n");match("(");expr();match(")");break;case 1:printf("factor-->id\n");match("id");break;case 99:printf("factor-->num\n");match("num");break;default:flagerror=1;break;}
}
void match(string str)
{char cha[20];for(int i=0;i<20;i++){cha[i]='\0';}for(int k=0;k<str.length();k++){cha[k]=str[k];}//cout<<finaltable[finalnum]<<endl;//cout<<cha<<endl;if(strcmp(finaltable[finalnum],cha)==0){//cout<<"1"<<endl;}else{flagerror=1;return;}finalnum++;
}//--------------
//词法分析器部分 
void CifaBegin()
{p=0;do {GetToken();//启动字符识别函数 //if(ch==EOF) break; switch(sym)//打印字符状态 {case 1:cout<<"("<<line<<" "<<token<<" "<<"标识符"<<")"<<endl;break;case 2:cout<<"("<<line<<" "<<token<<" "<<"保留字"<<")"<<endl;break;case 3:cout<<"("<<line<<" "<<token<<" "<<"整型"<<")"<<endl;break;case 31:cout<<"("<<line<<" "<<token<<" "<<"浮点型"<<")"<<endl;break;case 32:cout<<"("<<line<<" "<<token<<"S"<<" "<<"短类型"<<")"<<endl;break;case 33:cout<<"("<<line<<" "<<token<<"L"<<" "<<"长类型"<<")"<<endl;break;case 34:cout<<"("<<line<<" "<<token<<"O"<<" "<<"八进制数"<<")"<<endl;break;case 35:cout<<"("<<line<<" "<<token<<"H"<<" "<<"十六进制数"<<")"<<endl;break;case 4:cout<<"("<<line<<" "<<token<<" "<<"特殊符号"<<")"<<endl;break;case -1:cout<<"("<<line<<" "<<"错误！"<<")"<<endl;break;default:break;}}while(ch!=EOF);p=0;
}
void GetToken() 
{sym=0;//先把token[]数组清空 for (n=0;n<1000;n++){token[n]='\0';}n=0;ch=prog[p++];ch1=prog[p];//跳过空格，回车，tab的识别 while(ch==' '||ch=='\t'){ch=prog[p++];}if(ch=='\n'){line++;return;}if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch=='_')) {//标识符 状态1sym=1;do{token[n++]=ch;ch=prog[p++];}while ((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9'));//比较标识符与keyword的关键字是否相同，若相同转为状态2for(n=0;n<2;n++){if(strcmp(token,keyword[n])==0){sym=2;break;	}}p--;return;}else if (ch>='0'&&ch<='9') {	//识别到数字，置状态为3sym=3;do{	token[n++]=ch;ch=prog[p++];if(ch=='.'){sym=31;token[n++]=ch;ch=prog[p++];}if(ch=='S'){sym=32;ch=prog[p++];} if(ch=='L'){sym=33;ch=prog[p++];}if(ch=='O'){sym=34;ch=prog[p++];}	if(ch=='H'){sym=35;ch=prog[p++];}		}while(ch>='0'&&ch<='9'); p--;return;}//跳过注释的内容 else if(ch=='/' && ch1=='*'){	p++;do{ch=prog[p++];ch1=prog[p++];if(ch=='\n'){line++;}}while(ch!='*'||ch1!='/');return;}else if(ch=='/'&& ch1=='/'){p++;do{ch=prog[p++];}while(ch!='\n');line++;return;}else if(ch=='='&& ch1=='='){p++;sym=4;token[0]='=';token[1]='=';return;}else if(ch=='<'&& ch1=='='){p++;sym=4;token[0]='<';token[1]='=';return;}else if(ch=='>'&& ch1=='='){p++;sym=4;token[0]='>';token[1]='=';return;}else if(ch=='!'&& ch1=='='){p++;sym=4;token[0]='!';token[1]='=';return;}		else if(ch=='&'&& ch1=='&'){p++;sym=4;token[0]='&';token[1]='&';return;}	else if(ch=='|'&& ch1=='|'){p++;sym=4;token[0]='|';token[1]='|';return;}else {switch(ch)//识别关键符号 {	case '=':case '<':case '>':case '/':case '+':case '-':case '*':case '{':case '}':case ';':case '(':case ')':case ',':case '\'':case '\"':sym=4;token[0]=ch;break;default:sym=-1;break;}}return;}

运行结果：