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 »

SEMAPHORES TO IMPLEMENT PRODUCER CONSUMER PROBLEM

#include<sys/sem.h>
#include<fcntl.h>
#include<unistd.h>
#include<sys/types.h>
#include<stdio.h>
#include<sys/ipc.h>
void up(int);
void down(int);
union value
{
int val;
struct semid_ds *buf;
unsigned short *array;
struct seminto *_buf;
}
main()
{
int mutex,full,empty,pid,i,key,j,k;
union value arg;
key=ftok("",'a');
mutex=semget(key,1,0660|IPC_CREAT);
arg.val=0;
semctl(full,0,SETVAL,arg);
key=ftok("",'c');
empty=semget(key,1,0660|IPC_CREAT);
arg.val=4;
semctl(empty,0,SETVAL,arg);
pid=fork();
switch(pid)
{
case -1:
printf("Error");
case 0:
sleep(13);
printf("\n");
printf("Consumer consuming items\n");
for(i=0;i<5;i++)
{
down(full);
down(mutex);
for(j=4-i;j>=1;j--)
printf("*");
for(k=0;k<=i;k++)
printf("_");
printf("\n");
fflush(stdout);
up(mutex);
up(empty);
sleep(1);
}
printf("Buffer empty\n");
break;
default:
printf("Producer producing items\n");
for(i=0;i<5;i++)
{
down(full);
down(mutex);
//printf("producer is producing %dth item\n",i);
for(j=4-i;j>=1;j--)
printf("_");
for(k=0;k<=i;k++)
printf("*");
printf("\n");
fflush(stdout);
up(mutex);
up(full);
sleep(1);
}
printf("Buffer full\n");
break;
}}
void down(int id)
{
struct sembuf sb={0,-1,0};
semop(id,&sb,1);
}
void up(int id)
{
struct sembuf sb={0,1,0};
semop(id,&sb,1);
}

Read more »

Calculator using YACC program

Here is the Yacc program implementing a simple calculator:

%{
#include<stdio.h>
#include<ctype.h>
%}
%token num
%left '+''-'
%left '*''/'
%right '^'
%%
s:e'\n'{printf("%d",$1);}
e:    e '+' e{$$=$1+$3;}
 |e '-' e{$$=$1-$3;}
 |e '*' e{$$=$1*$3;}
 |e '/' e{$$=$1/$3;}
 |e '^' e {
  int i,j=$1;
  for(i=1;i<$3;i++)
  {
  j=j*$1;
  $$=j;
  }
  }
 |'('e')'{$$=$2;}
 |num1;
num1:num1 num{$$ = $1*10 + $2;}
 |num
 ;
%%
yylex()
{
int c;
c=getchar();
if(isdigit(c))
{
yylval=c-'0';
return num;
}
return c;
}
int main()
{
yyparse();
return 1;
}
int yyerror()
{
return 1;
}
int yywrap()
{
return 1;
}



Illustration:

Let the Input be 2+5

Moving from first definition s:e'\n'
s  --> move to DEF(e)
e: e '+' e is selected. Evaluate first 'e' ie e-->num1
num1 extracts the token (i.e, number here 2 is extracted and stored in $1)
Then '+' is extracted and stored in $2.
Then move to e--> num1, thus 5 is  extracted and stored  in $3.
Now add them and store result in $$.

Go back to S: e'\n' and print result (which is 'e' here..!!)


If you have any doubt regarding this post feel free to comment here.
Thank U..!!

For more Yacc programs click here..!!

Read more »

YACC program to convert infix

%{#include<stdio.h>
#include<ctype.h>
%}
%token num
%left '+''-'
%left '*' '/'
%%
s:e'\n'{}
e:e'+'e{printf("+");}
|e'-'e{printf("-");}
|e'/'e{printf("/");}
|e'*'e{printf("*");}
|num1{printf("%d",$1);}
num1:num1 num {$$=$1*10+$2;}
|num
;
%%
yylex()
{
 int c;
 c=getchar();
if(isdigit(c))
{ yylval=c-'0';
 return num;
}return c;
}
int main()
{
 yyparse();
return 1;
}
int yyerror()
{
return 1;
}
int yywrap()
{
 return 1;
}

Read more »

Yacc program to evaluate POSTFIX expression

%{#include<stdio.h>
#include<ctype.h>
%}
%token num
%left '+''-'
%left '*' '/'
%right '^'
%%
s:e'\n'{printf("\n%d",$1);}
e:e e'+'{$$=$1+$2;}
|e e'-'{$$=$1-$2;}
|e e'*'{$$=$1*$2;}
|e e'/'{$$=$1/$2;}
|num
;
%%
yylex()
{
int c;
c=getchar();
if(isdigit(c))
{ yylval=c-'0';
 return num;
}return c;
}
int main()
{
 yyparse();
return 1;
}
int yyerror()
{
return 1;
}
int yywrap()
{
 return 1;
}

Illustraion:

Evaluation of postfix expression can be done very easily.

34+
3--> store value in $1
4--> store value in $2
+--> add $1 and $2 and store result in $$

For more Yacc programs click here..!!

Read more »

C Program to generate Intermediate code

#include<stdio.h>
#include<ctype.h>
#include<string.h>
main()
{
char a[20];
int i=2,n;
printf("Exp  :");
scanf("%s", a);
if(isdigit(a[0]))
printf("MVI A,%c\n",a[0]);
else printf("MOV A,%c\n",a[0]);
n=strlen(a);
while(i<n)
{
switch(a[i])
{
case '+':printf("ADD B\n");i+=3;break;
case '-':printf("SUB B\n");i+=3;break;


default:if(isdigit(a[i]))
printf("MVI B,%c\n",a[i]);
else
printf("MOV B,%c\n",a[i]);
i--;
}
}
}

Read more »

LEX program to check the syntax of SCANF statement

%{
#include<stdio.h>
#include<ctype.h>
int i=0,j=0;
%}a "%d"|"%f"|"%c"|"%s"
id [a-zA-Z][a-zA-Z0-9]*
%%
scanf\((\"({a}*|.*)*\"(,\&{id})*\))\;
{for(i=0;i<yyleng;i++)
{if(yytext[i]=='%')
j++;
if(yytext[i]==',')
j--;
}
if(j==0)
printf("Correct");
else
printf("Incorrect");
}
%%
main()
{ yyin=fopen("sample.c","r");
yylex();
}
int yywrap()
{
return 1;
}        

Read more »