#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2013
    Posts
    5
    Rep Power
    0

    Determining Input and output


    Hey Guys,

    I have got this code from my friend which is basically a C++ program to calculate First and Follow sets of a particular grammar. The problem I'm facing that I'm unable to figure out for which input the program will work fine. I'm in a fix. Please help me out guys if possible. Here is the code:

    Code:
    using namespace std;
    #include<iostream>
    #include<fstream>
    #include<string>
    #include<cstring>
    #include<algorithm>
    
    char token[200];
    string temp[200][200];
    string temp_rectified[200][200];
    int count_non_terminal_first[50];
    int count_non_terminal_follow[50];
    string non_terminals[200][200];
    string our_non_terminals_rectified[200][200];
    int counter1=0,counter2=0,no_of_lines=0,r_flag=0;
    string first[200][200]; //to calculate first sets
    string follow[200][200]; //to calcluate follow sets
    string terminals[]={"VAR","BEGIN","END","ASSIGN","IF","WHILE","DO","THEN","PRINT","INT","REAL","STRING","PLUS","MINUS","UNDERSCORE","DIV","MULT","EQUAL","COLON","COMMA","SEMICOLON","LBRAC","RBRAC","LPAREN","RPAREN","NOTEQUAL","GREATER","LESS","LTEQ","GTEQ","DOT","ID","NUM","REALNUM"};
    
    	ifstream input2;
    	ofstream output2;
    
    int terminal_check(string input_sample)
    {	
    	for(int c=0;c<34;c++)
    	{	
    		if(input_sample==terminals[c])
    			return 1;
    	}
    
    	return 0;	
    }
    
    int non_terminal_check(string input_sample)
    {
        int flag = 0,m;
    	string::iterator iterator1,n;
    	//cout<<"detected"<<input_sample;
    	for(iterator1=input_sample.begin();iterator1<input_sample.end();iterator1++)
    	{
    		//cout<<*iterator1;
    		//extracting valid terminal and non-terminal names.
    			if(*(iterator1)=='[' || *(iterator1)==']' || *(iterator1)=='{' || *(iterator1)=='}')
    			{			
    				string decoy=input_sample;
    				char erase[]="[ ] { }";
    				for (unsigned int i = 0; i < strlen(erase); ++i)
    					decoy.erase (std::remove(decoy.begin(), decoy.end(), erase[i]), decoy.end());
    
    				input_sample=decoy;
    				iterator1=input_sample.begin();
    
    				//output2<<"new string:="<<input_sample;
    			}
    		
    		if(*(iterator1+1)=='[' || *(iterator1+1)==']' || *(iterator1+1)=='{' || *(iterator1+1)=='}')
    		{			
    				string decoy=input_sample;
    				char erase[]="[ ] { }";
    				for (unsigned int i = 0; i < strlen(erase); ++i)
    					decoy.erase (std::remove(decoy.begin(), decoy.end(), erase[i]), decoy.end());
    
    				input_sample=decoy;
    				iterator1=input_sample.begin();
    	
    				//output2<<"new string:="<<input_sample;
    		}
    		if(*(iterator1+2)=='[' || *(iterator1+2)==']' || *(iterator1+2)=='{' || *(iterator1+2)=='}')
    		{			
    				string decoy=input_sample;
    				char erase[]="[ ] { }";
    				for (unsigned int i = 0; i < strlen(erase); ++i)
    					decoy.erase (std::remove(decoy.begin(), decoy.end(), erase[i]), decoy.end());
    
    				input_sample=decoy;
    				iterator1=input_sample.begin();
    	
    				//output2<<"new string:="<<input_sample;
    		}
    
    		if(terminal_check(input_sample)==1 || input_sample == "|")
    			{break;}
    		
    		else if( (*iterator1 >=97 && *iterator1 <=122) || (*iterator1>=65 && *iterator1<=90))
    		{
    		
    			//output2<<*iterator1<<*(iterator1+1);
    			if(iterator1+1==input_sample.end())
    			{
    			//	return input_sample;
    				flag = 1;break;
    			}
    			else if( ( *(iterator1+1)>=65 && *(iterator1+1)<=90) || (*(iterator1+1) >=97 && *(iterator1+1) <=122) || (*(iterator1+1) >=48 && *(iterator1+1) <=57 ))
    				continue;
    			else
    			{
    				flag = 2;
    				break;				
    			}			
    		}
    
    		/*else if(*iterator1>=65 && *iterator1<=90)
    		{
    			flag=3; //for terminals coding is left.
    			break;
    
    		}*/
    			
    		else if(*iterator1=='-' || *iterator1=='|')
    		{
    			if((iterator1+1) == input_sample.end())
    			{	
    				break;
    			}
    			else
    			{
    				flag = 2;
    				break;
    			}		
    		}			
    		else
    		{
    			flag = 2;
    			break;
    		}
    	}//end for
    			if (flag == 1)
    			{
    				return 1;
    			}
    		
    			if( flag == 2)
    			{
    				output2<<"ERROR CODE 0: Input not according to format";
    				exit(0);
    			}
    return 0;
    		
    
    }//end function.
    
    
    void generate_first(int a1, int a2) //using recursion
    {
    	int m,error_flag=0,x;
    
    	if(count_non_terminal_first[a2]==0)
    	{
    			for(m=0;;m++)
    			{
    				if(first[a1][m]=="ishaan")break;
    				else if(first[a1][m]==temp[a2][0])
    					first[a1][m]=first[a2][0];
    			
    			}//a1,m
    			for(int n=1;;n++)			
    			{
    				if(first[a2][n]=="ishaan")break;
    
    				first[a1][m++]=first[a2][n];		
    			}
    			first[a1][m++]="ishaan";
    			
    	return;	
    	}
    			
    	for(int b=2;;b++)
    	{
    		if(first[a1][b]=="ishaan")
    			return;
    		if(non_terminal_check(first[a1][b])==1)
    		{ 
    			for(x=0;x<no_of_lines;x++)
    			{
    				if(first[a1][b]==temp[x][0])
    				{
    					error_flag=0;
    					generate_first(a1,x);
    				}
    			}
    	
    		}
    	}
    					
    
    } // end generate first
    
    void generate_follow(int a1,int a2)//0,0 using recursion
    {
    	int m,x;
    	if(count_non_terminal_follow[a2]==0)
    	{
    		for(m=0;;m++)
    		{
    			if(follow[a1][m]=="ishaan")
    				break;
    			else if(follow[a1][m]==temp[a2][0])
    				follow[a1][m]=first[a2][m];
    		}
    		
    		for(int n=m;;n++)			
    			{
    				if(first[a2][n]=="ishaan")break;
    
    				follow[a1][m++]=first[a2][n];		
    			}
    			follow[a1][m++]="ishaan";
    		
    
    	}
    
    	for(int b=2;;b++)
    	{
    		if(follow[a1][b]=="ishaan")
    			return;
    		if(non_terminal_check(follow[a1][b])==1)
    		{
    			for(x=0;x<no_of_lines;x++)
    			{
    				if(follow[a1][b]==temp[x][0])
    				{
    					generate_follow(a1,x);
    				}
    			}
    		}
    	}
    
    }
    
    /*void generate_follow(int a1,int a2)//1,1follow(1,2)=LIST
    {
    	int a;
    	for(a=0;a<no_of_lines;a++)	
    	{
    		if(temp[a][0]==follow[a1][a2])
    		{
    			follow[a1][a2]=first[a][2];
    		}
    		
    	}
    }*/
    
    
    string non_terminal_rectify(string input_sample)
    {
    	 
            int flag = 0,m;
    	string::iterator iterator1,n;
    
    	for(iterator1=input_sample.begin();iterator1<input_sample.end();iterator1++)
    	{
    		//extracting valid terminal and non-terminal names.
    			if(*(iterator1)=='[' || *(iterator1)==']' || *(iterator1)=='{' || *(iterator1)=='}')
    			{			
    				string decoy=input_sample;
    				char erase[]="[ ] { }";
    				for (unsigned int i = 0; i < strlen(erase); ++i)
    					decoy.erase (std::remove(decoy.begin(), decoy.end(), erase[i]), decoy.end());
    
    				input_sample=decoy;
    				iterator1=input_sample.begin();
    
    				//output2<<"new string:="<<input_sample;
    			}
    		
    		if(*(iterator1+1)=='[' || *(iterator1+1)==']' || *(iterator1+1)=='{' || *(iterator1+1)=='}')
    		{			
    				string decoy=input_sample;
    				char erase[]="[ ] { }";
    				for (unsigned int i = 0; i < strlen(erase); ++i)
    					decoy.erase (std::remove(decoy.begin(), decoy.end(), erase[i]), decoy.end());
    
    				input_sample=decoy;
    				iterator1=input_sample.begin();
    	
    				//output2<<"new string:="<<input_sample;
    		}
    		if(*(iterator1+2)=='[' || *(iterator1+2)==']' || *(iterator1+2)=='{' || *(iterator1+2)=='}')
    		{			
    				string decoy=input_sample;
    				char erase[]="[ ] { }";
    				for (unsigned int i = 0; i < strlen(erase); ++i)
    					decoy.erase (std::remove(decoy.begin(), decoy.end(), erase[i]), decoy.end());
    
    				input_sample=decoy;
    				iterator1=input_sample.begin();
    	
    				//output2<<"new string:="<<input_sample;
    		}
    
    		if( (*iterator1 >=97 && *iterator1 <=122) || (*iterator1 >= 65 && *iterator1 <= 90))
    		{
    		
    			//output2<<*iterator1<<*(iterator1+1);
    			if(iterator1+1==input_sample.end())
    			{
    			//	return input_sample;
    				flag = 1;break;
    			}
    			else if( (*(iterator1+1)>=65 && *(iterator1+1)<=90) || (*(iterator1+1) >=97 && *(iterator1+1) <=122) || (*(iterator1+1) >='1' && *(iterator1+1) <='9') )
    				continue;
    			else
    			{
    				flag = 2;
    				break;				
    			}			
    		}
    
    		else if( *iterator1 == '-' || *iterator1 == '|')
    		{
    			if(iterator1+1 == input_sample.end())
    			{	
    				flag = 1; break;
    			}
    			else
    			{
    				flag = 2;
    				break;
    			}
    		}	
    		
    	}//end for
    
    		if( flag == 1)
    		{
    			flag = 0;
    			return input_sample;
    		}
    		
    }//end rectify !!
    
    
    int main(int argc, char *argv[])
    {
    
    	if( argc != 2)
    		cout<<"Error in input file name: Please re-enter the file name";
    	
    	else
    	{
    		input2.open(argv[1]);
    		if(input2==NULL)
    		{
    			cout<<"Specified file does not exist."<<endl;
    		}
         		 else 
    		{
    			strcat(argv[1],".out");
    			output2.open(argv[1]);
    
    		int flag=0,new_flag=0;
    		int count=0;
    		int i=0;
    		int j=0;
    		char ch;
    		int a=0,b=2,c,d=0,e=2,x;
    	
    
       	  while(!input2.eof())
       	  {
    		ch=input2.get();
    		
    
    		//Tokenize and put the tokens in an array
    		while(!input2.eof())
    		{
           			while( ch ==' ' || ch=='\n' || ch =='\t' )
    			{
    				if(ch=='\n')				
    					no_of_lines++;
    
    				ch=input2.get();
    			} 
    		
    			while( ch !=' ' && ch!='\n' && ch !='\t' &&  !input2.eof() )
    			{				
    				token[count++]=ch;
    				ch=input2.get();
    			}
    			
    			if(ch != '\n')
    				temp[i][j++]=token;	
    			
    			else if(ch=='\n')
    			{ 
    				temp[i][j]=token;
    				temp[i][++j]="ishaan";
    				//output2<<temp[i][j]<<i<<j<<endl;
    				j=0;i++;
    								
    			}
    			
    				count=0;
    				for(int limit=0;limit<100;limit++)
    				{
    					token[limit]='\0';
    					
    				}
    				
    		}//end while for scanning input
    
    //coding to compute errors
    
    //ERROR CODE 0: Input not according to format
    
    for(a=0;a<no_of_lines;a++)
    {
    		if(temp[a][2]=="" || temp[a][2]=="ishaan")
    		{
    			output2<<"ERROR CODE 0: Input not according to format";
    			exit(0);
    		}
    		if(temp[a][1] != "-")
    		{
    			output2<<"ERROR CODE 0: Input not according to format";
    			exit(0);
    		}
    		if(temp[a][0] == "")
    		{
    			output2<<"ERROR CODE 0: Input not according to format";
    			exit(0);
    		}
    }
    		
    //coding to compute first sets.	
    
    //first rectify non terminals
    			int ar=0,br=2;
    			for(ar=0;ar<no_of_lines;ar++)
    			{
    				for(br=2;;br++)
    				{
    					if(temp[ar][br]=="ishaan")
    						break;
    					else 
    					{
    						temp_rectified[ar][br]=non_terminal_rectify(temp[ar][br]);
    					}
    				}
    			}
    
    //error coding...
    
    
    			for(a=0;a<no_of_lines;a++)
    			{
    				int e1=0;
    				for(b=2;;b++)
    				{
    					if(temp[a][b]=="ishaan")
    						break;
    					else if(temp[a][b]=="|")
    						b++;
    					else if(non_terminal_check(temp_rectified[a][b])==1)
    						our_non_terminals_rectified[a][e1++]=temp_rectified[a][b];
    					
    			
    				}
    					our_non_terminals_rectified[a][e1++]="ishaan";
    			}
    
    //ERROR CODE 1: non-terminal symbol listed in a rule but does not have a description
    			int e2;
    			for(e2=0;e2<no_of_lines;e2++)
    			{
    			 	for(b=0;;b++)
    				{
    					int error_flag = 0;
    					if(our_non_terminals_rectified[e2][b]=="ishaan")
    						break;
    					for(a=0;a<no_of_lines;a++)
    					{	
    						if(our_non_terminals_rectified[e2][b]==temp[a][0])
    						{
    							error_flag = 0;
    								break;
    						}
    						else
    							error_flag = 1;
    				
    						
    					}
    					if(error_flag == 1)
    					{
    						output2<<"ERROR CODE 1: non-terminal symbol listed in a rule but does not have a description";
    						exit(0);
    					}
    				}
    			}
    
    //ERROR CODE 2: terminal symbol appearing on the lefthand side of a rule
    
    			int c;
    			for(c=0;c<no_of_lines;c++)
    			{	
    		
    				if(terminal_check(temp[c][0])==1)
    				{
    					output2<<"ERROR CODE 2: terminal symbol appearing on the lefthand side of a rule";
    					exit(0);
    				}
    	
    			}
    	/** -----------------------------------------FIRST SETS-----------------------------------------------------  */		
    
    				for(a=0;a<no_of_lines;a++)
    				{	e=2;
    					for(b=2;;b++)
    					{
    						first[a][e++]=temp_rectified[a][b];
    				                int opt_flag=0;
    						for(int c=2;;c++)
    						{
    							string::iterator iterator1;
    							iterator1=temp[a][c].begin();
    							if(temp[a][c]=="ishaan")
    							{	
    								new_flag=1;
    									break;
    							}
    							else if(temp_rectified[a][c]=="|")
    							{
    							opt_flag=0;	
    							first[a][e++]=temp_rectified[a][c+1];
    							}
    						else if(*iterator1=='[' && opt_flag==0)
    							first[a][e++]=temp_rectified[a][c+1];
                            			else
    							opt_flag=1;
    						}
    					if(new_flag==1)
    					{
    						new_flag=0;
    						break;
    					}
    		
    					}
    					first[a][e++]="ishaan";
    				}
    		
    
    //initialize no of non terminals in first [] []
    for(int p=0;p<50;p++)
    {
    	count_non_terminal_first[p]=0;
    }
    
    //count non-terminals in first [] []
    				for(a=0;a<no_of_lines;a++)
    				{
    					for(b=2;;b++)
    					{
    						if(first[a][b]=="ishaan")
    							break;
    		
    						else if(non_terminal_check(first[a][b])==1)
    						{	//cout<<"function called";
    							count_non_terminal_first[a]++;
    						}
    					}
    				}
    
    
    				for(a=0;a<no_of_lines;a++)
    				{
    					if(count_non_terminal_first[a]>0)
    					{
    						generate_first(a,a);
    					}
    				}
    
    //printing first sets.
    
    			for(a=0;a<no_of_lines;a++)
    			{	 
    				output2<<"FIRST("<<temp[a][0]<<") = {";
    				for(b=2;;b++)
    				{
    					if(first[a][b]=="ishaan")
    					{
    						output2<<"}";
    						break;
    					}
    					else
    					{
    						if(first[a][b+1]=="ishaan")
    						{
    							output2<<first[a][b];			
    							
    						}
    						else if(first[a][b]!="")
    							output2<<first[a][b]<<','<<' ';			
    					}
    				}
    				output2<<endl;
    			}
    
    		/**---------------------------------------------FOLLOW SETS------------------------------------*/
    
    //coding to compute follow sets
    				int f;
    				for(f=0;f<no_of_lines;f++)
    				{
    					int f1=2,follow_flag=0;
    					
    					for(a=0;a<no_of_lines;a++)
    					{	
    						for(b=2;;b++)
    						{
    							if(temp[a][b]=="ishaan")
    							{				
    								break;
    							}
    							//if(temp[a][b+1]=="ishaan")
    							//	{follow_flag = 1;break;}
    						else if(temp[f][0]==temp_rectified[a][b])
    						{
    							if(temp_rectified[a][b+1]!="|")
    							{
    							follow_flag=0;
    							follow[f][f1++]=temp_rectified[a][b+1];
    								break;
    							}
    						}
    						//else if(temp[a][b]=="ishaan")
    						//	{follow_flag=1;}
    						else
    							follow_flag=1;
    					}
    				if(follow_flag == 0)
    					break;
    		
    				}
    				if(follow_flag == 1)
    				{
    					output2<<"FOLLOW("<<temp[f][0]<<") = {$}"<<endl;
    					
    					follow_flag = 0;
    				}
    					follow[f][f1++]="ishaan";
    				}
    
    //initialize no of non terminals in follow [] []
    for(int p=0;p<50;p++)
    {
    	count_non_terminal_follow[p]=0;
    }
    
    //counting no of non terminals in follow [] []
    
    			for(a=0;a<no_of_lines;a++)
    			{
    				for(b=2;;b++)
    				{
    					if(follow[a][b]=="ishaan")
    						break;
    			
    					else if(non_terminal_check(follow[a][b])==1)
    						count_non_terminal_follow[a]++;
    				}
    			}
    
    
    			for(a=0;a<no_of_lines;a++)
    			{
    
    				if(count_non_terminal_follow[a]>0)
    				{
    					generate_follow(a,a);
    			
    				}
    			}
    
    //sample printing.
    
    			/*for(a=0;a<no_of_lines;a++)
    			{
    				for(b=2;;b++)
    				{
    					if(first[a][b]=="ishaan")
    						break;	
    					output2<<first[a][b]<<' ';
    				}
    				output2<<endl;
    			}
    
    			for(a=0;a<no_of_lines;a++)
    			{
    				for(b=2;;b++)
    				{
    					if(follow[a][b]=="ishaan")
    						break;	
    					output2<<follow[a][b]<<' ';
    				}
    				output2<<endl;
    			}*/
    
    //printing follow sets
    
    			for(a=1;a<no_of_lines;a++)
    			{ 
    				output2<<"FOLLOW("<<temp[a][0]<<") = {";
    				for(b=2;;b++)
    				{
    					//if(follow[a][b-1]=="")
    					//{	output2<<"$";	}
    					if(follow[a][b]=="ishaan")
    					{
    						output2<<"}";
    		
    						break;
    					}
    					else
    					{
    						if(follow[a][b+1]=="ishaan")
    						{
    							output2<<follow[a][b];			
    						}
    						//else if(follow[a][b]=="" || follow[a][b]=="ishaan")
    						//{
    					//		output2<<"}";break;
    					//	}
    						else if(follow[a][b]=="")
    							output2<<"$";
    						else
    						{
    							output2<<follow[a][b]<<",";			
    						}
    					}
    				}
    			output2<<endl;
    			}
    
    		}//end while
    }//end else
    	}//end main while
    		
    
    		input2.close();
    		output2.close();
    
    }//end main
    The input which I'm trying to give is:
    decl idList1 idList #
    COLON ID COMMA #
    decl -> idList COLON ID #
    idList -> ID idList1 #
    idList1 -> COMMA ID idList1 # idList1 -> # ##

    But it is giving me error code 1.
    If possible guys please tell how to restructure the program accordingly for to get the desired the output which is:
    FIRST(decl) = { ID }
    FIRST(idList1) = { #, COMMA }
    FIRST(idList) = { ID }
    FOLLOW(decl) = { $ }
    FOLLOW(idList1) = { COLON }
    FOLLOW(idList) = { COLON }

    Thanks in advance and please reply asap.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    159
    Rep Power
    19
    First that using namespace std; statement should be after all your includes, not before them.

    Next why all those global variables?

    But it is giving me error code 1.
    What does this mean?

    Lastly you need to find and consistently use, an indentation style you like.

    Jim
  4. #3
  5. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,172
    Rep Power
    2222
    First to agree wholeheartedly with Jim. An inconsistent indentation style is almost as bad as none at all.

    Also, do you have your tabs set to 8 columns? Probably not, since that makes code more difficult to read. But regardless of what you have tabs set to in your editor, they will revert to 8 columns when you post your code here. But if you change your editor settings to use spaces instead of tab characters, then that would solve that problem.

    What warnings are you getting? Why are you ignoring them? I know that you must be getting warnings, because whereas you properly declared main to return int, I do not see where you actually perform that return. Do you not have warnings turned on? Why not?

    You are getting warnings. That means that there are problems with your code. Those problems could be causing the trouble you're having. Resolve those warnings.

    Never ignore warnings!

IMN logo majestic logo threadwatch logo seochat tools logo