// Recursive descent parser, a la Pascal, for expressions.
// Uses tables for binary tree rep of parse.
// Looking at syntax diagrams for Pascal, Pascal-S, etc. are useful
// BPW, 9/2012

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Not much of a language, but representative of expression elements
// i identifier
// + additive operator
// * multiplicative operator
// < comparison
// & logical and
// | logical or
// ! logical not
// ( 
// )
char* alpha="i+*<&|!()";
int alphaSize;
char program[1000];
int programSize;

typedef enum {
  TERMINAL,SIMPLE,EXPR,TERM,FACTOR,IDENTIFIER,UNKNOWN
} langElement;

typedef struct
{
  langElement element;
  int firstChild,rightSib,parent;  // Multiway tree mapped to binary tree
} nodeType;
nodeType tree[2000];

int nextSymbol; // Simple scan
int nextNode;   // Simple allocation of nodes

// Needed due to recursion (& functions can't nest in C)
int expr(int);
int simple(int);
int term(int);
int factor(int);

int expr(int parent)
// An expression is one or two simple expressions connected by a comparison
{
int myNum=nextNode++,simp1,comparePos,simp2;

tree[myNum].element=EXPR;
tree[myNum].firstChild=simp1=simple(myNum);
// tree[myNum].rightSib is determined elsewhere
tree[myNum].parent=parent;
if (program[nextSymbol]=='<')
{
  comparePos=nextSymbol++;
  tree[simp1].rightSib=comparePos;
  tree[comparePos].element=TERMINAL;
  tree[comparePos].firstChild=(-1);
  tree[comparePos].rightSib=simp2=simple(myNum);
  tree[simp2].rightSib=(-1);
  tree[comparePos].parent=myNum;
}
else
  tree[simp1].rightSib=(-1);
return myNum;
}

int simple(int parent)
// A simple expression is one or more terms connected by additive operators
{
int myNum=nextNode++,term1,plusOrPos,term2;

tree[myNum].element=SIMPLE;
tree[myNum].firstChild=term1=term(myNum);
// tree[myNum].rightSib is determined elsewhere
tree[myNum].parent=parent;
while (program[nextSymbol]=='+' || program[nextSymbol]=='|')
{
  plusOrPos=nextSymbol++;
  tree[term1].rightSib=plusOrPos;
  tree[plusOrPos].element=TERMINAL;
  tree[plusOrPos].firstChild=(-1);
  tree[plusOrPos].rightSib=term2=term(myNum);
  tree[plusOrPos].parent=myNum;
  term1=term2;
}

tree[term1].rightSib=(-1);
return myNum;
}

int term(int parent)
// A term is one or more factors connected by multiplicative operators
{
int myNum=nextNode++,factor1,multAndPos,factor2;

tree[myNum].element=TERM;
tree[myNum].firstChild=factor1=factor(myNum);
// tree[myNum].rightSib is determined elsewhere
tree[myNum].parent=parent;
while (program[nextSymbol]=='*' || program[nextSymbol]=='&')
{
  multAndPos=nextSymbol++;
  tree[factor1].rightSib=multAndPos;
  tree[multAndPos].element=TERMINAL;
  tree[multAndPos].firstChild=(-1);
  tree[multAndPos].rightSib=factor2=factor(myNum);
  tree[multAndPos].parent=myNum;
  factor1=factor2;
}

tree[factor1].rightSib=(-1);
return myNum;
}

