Loading

RE to DFA Conversion

C - Program to Implement Regular Expression to DFA Conversion




#include<stdio.h>
#include<conio.h>

char Po[25], In[25];
int node[10][10], flps[10][10], position[10][10], DF[10][10];
int NN=1, DD=1, S=0, var=0, terp=1, v;

struct STACK
{
   char data;
   struct STACK *D;
   struct STACK *next,*L,*R;
   int FP[10],LP[10];
}  *O, *A;

void PUSH(char a)
{
   struct STACK *t;
   t=(struct STACK *)malloc(sizeof(struct STACK));
   t->data=a;
   if (O!=NULL) t->next=O;
   else         t->next=NULL;
   O=t;
}

char POP()
{
   char l;
   l=O->data;
   if(O->next!=NULL) O=O->next;
   else              O=NULL;
   return l;
}

void PUSHNODE(struct STACK *a)
{
   struct STACK *t;
   t=(struct STACK *)malloc(sizeof(struct STACK));
   t->D=a;
   if(O!=NULL) t->next=O;
   else        t->next=NULL;
   O=t;
}

struct STACK *POPNODE()
{
   struct STACK *t;
   t=(struct STACK *)malloc(sizeof(struct STACK));
   t=O->D;
   if(O->next!=NULL) O=O->next;
   else              O=NULL;
   return t;
}

void INFIX2POSTFIX(char I[25])
{
   int i,j,k;
   char p;
   for(i=0;I[i]!='\0';i++){
       if(I[i]=='(')
      PUSH('(');
       else if(I[i]==')')
      while(1){
           p=POP();
           if(p!='(') Po[v++]=p;
           else         break;
      }
       else if(I[i]=='+'){
      while((O->data=='*'||O->data=='+'||O->data=='.')&&O!=NULL)
           Po[v++]=POP();
      PUSH(I[i]);
       }
       else if(I[i]=='.'){
      while((O->data=='*'||O->data=='.')&&O!=NULL)
           Po[v++]=POP();
      PUSH('.');
       }
       else if(I[i]=='*'&&O!=NULL)
           PUSH(I[i]);
       else    Po[v++]=I[i];
   }
   while(O!=NULL){
    p=POP();
    if(p!='(') Po[v++]=p;
   }
   Po[v++]='$';
   Po[v++]='.';
   Po[v]='\0';
}

void FORMTREE(char Po[])
{
   int i,j,k;
   struct STACK *N;
   O=NULL;
   for(i=0;Po[i]!='\0';i++){
       N=(struct STACK *)malloc(sizeof(struct STACK));
       N->data=Po[i]; N->L=NULL; N->R=NULL; N->next=NULL;
       N->FP[0]=0; N->LP[0]=0;
       if(Po[i]=='.'||Po[i]=='+'){
      N->R=POPNODE();
      N->L=POPNODE();
       }
       else if(Po[i]=='*'){
      N->L=POPNODE();
      N->R=NULL;
       }
       PUSHNODE(N);
   }
}
void FLPDISP (struct STACK *a)
{
   int i;
   if(a!=NULL){
      FLPDISP(a->L);
      FLPDISP(a->R);
      S++;
      printf("\n    %c",a->data);
      printf("\nFIRSTPOS -> ");
      for(i=1;i<=a->FP[0];i++)
      printf(" %d",a->FP[i]);
      printf("\nLASTPOS  -> ");
      for(i=1;i<=a->LP[0];i++)
      printf(" %d",a->LP[i]);
      printf("\n---------------");
      getch();
   }
}


