纯粹，为了记录.
以后某一天，回过头来看看.给大学留些痕迹hh.
PS:很多思路也都是学习前辈们的，如果能顺便帮到你，不客气！
强烈推荐学习资源：编译原理（哈工大）
本篇思路完全来自楼上链接，但是代码是纯自己瞎敲出来的。
一开始看这个非递归预测分析，一脸懵逼（比较笨），然后看了几遍教学终于看懂咯，如果你也搞不懂，也可以看看哈工大的教学。
内容编译原理 实验4
利用c语言实现以下LL（1）文法的分析程序。
对于给定的文法G[E]
E->TE’
E’->+TE’ | ε
T->FT’
T’->*F T’| ε
F->(E) | i
实验步骤
1、建立该文法的分析表；
2、编程实现非递归的预测分析程序。
（注：id简化为i了）
1、分析表
建立该文法的FIRST和FOLLOW集后，得分析表如下：
2、非递归预测分析过程
具体代码将根据上图所示思路实现。
3、具体代码实现
（1）模块划分
函数bao_map( ): 将分析表中的非终结符、输入符号映射到数组对应行、列号;
函数error( ): 报错处理，即不符合文法时退出程序并给出信息；
函数init( ): 进行初始化操作：
1、初始化工作栈 bao_stack
2、输入待分析的串 bao_str
3、初始化分析表 analysis_table[5][6]
函数is_end_sign( ): 判断输入的符号是否是终结符
函数print_situation()：打印当前栈的情况和串的剩余输入
函数main()：主体，进行非递归预测分析
（2）核心代码
（3）运行结果
#include暑期编程PK赛 得CSDN机械键盘等精美礼品！#include #include using namespace std; vector bao_stack; //栈，栈底为结束符'$' string bao_str; //串的剩余输入，尾部需增加结束符'$' string analysis_table[5][6]; //预测分析表,注：id简化为i,E'改为e,T'改为t int idx = 0; //串的指针，当前指向第一个输入符号 void error() { cout << endl << "输入串不符合该文法定义！" << endl; cout << "程序已退出..." << endl; exit(0); } int bao_map(string str) { int res = 2; //非终结符对应的行号 if (str == "E") { res = 0; } else if (str == "e") { res = 1; } else if (str == "T") { res = 2; } else if (str == "t") { res = 3; } else if (str == "F") { res = 4; } //输入符号对应的列号 else if (str == "i") { res = 0; } else if (str == "+") { res = 1; } else if (str == "*") { res = 2; } else if (str == "(") { res = 3; } else if (str == ")") { res = 4; } else if (str == "$") { res = 5; } return res; } void init() { //初始化工作栈 bao_stack.push_back("$"); bao_stack.push_back("E"); //输入待分析的串，末尾补结束符$ cin >> bao_str; bao_str += "$"; idx = 0; //初始化分析表，PS:就是把该文法的分析表抄进去 //对应输入符号处理为空的做报错处理：如非终结符E遇到'+' for (int i = 0; i < 5; i ++ ) { for (int j = 0; j < 6; j ++ ) { analysis_table[i][j] = "ERROR"; //暂且将全部置为错误情况 } } //非终结符E对应输入情况 analysis_table[bao_map("E")][bao_map("i")] = "Te"; analysis_table[bao_map("E")][bao_map("(")] = "Te"; //E' analysis_table[bao_map("e")][bao_map("+")] = "+Te"; analysis_table[bao_map("e")][bao_map(")")] = "NULL"; analysis_table[bao_map("e")][bao_map("$")] = "NULL"; //T analysis_table[bao_map("T")][bao_map("i")] = "Ft"; analysis_table[bao_map("T")][bao_map("(")] = "Ft"; //T' analysis_table[bao_map("t")][bao_map("+")] = "NULL"; analysis_table[bao_map("t")][bao_map("*")] = "*Ft"; analysis_table[bao_map("t")][bao_map(")")] = "NULL"; analysis_table[bao_map("t")][bao_map("$")] = "NULL"; //F analysis_table[bao_map("F")][bao_map("i")] = "i"; analysis_table[bao_map("F")][bao_map("(")] = "(E)"; } bool is_end_sign(string s) { if (s == "i" || s == "+" || s == "*" || s == "(" || s == ")") return true; return false; } void print_situation() { //栈当前情况 for (int i = bao_stack.size() - 1; i >= 0; i -- ) { if (bao_stack[i] == "e") { cout << "E'"; } else if (bao_stack[i] == "t") { cout << "T'"; } else { cout << bao_stack[i]; } } cout.width(18 - bao_stack.size()); //对齐哟 cout << " "; //输入串剩余输入 for (int i = idx; i < bao_str.size(); i ++ ) { cout << bao_str[i]; } cout.width(18 - bao_stack.size()); //对齐哟 cout << " "; } int main() { init(); //初始化 // //分析表输出测试 // for (int i = 0; i < 5; i ++ ) { // for (int j = 0; j < 6; j ++ ) { // cout.width(12); //对齐 // cout << analysis_table[i][j]; // } // cout << endl; // } cout << "栈 " << "剩余输入 " << " 输出" << endl; while (bao_stack.back() != "$") { //栈非空 string X = bao_stack.back(), a; a.assign(bao_str, idx, 1); print_situation(); //若栈顶是一个终结符，且等于串中当前指向的符号 if (is_end_sign(X) && X == a) { // cout << "标记1" << endl; bao_stack.pop_back(); //弹出栈顶 idx ++ ; //当前输入匹配完成，读取串中下一个输入 } //若栈顶是一个终结符号，但不等于串中当前指向的符号 else if (is_end_sign(X)) { // cout << "标记2" << endl; error(); } //若预测分析表中是一个报错条目，即 初始化时的"ERROR" else if (analysis_table[bao_map(X)][bao_map(a)] == "ERROR") { // cout << "标记3" << endl; error(); } //预测分析法存在其对应的转换 else { //输出对应产生式 cout.width(12); string out_buf = X + "->" + analysis_table[bao_map(X)][bao_map(a)]; for (int i = 0; i < out_buf.size(); i ++ ) { if (out_buf[i] == 'e') { cout << "E'"; } else if (out_buf[i] == 't') { cout << "T'"; } else { cout << out_buf[i]; } } cout << endl; //弹出栈顶 bao_stack.pop_back(); //将对应产生式入栈，注意要逆序进栈， //例如：F->TE',进栈顺序是E'、T string tmp = analysis_table[bao_map(X)][bao_map(a)]; if (tmp == "NULL") //替换为空串的情况，直接继续 continue; for (int i = tmp.size() - 1; i >= 0; i -- ) { string buf; buf.assign(tmp, i, 1); bao_stack.push_back(buf); } } cout << endl; } cout << "## 输入串符合该文法!" << endl; return 0; } //i+i*i