int factor(int parent)
{
int myNum=nextNode++,identifier1Pos,lparenPos,expr1,rparenPos,notPos,factor1;

tree[myNum].element=FACTOR;
switch (program[nextSymbol])
{
  case 'i':
    tree[myNum].firstChild=identifier1Pos=nextSymbol++;
    tree[identifier1Pos].element=IDENTIFIER;
    tree[identifier1Pos].firstChild=(-1);
    tree[identifier1Pos].rightSib=(-1);
    tree[identifier1Pos].parent=myNum;
    break;
  case '(': 
    tree[myNum].firstChild=lparenPos=nextSymbol++;
    tree[lparenPos].element=TERMINAL;
    tree[lparenPos].firstChild=(-1);
    tree[lparenPos].rightSib=expr1=expr(myNum);
    tree[lparenPos].parent=myNum;
    if (program[nextSymbol]!=')')
    {
      printf("parse error: ) expected, symbol %d is %c\n",
        nextSymbol,program[nextSymbol]);
      exit(0);
    }
    tree[expr1].rightSib=rparenPos=nextSymbol++;
    tree[rparenPos].element=TERMINAL;
    tree[rparenPos].firstChild=(-1);
    tree[rparenPos].rightSib=(-1);
    tree[rparenPos].parent=myNum;
    break;
  case '!':
    tree[myNum].firstChild=notPos=nextSymbol++;
    tree[notPos].element=TERMINAL;
    tree[notPos].firstChild=(-1);
    tree[notPos].rightSib=factor1=factor(myNum);
    tree[factor1].rightSib=(-1);
    tree[notPos].parent=myNum;
    break;
  default: 
    printf("parse error: i(! expected, symbol %d is %c\n",
      nextSymbol,program[nextSymbol]);
    exit(0);
}
// tree[myNum].rightSib is determined elsewhere
tree[myNum].parent=parent;

return myNum;
}

void verify(int x,int parent)
{
if (x==(-1))
  return;
if (x==999999)
{
  printf("Uninitialized link in node with parent %d\n",parent);
  return;
}
if (tree[x].element==UNKNOWN)
  printf("element UNKNOWN for node %d\n",x);
else if (x<programSize)
{
  if (program[x]=='i')
  {
    if (tree[x].element!=IDENTIFIER)
      printf("Node %d should be IDENTIFIER\n",x);
  }
  else if (tree[x].element!=TERMINAL)
    printf("Node %d should be TERMINAL\n",x);
}
else
{
  if (tree[x].element==TERMINAL)
    printf("Node %d should NOT be TERMINAL\n",x);
}
if (tree[x].parent!=parent)
  printf("node %d has parent %d, should be %d\n",x,tree[x].parent,parent);
verify(tree[x].firstChild,x);
verify(tree[x].rightSib,parent);
}

void treePrint(int x,int indent)
{
char str[7][20]={"TERMINAL","SIMPLE","EXPR","TERM","FACTOR",
            "IDENTIFIER","UNKNOWN"};
int i;

if (x==(-1))
  return;
for (i=0;i<2*indent;i++)
  printf(" ");
printf("%s ",str[tree[x].element]);
if (tree[x].element==IDENTIFIER || tree[x].element==TERMINAL)
  printf("%c",program[x]);
printf("\n");
treePrint(tree[x].firstChild,indent+1);
treePrint(tree[x].rightSib,indent);
}

main()
{
int i,j;
int root;

alphaSize=strlen(alpha);
scanf("%s",program);
programSize=strlen(program);
for (i=0;i<programSize;i++)
{
  for (j=0;j<alphaSize && program[i]!=alpha[j];j++)
    ;
  if (j==alphaSize)
  {
    printf("bonk on input %c\n",program[i]);
    exit(0);
  }
}

for (i=0;i<2*programSize;i++)
{
  tree[i].element=UNKNOWN;
  tree[i].firstChild=999999;
  tree[i].rightSib=999999;
  tree[i].parent=999999;
}

nextSymbol=0;
nextNode=programSize+1; // Nodes for terminals have same subscripts as program[]
root=expr(-1);
tree[root].rightSib=(-1);
if (nextSymbol<programSize)
  printf("%d unprocessed symbols\n",programSize-nextSymbol);
if (nextSymbol>programSize)
  printf("%d extra symbols processed during overrun!\n",nextSymbol-programSize);

verify(root,(-1));

treePrint(root,0);
}