void FP_LP_CAL(struct STACK *a)
{
   if(a!=NULL){
      int i, flg;
      FP_LP_CAL(a->L);
      FP_LP_CAL(a->R);
      if(a->data!='+'&&a->data!='.'&&a->data!='*'){
     a->FP[0]++; a->LP[0]++;
     a->FP[a->FP[0]]=terp;
     a->LP[a->LP[0]]=terp++;
     flg=0;
     for(i=0;i<var;i++)
       if(position[i][0]==a->data){
          position[i][1]++;
          position[i][position[i][1]+1]=terp-1;
          flg=1;
       }
       if(flg==0){
          position[var++][1]=1;
          position[var-1][2]=terp-1;
          position[var-1][0]=a->data;
       }
     }
     else if(a->data=='+'){
       for(i=1;i<=a->L->FP[0];i++){
           a->FP[0]++;
           a->FP[a->FP[0]]=a->L->FP[i];
       }
       for(i=1;i<=a->R->FP[0];i++){
         if(PRESENT(a->FP, a->R->FP[i],1)==0){
        a->FP[0]++;
        a->FP[a->FP[0]]=a->R->FP[i];
         }
       }
       for(i=1;i<=a->L->LP[0];i++){
           a->LP[0]++;
           a->LP[a->LP[0]]=a->L->LP[i];
       }
       for(i=1;i<=a->R->LP[0];i++)
          if(PRESENT(a->LP, a->R->LP[i], 1)==0){
         a->LP[0]++;
         a->LP[a->LP[0]]=a->R->LP[i];
          }
     }
     else if(a->data=='*'){
       for(i=1;i<=a->L->FP[0];i++){
           a->FP[0]++;
           a->FP[a->FP[0]]=a->L->FP[i];
       }
       for(i=1;i<=a->L->LP[0];i++){
           a->LP[0]++;
           a->LP[a->LP[0]]=a->L->LP[i];
       }
     }
     else if(a->data=='.'){
     //firstpos
        for(i=1;i<=a->L->FP[0];i++){
        a->FP[0]++;
        a->FP[a->FP[0]]=a->L->FP[i];
        }
        if(a->L->data=='*')
          for(i=1;i<=a->R->FP[0];i++)
         if(PRESENT(a->FP, a->R->FP[i],1)==0){
            a->FP[0]++;
            a->FP[a->FP[0]]=a->R->FP[i];
         }
     //lastpos
        for(i=1;i<=a->R->LP[0];i++){
        a->LP[0]++;
        a->LP[a->LP[0]]=a->R->LP[i];
        }
        if(a->R->data=='*')
        for(i=1;i<=a->L->LP[0];i++)
        if(PRESENT(a->LP,a->L->LP[i],1)==0){
          a->LP[0]++;
          a->LP[a->LP[0]]=a->L->LP[i];
        }
     }
   }
}
int PRESENT(int p[], int a, int b)
{
   int i,j;
   for(i=b,j=0;j<p[b-1];i++,j++)
       if(p[i]==a)
      return 1;
   return 0;
}

void FLPCAL(struct STACK *a, int n)
{
   int j;
   if(a!=NULL){
      FLPCAL(a->L,n);
      if(a->data=='.'){
     if(PRESENT(a->L->LP,n,1)==1)
        for(j=1;j<=a->R->FP[0];j++)
           if(PRESENT(flps[n],a->R->FP[j],1)==0){
          flps[n][1]++;
          flps[n][flps[n][1]+1]=a->R->FP[j];
           }
      }
      else if(a->data=='*'){
     if(PRESENT(a->LP,n,1)==1)
        for(j=1;j<=a->FP[0];j++)
          if(PRESENT(flps[n],a->FP[j],1)==0){
         flps[n][1]++;
         flps[n][flps[n][1]+1]=a->FP[j];
          }
      }
      FLPCAL(a->R,n);
   }
}
/***************/
void FOLLOWPOS()
{
   int i,j,k;
   A=O;
   flps[0][0]=terp;
   for(i=1;i<=terp;i++){
       flps[i][0]=i;
       flps[i][1]=0;
       FLPCAL(O->D,i);
   }
   O=A;
}

