parser.c

Trees are natural structures for representing certain kinds of hierarchical data. A (rooted) tree co

#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include "Tree.h"
#include "Parser.h"

Tree forked(TreeElementType, Tree, Tree); /* prototype */
Tree exp();                               /* prototype */


char word[11];  int len;  int ch;  int sy; /*parser state variables*/


void Error(char *msg) /* print error message and stop */
 { printf("Error: %s (word=%s)(ch=%c)\n", msg, word, ch);  exit(-1);
 }/*Error*/


void insymbol()  /* Simple Lexical Analyser Routine */
 { /* PRE: unprocessed = ?spaces? cde..., ch = first(unprocessed) */
   strncpy(word, "?", 10);
   while( ch==' ' ) ch=getchar();
   /* ch != ' ', ch = c, unprocessed = ch de... */
   len = 0;
   if( ch == '\n' )
      sy=eoExp;
   else
    { if( ch >= 'a' && ch <= 'z' ) /* alphanumeric */
       { while( ch >= 'a' && ch <= 'z' || ch >= '0' && ch <= '9' )
          { if(len < 10)
             { word[len] = ch; len++; word[len] = 0; }
            ch=getchar();
          }
         /* (ch < 'a' || ch > 'z') && (ch < '0' || ch > '9') */
         /* word[0..len-1] holds up to 10 leading alphanums of cde... */
         sy=ident;
       }
      else/* ch < 'a' || ch > 'z', i.e. not l.case letter */
       { word[0]=ch; word[1]=0; len=1;
         switch(ch)
          { case '+': sy=plusSy;  break;  case '-': sy=minusSy; break;
            case '*': sy=timesSy; break;  case '/': sy=overSy;  break;
            case '(': sy=openSy;  break;  case ')': sy=closeSy; break;
            default: Error("bad symbol");
          }/*switch*/
         ch=getchar();
         /* word[]=c0..., sy corresponds to word[0], */
         /* unprocessed=de..., ch=first(unprocessed) */
    }  }
 }/*insymbol*/


void check( int symbol, char *errMsg ) /* check and skip specified symbol */
 { if( sy == symbol ) insymbol(); else Error(errMsg); }


Tree sequence(Tree NonTerminal(void), int symbols)              /*L  C*/
/* Parse  <NonTerminal> [ symbols <NonTerminal> ]*                .  S*/
 { Tree T;  char operator[11];                                  /*A  S*/
   T = NonTerminal();                                           /*l  E*/
   while( sy & symbols ) /* i.e. sy in symbols */               /*l   */
    { strncpy(operator, word, 10);                              /*i  .*/
      insymbol();                                               /*s  a*/
      T = forked(operator, T, NonTerminal());/* left associative. o  u*/
    }                                                           /*n   */
   return T;
 }/*sequence*/


Tree factor()                 /* the expression parser proper starts here */
 { Tree oprnd;
   if( sy == ident )                           /* factor ::= identifier | */
    { oprnd = forked(word, (Tree)NULL, (Tree)NULL);
      insymbol();
      return oprnd;
    }
   else if( sy == openSy )                     /*            ( <exp> )    */
    { insymbol();
      oprnd = exp();
      check(closeSy, "missing )");
      return oprnd;
    }
   else Error("bad factor (operand)");
 }/*factor*/


Tree term() { return sequence(factor, timesSy | overSy); }

Tree exp()  { return sequence(term, plusSy | minusSy); }


Tree parse()
 { Tree T;
   strncpy(word, "?", 10); len=0; ch=' '; insymbol(); /* initialise state */

   T = exp();

   check(eoExp, "incomplete");
   return T;
 }/*parse*/

/* Simple Expression Parser */