求LL1文法的FIRST和FOLLOW集合

发表于2021-12-08更新于2022-04-08阅读次数

实验实验

实验链接

编译原理实验要求，写了一个求LL1文法的FIRST和FOLLOW集合的代码
可放心食用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=333;

vector<string> e[maxn];//左边的非终结符的产生式
set<ll> FIRST[maxn];
set<ll> FOLLOW[maxn];
set<ll> sta;//左边的非终结符
ll start;
bool is_no_end(ll x){//判断是否为非终结符
    if('A'<=x && x<='Z')  return 1;
    else  return 0;
}
void init(){//终结符初始化
    for(ll i=0;i<maxn;i++)  if(!is_no_end(i))
        FIRST[i].insert(i);
}
void add(ll c,string s){//添加产生式
    e[c].push_back(s);
}
void in(){//处理输入
    string s;
    while(cin>>s){
        if(s=="Q")  break;
        s[1]=s[2]=' ';
        for(ll i=0;i<(ll)s.length();i++)  if(s[i]=='|')  s[i]=' ';
        stringstream ss(s);
        char c;
        ss>>c;sta.insert((ll)c);
        while(ss>>s)  add((ll)c,s);
    }  
}
bool found(set<ll> s,ll x){//查找集合s中是否有x
    for(auto i:s)  if(i==x)  return true;
    return false;
}
bool uni(set<ll>& a,set<ll>& b,ll x){
    //将集合a加入到集合b中，并不加入x元素
    //返回值:成功加入新元素返回true,否则返回false;
    ll flag=0;
    for(auto i:a)  if(i!=x){
        if(b.count(i)==0)  flag=1;
        b.insert(i);
    }
    if(flag)  return true;
    else  return false;
}
void fir(){//求每个非终结符的FIRST集合
    for(auto u:sta){//第一条规则
        for(auto v:e[u]){
            if(!is_no_end(v[0]) || v[0]=='@')  FIRST[u].insert(v[0]);
        }
    }
    while(1){
        ll flag=0;
        for(auto u:sta){//第二条规则
            for(auto v:e[u]){
                ll len=v.length();
                ll pos1=0,pos2=0;
                while(pos1<len && is_no_end(v[pos1]))  pos1++;
                while(pos2<pos1 && found(FIRST[(ll)v[pos2]],'@'))  pos2++;
                for(ll k=0;k<=min(pos2,len-1);k++)  if(uni(FIRST[(ll)v[k]],FIRST[u],'@'))  flag=1;
                if(pos2==len){
                    if(FIRST[u].count('@')==0)  flag=1;
                    FIRST[u].insert('@');
                }
            }
        }
        if(flag==0)  break;
    }
}
void fol(){//求每个非终结符的FOLLOW集合
    FOLLOW[start].insert('#');
    for(auto u:sta){//第二条规则
        for(auto v:e[u]){
            ll len=v.length();
            for(ll k=0;k<len;k++)  if(k!=len-1 && is_no_end(v[k])){
                uni(FIRST[(ll)v[k+1]],FOLLOW[(ll)v[k]],'@');
            }
        }
    }
    while(1){
        ll flag=0;
        for(auto u:sta){//第三条规则
            for(auto v:e[u]){
                ll len=v.length();
                for(ll k=0;k<len;k++)  if(is_no_end(v[k])){
                    ll t=k+1;
                    while(t<len && FIRST[(ll)v[t]].count('@'))  t++;
                    if(t==len)  if(uni(FOLLOW[u],FOLLOW[(ll)v[k]],' '))  flag=1;
                }
            }
        }
        if(flag==0)  break;
    }
}
void out(){//输出
    for(auto u:sta){
        cout<<(char)u<<" {";
        ll flag=0;
        for(auto j=FIRST[u].begin();j!=FIRST[u].end();j++){
            if(*j=='@'){
                flag=1;continue;
            }
            if(j==--FIRST[u].end() && flag!=1)  cout<<(char)(*j);
            else  cout<<(char)(*j)<<',';
        }
        if(flag)  cout<<'@';
        cout<<"} {";
        flag=0;
        for(auto j=FOLLOW[u].begin();j!=FOLLOW[u].end();j++){
            if(*j=='#'){
                flag=1;continue;
            }
            if(j==--FOLLOW[u].end() && flag!=1)  cout<<(char)(*j);
            else  cout<<(char)(*j)<<',';
        }
        if(flag)  cout<<'#';
        cout<<"}"<<endl;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<"请手动将代码中的开始符初始化"<<endl;
    init();//终结符初始化
    in();//处理输入
    start='S';//开始符初始化
    fir();//求每个非终结符的FIRST集合
    fol();//求每个非终结符的FOLLOW集合
    out();//输出
    return 0;
}
/*
例题3.8  开始符:E
A:=+TA|@
T:=FB
B:=*FB|@
F:=(E)|i
E:=TA
Q

例题3.9  开始符:S
S:=iESA|a
A:=eS|@
E:=b
Q

例题3.10  开始符:S
S:=LA
L:=i:|@
A:=i=e
Q
*/