Recursive Descent Parser using C program

Updated on 09/02/15

Hello reader,

Here is the updated post considering your valuable suggestions. check it out.


The grammar on which we are going to do recursive descent parsing is:

E -> E+T | T
T -> T*F | F
F -> (E) | id
  RD parser will verify whether the syntax of the input stream is correct by checking each character  from left to right. A basic operation necessary is reading characters from the input stream and matching then with terminals from the grammar that describes the syntax of the input.

 The given grammar can accept all arithmetic equations involving +, * and ().
eg:
 a+(a*a)  a+a*a , (a), a , a+a+a*a+a.... etc are accepted
a++a, a***a, +a, a*, ((a . . . etc are rejected.

Solution:
First we have to avoid left recursion

E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' | ε
F -> (E) | id

After eliminating Left recursion, we have to simply move from one character to next by checking whether it follow the grammar. In this program, ε is indicated as $.


recursive.c

#include<stdio.h>
#include<string.h>
#include<ctype.h>
 
char input[10];
int i,error;
void E();
void T();
void Eprime();
void Tprime();
void F(); 
          main()
          {
i=0;
error=0;
                printf("Enter an arithmetic expression   :  "); // Eg: a+a*a
                gets(input);
                E();
                if(strlen(input)==i&&error==0)
                        printf("\nAccepted..!!!\n");
                else printf("\nRejected..!!!\n");
                          }
         
         
 
void E()
{
     T();
     Eprime();
}
void Eprime()
{
     if(input[i]=='+')
     {
     i++;
     T();
     Eprime();
     }
     }
void T()
{
     F();
     Tprime();
}
void Tprime()
{
     if(input[i]=='*')
     {
                      i++;
                      F();
                      Tprime();
                      }
                      }
     void F()
     {
          if(isalnum(input[i]))i++;
          else if(input[i]=='(')
          {
          i++;
          E();
          if(input[i]==')')
          i++;

          else error=1;
            }
        
          else error=1;
          }
           

Output:
 a+(a*a)  a+a*a , (a), a , a+a+a*a+a.... etc are  accepted
++a, a***a, +a, a*, ((a . . . etc are rejected.

Read more »

FIRST of a Given Grammar using C program

Hello Friend,

In this post we will discuss how to find FIRST of a grammar using C.


The rules for finding FIRST of a given grammar is:

1. If X is terminal, FIRST(X) = {X}.
2. If X → ε is a production, then add ε to FIRST(X).
3. If X is a non-terminal, and X → Y₁ Y₂ … Y_k is a production, and ε is in all of FIRST(Y₁), …, FIRST(Y_k), then add ε to FIRST(X).
4. If X is a non-terminal, and X → Y₁ Y₂ … Y_k is a production, then add a to FIRST(X) if for some i, a is in FIRST(Y_i), and ε is in all of FIRST(Y₁), …, FIRST(Y_i-1).

Assumptions:

1. Each Non terminal character is represented by one Uppercase letter.
2. Each Terminal character is represented by one lowercase letter.
3. LHS and RHS of each production will be separated by a "=" symbol.
4. There will be no Blank space within a production string. 
5. Assumed that Left recursion is avoided in all input productions. 

/* Author : Vipin
* mail:   vipinnarayantvm@gmail.com

 *Modified on : 23/03/2105

 */

#include<stdio.h>

#include<ctype.h>

void FIRST(char[],char );

void addToResultSet(char[],char);

int numOfProductions;

char productionSet[10][10];

main()

{

    int i;

    char choice; 

    char c;

    char result[20];

    printf("How many number of productions ? :");

    scanf(" %d",&numOfProductions);

    for(i=0;i<numOfProductions;i++)//read production string eg: E=E+T

    {

        printf("Enter productions Number %d : ",i+1);

        scanf(" %s",productionSet[i]);

    }

    do

    {

        printf("\n Find the FIRST of  :");

        scanf(" %c",&c);

        FIRST(result,c); //Compute FIRST; Get Answer in 'result' array

        printf("\n FIRST(%c)= { ",c);

        for(i=0;result[i]!='\0';i++)

        printf(" %c ",result[i]);       //Display result

        printf("}\n");

         printf("press 'y' to continue : ");
        scanf(" %c",&choice);

    }

    while(choice=='y'||choice =='Y');

}

/*

 *Function FIRST:

 *Compute the elements in FIRST(c) and write them

 *in Result Array.

 */

void FIRST(char* Result,char c)

{

    int i,j,k;

    char subResult[20];

    int foundEpsilon;

    subResult[0]='\0';

    Result[0]='\0';

    //If X is terminal, FIRST(X) = {X}.

    if(!(isupper(c)))

    {

        addToResultSet(Result,c);

               return ;

    }

    //If X is non terminal

    //Read each production

    for(i=0;i<numOfProductions;i++)

    {

//Find production with X as LHS

        if(productionSet[i][0]==c)

        {

//If X → ε is a production, then add ε to FIRST(X).

 if(productionSet[i][2]=='$') addToResultSet(Result,'$');

            //If X is a non-terminal, and X → Y1 Y2 … Yk

            //is a production, then add a to FIRST(X)

            //if for some i, a is in FIRST(Yi),

            //and ε is in all of FIRST(Y1), …, FIRST(Yi-1).

      else

            {

                j=2;

                while(productionSet[i][j]!='\0')

                {

                foundEpsilon=0;

                FIRST(subResult,productionSet[i][j]);

                for(k=0;subResult[k]!='\0';k++)

                    addToResultSet(Result,subResult[k]);

                 for(k=0;subResult[k]!='\0';k++)

                     if(subResult[k]=='$')

                     {

                         foundEpsilon=1;

                         break;

                     }

                 //No ε found, no need to check next element

                 if(!foundEpsilon)

                     break;

                 j++;

                }

            }

    }

}

    return ;

}

/* addToResultSet adds the computed

 *element to result set. 

 *This code avoids multiple inclusion of elements

  */

void addToResultSet(char Result[],char val)

{

    int k;

    for(k=0 ;Result[k]!='\0';k++)

        if(Result[k]==val)

            return;

    Result[k]=val;

    Result[k+1]='\0';

}

Output

Read more »

Print a string without using any semicolon

Write a program to print a  string without using any semicolon on the program:


#include<stdio.h>
main()
{
      if(printf("Hello.."))
      {
      }
}




I want to know how this program can modified to print any string accepted through Keyboard..!!

If anyone know, feel free to comment it here..!!  :):):)

Read more »

Letter Pattern

Write a program to print the following
         A
       B B
      CC CC
   DDD DDD





#include<stdio.h>
main()
{
      int i,j,n;
      printf("Enter Limit..  :  ");
      scanf("%d",&n);
      for(i=0;i<n;i++)
      {
      for(j=0;j<(n-i);j++)
      printf(" ");
      if(i==0)putchar(65);
      for(j=0;j<i;j++)putchar(65+i);      printf(" ");
        for(j=0;j<i;j++)putchar(65+i);
        printf("\n");
        }
        getch();
        }
     

Read more »

C program to print a Number pattern

Write a program to print the following pattern:
0

1 1
2 3 5
8 13 21 34



Hi buddy, Jst analyse the no.s in order, 0,1,1,2,3,5,8,13,21,34....
Yess!!!! this is a Fibonacci series.

0+1=1
1+1=2
1+2=3
2+3=5... and so on

Next requirement is to generate pattern. First line has 1 element, second line has 2 elements and so on. And total number of elements in whole pattern will be N*(N+1)/2 , if there are N number of lines.





#include<stdio.h>
main()
{
      int n,i,j,k=0;
      int a[20];
      printf("Enter the lmit..:   ");
      scanf("%d",&n);
      a[0]=0;
      a[1]=1;
      for(i=2;(i<n*(n+1)/2);i++)
      a[i]=a[i-1]+a[i-2];      for(j=0;j<=n;j++)
     {
      for(i=0;i<j;i++)
      printf("%d\t",a[k+i]);
      k+=i;
      printf("\n");
      }      getch();
}

Read more »

C program to Print a number table

Write a program to display the following format:

No	sum
1	1
2	3
3	6
4	10
5	15

Logic:

First column contains natural numbers serially..
second column contains  ( Current first column element+ previous second column element)
2+1=3
3+3=6
4+6=10
5+10=15




#include<stdio.h>
main()
{
      int j=0,z,i,n;
      printf("Enter the Limit...  :  ");
      scanf("%d",&n);
      printf("\n----------------\n
printf("no\tsum");
printf("\n------------------\n");
     
      for(i=1;i<=n;i++)
      {
      printf("\n%d",i);
      j+=i;
      printf("\t%d",j);
      }      getch();
      }
     
     
     

Read more »

Reverse words in a string using Recursion

Write a program to perform the following to any input string:
     
       Input : Structure is a derived datatype
      output: erutcurtS si a devired epytatad

My Code:

#include<stdio.h>
#include<string.h>
int main()
{
    char line[20],word[10];
    int i,j=0,len;
    printf("Entera string :  ");
    gets(line);
    len=strlen(line);
    for(i=0;i<len;i++)
    {
    while(line[i]!=' '&&i<len)
    word[j++]=line[i++];
    for(j--;j>=0;j--)
    printf("%c",word[j]);
    printf(" ");
    j=0;
    }
    getch();
    return 1;
}


I hope this code was useful for u!!
Have a better program for ths prblm??
Feel free to comment it here..!!  :):):)

