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

16 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. there are some error, when i run program
    getch();
    clrscr();
    exit(1);

    ReplyDelete
  3. 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. no need...i solved it...
      set NULL=0
      add stdlib.h (header file)

      Delete
  4. Can You Please explain your code line by line, if possible.

    ReplyDelete
  5. how to run this code please reply

    ReplyDelete
  6. It show nothing in cmd

    ReplyDelete
  7. 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
  8. it show nothing in cmd

    ReplyDelete
    Replies
    1. Anonymous11:47 pm

      use a txt a file, name as input.txt .

      Delete
  9. i want cfg program that will accept any string and validate

    ReplyDelete
  10. wrong code not working for many cases

    ReplyDelete
  11. Do more program in CFG to remove useless production .

    ReplyDelete

Back to Top