詳解遞歸下降分析法

通過一個具體的例子來學習遞歸下降分析法。

假設有文法：

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))處補上這條規則。

舉兩個例子來說：

1. 對于規則E` -> +TE`，顯然FIRST(+TE`)={+}，不含ε，是以隻需要在(E`, +)處寫上這條規則。
2. 對于規則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;
}
           

可以看到，每個非終結符就對應了一個函數，分析預測表中的每個entry就對應了函數中的一個case，非常清晰易懂。

Perfect！就寫到這裡吧。