Tuesday, June 26, 2012

Program for recursive decent parsing


#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 128
#define NONE -1
#define EOS '\0'
#define NUM 257
#define KEYWORD 258
#define ID 259
#define DONE 260
#define MAX 999
char lexemes[MAX];
char buffer[SIZE];
int lastchar=-1;
int lastentry=0;
int tokenval=DONE;
int lineno=1;
int lookahead;
struct entry
{
char *lexptr;
int token;
}symtable[100];
struct entry keywords[]={"if",KEYWORD,"else",KEYWORD,"for",KEYWORD,
"int",KEYWORD,"float",KEYWORD,"double",KEYWORD,
"char",KEYWORD,"struct",KEYWORD,"return",KEYWORD,
0,0};
void errormsg(char *m)
{
fprintf(stderr,"line %d:%s\n",lineno,m);
exit(1);
}
int lookup(char s[])
{
int k;
for(k=lastentry;k>0;k=k-1)
if(strcmp(symtable[k].lexptr,s)==0)
return k;
return 0;
}
int insert(char s[],int tok)
{
int len;
len=strlen(s);
if(lastentry+1>=MAX)
errormsg("symtable is full");
if(lastentry+len+1>=MAX)
errormsg("lexemes array is full");
lastentry=lastentry+1;
symtable[lastentry].token=tok;
symtable[lastentry].lexptr=&lexemes[lastchar+1];
lastchar=lastchar+len+1;
strcpy(symtable[lastentry].lexptr,s);
return lastentry;
}
void initialise()
{
struct entry *ptr;
for(ptr=keywords;ptr->token;ptr++)
insert(ptr->lexptr,ptr->token);
}
int lexer()
{
int t;
int val,i=0;
while(1)
{
t=getchar();
if(t==' '||t=='\t');
else if(t=='\n')
lineno=lineno+1;
else if(isdigit(t))
{
ungetc(t,stdin);
scanf("%d",&tokenval);
return NUM;
}
else if(isalpha(t))
{
while(isalnum(t))
{ buffer[i]=t;
t=getchar();
i=i+1;
if(i>=SIZE)
errormsg("compile error");
}
buffer[i]=EOS;
if(t!=EOF)
ungetc(t,stdin);
val=lookup(buffer);
if(val==0)
val=insert(buffer,ID);
tokenval=val;
return symtable[val].token;
}
else if(t==EOF)
return DONE;
else
{ tokenval=NONE;
return t;
}
}
}
void match(int t)
{
if(lookahead==t)
lookahead=lexer();
else
errormsg("syntax error");
}
void display(int t,int tval)
{
if(t=='+'||t=='-'||t=='*'||t=='/')
printf("\n arithmetic operator %c",t);
else if(t==NUM)
printf("\n number %d",tval);
else if(t==ID)
printf("\n identifier:%s",symtable[tval].lexptr);
else
printf("\n token:%d tokenval %d",t,tokenval);
}
void F()
{ void E();
switch(lookahead)
{
case '(':
match('(');
E();
match(')');
break;
case NUM:
display(NUM,tokenval);
match(NUM);
break;
case ID:
display(ID,tokenval);
match(ID);
break;
default:
errormsg("syntax error");
}
}
void T()
{ int t;
F();
while(1)
{ switch(lookahead)
{
case '*':
t=lookahead;
match(lookahead);
F();
display(t,NONE);
continue;
case '/':
t=lookahead;
match(lookahead);
F();
display(t,NONE);
continue;
default: return;
}
}
}
void E()
{ int t;
T();
while(1)
{ switch(lookahead)
{
case '+':
t=lookahead;
match(lookahead);
T();
display(t,NONE);
continue;
case '-':
t=lookahead;
match(lookahead);
T();
display(t,NONE);
continue;
default:
return;
}
}
}
void parser()
{
lookahead=lexer();
while(lookahead!=DONE)
{
E();
match(';');
}
}
int main()
{
char ans;
clrscr();
printf("\n \t \t Program for recursive decent parsing");
initialise();
printf("enter the expression & place;at the end \n Press CTRL+ Z to terminate");
parser();
return 0;
}

2 comments: