Search Tutorials

Loading...

Friday, 24 May 2013

C code to implement Context Free Grammar(CFG)

/* C program to implement CFG(Context Free Grammar). */

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

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

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

void findter()
{
    for(k=0;k<n;k++)
    {
        if(temp[i]==pro[k].lhs[0])
        {
            for(t=0;t<pro[k].n;t++)
            {
                for(l=0;l<20;l++)
                    temp2[l]='\0';
                for(l=i+1;l<strlen(temp);l++)
                    temp2[l-i-1]=temp[l];
                for(l=i;l<20;l++)
                    temp[l]='\0';
                for(l=0;l<strlen(pro[k].rhs[t]);l++)
                    temp[i+l]=pro[k].rhs[t][l];
                strcat(temp,temp2);
                if(str[i]==temp[i])
                    return;
                else if(str[i]!=temp[i] && temp[i]>=65 && temp[i]<=90)
                    break;
            }
            break;
        }
    }
    if(temp[i]>=65 && temp[i]<=90)
        findter();
}

void main()
{
    FILE *f;
    clrscr();

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

    f=fopen("input.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++;
    }
    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]);

    while(1)
    {
        for(l=0;l<10;l++)
            str[0]=NULL;

        printf("\n\nENTER ANY STRING ( 0 for EXIT ) : ");
        scanf("%s",str);
        if(str[0]=='0')
            exit(1);

        for(j=0;j<pro[0].n;j++)
        {
            for(l=0;l<20;l++)
                temp[l]=NULL;
            strcpy(temp,pro[0].rhs[j]);

            m=0;
            for(i=0;i<strlen(str);i++)
            {
                if(str[i]==temp[i])
                    m++;
                else if(str[i]!=temp[i] && temp[i]>=65 && temp[i]<=90)
                {
                    findter();
                    if(str[i]==temp[i])
                        m++;
                }
                else if( str[i]!=temp[i] && (temp[i]<65 || temp[i]>90) )
                    break;
            }

            if(m==strlen(str) && strlen(str)==strlen(temp))
            {
                printf("\n\nTHE STRING can be PARSED !!!");
                break;
            }
        }

        if(j==pro[0].n)
            printf("\n\nTHE STRING can NOT be PARSED !!!");
    }

    getch();
}




Input File For CFG Program:

S aBaA
S AB
A Bc
B c

For more C programs related to Automata, Check Automata label. Share and comment to improve this blog.

Related Programs:-

★ Convert NFA to DFA

★ Lexical Analyzer

★ Syntax Tree

★ Calculate In and Out

13 comments:

  1. the program does not work for all types of grammer..it has limitations....
    please update your program...
    example
    S aBDh
    S DEF
    B cC
    C bC
    D EF
    E g
    E ^
    F f
    F ^

    this type of grammer does not work in your program..

    by the ways good job for simple grammer

    ReplyDelete
    Replies
    1. Thanks and i will try to solve this problem and update it soon. :)

      Delete
    2. C ->bC not valid

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

    ReplyDelete
  3. This comment has been removed by a blog administrator.

    ReplyDelete
    Replies
    1. Don't use hindi here.

      Delete
    2. why we can not use hindi..?

      Delete
  4. This comment has been removed by a blog administrator.

    ReplyDelete
  5. there are some error, when i run program
    getch();
    clrscr();
    exit(1);

    ReplyDelete
  6. I am running this program in Ubuntu:

    cfg.c: In function ‘main’:
    cfg.c:78:19: warning: assignment makes integer from pointer without a cast [enabled by default]
    str[0]=NULL;
    ^
    cfg.c:83:13: warning: incompatible implicit declaration of built-in function ‘exit’ [enabled by default]
    exit(1);
    ^
    cfg.c:88:24: warning: assignment makes integer from pointer without a cast [enabled by default]
    temp[l]=NULL;

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. no need...i solved it...
      set NULL=0
      add stdlib.h (header file)

      Delete
  7. This comment has been removed by a blog administrator.

    ReplyDelete

Back to Top