通过一个具体的例子来学习递归下降分析法。
假设有文法：
E -> TE` E` -> +TE` | -TE` | ε T -> FT` T` -> *FT` | /FT` | ε F -> (E) | i现在希望用递归下降的方式写一个能识别这种语言的parser。
首先我们去求非终结符的FIRST和FOLLOW集合，如下：
| FIRST | FOLLOW | |
| E | ( i | ) |
| E` | + – ε | ) |
| T | ( i | + – ) |
| T` | * / ε | + – ) |
| F | ( i | * / + – ) |
在有的书里（比如虎书），ε是单独算在Nullable集合中的，此处为了方便，我们把它算到FIRST中，这并不影响什么。根据上面的表格，就可以来构造递归下降分析表了，构造的方法是：
对于规则A -> a，如果FIRST(a)不含ε，则在所有的(A,FIRST(a))处写上这条规则；如果含ε，还要在(A,FOLLOW(A))处补上这条规则。
举两个例子来说：
- 对于规则E` -> +TE`，显然FIRST(+TE`)={+}，不含ε，所以只需要在(E`, +)处写上这条规则。
- 对于规则E` -> ε，FIRST(ε)=ε，因为FOLLOW(E`)={)}，所以要在(E`,))处写上这条规则。
OK，我们如法炮制，可以得到如下的分析预测表：
| + | – | * | / | ( | ) | i | |
| E | E -> TE` | E -> TE` | |||||
| E` | E` -> +TE` | E` -> +TE` | E` -> ε | ||||
| T | T -> FT` | T -> FT` | |||||
| T` | T` -> ε | T` -> ε | T` -> *FT` | T` -> *FT` | T` -> ε | ||
| F | F -> (E) | F -> i |
然后根据这个表就可以写代码了：
#include
#include
using namespace std; const int pos = 0; string s = "i+(((((i*i*i*(i+i+(i/i))+i/i)))))$"; void eat(); void error(); void E(); void Eprime(); void T(); void Tprime(); void F(); void eat(){ s = s.substr(1); } void error(){ cout << "failed to match!" << endl; exit(1); } void E(){ switch(s[pos]){ case '$': break; case '(': case 'i': T(); Eprime(); break; default: error(); } } void Eprime() { switch(s[pos]){ case '$': break; case '+': case '-': eat(); T(); Eprime(); break; case ')': break; default: error(); } } void T() { switch(s[pos]){ case '$': break; case '(': case 'i': F(); Tprime(); break; default: error(); } } void Tprime() { switch(s[pos]){ case '$': break; case '+': case '-': case ')': break; case '*': case '/': eat(); F(); Tprime(); break; default: error(); } } void F() { switch(s[pos]){ case '$': break; case '(': eat(); E(); if(s[pos]==')') {eat(); break;} else error(); break; case 'i': eat(); break; default: error(); } } int main() { E(); cout << "finally s is " << s << endl; cout << "accepted!" <
可以看到，每个非终结符就对应了一个函数，分析预测表中的每个entry就对应了函数中的一个case，非常清晰易懂。
Perfect！就写到这里吧。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/214452.html原文链接：https://javaforall.net