Read more »

C program to find Size of a structure without using sizeof() operator

Write a program to find the size of following structure without using size of operator

struct ABC
 {
 int a;
 float b;
 char c;
 };



Hai Viewer, confused?? Hmm.. calculating the size of a datatype without using sizeof() operator seems to be weird. But pointers will help you to solve this problem.  First u have to initialize a null pointer on intended datatype .You know that in 'structure ' separate memory will be allocated to each element. So, on incrementing that pointer variable, the value of that pointer will be incremented by size of that structure . That is our Goal..!!!! :)
Since we have initialized pointer with 0 we simply need to print the current pointer value..!!



solution

#include<stdio.h>
struct  ABC
{
    int a;
    float b;
    char c;
};
int main()
{
    struct ABC *ptr=(struct ABC *)0;
    ptr++;
printf("%d",ptr);
getch();
return 1;
}


I hope this code was useful for u!!
Have a better program for ths prblm??
Feel free to comment it here..!!  :):):)

Read more »

C program to Print a Non-Fibonacci series

Write a C program to generate non-fibonacci series to given Limit:

#include<stdio.h>
#include<conio.h>
main()
{
 int n,a,b,c,d,x;
 a=0;
 b=1;
 c=0;
 printf("Enter the upper range of the series:");
 scanf("%d",&n);
 while(c<=n)
 {
  c=a+b;
  a=b;
  b=c;
  d=a+b;
  for(x=c+1;x<d;x++)
  {
   if(x<=n)
    printf("%d",x);
   else
    break;
  }
 }
 getch();
}


