目的：熟练掌握自上而下的语法分析方法，并能用程序实现。
要求：
例如. 使用的文法如下：
E->TE'E'->+ TE'| #T->FT 'T'->*FT'|#F->(E)|id编写First函数，实现其求解过程。
提示：
非终结符为 大写字母；或 后面带’的大写字母终结符为 小写字母和符号（+、*）推导符号为->用end结束文法。不针对特定文法，编写求first函数。首先first集的求法：
我的思路是这样的：
1.生成式结构体：左侧只有一个，用string类型；右侧可能有由"|"隔开的多个，所以用vector；first集，也用vector。
2.首先输入生成式个数，然后依次读入生成式（用“#”表示空），用classify函数分别放入左部、右部。
3.接下来就是求first集了，对于每个生成式，分别处理右部，也就是右部vector的每个元素（都是string类型），下面是几种情况。
（1）如果某个元素的开头是小写字母（终结符），那就接着看后面，截取全部的与第一个连续的小写字母，就是first集的一个元素，将其加入first集（判断是否已存在，如果不存在才能加入），当前元素处理完毕。
（2）如果开头是规定的符号终结符，直接加入当前结构体的first集，当前元素处理完毕。
（3）如果开头是大写字母，将其first集中除“#”外的元素无重复的加入当前结构体的first集中。
如果该非终结符的first集里面没有“#”，处理完毕。
如果有“#”，还要继续看后面的，我的理解是把后面那个当成是一个新的右部元素处理，所以直接把它加到右部元素的vector里，最后再把后加的都弹出就好啦。
最后放代码：
#include<iostream> #include<string> #include<vector> using namespace std; int N = 0; struct Generation{ string left; vector<string> right; vector<string> first; }; vector<Generation> G; int find(string left){ //找到left对应的生成式的下标 for(int i=0;i<G.size();i++) if(G[i].left==left) return i; return 1111; } bool in(vector<string> v,string s){ //判断一个字符串是否在vector里 for(int i=0;i<v.size();i++) if(v[i]==s) return true; return false; } void classify(string generation) //将产生式的左右部分别放入left，right { Generation g; int j,pos = 0; for (j = 0;j<=generation.length();j++){ if (generation[j] == '-'&&generation[j + 1] == '>'){ g.left = generation.substr(0, j); pos = j+2; } if(generation[j]=='|'||j==generation.length()){ g.right.push_back(generation.substr(pos, j-pos)); pos = j+1; } } G.push_back(g); } void First(){ int i,j,k,s; int add_num = 0; string v; for(i=G.size()-1;i>=0;i--){ Generation temp = G[i]; for(j=0;j<temp.right.size();j++){ //分别处理右部 v.clear(); add_num = 0; string right = temp.right[j]; if(right[0]>='a'&&right[0]<='z'){ v+=right[0]; int k=1; while(right[k]>='a'&&right[k]<='z'&&k<right.size()){ v+=right[k]; k+=1; } temp.first.push_back(v); } else if(right[0]=='*'||right[0]=='+'||right[0]=='('||right[0]==')'||right[0]=='#'){ v += right[0]; temp.first.push_back(v); } else if(right[0]>='A'||right[0]<='Z'){ v += right[0]; int num = find(v); v.clear(); if(num!=1111){ vector<string> target = G[num].first; for(k=0;k<target.size();k++){ if(!in(temp.first,target[k])&&target[k]!="#") //判断是否存在于temp的first集中 temp.first.push_back(target[k]); if(target[k]=="#"&&right.length()>1) { //如果右侧的非终结符的first里包含空，那就继续处理这个非终结符后面的 v=right.substr(1); temp.right.push_back(v); add_num += 1; } if(target[k]=="#"&&right.length()==1&&!in(temp.first,"#")){ temp.first.push_back(target[k]); } } } } } for(k=0;k<add_num;k++) //最后把加进去的right的元素都删除 temp.right.pop_back(); G[i] = temp; } } void handle(){ int i; string gen; cout << "请输入产生式个数:"; cin >> N; cout << endl<<"请输入产生式(要用#表示空)："<< endl; for(i=0;i<N;i++){ cin >> gen; classify(gen); } First(); } int main(){ handle(); /*for(int i=0;i<G.size();i++){ cout << G[i].left << " "; cout << G[i].right.size(); for(int j=0;j<G[i].right.size();j++) cout << G[i].right[j] << " "; }*/ cout << endl << "非终结符对应的first集为：" << endl; for(int i=0;i<G.size();i++){ cout << G[i].left<<" {"; for(int j=0;j<G[i].first.size();j++){ cout << G[i].first[j]; if(j==G[i].first.size()-1) cout << "}" << endl; else cout << ","; } } return 0; }
