目录
- 内容：
-
- 示例：
- 具体实现：
-
- C++代码：
- 运行结果：
内容：
实现以下语法的递归下降分析：
示例：
对于以下代码给出其递归下降语法分析过程：
{
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;
}
else
cout<<"文件输入错误！请输入源文件名：";
}
//将文件内容存储到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=='_'))
{
//标识符 状态1
sym=1;
do{
token[n++]=ch;
ch=prog[p++];
}while ((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9'));
//比较标识符与keyword的关键字是否相同，若相同转为状态2
for(n=0;n<2;n++)
{
if(strcmp(token,keyword[n])==0){
sym=2;
break;
}
}
p--;
return;
}
else if (ch>='0'&&ch<='9')
{
//识别到数字，置状态为3
sym=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;
}
运行结果：