详解递归下降分析法

80 阅读 0 评论 53 点赞

我是靠谱客的博主贤惠战斗机，这篇文章主要介绍详解递归下降分析法，现在分享给大家，希望可以做个参考。

通过一个具体的例子来学习递归下降分析法。

假设有文法：

复制代码

1
2
3
4
5
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 <iostream>
#include <string>

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!" <<endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <string>

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!" <<endl;
	return 0;
}