一、实验内容
1.实现LL(1)分析算法
2.输入：教材中的算术表达式文法；待分析的语句（如i+i*i）
3.输出：语句的分析过程（参见ppt例题）
4.要求：LL(1)分析表程序自动生成。如果使用已知的分析表，实验分数会降低。
二、实验目的
通过设计、编制、调试一个具体的文法分析程序，深入理解LL(1)预测分析法的基本分析原理，理解FIRST集、FOLLOW集的构造方法并对其加以实现，构造LL(1)预测分析表并利用分析表对语句、文法进行分析。
三、实验分析
书中算术表达式文法示例如下：
由于算术表达式文法不存在左公因子，所以无需消除回溯。
在程序实现时，可以消除文法中的或符号，即对其进行处理：
四、实验流程
4.1 整体流程
首先从文件中读入文法，识别出文法的终结符与非终结符，对文法进行消除左递归、消除回溯、消除或。再次识别出文法的终结符与非终结符，对每个符号与短语求出其FIRST集合与FOLLOW集合，自动分析生成建立分析表。输入待分析的文法，对其进行分析。整体流程如下图所示。
4.2 求FIRST
对字符或短语求FIRST集合时，往往需要用到递归。若在递归时发现c字符的FIRST集合已经求解完毕，则直接返回。若当前字符c是终结符，则FIRST集合为自己，返回。若不是终结符，则对其产生式进行遍历。若产生式中就是空字，则将空字加入FIRST集合。否则，遍历产生式的字符。递归的求解当前字符的FIRST集合，将该字符FIRST集合除了空字以外的元素加入。若该字符的FIRST集合存在空字，则遍历下一字符，如此循环。求解短语的FIRST集合的过程与求解某一非终结符的产生式的FIRST集合的流程是类似的。求FIRST集合的流程如下图。
4.3 求FOLLOW
4.4 求分析表并分析输入串
五、实验代码
5.1 数据结构
利用S表示文法的开始符，利用VN与VT分别表示非终结符与终结符。
字符的FIRST集合用map存储。map的键为字符，值为FIRST集合，用set存储。字符的FIRST集表被定义为：map> firstSet
短语的FIRST集合也用map存储。map的键为字符串，即短语。值为FIRST集合，用set存储。其被定义为：map> firstSetS
字符的FOLLOW集合用map存储。map的键为字符，值为FOLLOW集合，用set存储。字符的FOLLOW集表被定义为：map> followSet;
利用MAP表示产生式表，利用map存储。map的键为产生式的左部，值为产生式右部。因为一个非终结符可能有多个右部，所以值用vector存储，可以存储多个右部字符串。map> expressionSet;
预测分析表本体利用二维数组存储。vector> table;
文件读取到的文法、消左递归的文法、消除回溯的文法、增广的文法，可以用于求解FIRST与FOLLOW的文法存储在不同的变量名中。
vector<string> filebuffer;//文件读取的缓冲区 vector<string> expression_withoutrecursion;//消左递归 vector<string> expression_withoutback;//消完左递归和回溯 vector<string> inputExpression;//最后增广完成，用于进行分析的文法
5.2 部分核心算法设计
5.2.1 消除左递归与回溯并消除或
消除“或”时，同样需要找到每处”|”，并对含有”|”符号的字符串进行重新拼接处理。
void leftRecursion(){ for (string str : filebuffer){ if (str[0] == str[str.find('>') + 1]){ char newch = 'A'; for (newch = 'A'; newch <= 'Z'; newch++) if (VN.count(newch) == 0) break; VN.insert(newch); string newstr = ""; string alpha = str.substr(4, str.find('|') - 4); // cout << "\nalpha" << alpha << endl; //A->betaA' newstr = newstr + str[0] + (string)"->" + str.substr(str.find('|') + 1) + newch; expression_withoutrecursion.push_back(newstr); newstr = ""; //A'->alphaA'|e newstr = newstr + newch + "->" + alpha + newch + "|" + 'e'; //e表示空字符episilon VT.insert('e'); expression_withoutrecursion.push_back(newstr); } else expression_withoutrecursion.push_back(str); } cout << "\n消除左递归：\n"; for (string str : expression_withoutrecursion) cout << str << endl; } //消除回溯 void leftTraceback(){ for (string str : expression_withoutrecursion){ //发现回溯 if (str[3] == str[str.find("|") + 1]){ char newch = 'A'; for (newch = 'A'; newch <= 'Z'; newch++) if (VN.count(newch) == 0) break; VN.insert(newch); string delta = "" + str[3]; string newstr = ""; //A->alphaA' newstr += str[0] + "->" + delta + newch; expression_withoutback.push_back(newstr); newstr = ""; //A'->beta1|beta2 string beta1 = str.substr(4, str.find('|') - 4); string beta2 = str.substr(str.find('|') + 1); newstr += newch + "->" + beta1 + '|' + beta2; expression_withoutback.push_back(newstr); } else expression_withoutback.push_back(str); } cout << "\n消除回溯：\n"; for (string str : expression_withoutback) cout << str << endl; } //增广，删除竖线| void deleteor(){ for (string str : expression_withoutback){ if (str.find('|') != string::npos){ //将A->beta1|beta2拆成A->beta1和A->beta2 string right1 = str.substr(3, str.find('|') - 3); // cout << "right1" << right1 << endl; string newstr1 = ""; newstr1 = str[0] + (string)"->" + right1; // cout << "newstr1" << newstr1 << endl; inputExpression.push_back(newstr1); string right2 = str.substr(str.find('|') + 1); // cout << "right2" << right2 << endl; string newstr2 = ""; newstr2 += str[0] + (string)"->" + right2; // cout << "newstr2" << newstr2 << endl; inputExpression.push_back(newstr2); } else inputExpression.push_back(str); } cout << "\n增广\n"; for (string str : inputExpression) cout << str << endl; }
5.2.2 求解FIRST
求字符与短语的FIRST集合的过程与4.2章节中的流程图是一致的。这是一个递归的过程。因为涉及到了求单个字符与短语，所以需要对函数进行重载。
//字符的求first集 void getFirst(char c){ //已经求完了当前字符的first集 if (firstSet.count(c)) return; set<char> newset; //若c为终结符，则first为自己，结束 if (VT.count(c)){ newset.insert(c); firstSet[c] = newset; return; } for (string s : expressionSet[c]){ //若存在X->e，将e加入 if ('e' == c) newset.insert('e'); else{ for (char cur : s){ if (!firstSet.count(cur)) getFirst(cur); set<char> curFirst = firstSet[cur]; for (auto curf : curFirst) newset.insert(curf); //将Y的first集合中的元素中不是e的加入 if (!curFirst.count('e')) break; //如果加到了e，则循环回去，即X->Y1Y2..Yk时，Y1产生e，就需要加入Y2的first集合 } } } firstSet[c] = newset; } //多个字符（字符串、短语）first集求法 void getFirst(string s){ if (firstSetS.count(s)) return; set<char> newset; int i = 0; while (i < s.length()){ char cur = s[i]; if (!firstSet.count(cur)) getFirst(cur); //将当前字符的first集作为短语的first集 set<char> rightSet = firstSet[cur]; for (auto rs : rightSet) newset.insert(rs); //类似的，如果加到了e，则循环回去，即X->Y1Y2..Yk时，Y1产生e，就需要加入Y2的first集合 if (rightSet.count('e')) i++; else break; //遍历完了当前语句后，将空字加入当前语句first集 if (i == s.length()) newset.insert('e'); } firstSetS[s] = newset; }
5.2.3 求解FOLLOW
求解FOLLOW集合的流程是迭代的。在调用初始化函数时，需要针对每一个字符反复的对其求解FOLLOW集合。
//求每个非终结符的follow for (char c : VN) getFollow(c);
求解某一字符FOLLOW集合的流程与章节4.3的流程图是一致的。
//某个字符的follow集合 void getFollow(char c){ vector<string> list = expressionSet[c]; set<char> leftFollowSet; if (followSet.count(c)) leftFollowSet = followSet[c]; //对文法开始符号，将#加入follow集合 if (c == S) leftFollowSet.insert('#'); for (char ch : VN) { for (string s : expressionSet[ch]) { for (int i = 0; i < s.length(); i++) { //若有A->aBb（a可为空），则将b加入B的follow集合 if (c == s[i] && i + 1 < s.length() && VT.count(s[i + 1])) leftFollowSet.insert(s[i + 1]); } } } followSet[c] = leftFollowSet; for (string s : list){ int i = s.length() - 1; //对每个产生式从右往左遍历 while (i >= 0) { char cur = s[i]; //对于当前标识符B //对于当前标识符之后的字符，若是非终结符，则将这个非终结符的first集加入当前字符的follow集 if (VN.count(cur)){ string right = s.substr(i + 1); set<char> rightFirstSet; if (!followSet.count(cur)) getFollow(cur); set<char> curFollowSet = followSet[cur]; //若A->aB或A->aB\beta且\beta->e //则把follow(A)加到follow(B) if (right.length() == 0) for (auto lfs : leftFollowSet) curFollowSet.insert(lfs); else //将若A->Bbeta，将B后的字符的first（除e）加入 if (right.length() == 1) if (!firstSet.count(right[0])) getFirst(right[0]); rightFirstSet = firstSet[right[0]]; else if (!firstSetS.count(right)) getFirst(right); rightFirstSet = firstSetS[right]; for (char var : rightFirstSet) if (var != 'e') curFollowSet.insert(var); //若A->Bbeta且e属于first（beta），将follow（A）加入follow（B) if (rightFirstSet.count('e')) for (auto lfs : leftFollowSet) curFollowSet.insert(lfs); } followSet[cur] = curFollowSet; } i--; } } }
5.2.4 文法分析
void analyzeLL(){ cout << "\nLL分析过程\n"; cout << setw(20) << "stack" << setw(10) << "input" << setw(20) << "expression"; cout << endl; analyzeStack.push('#'); //#入栈 analyzeStack.push(S); //开始符入栈 displayLL(); char X = analyzeStack.top(); while (X != '#'){ char a = strInput[index]; if (X == a){ action = ""; analyzeStack.pop(); index++; } else if (VT.count(X)) return;//找到终结符，出错 else if (find(X, a) == "") return; else if (find(X, a) == "e"){ analyzeStack.pop(); action = ""; action += X; action += "->e"; }//空字，出栈 else{//其余情况，需要按分析表对栈顶元素进行推导 string str = find(X, a); if (str != ""){ action = ""; action += X; action += "->"; action += str; analyzeStack.pop(); int len = str.length(); for (int i = len - 1; i >= 0; i--) analyzeStack.push(str[i]);//栈顶元素出栈，按分析表和下一字符将分析表中元素入栈 } else { cout << "\nERROR!\n";//出错，直接返回 return; } } X = analyzeStack.top(); displayLL(); } }
5.3 完整程序
https://blog.csdn.net/qq_46640863/article/details/125705891
六、运行结果
从文件中读取输入文法为算术表达式文法如下，这一文法存在左递归，且没有增广。
对于消除了”|”完成的文法，再次识别终结符与非终结符，并对每个非终结符输出其产生式右部。
在预处理工作完成后，即可对每个终结符与非终结符求解FIRST集合，求解非终结符的FOLLOW集合。其结果与第三章节的结果是完全一致的。
求解FIRST集合和FOLLOW集合完成后，构建分析表，其结果与第三章节的分析是一致的。
在对正确地文法分析完毕后，分析过程正确地停止，程序退出。
