Operator Precedence Parser algorithm & program in c

(If you have any doubts regarding the concept and working of operator precedence parser then refer  the following video)

PART 1

PART 2

Algorithm

1) Set input pointer ip to point to the first symbol of w$

2) Repeat forever
 
    if $ is on top of the stack and ip points to  $

        return
 
    else
 
        begin
 
            let a be the top most terminal symbol on the stack

            and let b be the symbol pointed by ip.

            if a<b or a=b then

                begin

                     push b into the stack.
 
                     advance ip to the next input symbol.

                end

           else if a>b then

                repeat pop the stack until the top of the stack terminal is related by < to the

                terminal most recently popped.

           else

                error

       end
     

    Program ( in c )

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
int k,w,e,q,length,rhslength,len,plength,row;
int column,i,y,u,valid,v,begin,top,z;
char aa,bb,temp,term[10],rhs[10],token[25],stack[20],nt,handle[10],tm;
char table[10][10]={
   {' ','+','-','*','/','^','i','(',')','$'},
   {'+','>','>','<','<','<','<','<','>','>'},
   {'*','>','>','<','<','<','<','<','>','>'},
   {'/','>','>','>','>','<','<','<','>','>'},
   {'^','>','>','>','>','<','<','<','>','>'},
   {'i','>','>','>','>','>',' ',' ','>','>'},
   {'(','<','<','<','<','<','<','<','=',' '},
   {')','>','>','>','>','>',' ',' ','>','>'},
   {'$','<','<','<','<','<','<','<','>','>'}
};
char production[9][10]={
{'E','-','>','E','A','E','\0'},
{'E','-','>','(','E',')','\0'},
{'E','-','>','-','E','\0'},
{'E','-','>','i','\0'},
{'A','-','>','+','\0'},
{'A','-','>','-','\0'},
{'A','-','>','*','\0'},
{'A','-','>','/','\0'},
{'A','-','>','^','\0'},
};
void find_row_for_a(char a){
  int j;
  for(j=0;j<=10;j++){
  if(table[j][0]==a)
  break;
  }
 row=j;
 if(j==10){
  printf("\n String is not accepted");
  getch();
  exit(0);
  }
}
void find_column_for_b(char b){
 int j;
  for(j=0;j<10;j++){
  if(table[0][j]==b)
  break;
 }
  column=j;
  if(j==10)
  {
  printf("\n String is not accepted");
  getch();
  exit(0);
}
}
void push(char info)
{
 top++;
  stack[top]=info;
  for(k=0;k<length;k++)
  token[k]=token[k+1];
  length--;
  token[length]='\0';
}
void get_rhs(){
 e=0;
 plength=strlen(production[y]);
  nt=production[i][0];
  while(production[y][e]!='>')
  e++;
 e++;
  q=0;
  while(e<plength){
  rhs[q]=production[y][e];
  e++;
  q++;
  }
if((rhs[1]=='A'&&(handle[1]=='+')||(handle[1]=='*')||handle[1]==
'-')||(handle[1]=='^')||(handle[1]=='/'))
  rhs[1]=handle[1];
  rhs[q]='\0';
 rhslength=strlen(rhs);
}
void reduce(){
 for(y=0;y<9;y++){
  get_rhs();
  if(strcmp(rhs,handle)==0){
    top++;
    stack[top]=nt;
  break;
  }
 }
  if(y==9){
  printf("\n String is not accepted");
  getch();
  exit(0);
  }
  stack[top+1]='\0';
}

void check_for_precedence(){
  aa=stack[top];
  z=top;
  while(aa=='E'||aa=='A'){
  z--;
  aa=stack[z];
  }
  bb=token[i];
  find_row_for_a(aa);
  find_column_for_b(bb);
  if(table[row][column]=='<'||table[row][column]=='=')
  push(bb);
  else if(table[row][column]=='>'){
  u=0;
  while(top>=0){
  if(stack[top]=='E'||stack[top]=='A'){
    while(stack[top]=='E'||stack[top]=='A'){
    term[u]=stack[top];
    top--;
    u++;
    }
  }
  term[u]=stack[top];
  tm=stack[top];
  top--;
  while(stack[top]=='E'||stack[top]=='A'){
    u++;
    term[u]=stack[top];
    top--;
    }
    temp=stack[top];
    find_row_for_a(temp);
    find_column_for_b(tm);
    if(table[row][column]=='<'){
    valid=1;
    break;
    }
    u++;
  }
  if(!valid){
  printf("\n String is not accepted");
  getch();
  exit(0);
 }
 len=u+1;
  v=len-1;
  for(w=0;w<len;w++){
  handle[w]=term[v];
  v--;
  }
  handle[len]='\0';
  reduce();
 }
  else{
  printf("\n String is not accepted");
  getch();
  exit(0);
  }
}

void check(){
  while(length>(-1)){
  check_for_precedence();
  begin=1;
if(stack[0]=='$'&& stack[1]=='E'&& stack[2]=='\0'&&
  token[0]=='$'&&token[1]=='\0'){
    printf("\n String is accepted");
    getch();
    exit(0);
  }
  if(stack[0]=='$'&& stack[1]=='i'&& stack[2]=='\0'&&
token[0]=='$'&&token[1]=='\0'){
  printf("\n String is accepted");
    getch();
    exit(0);
  }
  if(stack[0]=='$'&& stack[1]!='E'&& stack[2]=='\0'&&
token[0]=='$'&&token[1]=='\0'){
    printf("\n String is not accepted");
    getch();
    exit(0);
  }
  }
 }
 void main(){
  clrscr();
  printf("\n Operator precedence for the parcer\n");
  printf("\n E->EAE|(E)|E|i\n");
  printf("\n A->+|-|*|/|^\n\n Enter the string (add $ to the end of the string):\n");
  scanf("%s",&token);
  i=0;
  length=strlen(token);
  begin=0;
  top=0;
  stack[top]='$';
  if((stack[top]=='$')&&(strcmp(token,"$")==0)){
  printf("\n String is not accepted");
  getch();
  exit(0);
  }
  check();
  getch();
}

Result

Operator precedence for the parser

E --> EAE / (E) / E / i

A --> + / - / * / / / ^

Enter the string ( add $ to the end of the string ): (i*i)$

String is accepted