构造FIRST集和FOLLOW集的方法

【编译原理】语法分析LL（1）分析法的FIRST和FOLLOW集 近来复习编译原理，语法分析中的⾃上⽽下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集都不再增⼤为⽌。

⽼师和同学能很敏锐地求出来，⽽我只能按照规则，像程序⼀样⼀条条执⾏。

于是我把这个过程写成了程序，如下：数据元素的定义：1const int MAX_N = 20;//产⽣式体的最⼤长度2const char nullStr = '$';//空串的字⾯值3 typedef int Type;//符号类型45const Type NON = -1;//⾮法类型6const Type T = 0;//终结符7const Type N = 1;//⾮终结符8const Type NUL = 2;//空串910struct Production//产⽣式11 {12char head;13char* 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 }20bool operator<(const Production& p)const{//内部const则外部也为const21if(head == p.head) return body[0] < p.body[0];//注意此处只适⽤于LL(1)⽂法，即同⼀VN各候选的⾸符不能有相同的，否则这⾥的⼩于符号还要向前多看⼏个字符，就不是LL(1)⽂法了22return head < p.head;23 }24void print() const{//要加const25 printf("%c -- > %s\n", head, body);26 }27 };2829//以下⼏个集合可以再封装为⼀个⼤结构体--⽂法30set<Production> P;//产⽣式集31set<char> VN, VT;//⾮终结符号集，终结符号集32char S;//开始符号33 map<char, set<char> > FIRST;//FIRST集34 map<char, set<char> > FOLLOW;//FOLLOW集3536set<char>::iterator first;//全局共享的迭代器，其实觉得应该⽤局部变量37set<char>::iterator follow;38set<char>::iterator vn;39set<char>::iterator vt;40set<Production>::iterator p;4142 Type get_type(char alpha){//判读符号类型43if(alpha == '$') return NUL;//空串44else if(VT.find(alpha) != VT.end()) return T;//终结符45else if(VN.find(alpha) != VN.end()) return N;//⾮终结符46else return NON;//⾮法字符47 }主函数的流程很简单，从⽂件读⼊指定格式的⽂法，然后依次求⽂法的FIRST集、FOLLOW集1int main()2 {3 FREAD("grammar2.txt");//从⽂件读取⽂法4int numN = 0;5int numT = 0;6char c = '';7 S = getchar();//开始符号8 printf("%c", S);9 VN.insert(S);10 numN++;11while((c=getchar()) != '\n'){//读⼊⾮终结符12 printf("%c", c);13 VN.insert(c);14 numN++;15 }16 pn();17while((c=getchar()) != '\n'){//读⼊终结符18 printf("%c", c);19 VT.insert(c);20 numT++;21 }22 pn();23 REP(numN){//读⼊产⽣式24 c = getchar();25int n; RINT(n);26while(n--){27char body[MAX_N];28 scanf("%s", body);29 printf("%c --> %s\n", c, body);30 P.insert(Production(c, body));31 }32 getchar();33 }3435 get_first();//⽣成FIRST集36for(vn = VN.begin(); vn != VN.end(); vn++){//打印⾮终结符的FIRST集37 printf("FIRST(%c) = { ", *vn);38for(first = FIRST[*vn].begin(); first != FIRST[*vn].end(); first++){39 printf("%c, ", *first);40 }41 printf("}\n");42 }4344 get_follow();//⽣成⾮终结符的FOLLOW集45for(vn = VN.begin(); vn != VN.end(); vn++){//打印⾮终结符的FOLLOW集46 printf("FOLLOW(%c) = { ", *vn);47for(follow = FOLLOW[*vn].begin(); follow != FOLLOW[*vn].end(); follow++){48 printf("%c, ", *follow);49 }50 printf("}\n");51 }52return0;53 }主函数其中⽂法⽂件的数据格式为（按照平时做题的输⼊格式设计的）：第⼀⾏：所有⾮终结符，⽆空格，第⼀个为开始符号；第⼆⾏：所有终结符，⽆空格；剩余⾏：每⾏描述了⼀个⾮终结符的所有产⽣式，第⼀个字符为产⽣式头（⾮终结符），后跟⼀个整数位候选式的个数n，之后是n个以空格分隔的字符串为产⽣式体。

计算f i r s t集合和f o l l o w集合--编译原理计算first 集合和follow 集合姓名：彦清 学号：E10914127一、实验目的输入：任意的上下文无关文法。

输出：所输入的上下文无关文法一切非终结符的first 集合和follow 集合。

