递归下降分析法

article/2025/10/15 6:19:03

介绍：

递归下降分析法是针对LL(1)文法的一种语法分析方法；
通过对文法的消除左递归，提取左公因子，对各个产生式和非终结符求first()和follow()集，通过first()和follow()集构造该文法的预测分析表，当这个预测分析表中不存在多重定义项，那么这个文法就是LL(1)文法，可以通过递归下降分析法来判断某个句子是否可以结果这个文法得到。

实现：

文法：
- E->TE’ E’->+TE’ | 空串
- T->FT’ T’->*FT’ | 空串
- F->i | (E)
预测分析表：
代码：

#include<iostream>
#include<string>
using namespace std;
string instring="i+i*i#";
void advance(){cout<<instring[0]<<"被匹配"<<endl;instring=instring.substr(1);
}
void error(){cout<<"出错"<<endl;
}void E();
void Ep();
void Tp();
void T();
void F();void E(){cout<<"E被使用"<<endl; switch(instring[0]){case 'i':case '(':T();Ep();break;case '+':case '*':case '#':case ')':error();}
} void Ep(){cout<<"Ep被使用"<<endl;switch(instring[0]){case '+':advance();T();Ep();break;case ')':case '#':break;case 'i':case '*':case '(':error();	}
}void T(){cout<<"T被使用"<<endl;switch(instring[0]){case 'i':case '(':F();Tp();break;case '+':case '*':case ')':case '#':error(); }
}void Tp(){cout<<"Tp被使用"<<endl;switch(instring[0]){case '+':case ')':case '#':break;case '*':advance();F();Tp();break;case 'i':case '(':error();}
}
void F(){cout<<"F被使用"<<endl;switch(instring[0]){case 'i':advance();break; case '(':{advance();E();if(instring[0]==')'){break;}error();break;}case '+':case '*':case ')':case '#':error();}
}void test(){E();if(instring[0]=='#'){cout<<"匹配成功"<<endl;}else{cout<<"匹配失败"<<endl;}
}
int main(){test();return 0;
}