基于C++ 设计与实现语法分析程序【100012464】

# 语法分析程序的设计与实现 ## 实验内容 * ### 题目： 与法分析程序的设计与实现 * ### 实验内容 编写语法分析程序，实现对算术表达式的语法分析。 * ### 实验要求 在对输入的算术表达式进行分析的过程中，一次输出所采用的产生式。 * ### 实验方法 编写LL(1)语法分析程序 - 编程实现课本算法4.2，为给定文法自动构造预测分析表 - 编写实现课本算法4.1，构造LL(1)预测分析程序。 ## 运行开发环境 * **系统环境**：macOS Big Sur: 11.4 * **编译环境**：Clion: 11.0.10+9-b1341.41 aarch64 * **版本管理工具**：github ## 设计、实现说明 * ### 该要设计 #### 1. 实现为给定文法自动构造预测分析表 * 从input.txt文件中读取未经处理的原始文法 * 消除左递归 * 消除左公因子 * 打印文法，并将处理后的文法输出到input.out.txt文件 * 构造LL1预测分析表 * 构造FIRST集 * 构造FOLLOW集 * 生成分析表 * 加入错误处理sync * 打印LL1分析表，并将分析表输出到LL1_table.txt文件 #### 2. 构造LL1预测分析程序 * 读入待分析表达式 * 读入LL1分析表 * 初始化分析器 * 循环直到栈空 * 输出每次所采用的产生式 * 输出分析结果(接受或不接受)  <!--之所以把左递归回溯、构造分析表、LL1分析程序三者分开，是出于对提高分析程序的简洁与运行性能的考量--> * ### 详细设计 * ##### 1. 结构变量说明 ```C++ set<string> non_terminal, terminal; //使用set存储非终结符与终结符，省去对重复项的过滤 map<string, set<string>> first, follow; //使用hash_map存储first、follow集，string到set<string>的映射同样可以省去对重复项的过滤 map<string, vector<string>> G; //存储文法 map<string, string> still_empty; //用于构造follow集时出现的未计算的产生式 string s; //待分析表达式 string start; //起始非终结符 struct StringPairHash { size_t operator()( const pair<std::string, string> &obj) const { static const hash<string> hash; return (hash (obj.first) << 16) + hash (obj.second); } }; unordered_map<pair<string, string>, vector<string>, StringPairHash> table; //预测分析表，使用pair<string, string>到vector<string>的映射 ``` * ##### 2. 函数成员 ```C++ void fix_left_recursion(); //消除左递归 void fix_left_common_factor(); //消除回溯 void read_input_out_txt(); //读取处理好的文法输入文件 void get_first(); //获取first集 void get_follow(); //获取follow集 void make_table(); //构造预测分析表 void analyze(); //预测分析 void find_terminal(const string &left, const string &right, int times, const string& init); //求解first集所用递归函数 vector<string> split_blank(const string& str); //获取文件读入划分字符串 ``` * ##### 3. 构造FIRST集  ```C++ void find_terminal(const string &left, const string &right, int times, const string& init) { if(terminal.find(right.substr(0, 1)) != terminal.end()) { first[left].insert(right.substr(0, 1)); first[init].insert(right.substr(0, 1)); return; } else if(times < non_terminal.size()){ for(auto &i : G[right.substr(0, 1)]) { find_terminal(left, i, times+1, init); } } else return; } void get_first() { for(const auto& i : non_terminal) { //遍历每个非终结符 for(const auto& j : G[i]) { //遍历每个非终结对应右句 if(terminal.find(j.substr(0, 1)) != terminal.end()) { //如果右式当前遍历项为非终结符，则加入first first[i].insert(j.substr(0, 1)); first[j].insert(j.substr(0, 1)); //first[j] += j.substr(0, 1); } else { find_terminal(i, j, 0, j); } } } //cout << "first get" << endl; } ``` * ##### 4. 构造FOLLOW集  ```C++ void get_follow() { //规则1 follow[start].insert("$"); int pre_size = -1, now_size = 0; while(pre_size != now_size) { pre_size = now_size; for(const auto& i : G) { vector<string> elements = i.second; for(auto & element : elements) { if(element[0] != '~') { //当前非epsilon for(int k = 0; k < element.size()-1; k++) { string cur = element.substr(k, 1), next = element.substr(k+1, 1); if(terminal.find(cur) != terminal.end()) { //若当前字符为终结符 follow[cur].insert(cur); //终结符本身的follow集即为自身 } else{ if(terminal.find(next) != terminal.end()) { //若下一个为终结符 follow[cur].insert(next); } else { //下一个为非终结符，加入next的first //if(first[next].find("~") == first[next].end()) { //若下一个是非终结符并且该非终结符不包含epsilon for(const auto& l : first[next]) { //加入他的first集 if(l != "~") follow[cur].insert(l); } //} if(first[next].find("~") != first[next].end()) { //若下一个是非终结符并且包含epsilon if(!follow[i.first].empty()) for(const auto& l : follow[i.first]) { follow[cur].insert(l); still_empty[next] = cur; } else { still_empty[next] = cur; } } } } } string k = element.substr((int)element.size()-1 ,1); if(terminal.find(k) == terminal.end()) { if(!follow[i.first].empty()) { //若不为空 for(const auto& l : follow[i.first]) { follow[k].insert(l); still_empty[k] = i.first; } } else { still_empty[k] = i.first; } } } } } for(const auto& i : still_empty) { follow[i.first].insert(follow[i.second].begin(), follow[i.second].end()); } now_size = 0; for(const auto& i : non_terminal) { now_size += (int)follow[i].size(); } } //cout << "follow get" << endl; } ``` * ##### 5. 构造预测分析表  ```C++ void analyze() { stack<string> status, input; status.push("$"); status.push(start); input.push("$"); for(int i = (int)s.size()-1; i >= 0; i--) { input.push(s.substr(i, 1)); } //格式化