二、实验原理设文法G[S]＝（V N ，V T ，P ，S ），则首字符集为：FIRST （α）＝{a | α⇒*a β，a ∈V T ，α,β∈V *}。

若α⇒*ε，ε∈FIRST （α）。

由定义可以看出，FIRST （α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。

所以FIRST 集也称为首符号集。

设α＝x 1x 2…x n ，FIRST （α）可按下列方法求得：令FIRST （α）＝Φ，i ＝1；（1）若x i ∈V T ，则x i ∈FIRST （α）； （2） 若x i ∈V N ；① 若ε∉FIRST （x i ），则FIRST （x i ）∈FIRST （α）；② 若ε∈FIRST （x i ），则FIRST （x i ）－{ε}∈FIRST （α）；（3） i ＝i+1，重复（1）、（2），直到x i ∈V T ，（i ＝2，3，…，n ）或x i ∈V N 且若ε∉FIRST （x i ）或i>n 为止。

当一个文法中存在ε产生式时，例如，存在A →ε，只有知道哪些符号可以合法地出现在非终结符A 之后，才能知道是否选择A →ε产生式。

这些合法地出现在非终结符A 之后的符号组成的集合被称为FOLLOW 集合。

下面我们给出文法的FOLLOW 集的定义。

设文法G[S]＝（V N ，V T ，P ，S ），则FOLLOW （A ）＝{a | S ⇒… Aa …，a ∈V T }。

若S ⇒*…A ，#∈FOLLOW （A ）。

由定义可以看出，FOLLOW （A ）是指在文法G[S]的所有句型中，紧跟在非终结符A 后的终结符号的集合。

编译原理实验+求first集和follow集+代码/*说明：输入格式：每行输入一个产生式，左部右部中间的→用空格代替。

非终结符等价于大写字母^ 表示空输入到文件结束，或用 0 0 结尾。

Sample Input：(习题5·3):S MHS aH LSoH ^K dMLK ^L eHfM KM bLM0 0*/#include#include#include#include#includeusing namespace std;char l;string r;multimap sentence; //存储产生式multimap senRever; //产生式逆转set ter; //非终结符集合map toEmpty; //非终结符能否推出空bool flag;set fir; // 保存单个元素的first集set follow; //保存单个元素的follow集vector rightSide; //右部char Begin;bool capL(char c) //字母是否大写{if(c<='Z' && c>='A')return true;return false;}/*bool lowerL(char c) //小写字母{if(c<='z' && c>='a')return true;return false;}*/bool CapLString(string s) // 大写字符串{for(int i=0; iif(!capL(s[i])) {return false;}}return true;}bool isToEmpty(char ch) // 判断终结符能否推出空{bool flag;// for(set::iterator sIter = ter.begin(); sIter!=ter.end(); ++sIter) {flag = false;multimap::iterator mIter = sentence.find(ch);int cnt = sentence.count(ch);for(int i=0; iif(mIter->second=="^") {return true;// toEmpty[ch] = true;}else if(CapLString(mIter->second)){string s(mIter->second);bool flag2 = true;for(int j=0; jif(!isToEmpty(s[j]) || s[j]==ch) {flag2 = false;break;}}if(flag2) { // 右部全为终结符，全能推出空return true;}}}// }return false;}void getFirst(char ch, set &First) //求单个元素的 FIRST集{// if(flag)// return;multimap::iterator imul = sentence.find(ch);if(imul==sentence.end())return;int sum = sentence.count(imul->first);// cout<first<<endl;for(int i=0; i// cout<second<<endl;string s(imul->second);for(int j=0; jif(!capL(s[j])) {// cout<<" "<<s[j]<<endl;First.insert(s[j]);// flag = true;break;}else if(capL(s[j])) {if(s[j]==ch) { //有左递归,跳出循环break;;}getFirst(s[j], First);if(toEmpty[s[j] ]==false) {break;}}}}flag = true;}bool isLast(string s, char ch) //ch 是否是 s 的直接或间接的最后一个非终结符{if(!capL(ch))return false;for(int i=s.size()-1; i>=0; i--) {if(ch==s[i])return true;if(!capL(s[i]) || toEmpty[s[i] ]==false) {return false;}}return false;}void getFollow(char ch, set<cha</cha</s[j]<<endl;</endl;</endl;r> &follow) //求单个元素的 FOLLOW集{if(!capL(ch))return;for(vector::iterator iter=rightSide.begin(); iter!=rightSide.end(); ++iter) {for(int i=0; i<(*iter).size(); i++) {if(ch==(*iter)[i] && i!=(*iter).size()-1) {if(!capL((*iter)[i+1])) {follow.insert((*iter)[i+1]);}else {getFirst((*iter)[i+1], follow);}}if(ch==(*iter)[i] && i==(*iter).size()-1) { //判断是否是右部的最后一个非终结符 follow +#follow.insert('#');}else if(ch==(*iter)[i] && i<(*iter).size()-1){ //不是最后一个但之后全是非终结符且都能推出空 follow +#bool flag1=true;for(int j=i+1;j<(*iter).size(); j++) {if(!capL((*iter)[j]) || toEmpty[(*iter)[j]]==false) {flag1 = false;if(!capL((*iter)[j])) {follow.insert((*iter)[j]);}break;}}if(flag1 == true) {follow.insert('#');}}}if(isLast(*iter, ch)) { //ch是*iter的最后一个符号（直接或间接）int n = senRever.count(*iter);multimap::iterator mIter = senRever.find(*iter);for(int i=0 ;iif(mIter->second!=ch )getFollow(mIter->second, follow);}}}}int main(){int cnt=0;while(cin>>l>>r) {if(cnt==0) {Begin = l;cnt++;}if(l=='0')break;sentence.insert(make_pair(l, r)); //产生式senRever.insert(make_pair(r,l));ter.insert(l); //非终结符集合(左部)rightSide.push_back(r); //右部的集合/* if(r=="^") { // 判断是否有非终结符->^toEmpty[l] = true;}else {if(toEmpty.find(l)==toEmpty.end()) {toEmpty[l] = false;}} */}for(set::iterator sIter = ter.begin(); sIter!=ter.end(); ++sIter) { // 判断是否有非终结符->^if(isToEmpty(*sIter) ) {toEmpty[*sIter] = true;}else {toEmpty[*sIter] = false;}}for(set::iterator iter=ter.begin(); iter!=ter.end(); iter++) {flag = false;cout<<*iter<<" FIRST集 :";fir.clear();getFirst(*iter, fir);for(set::iterator iterF=fir.begin(); iterF!=fir.end(); iterF++) {cout<<" "<<*iterF;}cout<<endl;follow.clear();getFollow(*iter, follow);cout<<" FOLLOW集:";if(*iter==Begin) {cout<<" #";}for(set::iterator iterF=follow.begin(); iterF!=follow.end(); ++iterF) {if(*iterF!='^')cout<<" "<<*iterF;}cout<<endl<<endl;}system("pause");return 0;}</endl<<endl; </endl;。

