近来复习编译原理，语法分析中的自上而下LL(1)分析法，需要构造求出一个文法的FIRST和FOLLOW集，然后构造分析表，利用分析表+一个栈来做自上而下的语法分析（递归下降/预测分析），可是这个FIRST集合FOLLOW集看得我头大。。。
教课书上的规则如下，用我理解的语言描述的：
任意符号α的FIRST集求法：1. α为终结符，则把它自身加入FIRSRT(α)2. α为非终结符，则：（1）若存在产生式α->a...，则把a加入FIRST(α),其中a可以为ε（2）若存在一串非终结符Y1,Y2, ..., Yk-1，且它们的FIRST集都含空串，且有产生式α->Y1Y2...Yk...，那么把FIRST(Yk)-{ε}加入FIRST(α)。如果k-1抵达产生式末尾，那么把ε加入FIRST(α) 注意（2）要连续进行，通俗地描述就是：沿途的Yi都能推出空串，则把这一路遇到的Yi的FIRST集都加进来，直到遇到第一个不能推出空串的Yk为止。 重复1,2步骤直至每个FIRST集都不再增大为止。 任意非终结符A的FOLLOW集求法：1. A为开始符号，则把#加入FOLLOW(A)2. 对于产生式A-->αBβ： （1）把FIRST(β)-{ε}加到FOLLOW(B) （2）若β为ε或者ε属于FIRST(β)，则把FOLLOW(A)加到FOLLOW(B) 重复1,2步骤直至每个FOLLOW集都不再增大为止。 老师和同学能很敏锐地求出来，而我只能按照规则，像程序一样一条条执行。于是我把这个过程写成了程序，如下：
数据元素的定义：
1 const int MAX_N = 20;//产生式体的最大长度 2 const char nullStr = '$';//空串的字面值 3 typedef int Type;//符号类型 4 5 const Type NON = -1;//非法类型 6 const Type T = 0;//终结符 7 const Type N = 1;//非终结符 8 const Type NUL = 2;//空串 9 10 struct Production//产生式11 {12 char head;13 char* body;14 Production(){}15 Production(char h, char b[]){16 head = h;17 body = (char*)malloc(strlen(b)*sizeof(char));18 strcpy(body, b);19 }20 bool operator<(const Production& p)const{ //内部const则外部也为const21 if(head == p.head) return body[0] < p.body[0];//注意此处只适用于LL(1)文法，即同一VN各候选的首符不能有相同的，否则这里的小于符号还要向前多看几个字符，就不是LL(1)文法了22 return head < p.head;23 }24 void print() const{ //要加const25 printf("%c -- > %s\n", head, body);26 }27 };28 29 //以下几个集合可以再封装为一个大结构体--文法30 set P;//产生式集31 set VN, VT;//非终结符号集，终结符号集32 char S;//开始符号33 map > FIRST;//FIRST集34 map > FOLLOW;//FOLLOW集35 36 set ::iterator first;//全局共享的迭代器，其实觉得应该用局部变量37 set ::iterator follow;38 set ::iterator vn;39 set ::iterator vt;40 set ::iterator p;41 42 Type get_type(char alpha){ //判读符号类型43 if(alpha == '$') return NUL;//空串44 else if(VT.find(alpha) != VT.end()) return T;//终结符45 else if(VN.find(alpha) != VN.end()) return N;//非终结符46 else return NON;//非法字符47 } 主函数的流程很简单，从文件读入指定格式的文法，然后依次求文法的FIRST集、FOLLOW集
1 int main() 2 { 3 FREAD("grammar2.txt");//从文件读取文法 4 int numN = 0; 5 int numT = 0; 6 char c = ' '; 7 S = getchar();//开始符号 8 printf("%c", S); 9 VN.insert(S);10 numN++;11 while((c=getchar()) != '\n'){ //读入非终结符12 printf("%c", c);13 VN.insert(c);14 numN++;15 }16 pn();17 while((c=getchar()) != '\n'){ //读入终结符18 printf("%c", c);19 VT.insert(c);20 numT++;21 }22 pn();23 REP(numN){ //读入产生式24 c = getchar();25 int n; RINT(n);26 while(n--){27 char body[MAX_N];28 scanf("%s", body);29 printf("%c --> %s\n", c, body);30 P.insert(Production(c, body));31 }32 getchar();33 }34 35 get_first();//生成FIRST集36 for(vn = VN.begin(); vn != VN.end(); vn++){ //打印非终结符的FIRST集37 printf("FIRST(%c) = { ", *vn);38 for(first = FIRST[*vn].begin(); first != FIRST[*vn].end(); first++){39 printf("%c, ", *first);40 }41 printf("}\n");42 }43 44 get_follow();//生成非终结符的FOLLOW集45 for(vn = VN.begin(); vn != VN.end(); vn++){ //打印非终结符的FOLLOW集46 printf("FOLLOW(%c) = { ", *vn);47 for(follow = FOLLOW[*vn].begin(); follow != FOLLOW[*vn].end(); follow++){48 printf("%c, ", *follow);49 }50 printf("}\n");51 }52 return 0;53 } 其中文法文件的数据格式为（按照平时做题的输入格式设计的）：
第一行：所有非终结符，无空格，第一个为开始符号；
第二行：所有终结符，无空格；
剩余行：每行描述了一个非终结符的所有产生式，第一个字符为产生式头（非终结符），后跟一个整数位候选式的个数n，之后是n个以空格分隔的字符串为产生式体。
示例文件如下：（注：非终结符本应都用大写字母，原题用的是加上标的方法，如E′，但我用char型存每个符号，所以用的是相应的小写字母，如e）
1 EeTtFfP2 +*()^ab3 E 1 Te4 e 2 +E $5 T 1 Ft6 t 2 T $7 F 1 Pf8 f 2 *f $9 P 4 (E) ^ a b
求FIRST集的部分：
1 void get_first(){ //生成FIRST集 2 for(vt = VT.begin(); vt != VT.end(); vt++) 3 FIRST[*vt].insert(*vt);//终结符的FIRST集包含它自身 4 FIRST[nullStr].insert(nullStr);//空串的FIRST集包含它自身 5 bool flag = true; 6 while(flag){ //上一轮迭代中集合有扩大 7 flag = false; 8 for(vn = VN.begin(); vn != VN.end(); vn++){ //对于每个非终结符 9 for(p = P.begin(); p != P.end(); p++){10 //(*p).print();11 if(p->head == *vn){ //找所有左部为A的产生式12 int before = FIRST[*vn].size();13 put_body(*vn, &(p->body)[0]);14 if(FIRST[*vn].size() > before)//集合有扩大15 flag = true;16 //printf("%c size %d -> %d\n", *vn, before, FIRST[*vn].size());17 }18 }19 } 20 }21 } 与FIRST集相关的几个辅助函数：
1 void put_first_first(char A, char B){ //把FIRST[B]-{$}加到FIRST[A]2 first = FIRST[B].begin();3 for(; first != FIRST[B].end(); first++){4 if(*first != nullStr)5 FIRST[A].insert(*first);6 }7 } 1 void put_body(char A, char* pb){ //用产生式体从pb开始往后的部分扩充A的FIRST集 2 if(*pb == '\0'){ //抵达产生式体的末尾 3 FIRST[A].insert(nullStr);//向FIRST(A)加入空串 4 return ; 5 } 6 switch(get_type(*pb)){ 7 case 1://pb[0]为非终结符，把pb[0]的FIRST集加到A的FIRST集 8 put_first_first(A, *pb); 9 if(FIRST[*pb].find(nullStr) != FIRST[*pb].end())10 put_body(A, pb+1);11 break;12 case 0://pb[0]位终结符，把pb[0]加到A的FIRST集13 FIRST[A].insert(*pb);14 break;15 case 2: //pb[0]为空，把空串加入A的FIRST集16 FIRST[A].insert(nullStr);17 break;18 default: return ;19 }20 }
求FOLLOW集的部分
1 void get_follow(){ //生成FOLLOW集 2 FOLLOW[S].insert('#');//结束符放入文法开始符号的FOLLOW集 3 bool flag = true; 4 while(flag){ 5 flag = false; 6 for(vn = VN.begin(); vn != VN.end(); vn++){ //对于每个非终结符 7 for(p = P.begin(); p != P.end(); p++){ 8 //(*p).print(); 9 char A = p->head;10 int i;11 for(i=0; (p->body)[i+1] != '\0'; i++){12 char B = (p->body)[i];13 char beta = (p->body)[i+1];14 int before = FOLLOW[B].size();15 if(get_type(B) == N){ //跟在B后面的可以扩充B的FOLLOW集16 put_follow_first(B, beta);17 if(get_type(beta) == NUL)//beta为空串18 put_follow_follow(B, A);19 else if(FIRST[beta].find(nullStr) != FIRST[beta].end())20 put_follow_follow(B, A);21 if(FOLLOW[B].size() > before) flag = true;22 //printf("%c size %d -> %d\n", B, before, FOLLOW[B].size());23 }24 }25 put_follow_follow((p->body)[i], A);26 }27 } 28 }29 } 与FOLLOW集相关的几个辅助函数：
1 void put_follow_first(char B, char beta){ //把FIRST[beta]加到FOLLOW[B]2 first = FIRST[beta].begin();3 for(; first != FIRST[beta].end(); first++){4 if(*first != nullStr)5 FOLLOW[B].insert(*first);6 }7 } 1 void put_follow_follow(char B, char A){ //把FOLLOW[A]加到FOLLOW[B]2 follow = FOLLOW[A].begin();3 for(; follow != FOLLOW[A].end(); follow++){4 FOLLOW[B].insert(*follow);5 }6 } 运行结果（请忽略集合最后一个元素后的逗号。。。）：
注：
1. 语法分析的每个终结符号实际上代表一个单词，是从词法分析器获取的，这里为了简化问题所以只用了一个char型表示；而每个非终结符号则是一个语法单元，这里同样用char型表示了；
2. 感觉我的实现稍显复杂，C++的集合操作不太会用（没有找到原生的类似.addAll这样的方法，所以是自己用迭代器一个个加的），考完试用其他语言实现一个更简洁的。
3. 这样的算法用程序实现并不复杂，但是它规则比较多，且退出的条件是“集合不再增大”，手算起来一轮一轮的容易乱。祝我期末好运吧。