Title:Write a program to convert RE to DFA. (Compiler point of view, RE to DFA direct method from Uho Ulman Sethi).
#include<stdio.h>
#include <stdlib.h>
typedef struct tree
{
char ch;
int pos;
int nullable;
int fpos[5];
int lpos[5];
struct tree * lc;
struct tree * rc;
}node;
typedef struct foll
{
int follpos[10];
char ch;
}follpos;
follpos folltab[100];
char inpt[10];
int dfaa[30],df=0,state[10][10];;
node* alloc(char ch)
{
node * temp;
temp=(node *)malloc(sizeof(node));
temp->nullable=1;
temp->lc=NULL;
temp->rc=NULL;
temp->ch=ch;
temp->fpos[0]=-1;
temp->lpos[0]=-1;
return temp;
}
void print_follow(int n)
{
int i;
printf("FOLLOWPOS\n");
printf("POS\tNAME\tFOLLOWPOS\n");
for(i=1;i<=n;++i)
{
printf("%d\t%c\t",i,folltab[i].ch);
int j=0;
while(folltab[i].follpos[j]!=-1)
{
printf("%d ",folltab[i].follpos[j]);
j++;
}
printf("\n");
}
}
void print_nullable(node *root)
{
if(root!=NULL)
{
print_nullable(root->lc);
print_nullable(root->rc);
printf("%c\t",root->ch);
int i=0;
while(root->fpos[i]!=-1)
{
printf("%d ",root->fpos[i]);
i++;
}
printf("\t");
i=0;
while(root->lpos[i]!=-1)
{
printf("%d ",root->lpos[i]);
i++;
}
printf("\n");
}
}
node * create(char str[],int *l)
{
node * nw;
nw=alloc(str[*l]);
if(str[*l]=='*'||str[*l]=='|'||str[*l]=='.')
{
if(str[*l]!='*')
{
(*l)--;
nw->nullable=0;
nw->rc=create(str,l);
}
(*l)--;
nw->lc=create(str,l);
}
else
nw->nullable=0;
return nw;
}
void inorder(node *root)
{
if(root!=NULL)
{
inorder(root->lc);
printf("%c",root->ch);
inorder(root->rc);
}
}
void create_nullable(node *root,int *pos)
{
if(root->lc!=NULL)
{
create_nullable(root->lc,pos);
//printf("\t%c ",root->lc->ch);
}
if(root->rc!=NULL){
create_nullable(root->rc,pos);
//printf("\t%c ",root->lc->ch);
}
if(root->lc==NULL && root->rc==NULL)
{
root->pos=(*pos);
root->fpos[0]=root->lpos[0]=(*pos);
root->fpos[1]=root->lpos[1]=-1;
folltab[*pos].ch=root->ch;
folltab[*pos].follpos[0]=-1;
(*pos)++;
}
else
{
if(root->ch=='|')
{
if(root->lc->nullable==1 || root->rc->nullable==1)
root->nullable=1;
else
root->nullable=0;
unio(root->fpos,root->lc->fpos);
unio(root->fpos,root->rc->fpos);
unio(root->lpos,root->lc->lpos);
unio(root->lpos,root->rc->lpos);
}
else if(root->ch=='*')
{
unio(root->fpos,root->lc->fpos);
unio(root->lpos,root->lc->lpos);
}
else if(root->ch=='.')
{
if(root->lc->nullable==1 && root->rc->nullable==1)
root->nullable=1;
else
root->nullable=0;
if(root->lc->nullable==1)
{
unio(root->fpos,root->rc->fpos);
}
unio(root->fpos,root->lc->fpos);
if(root->rc->nullable==1)
{
unio(root->lpos,root->lc->lpos);
}
unio(root->lpos,root->rc->lpos);
}
follow(root);
}
}
void follow(node *root)
{
int i=0;
if(root->ch=='*')
{
while(root->lpos[i]!=-1)
{
unio(folltab[root->lpos[i]].follpos,root->fpos);
i++;
}
}
else if(root->ch=='.')
{
while(root->lc->lpos[i]!=-1)
{
unio(folltab[root->lc->lpos[i]].follpos,root->rc->fpos);
i++;
}
}
}
void unio(int arr1[],int arr2[])
{
int i=0;
while(arr1[i]!=-1)
i++;
int j=0;int k=0;
while(arr2[j]!=-1)
{
for(k=0;k<i;++k)
{
if(arr2[j]==arr1[k])
break;
}
if(k==i)
{
arr1[i]=arr2[j];
i++;
}
j++;
}
arr1[i]=-1;
}
void dfa()
{
int j=0,k=0,temp[10],i;
temp[0]=-1;
int nos=1;
for(i=0;i<10;++i)
state[i][0]=-1;
i=0;
int m;
unio(state[0],folltab[1].follpos);
while(1)
{
for(i=0;inpt[i]!=NULL;++i)
{
for(j=0;state[k][j]!=-1;++j)
{
if(folltab[state[k][j]].ch==inpt[i])
{
unio(temp,folltab[state[k][j]].follpos);
}
}
m=check(temp,nos);
if(m==-1)
{
unio(state[nos++],temp);
m=nos-1;
}
dfaa[df++]=m;
temp[0]=-1;
}
if(k==nos-1)
break;
k++;
}
}
int check(int temp[],int nos)
{
int i,j;
for(i=0;i<nos;++i)
{
for(j=0;temp[j]!=-1;++j)
{
if(temp[j]!=state[i][j])
break;
}
if(temp[j]==-1 && state[i][j]==-1)
return i;
}
return -1;
}
void display_dfa()
{
int i,j,k;
printf("\nDFA TABLE\n ");
for(i=0;inpt[i]!=NULL;i++)
printf("\t%c",inpt[i]);
for(j=0;j<(df/i);j++)
{
printf("\n%c\t",j+65);
for(k=j*i;k<(j*i)+i;k++)
printf("%c\t",dfaa[k]+65);
}
}
void main()
{
int i;
char str[50];
inpt[0]=NULL;
printf("Enter the postfix expression\n");
scanf("%s",str);
node *root;
int l;
strcat(str,"#.\0");
l=strlen(str);
// printf("\n%d\n",l);
l--;
int j=0;
for(i=0;i<l-1;++i)
{
j=0;
while(inpt[j]!=NULL)
{
if(inpt[j]==str[i])
break;
j++;
}
if(inpt[j]!=str[i] && str[i]!='|' && str[i]!='*' && str[i]!='.')
{
inpt[j]=str[i];
inpt[j+1]=NULL;
}
}
int pos=1;
root=create(str,&l);
create_nullable(root,&pos);
printf("\nElement\tFPOS\tLPOS\n");
print_nullable(root->lc);
print_follow(pos-2);
dfa();
display_dfa();
}
#include<stdio.h>
#include <stdlib.h>
typedef struct tree
{
char ch;
int pos;
int nullable;
int fpos[5];
int lpos[5];
struct tree * lc;
struct tree * rc;
}node;
typedef struct foll
{
int follpos[10];
char ch;
}follpos;
follpos folltab[100];
char inpt[10];
int dfaa[30],df=0,state[10][10];;
node* alloc(char ch)
{
node * temp;
temp=(node *)malloc(sizeof(node));
temp->nullable=1;
temp->lc=NULL;
temp->rc=NULL;
temp->ch=ch;
temp->fpos[0]=-1;
temp->lpos[0]=-1;
return temp;
}
void print_follow(int n)
{
int i;
printf("FOLLOWPOS\n");
printf("POS\tNAME\tFOLLOWPOS\n");
for(i=1;i<=n;++i)
{
printf("%d\t%c\t",i,folltab[i].ch);
int j=0;
while(folltab[i].follpos[j]!=-1)
{
printf("%d ",folltab[i].follpos[j]);
j++;
}
printf("\n");
}
}
void print_nullable(node *root)
{
if(root!=NULL)
{
print_nullable(root->lc);
print_nullable(root->rc);
printf("%c\t",root->ch);
int i=0;
while(root->fpos[i]!=-1)
{
printf("%d ",root->fpos[i]);
i++;
}
printf("\t");
i=0;
while(root->lpos[i]!=-1)
{
printf("%d ",root->lpos[i]);
i++;
}
printf("\n");
}
}
node * create(char str[],int *l)
{
node * nw;
nw=alloc(str[*l]);
if(str[*l]=='*'||str[*l]=='|'||str[*l]=='.')
{
if(str[*l]!='*')
{
(*l)--;
nw->nullable=0;
nw->rc=create(str,l);
}
(*l)--;
nw->lc=create(str,l);
}
else
nw->nullable=0;
return nw;
}
void inorder(node *root)
{
if(root!=NULL)
{
inorder(root->lc);
printf("%c",root->ch);
inorder(root->rc);
}
}
void create_nullable(node *root,int *pos)
{
if(root->lc!=NULL)
{
create_nullable(root->lc,pos);
//printf("\t%c ",root->lc->ch);
}
if(root->rc!=NULL){
create_nullable(root->rc,pos);
//printf("\t%c ",root->lc->ch);
}
if(root->lc==NULL && root->rc==NULL)
{
root->pos=(*pos);
root->fpos[0]=root->lpos[0]=(*pos);
root->fpos[1]=root->lpos[1]=-1;
folltab[*pos].ch=root->ch;
folltab[*pos].follpos[0]=-1;
(*pos)++;
}
else
{
if(root->ch=='|')
{
if(root->lc->nullable==1 || root->rc->nullable==1)
root->nullable=1;
else
root->nullable=0;
unio(root->fpos,root->lc->fpos);
unio(root->fpos,root->rc->fpos);
unio(root->lpos,root->lc->lpos);
unio(root->lpos,root->rc->lpos);
}
else if(root->ch=='*')
{
unio(root->fpos,root->lc->fpos);
unio(root->lpos,root->lc->lpos);
}
else if(root->ch=='.')
{
if(root->lc->nullable==1 && root->rc->nullable==1)
root->nullable=1;
else
root->nullable=0;
if(root->lc->nullable==1)
{
unio(root->fpos,root->rc->fpos);
}
unio(root->fpos,root->lc->fpos);
if(root->rc->nullable==1)
{
unio(root->lpos,root->lc->lpos);
}
unio(root->lpos,root->rc->lpos);
}
follow(root);
}
}
void follow(node *root)
{
int i=0;
if(root->ch=='*')
{
while(root->lpos[i]!=-1)
{
unio(folltab[root->lpos[i]].follpos,root->fpos);
i++;
}
}
else if(root->ch=='.')
{
while(root->lc->lpos[i]!=-1)
{
unio(folltab[root->lc->lpos[i]].follpos,root->rc->fpos);
i++;
}
}
}
void unio(int arr1[],int arr2[])
{
int i=0;
while(arr1[i]!=-1)
i++;
int j=0;int k=0;
while(arr2[j]!=-1)
{
for(k=0;k<i;++k)
{
if(arr2[j]==arr1[k])
break;
}
if(k==i)
{
arr1[i]=arr2[j];
i++;
}
j++;
}
arr1[i]=-1;
}
void dfa()
{
int j=0,k=0,temp[10],i;
temp[0]=-1;
int nos=1;
for(i=0;i<10;++i)
state[i][0]=-1;
i=0;
int m;
unio(state[0],folltab[1].follpos);
while(1)
{
for(i=0;inpt[i]!=NULL;++i)
{
for(j=0;state[k][j]!=-1;++j)
{
if(folltab[state[k][j]].ch==inpt[i])
{
unio(temp,folltab[state[k][j]].follpos);
}
}
m=check(temp,nos);
if(m==-1)
{
unio(state[nos++],temp);
m=nos-1;
}
dfaa[df++]=m;
temp[0]=-1;
}
if(k==nos-1)
break;
k++;
}
}
int check(int temp[],int nos)
{
int i,j;
for(i=0;i<nos;++i)
{
for(j=0;temp[j]!=-1;++j)
{
if(temp[j]!=state[i][j])
break;
}
if(temp[j]==-1 && state[i][j]==-1)
return i;
}
return -1;
}
void display_dfa()
{
int i,j,k;
printf("\nDFA TABLE\n ");
for(i=0;inpt[i]!=NULL;i++)
printf("\t%c",inpt[i]);
for(j=0;j<(df/i);j++)
{
printf("\n%c\t",j+65);
for(k=j*i;k<(j*i)+i;k++)
printf("%c\t",dfaa[k]+65);
}
}
void main()
{
int i;
char str[50];
inpt[0]=NULL;
printf("Enter the postfix expression\n");
scanf("%s",str);
node *root;
int l;
strcat(str,"#.\0");
l=strlen(str);
// printf("\n%d\n",l);
l--;
int j=0;
for(i=0;i<l-1;++i)
{
j=0;
while(inpt[j]!=NULL)
{
if(inpt[j]==str[i])
break;
j++;
}
if(inpt[j]!=str[i] && str[i]!='|' && str[i]!='*' && str[i]!='.')
{
inpt[j]=str[i];
inpt[j+1]=NULL;
}
}
int pos=1;
root=create(str,&l);
create_nullable(root,&pos);
printf("\nElement\tFPOS\tLPOS\n");
print_nullable(root->lc);
print_follow(pos-2);
dfa();
display_dfa();
}
0 Comments