在之前已经通过手写的方式实现了一个词法分析器，现在，我将利用之前手写的词法分析器，使用递归下降的方式，实现一个简单的语法分析器。
首先看看实验要求：
用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。
为减轻实验编程负担，这里只要求实现部分产生式，文法的开始符号为program。
第一步，消除左递归。观察上面各个产生式，出现左递归的地方有expr和term。
针对以上式子，首先提取左因子：
消除左递归：
观察到 在if语句处也存在左公因子，一并提取，最终文法定义为：
定义好文法后，考虑词法分析与语法分析的接口，由于采用递归下降的分析过程中，存在对token的回溯操作，因此，每次逐个获取词法单元并不容易实现，考虑将token对应的标志和内容使用pair<int,string>的数组保存下来。
pair<int, string> tokens[10000];int cursor_;int tokens_size_;
并使用cursor_记录当前准备分析的位置，通过移动cursor_实现对token串的回溯过程。然后根据每一条语句，写出对应的梯度下降递归函数，就可以完成本实验，使用yylex自动生成的方法也类似，只需要维护tokens数组即可。
// 工具函数：获得一个向前看，但并不移动指针pair<int, string> get_ahead(){ return tokens[cursor_];}// 工具函数：尝试匹配一个类型，匹配返回真bool match(int type){ if(cursor_ >= tokens_size_) return false; if(tokens[cursor_].first == type) { cursor_ ; return true; } return false;}// 工具函数：尝试匹配一个类型和字符串，都匹配返回真bool match(int type, string target){ if(tokens[cursor_].first == type && tokens[cursor_].second == target) { cursor_ ; return true; } return false;}bool factor(){ cout << “Try to match factor” << endl; if(match(IDENTITY)) return true; if(match(DIGIT)) return true; return match(SYMBOL, “(“) && expr() && match(SYMBOL, “)”);}bool B3(){ cout << “Try to match B3” << endl; return match(SYMBOL, “%”) && factor();}bool B2(){ cout << “Try to match B2” << endl; return match(SYMBOL, “/”) && factor();}bool B1(){ cout << “Try to match B1” << endl; return match(SYMBOL, “*”) && factor();}bool B(){ cout << “Try to match B” << endl; int backup_cursor = cursor_; if(B1()) return true; cursor_ = backup_cursor; if(B2()) return true; cursor_ = backup_cursor; if(B3()) return true; cursor_ = backup_cursor; return false;}bool D(){ cout << “Try to match D” << endl; pair<int, string> ahead = get_ahead(); if(ahead.first == SYMBOL && (ahead.second == “*” || ahead.second == “/” || ahead.second == “%”)) return B() && D(); return true;}bool term(){ cout << “Try to match term” << endl; return factor() && D();}bool A2(){ cout << “Try to match A2” << endl; return match(SYMBOL, “-“) && term();}bool A1(){ cout << “Try to match A1″ << endl; return match(SYMBOL, ” “) && term();}bool A(){ cout << “Try to match A” << endl; int backup_cursor = cursor_; if(A1()) return true; cursor_ = backup_cursor; if(A2()) return true; cursor_ = backup_cursor; return false;}bool C(){ cout << “Try to match C” << endl; pair<int, string> ahead = get_ahead(); if(ahead.first == SYMBOL && (ahead.second == ” ” || ahead.second == “-“)) return A() && C(); return true;}bool expr(){ cout << “Try to match expr” << endl; return term() && C();}bool F(){ cout << “Try to match F” << endl; pair<int, string> ahead = get_ahead(); if(ahead.first == RELOP) return match(RELOP) && expr(); return true;}bool bool_(){ cout << “Try to match bool” << endl; return expr() && F();}bool E(){ cout << “Try to match E” << endl; pair<int, string> ahead = get_ahead(); if(ahead.first == KEYWORD && ahead.second == “else”) return match(KEYWORD, “else”) && stmt(); return true;}bool stmt6(){ cout << “Try to match stmt choice 6” << endl; return block();}bool stmt5(){ cout << “Try to match stmt choice 5” << endl; return match(KEYWORD, “break”) && match(SYMBOL, “;”);}bool stmt4(){ cout << “Try to match stmt choice 4” << endl; return match(KEYWORD, “do”) && stmt() && match(KEYWORD, “while”) && match(SYMBOL, “(“) && bool_() && match(SYMBOL, “)”) && match(SYMBOL, “;”);}bool stmt3(){ cout << “Try to match stmt choice 3” << endl; return match(KEYWORD, “while”) && match(SYMBOL, “(“) && bool_() && match(SYMBOL, “)”) && stmt();}bool stmt2(){ cout << “Try to match stmt choice 2” << endl; return match(KEYWORD, “if”) && match(SYMBOL, “(“) && bool_() && match(SYMBOL, “)”) && stmt() && E();}bool stmt1(){ cout << “Try to match stmt choice 1” << endl; return match(IDENTITY) && match(SYMBOL, “=”) && expr() && match(SYMBOL, “;”);}bool stmt(){ cout << “Try to match stmt” << endl; int backup_cursor = cursor_; // 指针的回溯 if(stmt1()) return true; cursor_ = backup_cursor; if(stmt2()) return true; cursor_ = backup_cursor; if(stmt3()) return true; cursor_ = backup_cursor; if(stmt4()) return true; cursor_ = backup_cursor; if(stmt5()) return true; cursor_ = backup_cursor; if(stmt6()) return true; cursor_ = backup_cursor; return false;}bool stmts(){ cout << “Try to match stmts” << endl; pair<int, string> ahead = get_ahead(); if(ahead.first == SYMBOL && ahead.second == “}”) return true; else return stmt() && stmts();}bool block(){ cout << “Try to match block” << endl; return match(SYMBOL, “{“) && stmts() && match(SYMBOL, “}”);}bool program(){ cout << “Try to match program” << endl; return block();}
由于已经高度模块化，main函数很简单：
int main(){ if(!DFA()) return 0; // 词法分析tokens_size_=cursor_; cursor_ = 0; // 初始化指针 if(program()) cout << “ACCEPT !” << endl; else cout << “ERROR !” << endl;}
测试：
使用实验指导代码测试：
input:{i = 2; sum = 0; while (i <=100) { sum = sum i; i = i 2; if(i%5==0) break; }}output:SYMBOL : {i = 2;IDENTITY : iSYMBOL : =DIGIT : 2SYMBOL : ; sum = 0;IDENTITY : sumSYMBOL : =DIGIT : 0SYMBOL:;KEYWORD : whileSYMBOL : (IDENTITY : iRELOP : <=DIGIT : 100SYMBOL : )SYMBOL:{IDENTITY : sumSYMBOL : =IDENTITY : sumSYMBOL : IDENTITY : iSYMBOL:;IDENTITY : iSYMBOL : =IDENTITY : iSYMBOL : DIGIT : 2SYMBOL:;KEYWORD : ifSYMBOL : (IDENTITY : iSYMBOL : %DIGIT : 5RELOP : ==DIGIT : 0SYMBOL : )KEYWORD : breakSYMBOL:;SYMBOL:}SYMBOL:}Try to match programTry to match blockTry to match stmtsTry to match stmtTry to match stmt choice 1Try to match exprTry to match termTry to match factorTry to match DTry to match CTry to match stmtsTry to match stmtTry to match stmt choice 1Try to match exprTry to match termTry to match factorTry to match DTry to match CTry to match stmtsTry to match stmtTry to match stmt choice 1Try to match stmt choice 2Try to match stmt choice 3Try to match boolTry to match exprTry to match termTry to match factorTry to match DTry to match CTry to match FTry to match exprTry to match termTry to match factorTry to match DTry to match CTry to match stmtTry to match stmt choice 1Try to match stmt choice 2Try to match stmt choice 3Try to match stmt choice 4Try to match stmt choice 5Try to match stmt choice 6Try to match blockTry to match stmtsTry to match stmtTry to match stmt choice 1Try to match exprTry to match termTry to match factorTry to match DTry to match CTry to match ATry to match A1Try to match termTry to match factorTry to match DTry to match CTry to match stmtsTry to match stmtTry to match stmt choice 1Try to match exprTry to match termTry to match factorTry to match DTry to match CTry to match ATry to match A1Try to match termTry to match factorTry to match DTry to match ETry to match stmtsTry to match stmtsACCEPT !
最后发现梯度递归函数已经成功地接受了我们的输入。
