Untitled
unknown
plain_text
22 days ago
3.7 kB
2
Indexable
Never
C++ Code:- #include<bits/stdc++.h> using namespace std; set<char>FOLLOW[1000]; vector<string> G[1000]; set<char>FIRST[1000]; bool vis[1000]; void F(int start){ if(vis[start])return; for(int i=0;i<G[start].size();i++){ if(G[start][i]=="~"){ FIRST[start].insert('~'); } else if(!isupper(G[start][i][0])){ FIRST[start].insert(G[start][i][0]); } else{ bool flag; int k; for(k=0;k<G[start][i].length();k++){ char nxt=G[start][i][k]; if(!isupper(nxt)){ FIRST[start].insert(nxt); break; } if(!vis[nxt-'A']) F(nxt-'A'); flag=0; for(set<char>::iterator itr=FIRST[nxt-'A'].begin();itr!=FIRST[nxt-'A'].end();itr++){ if((*itr)=='~'){ flag=1; } else FIRST[start].insert(*itr); } if(!flag) break; } if(k==G[start][i].length()){ FIRST[start].insert('~'); } } } vis[start]=1; } void Follow(int start) { if(start==0){ FOLLOW[start].insert('$'); } for(int i=0;i<G[start].size();i++){ int j; for( j=0;j<G[start][i].size()-1;j++){ char ch=G[start][i][j]; if(isupper(ch)){ bool f=false; int k; for(k=j+1;k<G[start][i].size();k++){ char nx=G[start][i][k]; if(!isupper(nx)){ FOLLOW[ch-'A'].insert(nx); break; } else{ f=false; for(set<char>::iterator itr=FIRST[nx-'A'].begin();itr!=FIRST[nx-'A'].end();itr++){ if((*itr)=='~'){ f=true; } else FOLLOW[ch-'A'].insert(*itr); } if(!f)break; } } if(k==G[start][i].size()){ for(set<char>::iterator itr=FOLLOW[start].begin();itr!=FOLLOW[start].end();itr++){ FOLLOW[ch-'A'].insert(*itr); } } } } char ch=G[start][i][j]; if(isupper(ch)){ for(set<char>::iterator itr=FOLLOW[start].begin();itr!=FOLLOW[start].end();itr++){ FOLLOW[ch-'A'].insert(*itr); } } } } int main() { int test=0,t=0,i,j,k,n,m; string str; fstream fin,fout; fin.open("input.txt"); fout.open("output.txt"); cout<<"\nEnter the number of grammars: "; fin>>test; cout<<test<<"\n"; while(t++ != test){ for(i=0;i<1000;i++){ G[i].clear(); FIRST[i].clear(); FOLLOW[i].clear(); } memset(vis,0,sizeof(vis)); cout<<"\n\nEnter number of nonterminals: "; fin>>n; cout<<n<<"\n"; for(i=0;i<n;i++){ cout<<"\nEnter the productions for NT "<<(char)(i+'A')<<": "; fin>>m; cout<<m<<" "; for(j=0;j<m;j++){ fin>>str; cout<<str<<" "; G[i].push_back(str); } } for(i=0;i<n;i++){ F(i); } fout<<"\n"<<t<<")\nFIRST TABLE: \n"; cout<<"\n"<<t<<")\nFIRST TABLE: \n"; for(i=0;i<n;i++){ fout<<'\t'<<char(i+'A')<<"-> "; cout<<'\t'<<char(i+'A')<<"-> "; for(set<char>::iterator itr=FIRST[i].begin();itr!=FIRST[i].end();itr++){ fout<<(*itr)<<" "; cout<<(*itr)<<" "; } fout<<"\n"; cout<<"\n"; } for(i=0;i<n;i++){ Follow(i); } for(i=0;i<n;i++){ Follow(i); } fout<<"FOLLOW TABLE: \n"; cout<<"FOLLOW TABLE: \n"; for(i=0;i<n;i++){ fout<<'\t'<<char(i+'A')<<"-> "; cout<<'\t'<<char(i+'A')<<"-> "; for(set<char>::iterator itr=FOLLOW[i].begin();itr!=FOLLOW[i].end();itr++){ fout<<(*itr)<<" "; cout<<(*itr)<<" "; } fout<<"\n"; cout<<"\n"; } } } /* Sample input: Enter the number of grammars: 4 Enter number of nonterminals: 4 Enter the productions for NT A: 3 BDC DbC Ca Enter the productions for NT B: 2 da CD Enter the productions for NT C: 2 g ~ Enter the productions for NT D: 2 h ~ Enter number of nonterminals: 6 Enter the productions for NT A: 1 BCDEF Enter the productions for NT B: 2 a ~ Enter the productions for NT C:2 b ~ Enter the productions for NT D:1 c Enter the productions for NT E:2 d ~ Enter the productions for NT F:2 e ~ Enter number of nonterminals: 5 Enter the productions for NT A: 1 CB Enter the productions for NT B: 2 +CB ~ Enter the productions for NT C: 1 ED Enter the productions for NT D: 2 *ED ~ Enter the productions for NT E: 2 i (A) Enter number of nonterminals: 3 Enter the productions for NT A: 2 Bb Cd Enter the productions for NT B: 2 aB ~ Enter the productions for NT C: 2 cC ~ */
Leave a Comment