I hope this code was useful for u!!
Have a better program for ths prblm??
Feel free to comment it here..!!  :):):)

Read more »

C program to Reverse a string using recursion

Write a program to reverse any string using recursion (Maximum 15 steps)

Eg: Input   :  Bjarne Stroustrup developed C++
     Output  : ++C depoleved purtsuortS enrajB

This is one of the common question asked in technical contests and interviews.!! it checks ur knowledge about recursion and string. We recursively calls itself until encountering endl character. This fragment plays the vital role: 

{
if (current character != endl) process( next caharacter);
print(current character); 
}


My code:

#include<stdio.h>
char line[20];
void print(int i)
{
     if(line[i]!='\0')
     print(i+1);
     printf("%c",line[i]);
}
main()
{
      printf("Enter a  string..:   ");
      gets(line);
      print(0);
      getch();
}
 



I hope this code was useful for u!!
Have a better program for ths prblm??
Feel free to comment it here..!!  :):):)

Read more »

Coding Contest- Matrix multiplication

PROBLEM : Write a program to multiply two 3 x 3 matrices where resulting matrix should produce

• If cell element is even '0'
• If cell element is odd '1'

eg: If resulting matrix of multiplication is

My code:


#include<stdio.h>
main()
{
      int a[3][3],b[3][3],c[3][3],d[3][3];
      int i,j,k;
      printf("Enter First matrix:...\n");
      for(i=0;i<3;i++)
      for(j=0;j<3;j++)
      scanf("%d",&a[i][j]);
       printf("Enter Second matrix:...\n");
      for(i=0;i<3;i++)
      for(j=0;j<3;j++)
      scanf("%d",&b[i][j]);
     
      for(i=0;i<3;i++)
      for(j=0;j<3;j++)
      {
      c[i][j]=0;
      for(k=0;k<3;k++)
      c[i][j]+=a[i][k]*b[k][j];
      }      for(i=0;i<3;i++)
      for(j=0;j<3;j++)
      {
      if(c[i][j]%2)d[i][j]=1;
      else d[i][j]=0;      }
      printf("\n Product is..\n");
      for(i=0;i<3;i++)
      {
      for(j=0;j<3;j++)
      printf("%d\t",c[i][j]);
      printf("\n");
      }
       printf("\n Response is..\n");
      for(i=0;i<3;i++)
      {
      for(j=0;j<3;j++)
      printf("%d\t",d[i][j]);
      printf("\n");
      }
     
      getch();
}     
     