void DFA()
{
   int i,j,k,l,m,fg,find;
   int tmp[10], newn[10];
   node[0][0]=1;
   node[1][0]='A';
   node[1][1]=0;
   for(i=1;i<=O->D->FP[0];i++){
       node[1][1]++;
       node[1][node[1][1]+1]=O->D->FP[i];
   }
   DF[0][0]=var-1;
   for(i=1;i<var;i++)
      DF[0][i]=position[i-1][0];
   for(i=1;i<=node[0][0];i++){
       DF[i][0]=node[i][0];
       for(j=1;j<=DF[0][0];j++){
       tmp[0]=0;
       newn[0]=0;
       for(k=2;k<=node[i][1]+1;k++){
           if(PRESENT(position[j-1],node[i][k],2)==1)
          tmp[++tmp[0]]=node[i][k];
          for(l=1;l<=tmp[0];l++){
             for(m=2;m<=flps[tmp[l]][1]+1;m++)
            if(PRESENT(newn,flps[tmp[l]][m],1)==0){
               newn[0]++;
               newn[newn[0]]=flps[tmp[l]][m];
            }
          }
       }
       printf(" ");
       fg=0;
       for(l=1;l<=node[0][0];l++){
           find=0;
           if(newn[0]==node[l][1])
          for(k=1;k<=newn[0];k++)
             if(PRESENT(node[l],newn[k],2)==0)
              fg=1;
             else find++;
          if(find==newn[0]&&find!=0)
             goto l1;
       }
       if(newn[0]==0){
          DF[i][j]='-';
          goto l2;
       }
       node[0][0]++;
       node[node[0][0]][0]=node[node[0][0]-1][0]+1;
       for(m=0;m<=newn[0];m++)
          node[node[0][0]][m+1]=newn[m];
       DF[i][j]=node[node[0][0]][0];
       goto l2;
l1:       DF[i][j]=node[l][0];
l2:      if(fg==1||fg==0)  printf(" ");
       }
   }
   printf("\n\nNODES:\n\n");
   for(i=1;i<=node[0][0];i++,printf("\n\n"))
      for(j=0;j<=node[i][1]+1;j++)
     if(j==0)
        printf(" %c ",node[i][j]);
     else if(j==1)
        printf(" => ");
     else
        printf(" %d ",node[i][j]);
   printf("\n\nDFA TABLE:\n\n");
   for(i=0;i<=node[0][0];i++,printf("\n\n"))
      for(j=0;j<=DF[0][0];j++)
      if(i==0&&j==0)
         printf("    ");
      else
         printf("%4c",DF[i][j]);
}


void main()
{
   int i,j,k, gd, gm;
   int ch;
   O=NULL; A=NULL; v=0;
do{

   clrscr();

   printf("\n----------------------------");
   printf("\n        RE -> DFA    ");
   printf("\n----------------------------");
   printf("\n     1. ENTER R.E.");
   printf("\n     2. POSTFIX EXPRESSION ");
   printf("\n     3. VIEW FOLLOWPOS");
   printf("\n     4. VIEW DFA ");
   printf("\n     5. QUIT");
   printf("\n---------------------------");
   printf("\n\n    ENTER YOUR CHOICE : ");
  scanf("%d",&ch);
   switch(ch)
   {
      case 1:
           printf("\n\n    ENTER REGULAR EXPRESSION : ");
           scanf("%s",&In);
           break;
      case 2:
           INFIX2POSTFIX(In);
           printf("\n\n    POSTFIX EXPRESSION : \n\n\t%s",Po);
           O=NULL;
           FORMTREE(Po);
           break;
      case 3:
           FP_LP_CAL(O->D);
           FLPDISP(O->D);
           FOLLOWPOS();
           printf("\n\n    FOLLOWPOS :\n\n");
           for(i=1;i<terp;i++)
           {
           for(j=0;j<=flps[i][1]+1;j++)
              if(j!=1)
             printf(" %d ",flps[i][j]);
              printf("\n");
           }
           break;
      case 4:
           printf("\n\n    POSITION MATRIX :\n\n");
           for(i=0;i<var;i++)
           {
           for(j=0;j<=position[i][1]+1;j++)
               if(j==0)
              printf(" %c ",position[i][j]);
               else if (j!=1)
              printf(" %d ",position[i][j]);
               printf("\n\n");
           }
           DFA();
           break;
      case 5:
    printf("\n    Thanks.....\a");

           break;
      default :
           printf("\n\n    SORRY!! WRONG CHOICE!\a");
           break;
     }
   }while(ch!=5);
   getch();
}

Click Here to Download Source Code with Executable Program

This entry was posted in . Bookmark the permalink.

2 Responses to RE to DFA Conversion

  1. this code is not running properly.
    Kindly explain your code how it works?

    ReplyDelete
  2. this code is not running properly.
    Kindly explain your code how it works?

    ReplyDelete