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.