Compiler Design Lab(combined)

------SIMPLE DFA ACCEPTING------


#include <iostream>
#include <fstream>

using namespace std;

int main()
{
	fstream obj;
	char ch,str[30],input;
	int k=0,initial=9,final[5],num_stats=0,num_inputs=0,num_final,q_prev,q_new,i=0,j=0,mat[5][5];
	obj.open("input.txt", ios::in);
	obj>>initial;
	obj.get(ch);
	while((ch = obj.get()) != '\n')
	{
		if(ch == ' ')
			continue;
		else
			final[i++] = ch - '0';
	}
	num_final = i;
	obj >> num_stats;
	obj.get(ch);
	i = 0;
	while((ch = obj.get()) != EOF)
	{
		if (ch == '\n') // new line found
		{
			i++;
			j=0;
		}
		else if(ch == '-')
		{
			mat[i][j] = -1;
			j++;
		}
		else if(ch == ' ')
		{
			// ignore spaces
		}
		else
		{
			mat[i][j]=ch-'0';
			j++;
		}
	}

	num_inputs = j-1;
	cin>>str;

	i = 0;
	q_prev = initial;
	q_new = initial;
	while(str[i] != '\0')
	{
		input = str[i] - '0';
		q_new = mat[q_prev][input];
		if (q_new == -1)
		{
			// transition when no output edge!
			break;
		}
		q_prev = q_new;
		i++;
	}
	//int flag = 0;
	for(k = 0; k < num_final; k++)
	{
		if(q_new == final[k])
		{
			cout << "Accepted!";
			break;
		}
	}

	if(k == num_final)
		cout<<"Not Accepted";
	
}



-----SIMPLE NFA ACCEPTING-----

#include<stdio.h>
#include<string.h>
#include<ctype.h>

char mat[30][30][30];
char fin[30];
char inp[30];
int no_st,no_out,maxj=0,len;

void read()
{
	FILE *fp;
	char ch;
	int i,j,k,z,flag;
	i=0;
	j=0;
	k=0;
	z=0;
	flag=0;
	fp=fopen("accept_nfa_data.txt","r");
	while(!feof(fp))
	{
		fscanf(fp,"%c",&ch);
		if(flag==0)
		{
			if(ch==' ')
			{
				mat[i][j][k]='\0';
				k=0;
				j++;
			}
			else if(ch==',')
			{
				continue;
			}
			else if(ch=='\n')
			{
				mat[i][j][k]='\0';
				k=0;
				j++;
				if(maxj<j)
				{
					maxj=j;
				}
				mat[i][j][0]='\0';
				j=0;
				i++;
			}
			else if(isdigit(ch) || ch=='#')
			{
				mat[i][j][k++]=ch;
			}
			else if(ch=='@')
			{
			    flag=1;
			}
		}
		else
		{
			if(ch==' ' || ch==',')
			{
				continue;
			}
			else if(isdigit(ch))
			{
			    fin[z++]=ch;
			}
		}
	}
	no_st=i;
	no_out=z;
}

void print()
{
    int i,j,k;
	printf("States");
	for(i=0;i<maxj;i++)
	{
		printf("\t\t%c",97+i);
	}
	puts("");
	for(i=0;i<no_st;i++)
	{
		printf("Q%d",i);
		for(j=0;mat[i][j][0]!='\0';j++)
		{
			printf("\t\t");
			for(k=0;mat[i][j][k]!='\0';k++)
			{
				
				if(mat[i][j][k]=='#')
				{
					printf("-");	
				}
				else
				{
					printf("Q%c,",mat[i][j][k]);		
				}
			}
		}
		puts("");
	}
	puts("\nOUTPUT STATES:");
	for(i=0;i<no_out;i++)
	{
		if(i<no_out-1)
		{
			printf("%c,",fin[i]);	
		}
		else
		{
			printf("%c",fin[i]);
		}
		
	}	
}


int input()
{
	int i;
	again:
	puts("\n\nEnter a String to check its validation!!");
	scanf("%s",inp);
	for(i=0;inp[i]!='\0';i++)
	{
		if(isalpha(inp[i]))
		{
			inp[i]=tolower(inp[i]);
		}
		else
		{
			puts("Invalid string [Please use English alphabets only]");
			return 0;
		}
	}
	return 1;
}