First集合的求法：First集合最终是对产生式右部的字符串而言的，但其关键是求出非终结符的First集合，由于终结符的First集合就是它自己，所以求出非终结符的First集合后，就可很直观地得到每个字符串的First集合。

1. 直接收取：对形如U－a…的产生式（其中a是终结符），把a收入到First(U)中2. 反复传送：对形入U－P…的产生式（其中P是非终结符），应把First(P)中的全部内容传送到First(U)中。

Follow集合的求法：Follow集合是针对非终结符而言的，Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合，特别地，“#”是识别符号的后随符。

1. 直接收取：注意产生式右部的每一个形如“…Ua…”的组合，把a直接收入到Follow(U)中。

2．直接收取：对形如“…UP…”(P是非终结符)的组合，把First(P)除ε直接收入到Follow(U)中。

3．反复传送：对形如P－…U的产生式（其中U是非终结符），应把Follow(P)中的全部内容传送到Follow(U)中。

(或 P－…UB且First(B)包含ε，则把First(B)除ε直接收入到Follow(U)中，并把Follow(P)中的全部内容传送到Follow(U)中)例1：判断该文法是不是LL(1)文法，说明理由 S→ABc A→a|ε B→b|ε？First集合求法就是：能由非终结符号推出的所有的开头符号或可能的ε，但要求这个开头符号是终结符号。

