{
if(!capL(ch))
}
void getFirst(char ch, set<char> &First)//求单个元素的FIRST集
{
multimap<char, string>::iterator imul = sentence.find(ch);
if(imul==sentence.end())
return;
int sum = sentence.count(imul->first);
（1）若xi∈VT，则xi∈FIRST（α）；
（2）若xi∈VN；
①若ε FIRST（xi），则FIRST（xi）∈FIRST（α）；
②若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）；
（3）i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若ε FIRST（xi）或i>n为止。
int cnt = sentence.count(ch);
for(int i=0; i<cnt; ++i, ++mIter) {
if(mIter->second=="^") {
return true;
}
else if(CapLString(mIter->second)){
string s(mIter->second);
bool flag2 = true;
for(int j=0; j<s.size(); j++) {
if(!isToEmpty(s[j]) || s[j]==ch) {
flag2 = false;
break;
}
}
if(flag2) {//右部全为终结符，全能推出空
return true;
}
}
}
//}
return false;
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的直接或间接的最后一个非终结符
vector<string> rightSide; //右部
char Begin;
bool capL(char c) //字母是否大写
{
if(c<='Z' && c>='A')
return true;
return false;
}
bool CapLString(string s) //大写字符串
{
for(int i=0; i<s.size(); i++) {
if(!capL(s[i])) {
rHale Waihona Puke turn false;}}
return true;
}
bool isToEmpty(char ch) //判断终结符能否推出空
{
bool flag;
flag = false;
multimap<char, string>::iterator mIter = sentence.find(ch);
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;
char l;
string r;
multimap<char, string> sentence; //存储产生式
若S …A，#∈FOLLOW（A）。
由定义可以看出，FOLLOW（A）是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。
FOLLOW集可按下列方法求得：
（1）对于文法G[S]的开始符号S，有#∈FOLLOW（S）；
（2）若文法G[S]中有形如B→xAy的规则，其中x，y∈V*，则FIRST（y）－{ε}∈FOLLOW（A）；
for(int i=0; i<sum; ++i, ++imul) {
string s(imul->second);
for(int j=0; j<s.size(); j++) {
if(!capL(s[j])) {
First.insert(s[j]);
break;
}
else if(capL(s[j])) {
FIRST（α）＝{a |α aβ，a∈VT，α,β∈V*}。
若α ε，ε∈FIRST（α）。
由定义可以看出，FIRST（α）是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。
设α＝x1x2…xn，FIRST（α）可按下列方法求得：
令FIRST（α）＝Φ，i＝1；
编译原理实验报告
实验名称计算first集合和follow集合
实验时间2016年6月8日
院系计算机科学与技术
班级计算机科学与技术（1）班
学号
姓名
1.试验目的：
输入：任意的上下文无关文法。
输出：所输入的上下文无关文法一切非终结符的first集合和follow集合。
2.实验原理：
设文法G[S]＝（VN，VT，P，S），则首字符集为：
当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。
设文法G[S]＝（VN，VT，P，S），则
FOLLOW（A）＝{a | S …Aa…，a∈VT}。
multimap<string, char> senRever; //产生式逆转
set<char> ter;//非终结符集合
map<char, bool>toEmpty;//非终结符能否推出空
bool flag;
set<char> fir;//保存单个元素的first集
set<char> follow; //保存单个元素的follow集
（3）若文法G[S]中有形如B→xA的规则，或形如B→xAy的规则且ε∈FIRST（y），其中x，y∈V*，则FOLLOW（B）∈FOLLOW（A）；
3.实验代码与结果：
输入格式：
每行输入一个产生式，左部右部中间的→用空格代替。
非终结符等价于大写字母
^表示空
输入到文件结束，或用0 0结尾。
以编译原理（清华大学第二版）5.6典型例题及答案中的例题一为例（96页）：