int nfa_accepted(state,j,iter)
{
	char c,ch;
	int z=0,x;
	char next_States[30];
	if(j==len)
	{
		 for(x=0;x<no_out;x++)
		 {
		 	 if(fin[x]-'0'==state)
		 	 {
		 	 	return 1;
		 	 }
		 }
	}
	c=inp[j++];
	for(x=0;mat[state][c-'a'][x]!='\0';x++)
	{
		ch=mat[state][c-'a'][x];
		if(ch=='#')
		{
			return 0;
		}
		next_States[z++]=ch;
	}
	for(x=0;x<z;x++)
	{
		if(nfa_accepted(next_States[x]-'0',j,iter++))
		{
			return 1;
		}
	}
	return 0;
}

void validate()
{
	if(nfa_accepted(0,0,1))
	{
		printf("'%s' is a valid string for the nfa in accept_nfa_data.txt",inp);
	}
	else
	{
		puts("String is Invalid!!\nPlease try another string");
	}
}

int main()
{
	int i;
	read();
	print();
	while(1)
	{
		puts("\n*******************************************\n\t\tMENU\n\n1.NFA matching\n2.Show Table\n3.Exit\n");
		scanf("%d",&i);
		switch(i)
		{
			case 1:if(input())
			       {
			       	len=strlen(inp);
			       	validate();
			       }
				   break;
			case 2:print();
			       break;
			case 3:return 0;
		}
	}
}

----REGEX ACCEPTING----


#include<stdio.h>
#include<ctype.h>
#include<string.h>
char inp[40],mat[40][40],regex[40];
int no,row;

void read()
{
    int i=0,j;
    char ch;
	FILE *fp;
	fp=fopen("accept_regex_data.txt","r");
	while(!feof(fp))
	{
       fscanf(fp,"%c",&ch);
       if(ch!='\n')
       regex[i++]=ch;
    }
    no=i;
    regex[i]='\0';               
}

void prepare_matrix()
{
  int i,x,y;
  x=0;
  y=0;
  for(i=0;i<no;i++)
  {
     if(isalpha(regex[i]))
     {
        mat[x][y++]=regex[i];
     }
     else if(regex[i]=='+')
     {
        mat[x][y]='\0';
        y=0;
        x++;
     }
     else if(regex[i]==')')
     {
        mat[x][y]='\0';
        row=++x;
     }
  }    
  printf("( %d )",row);    
}


void p()
{
     int i;
     for(i=0;i<row;i++)
     puts(mat[i]);
}
void print()
{
   puts(regex);
}

int compare(char *arr1,char *arr2,int st,int end)
{
    int i,j;
    for(i=st,j=0;i<end;i++,j++)
    {
       if(arr1[j]!=arr2[i])
       {
           return 0;
       }
    }
    return 1;
}

void validate(int flag)
{
   if(flag)
   {
       puts("String Accepted!!!");
   }
   else
   {
       puts("String Not Accepted!!!");
   }
}


void match()
{
   int i=0,flag=1,j;
   prepare_matrix();
   p();
   input();
   if(regex[strlen(regex)-1]=='*')
   {
      while(i<strlen(inp))
      {
         for(j=0;j<row;j++)
         {               
            if(compare(mat[j],inp,i,strlen(mat[j])+i))
            {
               i=i+strlen(mat[j]);
               flag=1;
               break;
            }
            else
            {
                flag=0;
            }
         }
         if(flag==0)
         break;
      }
   }
   else
   {
       for(j=0;j<row;j++)
         {               
            if(compare(mat[j],inp,0,strlen(inp)))
            {
             flag=1;
             break;
            }
            else
            {
              flag=0;
            }
         }
      }
   validate(flag);
}

input()
{
   int i;
   puts("Enter a String to be Matched\n");
   scanf("%s",inp);
}

