Search Tutorials

Friday 24 May 2013

C code to Find First and Follow in a given Grammar

C program to find First and Follow in a given Grammar.

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

int i,j,l,m,n=0,o,p,nv,z=0,x=0; 
char str[10],temp,temp2[10],temp3[20],*ptr; 

struct prod 
{ 
    char lhs[10],rhs[10][10],ft[10],fol[10]; 
    int n; 
}pro[10]; 

void findter() 
{ 
    int k,t; 
    for(k=0;k<n;k++) 
    { 
        if(temp==pro[k].lhs[0]) 
        { 
            for(t=0;t<pro[k].n;t++) 
            { 
                if( pro[k].rhs[t][0]<65 || pro[k].rhs[t][0]>90 ) 
                    pro[i].ft[strlen(pro[i].ft)]=pro[k].rhs[t][0]; 
                else if( pro[k].rhs[t][0]>=65 && pro[k].rhs[t][0]<=90 ) 
                { 
                    temp=pro[k].rhs[t][0]; 
                    if(temp=='S') 
                        pro[i].ft[strlen(pro[i].ft)]='#'; 
                    findter(); 
                } 
            } 
            break; 
        } 
    } 
} 

void findfol() 
{ 
    int k,t,p1,o1,chk; 
    char *ptr1; 
    for(k=0;k<n;k++) 
    { 
        chk=0; 
        for(t=0;t<pro[k].n;t++) 
        { 
            ptr1=strchr(pro[k].rhs[t],temp); 
            if( ptr1 ) 
            { 
                p1=ptr1-pro[k].rhs[t]; 
                if(pro[k].rhs[t][p1+1]>=65 && pro[k].rhs[t][p1+1]<=90) 
                { 
                    for(o1=0;o1<n;o1++) 
                        if(pro[o1].lhs[0]==pro[k].rhs[t][p1+1]) 
                        { 
                                strcat(pro[i].fol,pro[o1].ft); 
                                chk++; 
                        } 
                } 
                else if(pro[k].rhs[t][p1+1]=='\0') 
                { 
                    temp=pro[k].lhs[0]; 
                    if(pro[l].rhs[j][p]==temp) 
                        continue; 
                    if(temp=='S') 
                        strcat(pro[i].fol,"$"); 
                    findfol(); 
                    chk++; 
                } 
                else 
                { 
                    pro[i].fol[strlen(pro[i].fol)]=pro[k].rhs[t][p1+1]; 
                    chk++; 
                } 
            } 
        } 
        if(chk>0) 
            break; 
    } 
} 

