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)

13 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
  2. Gives a Runtime Error For me..!!

    ReplyDelete
    Replies
    1. Tab5.txt file diya program ko

      Delete
    2. tab5.txt save kha karna hai

      Delete
  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. This comment has been removed by the author.

    ReplyDelete

Back to Top