当前位置：文档库 › 编译原理实验+求first集和follow集+代码

编译原理实验+求first集和follow集+代码

/*
说明：
输入格式：
每行输入一个产生式，左部右部中间的→用空格代替。
非终结符等价于大写字母
^ 表示空
输入到文件结束，或用 0 0 结尾。

Sample Input：
(习题5·3):

S MH
S a
H LSo
H ^
K dML
K ^
L eHf
M K
M bLM
0 0

*/
#include
#include
#include
#include
#include
using 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<
for(int i=0; i// cout<second<string s(imul->second);
for(int j=0; jif(!capL(s[j])) {
// cout<<" "<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

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<
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<
}

system("pause");
return 0;
}