/*CSEMATTER.BLOGSPOT.IN
PROGRAM NAME-STACK IMPLEMENTATION OF PREDICTIVE PARSER*/
#include<ctype.h>
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#define non_term_count 5
#define term_count 6
#define rightHandMarker term_count-1
#define no_of_production 8
char nt[]={'E','A','T','B','F'},ter[]={'i','+','*','(',')','$'};
char arr[20][20][20]={
{"TA","","","TA","",""},
{"","+TA","","","@","@"},
{"FB","","","FB","",""},
{"","@","*FB","","@","@"},
{"i","","","(E)","",""}
};
char ipstr[20];
char stack[40],prod[10];
int i=0,top=1,ia,ix;
struct predictive_table
{
char prod[10];
}table[non_term_count][term_count]={"\0"};
struct
{
int isNull;
char term[10];
}first[non_term_count]={{0,"(i"},{1,"+"},{0,"(i"},{1,"*"},{0,"(i"}};
struct
{
int isMarker;
char term[10];
}follow[non_term_count]={{1,")"},{1,")"},{1,"+)"},{1,"+)"},{1,"+*)"}};
char terminals[term_count-1][2]={"i","+","*","(",")"};
char nonTerminals[non_term_count][3]={"E","A","T","B","F"};
char grammar[no_of_production][10]={"E T A","A + T A","A @","T F B","B * F B","B @","F ( E )","F i"};
char pgrammar[no_of_production][10]={"E->TA","A->+TA","A->@","T->FB","B->*FB","B->@","F->(E)","F->i"};
int matchTerminals(char term[])
{
int i=-1;
for(i=0; i<term_count-1; i++)
if(!strcmp(term,terminals[i]))
break;
return i;
}
void copy_follow(int index,int loc)
{
char term[2];
int j,ind;
if(follow[index].isMarker==1)
{
if(strlen(table[index][rightHandMarker].prod)==0)
strcpy(table[index][rightHandMarker].prod,pgrammar[loc]);
else
printf("\nGiven Grammar is not LL(1)");
}
j=0;
while(follow[index].term[j]!='\0')
{
term[0]=follow[index].term[j];
term[1]='\0';
ind = matchTerminals(term);
if(strlen(table[index][ind].prod)==0)
strcpy(table[index][ind].prod,pgrammar[loc]);
else
printf("\nGiven Grammar is not LL(1)");
j++;
}
}
int matchNonTerminals(char non_term[])
{
int i=-1;
for(i=0; i<non_term_count; i++)
if(!strcmp(non_term,nonTerminals[i]))
break;
return i;
}
void show_table()
{
int k,i,j;
printf("\n\t\t\tPredictive Parser Table \n\n");
printf(" |");
for(i=0; i<term_count-1; i++)
printf(" %s |",terminals[i]);
printf(" $ |");
for(i=0; i<non_term_count; i++)
{
printf("\n----------------------------------------------------------------");
printf("\n%s",nonTerminals[i]);
for(k=strlen(nonTerminals[i]); k<3; k++)
printf(" ");
printf("|");
for(j=0; j<term_count; j++)
{
printf(" %s",table[i][j].prod);
for(k=strlen(table[i][j].prod); k<8; k++)
printf(" ");
printf("|");
}
}
}
void fun();
int main()
{
int i,k,j,t,flag=0,indexTerm,indexNonTerm,index;
char nextChar[10]="\0",nonterm[10]="\0",term[10]="\0";
for(i=0; i<no_of_production; i++)
{
t=0;
j=0;
flag=0;
while(grammar[i][j]!=' '&&grammar[i][j]!='\0')
nonterm[t++]=grammar[i][j++];
nonterm[t]='\0';
indexNonTerm=matchNonTerminals(nonterm);
X: j++;
t=0;
while(grammar[i][j]!=' '&&grammar[i][j]!='\0')
nextChar[t++]=grammar[i][j++];
nextChar[t]='\0';
if(!strcmp(nextChar,"@"))
copy_follow(indexNonTerm,i);
else
{
index=matchTerminals(nextChar);
if(index!=term_count-1)
{
if(strlen(table[indexNonTerm][index].prod)==0)
strcpy(table[indexNonTerm][index].prod,pgrammar[i]);
else
{
printf("\nGiven Grammar is not LL(1)");
break;
}
}
else
{
index=matchNonTerminals(nextChar);
if(index!=non_term_count)
{
k=0;
while(first[index].term[k]!='\0')
{
term[0]=first[index].term[k];
term[1]='\0';
indexTerm=matchTerminals(term);
if(strlen(table[indexNonTerm][indexTerm].prod)==0)
strcpy(table[indexNonTerm][indexTerm].prod,pgrammar[i]);
else
{
printf("\n Given Grammar is not LL(1) ");
break;
}
k++;
} //end while
if(first[index].isNull==1)
{
flag=1;
goto X;
}
else
flag=0;
}
}
}
if(flag==1)
copy_follow(indexNonTerm,i);
}
show_table();
fun();
getch();
}
void fun()
{
void pop();
void push(char);
int resolve_nt(char);
int resolve_t(char);
void advance();
char a,x;
int len,k;
stack[0]='$';
stack[1]='E';
printf("\nenter the input string:\n");
scanf("%s",ipstr);
printf("I/p string\t\tStack\t\tProduction Used\n");
while(1)
{
a=ipstr[i];
x=stack[top];
for(k=i;ipstr[k]!='$';k++)
printf("%c",ipstr[k]);
printf("$\t\t");
if(x==a)
{
if(x=='$')
{
printf("input is accepted");
break;
}
else
{
pop();
advance();
}
}
else if(isupper(x))
{
ix=resolve_nt(x);
ia=resolve_t(a);
strcpy(prod,arr[ix][ia]);
len=strlen(prod);
pop();
for(k=1;k<=len;k++)
push(prod[len-k]);
if(stack[top]=='@')
pop();
}
else
{
printf("error");
break;
}
for(k=0;k<=top;k++)
printf("%c",stack[k]);
printf("\t\t\t%s\n",prod);
}
}
void push(char t)
{
top+=1;
stack[top]=t;
}
void pop()
{
top--;
}
void advance()
{
i++;
}
int resolve_nt(char t)
{
int k,index;
for(k=0;k<5;k++)
{
if(t==nt[k])
{
index=k;
break;
}
}
return index;
}
int resolve_t(char t)
{
int k,index;
for(k=0;k<6;k++)
{
if(t==ter[k])
{
index=k;
break;
}
}
return index;
}
/*OUTPUT
Predictive Parser Table
| i | + | * | ( | ) | $ |
----------------------------------------------------------------
E | E->TA | | | E->TA | | |
----------------------------------------------------------------
A | | A->+TA | | | A->@ | A->@ |
----------------------------------------------------------------
T | T->FB | | | T->FB | | |
----------------------------------------------------------------
B | | B->@ | B->*FB | | B->@ | B->@ |
----------------------------------------------------------------
F | F->i | | | F->(E) | | |
enter the input string:
i+i*i$
I/p string Stack Production Used
i+i*i$ $AT TA
i+i*i$ $ABF FB
i+i*i$ $ABi i
i+i*i$ $AB i
+i*i$ $A @
+i*i$ $AT+ +TA
+i*i$ $AT +TA
i*i$ $ABF FB
i*i$ $ABi i
i*i$ $AB i
*i$ $ABF* *FB
*i$ $ABF *FB
i$ $ABi i
i$ $AB i
$ $A @
$ $ @
$ input is accepted
*/
