目的:熟练掌握自上而下的语法分析方法,并能用程序实现。
要求:
例如,使用的文法如下:
编写First函数,实现其求解过程。
E -> TE'
E' -> +TE' | #
T -> FT'
T' -> *FT' | #
F -> (E) | id
end
提示:
不针对特定文法,编写求first函数。
/** * @brief Function for generating set of First(a) * @author 立秋小猪 * @time: 2021/10/13 * @notice: 要求产生体句型不得有空格 * 左递归的产生体中必须有空串(必须能够终结) * char '#' act as varepsilon * **/ #include <iostream> #include <unordered_map> #include <vector> #include <string> #include <fstream> #include <unordered_set> using namespace std; unordered_map<string, vector<string>> P; //产生式P的集合 void scan(){ //scan函数实现从文件扫描文法,将对应的产生式加入到映射P中 fstream fs; string input; fs.open("lan.txt"); if(!fs.is_open()){ // 文件打开失败 cout << "Error: Could not open the file" << endl; exit(-1); } fs >> input; while(input != "end"){ string VN = input; // 产生式的非终结符 fs >> input; //跳过推导符号 if (input != "->" && input != "→"){ cout << "Error: undefined symbol [" << input << "]" << endl; exit(-2); } fs >> input; //产生体拆开后加入到set集合中,默认推导符号后必有一个产生体 P[VN].emplace_back(input); while( fs >> input && input == "|"){ fs >> input; P[VN].emplace_back(input); } } } // void generate(){ // } unordered_set<char> First(const string& str){ // 终结符以及空串情况下, whether has the VN or not if(str == "" || str == "#" || P.find(str) == P.end()) return {}; if(!(str[0] >= 'A' && str[0] <= 'Z')) return {str[0]}; vector<string> bodys = P[str]; // str -> bodys unordered_set<char> res = {}; for(auto &s: bodys){ bool hasBlank = true;//是否含有空串,是否继续读产生体 for (int i = 0; i < s.size() && hasBlank; ++i){ if(s[i] >= 'A' && s[i] <= 'Z'){//是否为终结符 unordered_set<char> temp = {};//递归的临时集 string next; if(i < s.size() - 1 && s[i + 1] == '\''){ // 大写字母 + ' 的非终结符 next = s.substr(i, 2); ++i; }else{ //仅仅是大写字母的终结符 next = s[i]; } if(next != str){ //避免无限递归,默认自身是含有空串(hasBlank为True) temp = First(next); //递归求解 hasBlank = false; //先默认temp中没有空串 for(auto &c : temp) if(c == '#') hasBlank = true;//temp中发现了空串 else res.emplace(c); } }else{ res.emplace(s[i]); hasBlank = false;//默认连接的终结符不为空,故此终结符后不会再有新元素加入First集 } } if(hasBlank) //产生体中所有非终结符都包含空串,则将空串加入first集中 res.emplace('#'); } return res; } int main(){ // unordered_map<string, vector<char>> First; //First集合 scan(); cout << "输入的产生式如下:\n" << "********************************\n"; for(auto &[vn, bodys]: P){ cout << vn << " -> " << bodys[0]; for (int i = 1; i < bodys.size(); ++i) cout << " | " << bodys[i]; cout << endl; } cout << "********************************\n"; for(auto &[vn,_]: P){ unordered_set<char> f = First(vn); cout << "First(" << vn << ") : "; auto iter = f.begin(); if(iter != f.end()){ cout << *iter; while(++iter != f.end()){ cout << " , " << *iter; } } cout << endl; } return 0; }
E -> TE' E' -> +TE' | # T -> FT' T' -> *FT' | # F -> (E) | id end
S -> SaRb | # R -> RSQ | # Q -> e end
本人也只是编程小白,代码仅供参考,如有错误请见谅,如有疑问欢迎交流讨论,欢迎提出任何建议和评价。