int main()
{
	int i;
	read();
	print();
	while(1)
	{
		puts("\n*******************************************\n\t\tMENU\n\n1.Match Regular Expression to a String\n2.Show Regex\n3.Exit\n");
		scanf("%d",&i);
		switch(i)
		{
			case 1:match();
			       break;
            case 2:print();
                   break;
			case 3:return 0;
		}
	}
}


----MEALEY----

#include<stdio.h>
#include<ctype.h>
#include<string.h>
# define states 30
# define inputs 30

char mat[states][inputs][2];
char inp_str[50],out_str[50];
int no_st,no_inp=-1,len;

void read()
{
     int i,j,k;
     char ch;
     FILE *fp;
     i=0;
     j=0;
     fp=fopen("meely_data.txt","r");
     while(!feof(fp))
     {
        fscanf(fp,"%c",&ch);
        if(ch==' ')
        {
            mat[i][j][2]='\0';
        }
        else if(ch==',')
        {
             continue;
        }
        else if(isalpha(ch))
        {
             mat[i][j][1]=ch;
             j++;
        }
        else if(isdigit(ch))
        {
             mat[i][j][0]=ch;
        }
        else if(ch=='#')
        {
             mat[i][j][0]=ch;
             mat[i][j][1]='\0';
             j++;
        }
        else if(ch=='\n')
        {
             mat[i][j][2]='\0';
             i++;
             if(no_inp<j)
             {
                 no_inp=j;
             }
             j=0;
        }
     }
     no_st=i+1;
}
void print()
{
     int i,j;
     puts("State Transistion Diagram\n");
     printf("States");
     for(i=0;i<no_inp;i++)
     {
         printf("\t\t%c",i+97);
     }
     puts("");
     for(i=0;i<no_st;i++)
     {
         printf("Q%d",i);
         for(j=0;j<no_inp;j++)
         {
             if(mat[i][j][0]=='#')
             {
                 printf("\t\t-");
             }
             else
             {
                 printf("\t\tQ%c,%c",mat[i][j][0],mat[i][j][1]);
             }
         }
         puts("");
     }
}


int show_output(int i,int j)
{
     int z,s;
     char curr_input,curr_state;
     z=0,s=0;
     curr_input=inp_str[z++];
     j=curr_input-'a';
     curr_state=mat[i][j][0];
     if(curr_state=='#')
     {
         return 0;
     }
     out_str[s++]=mat[i][j][1];
     i=curr_state-'0';
     while(z<len)
     {
         curr_input=inp_str[z++];
         j=curr_input-'a';
         curr_state=mat[i][j][0];
         if(curr_state=='#')
         {
             return 0;
         }
         
         out_str[s++]=mat[i][j][1];
         i=curr_state-'0';
     }
     out_str[s]='\0';
}

void validate()
{
     if(show_output(0,0))
     {   
         puts("OUTPUT:");             
         puts(out_str);
     }
     else
     {
         puts("Machine went to undefined state!!...\ntry another input string");
     }
}


int input()
{
    int i;
    puts("Enter a Input String.");
    scanf("%s",inp_str);
    len=strlen(inp_str);
    for(i=0;i<len;i++)
    {
        if(!isalpha(inp_str[i]))
        {
            return 0;
        }
        else
        {
            inp_str[i]=tolower(inp_str[i]);
        }
    }
    return 1;
}



int main()
{
    int i;
    read();
    print();
    while(1)
    {
        puts("\n************************************************\n1.Meely Machine\n2.Show Table\n3.Exit");
        scanf("%d",&i);
        switch(i)
        {
            case 1:if(input())
                   {
                      validate();
                   }
                   else
                   {
                       puts("ERROR!!!\nString pattern incorrect.\n");
                   }
                   break;
            case 2:print();
                   break;
            case 3:return 0;
        }
    }
}



----MOORE----


#include<stdio.h>
#include<ctype.h>
#include<string.h>

int max,no_st;
char mat[40][40],out[40],inp[40],str[40];

