fork download
copy 
  1. /* PROGRAM FOR FINDING THE FIRST AND FOLLOW OF A GIVEN GRAMMAR
  2.   %
  3.   % Author: Shivam Prasad (prasadshivam2296@gmail.com)
  4.   % Date:   19th March 2018
  5.   % Description: This program finds the first and follow of a given grammar.
  6.   %
  7.   % Usage: First and Follow are used in the LL(1) Predictive Parser
  8.   %
  9.   %
  10.   % Input:  The program takes its input from a text file input.txt
  11.   %         It assumes that the nonterminals are named A,B,C,D... and the productions are separated by spaces.
  12.   %         See sample input for more on this.
  13.   %
  14.   % Output: Finds the first and follow of each nonterminal and saves it in an output file output.txt
  15.   %
  16. */
  17. #include<bits/stdc++.h>
  18. using namespace std;
  19.  
  20. set<char>FOLLOW[1000];
  21. vector<string> G[1000];
  22. set<char>FIRST[1000];
  23.     bool vis[1000];
  24.  
  25. void F(int start){
  26.  
  27.     if(vis[start])return;
  28.  
  29.     for(int i=0;i<G[start].size();i++){
  30.         if(G[start][i]=="~"){
  31.             FIRST[start].insert('~');
  32.         }
  33.         else if(!isupper(G[start][i][0])){
  34.             FIRST[start].insert(G[start][i][0]);
  35.         }
  36.         else{
  37.                 bool flag;
  38.                 int k;
  39.             for(k=0;k<G[start][i].length();k++){
  40.             char nxt=G[start][i][k];
  41.             if(!isupper(nxt)){
  42.                   FIRST[start].insert(nxt);
  43.                   break;
  44.             }
  45.  
  46.             if(!vis[nxt-'A'])
  47.                 F(nxt-'A');
  48.  
  49.                 flag=0;
  50.             for(set<char>::iterator itr=FIRST[nxt-'A'].begin();itr!=FIRST[nxt-'A'].end();itr++){
  51.                 if((*itr)=='~'){
  52.                     flag=1;
  53.                 }
  54.                 else FIRST[start].insert(*itr);
  55.             }
  56.                 if(!flag) break;
  57.             }
  58.             if(k==G[start][i].length()){
  59.                 FIRST[start].insert('~');
  60.             }
  61.         }
  62.     }
  63.     vis[start]=1;
  64. }
  65.  
  66. void Follow(int start)
  67. {
  68.     if(start==0){
  69.         FOLLOW[start].insert('$');
  70.     }
  71.  
  72.     for(int i=0;i<G[start].size();i++){
  73.             int j;
  74.         for( j=0;j<G[start][i].size()-1;j++){
  75.             char ch=G[start][i][j];
  76.             if(isupper(ch)){
  77.                 bool f=false;
  78.                 int k;
  79.                 for(k=j+1;k<G[start][i].size();k++){
  80.                 char nx=G[start][i][k];
  81.                 if(!isupper(nx)){
  82.                     FOLLOW[ch-'A'].insert(nx);
  83.                     break;
  84.                 }
  85.                 else{
  86.                         f=false;
  87.                     for(set<char>::iterator itr=FIRST[nx-'A'].begin();itr!=FIRST[nx-'A'].end();itr++){
  88.                         if((*itr)=='~'){
  89.                             f=true;
  90.                         }
  91.                         else FOLLOW[ch-'A'].insert(*itr);
  92.                     }
  93.                     if(!f)break;
  94.                 }
  95.                 }
  96.                 if(k==G[start][i].size()){
  97.                     for(set<char>::iterator itr=FOLLOW[start].begin();itr!=FOLLOW[start].end();itr++){
  98.                         FOLLOW[ch-'A'].insert(*itr);
  99.                     }
  100.                 }
  101.             }
  102.         }
  103.  
  104.         char ch=G[start][i][j];
  105.         if(isupper(ch)){
  106.             for(set<char>::iterator itr=FOLLOW[start].begin();itr!=FOLLOW[start].end();itr++){
  107.                 FOLLOW[ch-'A'].insert(*itr);
  108.             }
  109.         }
  110.     }
  111. }
  112. int main()
  113. {
  114.     int test=0,t=0,i,j,k,n,m;
  115.     string str;
  116.  
  117.     fstream fin,fout;
  118.     fin.open("input.txt");
  119.     fout.open("output.txt");
  120.     cout<<"\nEnter the number of grammars: ";
  121.     fin>>test;
  122.     cout<<test<<"\n";
  123.  
  124.     while(t++ != test){
  125.             for(i=0;i<1000;i++){
  126.                 G[i].clear();
  127.                 FIRST[i].clear();
  128.                 FOLLOW[i].clear();
  129.             }
  130.             memset(vis,0,sizeof(vis));
  131.     cout<<"\n\nEnter number of nonterminals: ";
  132.     fin>>n;
  133.     cout<<n<<"\n";
  134.     for(i=0;i<n;i++){
  135.         cout<<"\nEnter the productions for NT "<<(char)(i+'A')<<": ";
  136.         fin>>m;
  137.         cout<<m<<" ";
  138.         for(j=0;j<m;j++){
  139.             fin>>str;
  140.             cout<<str<<" ";
  141.             G[i].push_back(str);
  142.         }
  143.  
  144.     }
  145.     for(i=0;i<n;i++){
  146.         F(i);
  147.     }
  148.     fout<<"\n"<<t<<")\nFIRST TABLE: \n";
  149.     cout<<"\n"<<t<<")\nFIRST TABLE: \n";
  150.     for(i=0;i<n;i++){
  151.             fout<<'\t'<<char(i+'A')<<"-> ";
  152.             cout<<'\t'<<char(i+'A')<<"-> ";
  153.             for(set<char>::iterator itr=FIRST[i].begin();itr!=FIRST[i].end();itr++){
  154.                 fout<<(*itr)<<" ";
  155.                 cout<<(*itr)<<" ";
  156.             }
  157.         fout<<"\n";
  158.         cout<<"\n";
  159.     }
  160.     for(i=0;i<n;i++){
  161.         Follow(i);
  162.     }
  163.     for(i=0;i<n;i++){
  164.         Follow(i);
  165.     }
  166.     fout<<"FOLLOW TABLE: \n";
  167.     cout<<"FOLLOW TABLE: \n";
  168.     for(i=0;i<n;i++){
  169.             fout<<'\t'<<char(i+'A')<<"-> ";
  170.             cout<<'\t'<<char(i+'A')<<"-> ";
  171.             for(set<char>::iterator itr=FOLLOW[i].begin();itr!=FOLLOW[i].end();itr++){
  172.                 fout<<(*itr)<<" ";
  173.                 cout<<(*itr)<<" ";
  174.             }
  175.             fout<<"\n";
  176.             cout<<"\n";
  177.     }
  178.     }
  179. }
  180. /*
  181. Sample input:
  182. Enter the number of grammars: 4
  183.  
  184. Enter number of nonterminals: 4
  185. Enter the productions for NT A: 3 BDC DbC Ca
  186. Enter the productions for NT B: 2 da CD
  187. Enter the productions for NT C: 2 g ~
  188. Enter the productions for NT D: 2 h ~
  189.  
  190. Enter number of nonterminals: 6
  191. Enter the productions for NT A: 1 BCDEF
  192. Enter the productions for NT B: 2 a ~
  193. Enter the productions for NT C:2 b ~
  194. Enter the productions for NT D:1 c
  195. Enter the productions for NT E:2 d ~
  196. Enter the productions for NT F:2 e ~
  197.  
  198. Enter number of nonterminals: 5
  199. Enter the productions for NT A: 1 CB
  200. Enter the productions for NT B: 2 +CB ~
  201. Enter the productions for NT C: 1 ED
  202. Enter the productions for NT D: 2 *ED ~
  203. Enter the productions for NT E: 2 i (A)
  204.  
  205. Enter number of nonterminals: 3
  206. Enter the productions for NT A: 2 Bb Cd
  207. Enter the productions for NT B: 2 aB ~
  208. Enter the productions for NT C: 2 cC ~
  209. */
Success #stdin #stdout 0.01s 5536KB
comments (?)
stdin
copy 
2
5
1
1
1
1
6
2
1
3
stdout
copy 
Enter the number of grammars: 0
https://ideone.com/C2Bvwb
language:
C++ 4.3.2 (gcc-4.3.2)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!