自顶向下的语法分析器—采用递归下降方法
在之前已经通过手写的方式实现了一个词法分析器，现在，我将利用之前手写的词法分析器，使用递归下降的方式，实现一个简单的语法分析器。
首先看看实验要求：
用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。
为减轻实验编程负担，这里只要求实现部分产生式，文法的开始符号为 program 。
第一步，消除左递归。观察上面各个产生式，出现左递归的地方有expr和term。
针对以上式子，首先提取左因子：
消除左递归：
观察到 在if语句处也存在左公因子，一并提取，最终文法定义为：
定义好文法后，考虑词法分析与语法分析的接口，由于采用递归下降的分析过程中，存在对token的回溯操作，因此，每次逐个获取词法单元并不容易实现，考虑将token对应的标志和内容使用pair的数组保存下来。
pair tokens[10000];int cursor_;int tokens_size_;并使用cursor_记录当前准备分析的位置，通过移动cursor_实现对token串的回溯过程。然后根据每一条语句，写出对应的梯度下降递归函数，就可以完成本实验，使用yylex自动生成的方法也类似，只需要维护tokens数组即可。
// 工具函数：获得一个向前看，但并不移动指针pair 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 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 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 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 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 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 !最后发现梯度递归函数已经成功地接受了我们的输入。
华为助力Smart全云化核心网以NFVO为中心的运维平台成功商用
台湾地区与韩国对光刻机需求最强烈 先进制程的光刻设备出货前景看好
万用表与钳形表测量电流原理的异同？
应急广播灾害预警广播系统
指纹方案的设计
自顶向下的语法分析器—采用递归下降方法
在智能穿戴设备和家用电器中实现物联网和AI的高级融合
12月全国狭义乘用车销量为228.8万辆,呈现市场稳步回暖的态势
电阻器和颜色代码及阻值识别分析
vivo NEX 3S将于3月10日正式发布该机搭载骁龙865平台支持双模5G
AI技术的快速发展让电话机器人应运而生
支持向量机（系统识别的性能度量之ROC曲线）
集成光子制备工艺的研究
汽车电子不同制动器的结构和作用
加速电容作用?电路工作原理分析
三星Tab S7系列平板渲染图在网上曝光 还有新功能加入
脉冲电子围栏常见故障及解决方法
小米Civi 2官宣 将于9月27日正式发布
变压器和电源是不是同一种产品？
射频导纳料位计与静电容式料位计的区别
首先看看实验要求：
用递归下降法编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。
为减轻实验编程负担，这里只要求实现部分产生式，文法的开始符号为 program 。
第一步，消除左递归。观察上面各个产生式，出现左递归的地方有expr和term。
针对以上式子，首先提取左因子：
消除左递归：
观察到 在if语句处也存在左公因子，一并提取，最终文法定义为：
定义好文法后，考虑词法分析与语法分析的接口，由于采用递归下降的分析过程中，存在对token的回溯操作，因此，每次逐个获取词法单元并不容易实现，考虑将token对应的标志和内容使用pair的数组保存下来。
pair tokens[10000];int cursor_;int tokens_size_;并使用cursor_记录当前准备分析的位置，通过移动cursor_实现对token串的回溯过程。然后根据每一条语句，写出对应的梯度下降递归函数，就可以完成本实验，使用yylex自动生成的方法也类似，只需要维护tokens数组即可。
// 工具函数：获得一个向前看，但并不移动指针pair 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 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 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 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 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 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 !最后发现梯度递归函数已经成功地接受了我们的输入。
华为助力Smart全云化核心网以NFVO为中心的运维平台成功商用
台湾地区与韩国对光刻机需求最强烈 先进制程的光刻设备出货前景看好
万用表与钳形表测量电流原理的异同？
应急广播灾害预警广播系统
指纹方案的设计
自顶向下的语法分析器—采用递归下降方法
在智能穿戴设备和家用电器中实现物联网和AI的高级融合
12月全国狭义乘用车销量为228.8万辆,呈现市场稳步回暖的态势
电阻器和颜色代码及阻值识别分析
vivo NEX 3S将于3月10日正式发布该机搭载骁龙865平台支持双模5G
AI技术的快速发展让电话机器人应运而生
支持向量机（系统识别的性能度量之ROC曲线）
集成光子制备工艺的研究
汽车电子不同制动器的结构和作用
加速电容作用?电路工作原理分析
三星Tab S7系列平板渲染图在网上曝光 还有新功能加入
脉冲电子围栏常见故障及解决方法
小米Civi 2官宣 将于9月27日正式发布
变压器和电源是不是同一种产品？
射频导纳料位计与静电容式料位计的区别