void read()
{
	FILE *fp;
	int i,j;
	int z;
	char ch;
	z=0;
	i=0;
	j=0;
	fp=fopen("moore_data.txt","r");
	while(!feof(fp))
	{
		fscanf(fp,"%c",&ch);
		if(ch==' ')
		{
			continue;
		}
		else if(isdigit(ch) || ch=='#')
		{
			mat[i][j++]=ch;
		}
		else if(ch=='\n')
		{
			continue;
		}
		else if(isalpha(ch))
		{
			out[z++]=ch;
			mat[i][j]='\0';
			i++;
			if(max<j)
			{
				max=j;
			}
			j=0;
		}
	}
	no_st=z;
}

void print()
{
	int i,j;
	printf("States");
	for(i=0;i<max;i++)
	{
		printf("\t\t%c",97+i);
	}
	printf("\t\t OUTPUT\n");
	for(i=0;i<no_st;i++)
	{
		printf("Q%d",i);
		for(j=0;mat[i][j]!='\0';j++)
		{
			printf("\t\t%c",mat[i][j]);
		}
		printf("\t\t%c",out[i]);
		puts("");
	}
}

int process()
{
	int i,j,z,len,current_state,current_inp;
	char var;
	i=0;
	j=0;
	z=0;
	len=strlen(inp);
	puts("OUTPUT::");
	while(j<len)
	{
		str[z++]=out[i];
		current_state=i;
		current_inp=inp[j++]-97;
		var=mat[current_state][current_inp];
		if(var=='#')
		{
			return 0;
		}
		i=var-48;
	}
	str[z++]=out[i];
	str[z]='\0';
	return 1;
}

void validate()
{
	if(process())
	{
		puts(str);
	}
	else
	{
		puts("Invalid String!!");
	}
}

int input()
{
	int i;
	again:
	puts("\n\nEnter a String to check its validation!!");
	scanf("%s",inp);
	for(i=0;inp[i]!='\0';i++)
	{
		if(isalpha(inp[i]))
		{
			inp[i]=tolower(inp[i]);
		}
		else
		{
			puts("Invalid string [Please use English alphabets only]");
			return 0;
		}
	}
	return 1;
}

int main()
{
	int i;
	read();
	print();
	while(1)
	{
		puts("\n****************************************************\n1.Moore Machine\n2.Show Table\n3.Exit\n");
		scanf("%d",&i);
		switch(i)
		{
			case 1:if(input())
				   {
			       validate();
			       }
			       break;
			case 2:print();
			       break;
			case 3:return 0;
		}
	}
}


----NFA TO DFA----


#include<stdio.h>
#include<string.h>
#include<ctype.h>

char NFAtab[30][30][30];
char DFAtab[30][30],fin[30];
int NFA_states,DFA_states,NFA_symbols=-1,outputs,dfa_finals[40],s;

void read()
{
	FILE *fp;
	char ch;
	int i,j,k,z,flag;
	i=0;
	j=0;
	k=0;
	z=0;
	flag=0;
	fp=fopen("nfa2dfa_data.txt","r");
	while(!feof(fp))
	{
		fscanf(fp,"%c",&ch);
		if(flag==0)
		{
			if(ch==' ')
			{
				NFAtab[i][j][k]='\0';
				k=0;
				j++;
			}
			else if(ch==',')
			{
				continue;
			}
			else if(ch=='\n')
			{
				NFAtab[i][j][k]='\0';
				k=0;
				j++;
				if(NFA_symbols<j)
				{
					NFA_symbols=j;
				}
				NFAtab[i][j][0]='\0';
				j=0;
				i++;
			}
			else if(isdigit(ch))
			{
				NFAtab[i][j][k++]=ch;
			}
			else if(ch=='#')
			{
				NFAtab[i][j][0]='\0';
			}
			else if(ch=='@')
			{
			    flag=1;
			}
		}
		else
		{
			if(ch==' ' || ch==',')
			{
				continue;
			}
			else if(isdigit(ch))
			{
			    fin[z++]=ch;
			}
		}
	}
	NFA_states=i;
	outputs=z;
	DFA_states=0;
}

