Search Tutorials

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

19 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
  8. Can You Please explain your code line by line, if possible.

    ReplyDelete
  9. how to run this code please reply

    ReplyDelete
  10. It show nothing in cmd

    ReplyDelete
  11. rhs[10][10] which is a 2D array is represented as 1D array sometimes in the code. Can anyone explain the process and how it works ?

    ReplyDelete

Back to Top