如此题A可以推导出a和ε，所以FIRST（A）=｛a，ε｝；同理FIRST （B）={b,ε};S可以推导出aBc，还可以推导出bc，还可以推导出c，所以FIRST(S）=｛a，b，c｝。

Follow集合的求法是：紧跟随其后面的终结符号或＃。

但文法的识别符号包含＃，在求的时候还要考虑到ε。

具体做法是把所有包含你要求的符号的产生式都找出来，再看哪个有用。

摘要：编译原理是计算机科学与技术专业最重要的一门专业基础课程，内容庞大，涉及面广，知识点多。

由于该课程教、学难度都非常大，往往费了大量时间而达不到预期教学效果俗语说：学习的最好方法是实践。

本次课程设计的目的正是基于此，力求为学生提供一个理论联系实际的机会，通过布置一定难度的课题，要求学生独立完成。

我们这次课程设计的主要任务是编程实现对给定文法的FIRST 集和FOLLOW集的求解。

通过实践，建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验、探索前言知识的习惯，树立团队协作精神。

同时，课程设计可以充分弥补课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助学生从全局角度把握课程体系。

关键词：编译原理；FIRST集；FOLLOW集目录1 课题综述 (1)1.1 课题来源 (1)1.2 课题意义 (1)1.3 预期目标 (1)1.4 面对的问题 (1)1.5 需解决的关键技术 (1)2 系统分析 (2)2.1 基础知识 (2)2.1.1 FIRST集定义 (2)2.1.2FIRST集求解算法.................................................................... 错误!未定义书签。

2.1.3FOLLOW集的定义 (4)2.1.4 FOLLOW集算法 (4)2.2 解决问题的基本思路 (4)2.3 总体方案 (4)3 系统设计 (5)3.1 算法实现 (5)3.2 流程图 (6)4 代码编写 (10)5 程序调试 (15)6 运行与测试 (15)1 课题综述1.1 课题来源文法：包含若干终结符，非终结符，由终结符与非终结符组成的产生式。

本次课程设计就是对产生式进行左递归分析，待无左递归现象后进行FIRST集与FOLLOW集的求解。

1.2 课题意义由文法产生的若干个句子有可能是合法的或者不合法的，也有可能产生歧义，所以要消除歧义先消除文法左递归，然后根据求得的FIRST集与FOLLOW 集构造分析表，分析给定句子的合法性。

import java.awt.*;import java.awt.event.*;import javax.swing.*;import javax.swing.table.DefaultTableModel;import java.sql.*;import java.util.Vector;public class LL1 extends JFrame implements ActionListener { /****/private static final long serialVersionUID = 1L;JTextField tf1;JTextField tf2;JLabel l;JButton b0;JPanel p1, p2, p3;JTextArea t1, t2, t3;JButton b1, b2, b3;JLabel l0, l1, l2, l3, l4;JTable table;Statement sta;Connection conn;ResultSet rs;DefaultTableModel dtm;String Vn[] = null;Vector<String> P = null;int firstComplete[] = null;// 存储已判断过first的数据char first[][] = null;// 存储最后first结果int followComplete[] = null;// 存储已判断过follow的数据char follow[][] = null;// 存储最后follow结果char select[][] = null;// 存储最后select结果int LL = 0;// 标记是否为LL（1）String vt_tou[] = null;// 储存VtObject shuju[][] = null;// 存储表达式数据char yn_null[] = null;// 存储能否推出空LL1() {setLocation(100, 0);setSize(700, 780);tf1 = new JTextField(13);tf2 = new JTextField(13);l = new JLabel(">>");l0 = new JLabel("输入字符串：");l1 = new JLabel("输入的文法为：");l2 = new JLabel(" ");l3 = new JLabel("分析的结果：");l4 = new JLabel("预测分析表：");// p1=new JPanel();p2 = new JPanel();p3 = new JPanel();t1 = new JTextArea(24, 20);t2 = new JTextArea(1, 30);t3 = new JTextArea(24, 40);b0 = new JButton("确定(S为开始)");b1 = new JButton(" 判断文法 ");b2 = new JButton("输入");b3 = new JButton("清空");table = new JTable();JScrollPane jp1 = new JScrollPane(t1);JScrollPane jp2 = new JScrollPane(t2);JScrollPane jp3 = new JScrollPane(t3);p2.add(tf1);p2.add(l);p2.add(tf2);p2.add(b0);p2.add(b1);p2.add(l0);p2.add(l2);p2.add(jp2);p2.add(b2);p2.add(b3);p2.add(l1);p2.add(l3);p2.add(jp1);p2.add(jp3);p3.add(l4);p3.add(new JScrollPane(table));add(p2, "Center");add(p3, "South");b0.addActionListener(this);b1.addActionListener(this);b2.addActionListener(this);b3.addActionListener(this);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);table.setPreferredScrollableViewportSize(new Dimension(660, 200));setVisible(true);}////////////////////界面设计public void actionPerformed(ActionEvent e) {if (e.getSource() == b0) {String a = tf1.getText();String b = tf2.getText();t1.append(a + '→' + b + '\n');}if (e.getSource() == b1) {t3.setText("");int Vnnum = 0, k;Vn = new String[100];P = new Vector<String>();String s[] = t1.getText().split("\n");for (int i = 0; i < s.length; i++) {if (s.length < 2) {t3.setText("文法输入有误，请重新输入");// 判断长度是否符合return;}if (s[i].charAt(0) <= 'Z' && s[i].charAt(0) >= 'A'&& s[i].charAt(1) == '→') {for (k = 0; k < Vnnum; k++) {if (Vn[k].equals(s[i].substring(0, 1))) {break;}}if (Vnnum == 0 || k >= Vnnum) {Vn[Vnnum] = s[i].substring(0, 1);// 存入Vn数据Vnnum++;}P.add(s[i]);} else {t3.setText("文法输入有误，请重新输入");return;}}yn_null = new char[100];first = new char[Vnnum][100];int flag = 0;String firstVn[] = null;firstComplete = new int[Vnnum];for (int i = 0; Vn[i] != null; i++) // 依次求 FIRST**{flag = 0;firstVn = new String[20];if ((flag = add_First(first[i], Vn[i], firstVn, flag)) == -1) return;firstComplete[i] = 1;}t3.append("first集：" + "\n"); // 显示FIRST**for (int i = 0; Vn[i] != null; i++) {t3.append("first(" + Vn[i] + ")={ ");for (int j = 0; first[i][j] != '\0'; j++) {t3.append(first[i][j] + " , ");}t3.append("}" + "\n");}follow = new char[Vnnum][100];String followVn[] = null;followComplete = new int[Vnnum];for (int i = 0; Vn[i] != null; i++) // 求FOLLOW**{flag = 0;followVn = new String[20];if(i==0){}else if ((flag = tianjiaFollow(follow[i], Vn[i], followVn, flag)) == -1)return;followComplete[i] = 1;}t3.append("follow集：" + "\n"); // 显示FOLLOW**for (int i = 0; Vn[i] != null; i++) {t3.append("follow(" + Vn[i] + ")={ ");for (int j = 0; follow[i][j] != '\0'; j++) {t3.append(follow[i][j] + " , ");}t3.append("}" + "\n");}select = new char[P.size()][100];for (int i = 0; i < P.size(); i++) // 求SELECT**{flag = 0;tianjiaSelect(select[i], (String) P.elementAt(i), flag);}t3.append("select集：" + "\n"); // 显示SELECT**for (int i = 0; i < P.size(); i++) {t3.append("select(" + (String) P.elementAt(i) + ")={ ");for (int j = 0; select[i][j] != '\0'; j++) {t3.append(select[i][j] + " , ");}t3.append("}" + "\n");}for (int i = 0; Vn[i] != null; i++)// 判断select交集是否为空{int biaozhi = 0;char save[] = new char[100];for (int j = 0; j < P.size(); j++) {String t = (String) P.elementAt(j);if (t.substring(0, 1).equals(Vn[i])) {for (k = 0; select[j][k] != '\0'; k++) {if (puanduanChar(save, select[j][k])) {save[biaozhi] = select[j][k];biaozhi++;} else// 当有交集时，不为LL（1）文法{t3.append("不是LL（1）文法！！" + "\n");return;}}}}}char Vt[] = new char[100];int biaozhi = 0;for (int i = 0; i < P.size(); i++) {String t = (String) P.elementAt(i);for (int j = 2; j < t.length(); j++)// 提取表达式右侧的终结符存入Vt{if (t.charAt(j) > 'Z' || t.charAt(j) < 'A') {if (puanduanChar(Vt, t.charAt(j))) {Vt[biaozhi] = t.charAt(j);biaozhi++;}}}}if (puanduanChar(Vt, '#'))// 若可推出空集，则将#加入Vt。

FIRST集和FOLLOW集求法龙书算法：First：（1）、如果X是终结符，那么First（X） = X;（2）、如果X是⾮终结符，且XàY1Y2......Yk是⼀个产⽣式，其中k>=1;那么如果对于某个I, a在First（Yi）中,且#（空串）在所有的First（Y1）…..First（Yi-1）中，就吧a加⼊到First（X）中。

（3）、如果Xà#(空串)是⼀个产⽣式，那么将#加⼊到First（X）中。

Follow：（1）、将$放⼊到Follow（S）中，其中S是开始符号，⽽$是输⼊右端结束的标记。

（2）、如果存在⼀个产⽣式AàaBb，那么First（b）中除#（空串）外地所有符号都在Follow（B）中。

（3）、如果存在⼀个产⽣式AàaB, 或存在AàaBb且First（b）包含#（空串），那么Follow（A）中的所有符号都在Follow（B）中。

⾃⼰理解：First：（看X的产⽣式）（1）、如果X是终结符，那么First（X）= X；（2）、如果X是⾮终结符，且XàY1Y2......Yk，i=1；1）、将First（Yi）加⼊到First（X）中，2）、如果#包含着First（Yi）中，i++，重复1）；3）、如果#不包含在First（Yi）中，First（X）计算完成；（3）、如果Xà#(空串)是⼀个产⽣式，那么将#加⼊到First（X）中。

Follow：（看在右边有B的产⽣式）（1）、将$放⼊到Follow（S）中，其中S是开始符号，⽽$是输⼊右端结束的标记。

（2）、如果存在⼀个产⽣式AàaBb，那么First（b）中除#（空串）外地所有符号都在Follow（B）中。

（3）、如果存在⼀个产⽣式AàaB, 或存在AàaBb且First（b）包含#（空串），那么Follow（A）中的所有符号都在Follow（B）中。

1.#include "stdafx.h"2.#include "LR.h"3.#include "MLR1.h"4.5.#ifdef _DEBUG6.#undef THIS_FILE7.static char THIS_FILE[]=__FILE__;8.#define new DEBUG_NEW9.#endif10.//----调试部分使用的代码11.CString MLR1::GetFirst(int i){12.if(i<0||i>=GetIdentNum())return"";13.return FirstSet5(m_first[i].Fi,m_first[i].flag&2);14.}15.CString MLR1::GetFollow(int i){16.if(i<0||i>=GetIdentNum())return"";17.return FollowSet1(m_first[i].Fo,m_first[i].flag&0x08);18.}19.//----构造部分20.MLR1::MLR1(){21.}22.MLR1::~MLR1(){23.}24.void MLR1::ReSet(FILE* pf){25.//使用文件指针pf来重新驱动程序26.int i;27. p_file=pf;28. list_Express.RemoveAll();29. list_Ident.RemoveAll();30.for(i=0;i<MAP_SIZE;I++) p="(char*)m_first+sizeof(s_first)*MAX_IDENT-1;"for(char* bit_map[i]="0;">=(char*)m_first;p--)31. *p=0;32. Lex3();33. FirstSet6();34.// FollowSet3();35.}36.//----输入分析部分37.bool MLR1::Lex1(){38.//截取一个分号段到tocken中39.//功能字符取其负数40.char ch=0;41.bool end=false;42. token_len=0;43.if(feof(p_file))return false;44.while(!end&&!feof(p_file)){45.if(token_len>=LINE_LENGTH)break;46.if(fread(&ch,1,1,p_file)<=0)break;47.if(ch<=0)goto error;48.switch(ch){49.case';':50. end=true;51.case'<':52.case'>':53.case'=':54. ch=-ch;55.break;56.case'\\':57. fread(&ch,1,1,p_file);58.if(ch<=0)goto error;59.break;60. }61. token[token_len++]=ch;62. }63. token[token_len]=0;64.return true;65.error:66. fprintf(stderr,"must be 1--127");67.return false;68.}69.int MLR1::Lex2_1(char*&s,bool isUse){70.//识别非终结符并加入list_Ident71.char ident[ID_LENGTH+1];72.int t=0;73.if((int)*s++!=-'<')return 0;74.if(isalpha(*s))ident[t++]=*s++;75.else return 0;76.while(isalpha(*s)||isdigit(*s))ident[t++]=*s++;77.while(*s=='\'')ident[t++]=*s++;78.if((int)*s++!=-'>')return 0;79.if(t==0)return 0;80. ident[t]=0;81.for(t=list_Ident.GetSize()-1;t>=0;t--)82.if(list_Ident[t]==(CString)ident)break;83.if(t<0){84.if(list_Ident.GetSize()>=MAX_IDENT)return false;85. list_Ident.Add((CString)ident);86. t=list_Ident.GetSize()-1;87.if(isUse)bit_map[t/8]|=1<<(t%8);88. }89.if(!isUse)bit_map[t/8]&=~(1<<(t%8));90.return t+1;91.}92.bool MLR1::Lex2(){93.//将token中的非终结符用(-1) -- (-127)表示94.//进行语法判断<终结符>=符号表;95.register char *s,*d;96.char * end;97.int i;98. s=d=token;99. end=&token[token_len];100.if(i=Lex2_1(s))*d++=-i;101.else return false;102.if(*s++!=-'=')return false;103.while(s<END){ if(*p while(*p!="0){" *p="X+1;"char const判断表达式X能否推出LR_NULL *X){ MLR1::FirstSet1(const bool * 首先判断某非终结符能否推出LR_NULL ----First集 } true; return false; if(bit_map[i]!="0)return" i="0;i<MAP_SIZE;i++ )"for(int else list_Express.Add((CString)token); if(Lex2()) if(token_ len="=0)continue;"while(Lex1()){ 判断bit_map是否为全零，如果不是则表示有未定义的非终结符循环调用Lex1读入一句，调用Lex2进行语法分析 MLR1::Lex3(){ s<end; *d="0;" *d++="*s++;" }else if(i="Lex2_1(s,true ))*d++=-i;"if((int)*s="=-'<'){"if(*s="=-';')break;">=1){104.return false;105. }else{106.if(*p==*X)return false;107.if(!FirstSet2(*p))108.return false;109. }110. p++;111. }112.return true;113.}114.bool MLR1::FirstSet2(const char X){115.//判断非终结符X能否推出LR_NULL116. CString temp;117.if(m_first[-X-1].flag&0x40)return false;118.if(m_first[-X-1].flag&1)119.return (m_first[-X-1].flag&2)!=0;120. m_first[-X-1].flag|=0x40;121.for(int i=list_Express.GetSize();i>0;i--){122. temp=list_Express.GetAt(i-1);123.if(temp[0]==X){124.if(FirstSet1((LPCSTR)temp)){125. m_first[-X-1].flag|=3;126.return true;127. }128. }129. }130. m_first[-X-1].flag|=1;131. m_first[-X-1].flag^=0x40;132.return false;133.}134.bool MLR1::FirstSet3(const char *X,char*Fi){135.//求产生式X的First集放在F中,如果LR_NULL在First集中则返回true 136.//如果要求符号串的First集,就将X[0]设为0137.//假设X中不出现LR_NULL,LR_EOF和LR_EOS138.//假设F的长度为MAP_SIZE,有128b139.const char *p=X;140. X++;141.while(*X!=0){142.if(*X>=1){143. Fi[(*X)/8]|=1<<(*X)%8;144.return false;145. }else{146.if(*X==*p){147.if(!FirstSet2(*X))148.return false;149. }else if(!FirstSet4(*X,Fi)){150.return false;151. }152. }153. X++;154. }155.return true;156.}157.bool MLR1::FirstSet4(char const X,char*Fi){158.//求非终结符X的First集放在F中159.//如果LR_NULL在其中则返回true160. CString temp;161.if(m_first[-X-1].flag&0x40)return false;162.if((m_first[-X-1].flag&4)==0){163. m_first[-X-1].flag|=0x40;164.for(int i=list_Express.GetSize();i>0;i--){165. temp=list_Express.GetAt(i-1);166.if(temp[0]==X)167. FirstSet3((LPCSTR)temp,m_first[-X-1].Fi);168. }169. m_first[-X-1].flag|=4;170. m_first[-X-1].flag^=0x40;171. }172.if(Fi!=m_first[-X-1].Fi){173.for(int i=0;i<MAP_SIZE;I++) *p="t;"char } return for(i="0;i< MAP_SIZE;i++){" i; int为每个非终结符求First集 MLR1::FirstSet6(){ void (CString)t; if(has_null)*p++="LR_NULL;" *p+ +="i*8+j;"if(Fi[i]&(1<<j)) if(Fi[i])for(j="0;j<8;j++)" i,j; t[128];将集合表示的First变为字符串式 has_null){ char*Fi,bool MLR1::FirstSet5(const CString (m_first[-X-1 ].flag&2); Fi[i]|="m_first[-X-1].Fi[i];">0;i--){174.if((m_first[i-1].flag&1)==0)175. FirstSet2(-i);176. }177.for(i=list_Ident.GetSize();i>0;i--){178.if((m_first[i-1].flag&4)==0)179. FirstSet4(-i,m_first[i-1].Fi);180. }181.}182.CString MLR1::FollowSet1(const char*Fo,bool has_eof){183.//将集合表示的Follow变为字符串式184.char t[128];185.char *p=t;186.int i,j;187.for(i=0;i<MAP_SIZE;I++){ *p="0;"char bool * } return int (CString)t; *p++="i*8+j;" i,j; if(X 如果是非法符号则退出 *p; temp[LINE_LENGTH]; flag,rc="true;" flag.b5该符号的Follow集正在被计算 flag为真表示已经找到X,将找后继的第一个字符必须在执行前将LR_EOF加入识别符号的Follow集中只有在X的Follow集未被计算时才调用该函数求非终结符X的Follow集 Fo){ X,char MLR1::FollowSet2(const if(has_eof)*p++="LR_NULL;"if(Fo[i]&(1<<j)) if(Fo[i])for(j="0;j<8;j++)">=0||X<-MAX_IDENT)return true;188.//如果该符号正被计算则退出189.if(m_first[-X-1].flag&0x20)return false;190.//如果该符号为被计算则计算191.if((m_first[-X-1].flag&0x10)==0){192. m_first[-X-1].flag|=0x20;193.for(i=list_Express.GetSize();i>0;i--){194. sprintf(temp,list_Express.GetAt(i-1));195. flag=false;196. p=temp+1;197.while(*p!=0){198.if(!flag){199.if(*p==X){200.//表达式中出现了符号X201. flag=true;}202. }else{203.if(*p>0){204.//规则2:X后碰上终结符205. flag=false;206. Fo[*p/8]|=1<<(*p%8);207. }else{208.//规则2:X后碰上非终结符则并上它的First集209.for(j=0;j<MAP_SIZE;J++) } return for(i="0;i<M AP_SIZE;i++)" i; int void m_first[0].flag|="0x08;"求各非终结符的Follow 集 MLR1::FollowSet3(){ rc; Fo[i]|="m_first[-X-1].Fo[i];"if(Fo!="m_fir st[-X-1].Fo){" m_first[-X-1].flag^="0x20;"if(rc)m_first[-X-1].flag|="0x10;" m_first[-X-1].flag|="0x08;"if(m_first[-temp[0]-1].flag&0x08) F o[j]|="m_first[-*p-1].Fi[j];"for(j="0;j<MAP_SIZE;j++)" rc="false;"if (!FollowSet2(temp[0],m_first[-temp[0]-1].Fo)) 如果是自反关系则不计算规则3:将temp[0]的Follow集并到Fo上if(flag&&(X!="temp[0])){" p++; flag="false;"if((m_first[-*p-1].fla g&2)="=0)"如果X可以推出LR_NULL则继续>0;i--){210.if((m_first[i-1].flag&0x10)==0){211. FollowSet2(-i,m_first[i-1].Fo);212. }213. }214.}。

第1篇摘要：Follow集合在数据库查询中具有重要的应用价值，本文旨在介绍Follow集合的概念、求法以及在数据库查询中的应用。

通过详细阐述Follow集合的原理和方法，帮助读者深入理解其重要性，并学会在实际应用中有效利用Follow集合。

一、引言在数据库查询过程中，我们常常需要关注某些记录的关联记录，即所谓的“后续记录”。

为了方便查询，我们可以利用Follow集合来表示这些后续记录。

本文将介绍Follow集合的概念、求法以及在数据库查询中的应用。

二、Follow集合的概念1. 定义：Follow集合是指在一个数据表中，对于某一记录，所有与之存在关联关系的记录的集合。

2. 特点：（1）无序性：Follow集合中的记录没有特定的顺序；（2）唯一性：对于某一记录，其Follow集合是唯一的；（3）动态性：Follow集合随着查询条件的改变而改变。

三、Follow集合的求法1. 算法概述求Follow集合的基本思路是：从某一记录出发，遍历整个数据表，查找与之存在关联关系的记录，并将其加入Follow集合。

具体算法如下：（1）初始化Follow集合为空；（2）遍历数据表中的所有记录；（3）对于每一条记录，查找其关联记录，并将其加入Follow集合；（4）重复步骤（2）和（3），直到遍历完所有记录。

2. 算法实现以下是一个基于Python的Follow集合求法示例：```pythondef follow_set(data, record_id):"""求Follow集合的函数:param data: 数据表:param record_id: 记录ID:return: Follow集合"""follow_set = set()for record in data:if record['id'] == record_id:for relation in record['relations']:follow_set.add(relation)else:for relation in record['relations']:if relation in follow_set:follow_set.add(record['id'])return follow_set```3. 算法优化在实际情况中，数据表可能非常大，导致Follow集合求法效率低下。