void print()
{
    int i,j,k,faltu;
	printf("States");
	for(i=0;i<NFA_symbols;i++)
	{
		printf("\t\t%c",97+i);
	}
	puts("");
	for(i=0;i<NFA_states;i++)
	{
		printf("Q%d",i);
		for(j=0;j<NFA_symbols;j++)
		{
			printf("\t\t");
			k=0;
			do
			{
				if(NFAtab[i][j][0]=='\0')
				{
					printf("-");	
				}
				else
				{	
					if(k>0)
					{
						printf("Q%c,",NFAtab[i][j][k-1]);		
					}
				}
			}while(NFAtab[i][j][k++]!='\0');
			
		}
		puts("");
	}
	puts("\nOUTPUT STATES:");
	for(i=0;i<outputs;i++)
	{
		if(i<outputs-1)
		{
			printf("%c,",fin[i]);	
		}
		else
		{
			printf("%c",fin[i]);
		}
		
	}
}

void print_DFA()
{
	int i, j;

	puts("STATE TRANSITION TABLE");
	printf("States");
	
	for(i=0;i<NFA_symbols;i++)
	printf("\t\t%c  ",'a'+i);
	printf("\n");
	for (i=0;i<DFA_states;i++)
	{
		printf("Q%d",i);
		for (j=0;j<NFA_symbols;j++)
		{
			if(DFAtab[i][j]==-1)
			{
				printf("\t\t-");
			}
			printf("\t\tQ%d",DFAtab[i][j]);
		}
		printf("\n");
	}
	puts("\nOUTPUT STATES:");
	for(i=0;i<s;i++)
	{
		if(i<s-1)
		{
			printf("%d,",dfa_finals[i]);	
		}
		else
		{
			printf("%d",dfa_finals[i]);
		}
		
	}
}


void merge(char *arr1, char *arr2)
{
	char temp[30], *result=temp, *p=arr1;

	while (*p && *arr2) 
	{
		if (*p == *arr2) 
		{
			*result++ = *p++; 
			arr2++;
		} 
		else if (*p < *arr2) 
		{
			*result++ = *p++;
		}
		else
		{
			*result++ = *arr2++;
		}
	}
	*result = '\0';

	if(*p) 
	{
		strcat(result,p);	
	}
	else if(*arr2)
	{
		strcat(result,arr2);
	}

	strcpy(arr1, temp);
}


void next_state(char *nextstates,char *cur_states,int symbol)
{
	int i;
	char temp[40];

	temp[0] = '\0';
	for (i=0; i<strlen(cur_states); i++)
	{
		printf("current states length=%d\n",strlen(cur_states));
		puts(NFAtab[cur_states[i]-'0'][symbol]);
		merge(temp,NFAtab[cur_states[i]-'0'][symbol]);
	}
	puts(temp);
	strcpy(nextstates,temp);
}

void prepare_final_table(char *state,int st)
{
	int i,j;
	for(j=0;j<outputs;j++)
	{
		for(i=0;i<strlen(state);i++)
		{
			if(state[i]==fin[j])
			{
				dfa_finals[s++]=st;
				return;
			}
		}
	}
}

int state_at(char *state, char statename[][40], int *pn)
{
	int i;

	if (!*state)
	{
		return -1;	
	}
	
	for (i = 0; i < *pn; i++)
		if (!strcmp(state, statename[i])) return i;

	strcpy(statename[i], state);	
	prepare_final_table(state,*pn);
	return (*pn)++;
}


int nfa2dfa()
{
	char state[40][40];
	int i = 0;	
	int n = 1;	

	char next[40];
	int j;

	strcpy(state[0], "0");	

	for (i = 0; i < n; i++) 
	{	
		for (j = 0; j < NFA_symbols; j++) 
		{	
			next_state(next,state[i],j);
			DFAtab[i][j] = state_at(next,state,&n);
		}
	}

	return n;
}


int main()
{
	int i;
	read();
	print();
	while(1)
	{
		puts("\n*******************************************\n\t\tMENU\n\n1.NFA to DFA\n2.Show Table\n3.Exit\n");
		scanf("%d",&i);
		switch(i)
		{
			case 1:s=0;
				   DFA_states=nfa2dfa();
				   print_DFA();
			       break;
			case 2:print();
			       break;
			case 3:return 0;
		}
	}
}