LR PARSER

#include stdio.h
#include conio.h
#include string.h
#define MAX 36
char action_table[12][6][4]={
"s5","e1","e1","s4","e1","e1",
"e1","s6","e1","e1","e1","A",
"e1","r2","s7","e1","r2","r2",
"e1","r4","r4","e1","r4","r4",
"s5","e1","e1","s4","e1","e1",
"e1","r6","r6","e1","r6","r6",
"s5","e1","e1","s4","e1","e1",
"s5","e1","e1","s4","e1","e1",
"e1","s6","e1","e1","s11","e1",
"e1","r1","s7","e1","r1","r1",
"e1","r3","r3","e1","r3","r3",
"e1","r5","r5","e1","r5","r5"
};
char goto_table[12][3][4]={
"1","2","3",
" "," "," ",
" "," "," ",
" "," "," ",
"8","2","3",
" "," "," ",
" ","9","3",
" "," ","10",
" "," "," ",
" "," "," ",
" "," "," ",
" "," "," "
};

char G[6][10]={
"E-->E+T",
"E-->T",
"T-->T*F",
"T-->F",
"F-->(E)",
"F-->i"
};

int i,top=-1;
char stack[MAX],st[20];
char err_flag;
void push(char ch)
{
if(top>MAX-1)
printf("\n Stack is full \n");
else
{
if(ch=='')
return;
else
stack[++top]=ch;
}
}
char pop()
{
char ch;
if(top<0)
{
printf("\n stack is empty \n");
return '\0';
}
ch=stack[top--];
stack[top+1]='\0';
return ch;
}
int char_val(char ch)
{
int x;
switch(ch)
{
case'i':
case'E': x=0;
break;
case'+':
case'T': x=1;
break;
case'*':
case'F': x=2;
break;
case'(':x=3;
break;
case')':x=4;
break;
case'$' :x=5;
break;
}
return x;
}
void error()
{
err_flag=1;
}
void main()
{
char x,a,tab_e[5],goto_e[4];
int i=0,len,xx,yy,zz,red_val,l;
clrscr();
printf("\n Enter a string ending with a $: ");
fflush(stdin);
scanf("%s",st);
printf("\n Input string is %s ",st);
push('0');
printf("\n\n\n\n\t\t parse table for expression grammar");
printf("-------------------------------------------------\n");
printf("\n\t\tAction_Table\t\t\tGoto_table");
printf("-------------------------------------------------\n");
printf("\n%7s%7s%7s%7s%7s%7s%7s%7s%7s","id","+","*","(",")","$","E","T","F");
printf("\n-----------------------------------------------\n");

for(xx=0;xx<12;xx++)
{
for(yy=0;yy<6;yy++)
printf("%7s",action_table[xx][yy]);
for(yy=0;yy<3;yy++)
printf("%7s",goto_table[xx][yy]);
printf("\n\n");
}
printf("\n MOVES MADE BY LR PARSER \n");
printf("---------------------------\n");
printf("STACK\t\t\tINPUT_STRING \n");
printf("--------------------------\n");
do
{
if(stack[top]=='\n')
{
for(l=0;l printf("%c",stack[l]);
printf("%d\t\t",stack[top]);
}
else
printf("%s\t\t\t",stack);
for(xx=0;st[xx]!='\0';xx++)
if(xx printf(" ");
else
printf("%c",st[xx]);
printf("\n");
if(stack[top]=='1' && stack[top-1]=='1')
x=11;
else
x=stack[top];
a=st[i];
if(stack[top]=='\n')
xx=10;
else if(stack[top]=='1' && stack[top-1]=='1')
{
xx=11;
stack[--top]=11;
}
else
xx=x-'0';
if(top>2)
switch(stack[top-1])
{
case 'i':
case '+':
case '*':
case '(':
case ')':
case '$':
case 'E':
case 'T':
case 'F':
break;
default:
xx+=(stack[top-1]-'0')*10;
break;
}
yy=char_val(a);
strcpy(tab_e,action_table[xx][yy]);
if(tab_e[0]=='s')
{
push(a);
push(tab_e[1]);
if(tab_e[2]!='\0')
push(tab_e[2]);
a=st[++i];
}
else
if(tab_e[0]=='r')
{
red_val=tab_e[1]-'0';
len=strlen(G[red_val-1]);
for(len=len-4;len>0;len--)
{
pop();
pop();
}
xx=stack[top]-'0';
push(G[red_val-1][0]);
yy=char_val(G[red_val-1][0]);
if(xx==7&&yy==2)
push(10);
else
push(goto_table[xx][yy][0]);
}
else if(action_table[xx][yy][0]=='A')
break;
else
error();

}while(!err_flag);
if(err_flag)
printf("Parsing is unsuccessfull");
else
printf("\n parsing is successfull\n");
getch();
}

OUTPUT:
Input string is : i*i+i$

-------------------------------------------------------------------
parse table for expression grammar
-------------------------------------------------------------------
Action_Table Goto_table
-------------------------------------------------------------------
id + * ( ) $ E T F
-------------------------------------------------------------------
s5 e1 e1 s4 e1 e1 1 2 3

e1 s6 e1 e1 e1 A

e1 r2 s7 e1 r2 r2

e1 r4 r4 e1 r4 r4

s5 e1 e1 s4 e1 e1 8 2 3

e1 r6 r6 e1 r6 r6

s5 e1 e1 s4 e1 e1 9 3

s5 e1 e1 s4 e1 e1 10

e1 s6 e1 e1 s11 e1

e1 r1 s7 e1 r1 r1

e1 r3 r3 e1 r3 r3

e1 r5 r5 e1 r5 r5


MOVES MADE BY LR PARSER
---------------------------------------------
STACK INPUT_STRING
----------------------------------------------
0 i*i+i$
0i5 *i+i$
0F3 *i+i$
0T2 *i+i$
0T2*7 i+i$
0T2*7i5 +i$
0T2*7F10 +i$
0T2 +i$
0E1 +i$
0E1+6 i$
0E1+6i5 $
0E1+6F3 $
0E1+6T9 $
0E1 $

parsing is successfull