int main() 
{ 
    FILE *f; 
    //clrscr(); 

    for(i=0;i<10;i++) 
        pro[i].n=0; 

    f=fopen("tab5.txt","r"); 
    while(!feof(f)) 
    { 
        fscanf(f,"%s",pro[n].lhs); 
        if(n>0) 
        { 
            if( strcmp(pro[n].lhs,pro[n-1].lhs) == 0 ) 
            { 
                pro[n].lhs[0]='\0'; 
                fscanf(f,"%s",pro[n-1].rhs[pro[n-1].n]); 
                pro[n-1].n++; 
                continue; 
            } 
        } 
        fscanf(f,"%s",pro[n].rhs[pro[n].n]); 
        pro[n].n++; 
        n++; 
    } 

    printf("\n\nTHE GRAMMAR IS AS FOLLOWS\n\n"); 
    for(i=0;i<n;i++) 
        for(j=0;j<pro[i].n;j++) 
            printf("%s -> %s\n",pro[i].lhs,pro[i].rhs[j]); 

    pro[0].ft[0]='#'; 
    for(i=0;i<n;i++) 
    { 
        for(j=0;j<pro[i].n;j++) 
        { 
            if( pro[i].rhs[j][0]<65 || pro[i].rhs[j][0]>90 ) 
            { 
                pro[i].ft[strlen(pro[i].ft)]=pro[i].rhs[j][0]; 
            } 
            else if( pro[i].rhs[j][0]>=65 && pro[i].rhs[j][0]<=90 ) 
            { 
                temp=pro[i].rhs[j][0]; 
                if(temp=='S') 
                    pro[i].ft[strlen(pro[i].ft)]='#'; 
                findter(); 
            } 
        } 
    } 

    printf("\n\nFIRST\n"); 
    for(i=0;i<n;i++) 
    { 
        printf("\n%s -> ",pro[i].lhs); 
        for(j=0;j<strlen(pro[i].ft);j++) 
        { 
            for(l=j-1;l>=0;l--) 
                if(pro[i].ft[l]==pro[i].ft[j]) 
                    break; 
            if(l==-1) 
                printf("%c",pro[i].ft[j]); 
        } 
    } 

    for(i=0;i<n;i++) 
        temp2[i]=pro[i].lhs[0]; 
    pro[0].fol[0]='$'; 
    for(i=0;i<n;i++) 
    { 
        for(l=0;l<n;l++) 
        { 
            for(j=0;j<pro[i].n;j++) 
            { 
                ptr=strchr(pro[l].rhs[j],temp2[i]); 
                if( ptr ) 
                { 
                    p=ptr-pro[l].rhs[j]; 
                    if(pro[l].rhs[j][p+1]>=65 && pro[l].rhs[j][p+1]<=90) 
                    { 
                        for(o=0;o<n;o++) 
                            if(pro[o].lhs[0]==pro[l].rhs[j][p+1]) 
                                    strcat(pro[i].fol,pro[o].ft); 
                    } 
                    else if(pro[l].rhs[j][p+1]=='\0') 
                    { 
                        temp=pro[l].lhs[0]; 
                        if(pro[l].rhs[j][p]==temp) 
                            continue; 
                        if(temp=='S') 
                            strcat(pro[i].fol,"$"); 
                        findfol(); 
                    } 
                    else 
                        pro[i].fol[strlen(pro[i].fol)]=pro[l].rhs[j][p+1]; 
                } 
            } 
        } 
    } 

    printf("\n\nFOLLOW\n"); 
    for(i=0;i<n;i++) 
    { 
        printf("\n%s -> ",pro[i].lhs); 
        for(j=0;j<strlen(pro[i].fol);j++) 
        { 
            for(l=j-1;l>=0;l--) 
                if(pro[i].fol[l]==pro[i].fol[j]) 
                    break; 
            if(l==-1) 
                printf("%c",pro[i].fol[j]); 
        } 
    }
    printf("\n");
    //getch(); 
}

Input File(tab5.txt) For First and Follow Program:-

S ABE
S a
A p
A t
B Aq
S f
A w

Output:-

C code to Find First and Follow in a given Grammar

Related Programs:-

Regular Grammar

SLR Parser

Context Free Grammar (CFG)

DFA (Deterministic Finite Automata)

NFA (Non-Deterministic Finite Automata)

17 comments:

  1. what symbol represent epsilon?

    ReplyDelete
    Replies
    1. Did This Peice Of Code Worked For You?

      Delete
    2. This comment has been removed by the author.

      Delete
    3. epsilon is denoted as @

      Delete
  2. Gives a Runtime Error For me..!!

    ReplyDelete
  3. Gives a Runtime Error For me..!!

    ReplyDelete
  4. Segmentation fault (core dumped)

    ReplyDelete
    Replies
    1. there is a file u need to create so first try creatiing that

      Delete
  5. Segmentation fault (core dumped)

    ReplyDelete
  6. your input will be given from a text file....
    those who are getting segmentation fault...
    1. create a text file and rename it as "text5.txt"
    or any name but if you change the name of text file also do changes in code.

    ReplyDelete
  7. NOT WORKING FOR ε

    ReplyDelete
  8. This comment has been removed by the author.

    ReplyDelete
  9. give me a very simple solution of this grammer plzz

    ReplyDelete
  10. can u give me a solution of left factoring of this grammer

    ReplyDelete

Back to Top