PREDICTIVE PARSER PROGRAM

/*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

*/