Read more »

C program to implement DFA

//updated on 11/03/2015

Hello friends,

               This post describes how a Deterministic Finte Automata (DFA) can be implemented using C. Do you know, associated with every programming language compiler there is a program named  recognizer that takes a string , say string S, as input and answers "YES" if S is a sentence of the language and  " NO " otherwise..!! To accomplish this , we have to train recognizer about the syntactic structure of intended language ( done with regular expressions). For this purpose, we construct a transition diagram called a "finite automation". In a Deterministic Finite Automation, only one transition out of state is possible on the same input symbol. On the other hand, in NonDeterministic Finite Automata more than one transitions may possible for same input symbol.

  . Some interesting implementations using DFA are:

• whether DFA accepts all strings.
• whether DFA accepts any string
• whether two DFAs recognize the same language
• DFA with a minimum number of states for a particular regular language

Illustartion


Consider the DFA represented in this transition diagram.



   

                         


Here is a sample DFA with starting state " 0 ", and accepting state " 1" .  "a" and "b" are the input symbols.
This DFA will accept any string containing 'a's and 'b' and last symbol should be 'a'.


CODE:


#include <stdio.h>

#define TOTAL_STATES 2

#define FINAL_STATES 1

#define ALPHABET_CHARCTERS 2

#define UNKNOWN_SYMBOL_ERR 0

#define NOT_REACHED_FINAL_STATE 1

#define REACHED_FINAL_STATE 2

enum DFA_STATES{q0,q1};

enum input{a,b};

int Accepted_states[FINAL_STATES]={q1};

char alphabet[ALPHABET_CHARCTERS]={'a','b'};

int Transition_Table[TOTAL_STATES][ALPHABET_CHARCTERS];

int Current_state=q0;

void DefineDFA()

{

    Transition_Table[q0][a] = q1;

    Transition_Table[q0][b] = q0;

    Transition_Table[q1][a] = q1;

    Transition_Table[q1][b] = q0;

}

int DFA(char current_symbol)

{

int i,pos;

    for(pos=0;pos<ALPHABET_CHARCTERS; pos++)

        if(current_symbol==alphabet[pos])   

            break;//stops if any character other than a or b

    if(pos==ALPHABET_CHARCTERS)

         return UNKNOWN_SYMBOL_ERR;

    for(i=0;i<FINAL_STATES;i++)

 if((Current_state=Transition_Table[Current_state][pos])

==Accepted_states[i])

            return REACHED_FINAL_STATE;

    return NOT_REACHED_FINAL_STATE;

}

int main(void)

{

    char current_symbol;

    int result;

    DefineDFA();    //Fill transition table

    printf("Enter a string with 'a' s and 'b's:\n

                Press Enter Key to stop\n");

    while((current_symbol=getchar())!= '\n')

        if((result= DFA(current_symbol))==UNKNOWN_SYMBOL_ERR)

            break;

    switch (result) {

    case UNKNOWN_SYMBOL_ERR:printf("Unknown Symbol %c",

  current_symbol); 

 break;

    case NOT_REACHED_FINAL_STATE:printf("Not accepted"); break;

    case REACHED_FINAL_STATE:printf("Accepted");break;

    default: printf("Unknown Error");

    }

    printf("\n\n\n");

    return 0;

}

OUTPUT
========

String with only "a"s and "b"s and last symbol is "a".     ACCEPTED..!!

String with only "a"s and "b"s but  last symbol is not  "a".     REJECTED..!!

Unknown symbol "y" in input. REJECTED.!!!!

Read more »