博客已经迁移到 https://leerw.github.io，欢迎来访，共同交流进步

题目

目的：熟练掌握自上而下的语法分析方法，并能用程序实现。 要求： 例如. 使用的文法如下： E->TE' E'->+TE'|# T->FT' T'->*FT'|# F->(E)|id 编写First函数，实现其求解过程。 提示： 1， 非终结符为大写字母；或后面带'的大写字母 2， 终结符为 小写字母和符号（+、*）(#代表空串) 3， 推导符号为-> 4， 用end结束文法。 5， 不针对特定文法，编写求first函数。

思路

从文件中读取文法，对每一行将其拆分成两个部分：箭头左边的非终结符和箭头右边的对应产生式；再将产生式按其中的'|'分隔符拆分成若干个对应单词；对每个单词进行考察，若首字母为非终结符则递归寻找First集合，若为终结符，则加入到此非终结符对应的First集合中去。

代码

/* *Programed by Lee_rw_cs on 2017/05/04 *Find the first set of a set of grammar *eg. *E->TE' E'->+TE'|# T->FT' T'->*FT'|# F->(E)|id */ #include <iostream> #include <algorithm> #include <fstream> #include <map> #include <set> #include <string> using namespace std; //全局变量 set<string> non_terminal; //存放非终结符 set<string> productions; //存放产生式 std::map<string, string> match_map; //存放非终结符和其对应的产生式的文法的键值对 std::map<string, set<string>> first; //string:非终结符;set<string>:非终结符所对应的first集合 void divide_words(string grammar, map<string, string>& match_map) { for (int i = 0; i < (int)grammar.length(); ++i) { if (grammar[i] == '-' && grammar[i + 1] == '>') { /* code */ string left = grammar.substr(0, i); //一句文法的左边即非终结符 string right = grammar.substr(i + 2, grammar.length() - 1); //一句文法的右边即非终结符对应的产生式 non_terminal.insert(left); //插入非终结符集合里 productions.insert(right); //插入产生式集合里 match_map.insert(make_pair(left, right)); //将一句文法里的非终结符和其对应的文法作为键值对插入到匹配map里 break; } } } /*将被'|'隔开的产生式拆分成对应多个的单词*/ void divide_right(string grammar_right, set<string>& small_right) { /*或许可以用grammar.find_first_of一个一个找|，然后用substr分开子串，最后再insert到small_right中去*/ size_t found = grammar_right.find('|'); if (found != string::npos) { int i = 0; string temp = "\0"; while ((size_t)i < grammar_right.length()) { if (grammar_right[i] != '|') { temp += grammar_right[i]; i = i + 1; } else { i = i + 1; small_right.insert(temp); temp = "\0"; } if (i == grammar_right.length()) { small_right.insert(temp); temp = "\0"; } } } else { small_right.insert(grammar_right); } } /*对每个非终结符non_term寻找它的非终结符集合first*/ void find_first(string non_term, set<string>& first) { set<string> or_words; //存放产生式中被'|'隔开的单词 auto search = match_map.find(non_term); if (search != match_map.end()) { divide_right(search->second, or_words); //匹配非终结符是否在or_words的开头 for (set<string>::iterator i = or_words.begin(); i != or_words.end(); i++) { for (set<string>::iterator j = non_terminal.begin(); j != non_terminal.end(); j++) { if ((*i).find(*j) == 0) { //在or_words[i]的开头找到了一个非终结符 //递归寻找非终结符j的first集合 find_first((*j), first); } else { //在or_words[i]的开头如果没有找到非终结符，即终结符 if ((*i)[0] >= 'a' && (*i)[0] <= 'z') { first.insert(*i); } switch ((*i)[0]) { case '(': first.insert(string("(")); break; case ')': first.insert(string(")")); break; case '+': first.insert(string("+")); break; case '*': first.insert(string("*")); break; case '#': first.insert(string("#")); break; default: //如果没有匹配到符号的话就把这个单词插入到first集合中 //first.insert(*i); break; } continue; //找到之后跳出循环，避免进行多余的遍历浪费时间 } } } } } int main() { /*读取文法文件*/ const char* filename = "wenfa.txt"; ifstream inFile(filename); if (!inFile) { cout << "\nFiled to open file " << filename; return -1; } string st = "\0"; char buf[100]; while (!inFile.eof()) { inFile.getline(buf, 100); st = buf; if (strlen(buf) == 0 || st == "end") { break; } divide_words(st, match_map); //对每一行文法进行分析找出非终结符和对应的产生式 } inFile.close(); /*遍历非终结符集合，为每个非终结符寻找first集合*/ for (set<string>::iterator i = non_terminal.begin(); i != non_terminal.end(); ++i) { set<string> the_first; //当前非终结符的first集合 find_first(*i, the_first); first.insert(make_pair(*i, the_first)); } cout << "非终结符" << "\t" << "First集合" << endl; for (map<string, set<string>>::iterator i = first.begin(); i != first.end(); i++) { cout << "------------------------" << endl; cout << i->first << "\t|\t"; cout << "{"; //倒序输出first集合中的元素与文法中出现的顺序保持一致 for (set<string>::reverse_iterator j = (i->second).rbegin(); j != (i->second).rend(); j++) { cout << *j << ","; } cout << '\b'; cout << "}"; cout << endl; } cout << endl << endl; return 0; }

wenfa.txt 运行结果：