/*parser.c - recursive-descent parser for arithmetic expressions*/

/*There is, in general, one parsing function for each nonterminal symbol in the
  grammar.  Refer to the grammar (or syntax chart) to understand how these
  routines interact with each other.  Some regions of the code are commented
  very lightly, because their structure and function follow from the grammar.
 -There are two important and related invariant conditions over all these
  parsing functions.  On entry, the first token in the phrase about to be
  parsed is in 'token'.  On exit, the token immediately following the
  last token in the expression just parsed is in 'token' (except in the
  case of parse_program, where, if all is well, there is nothing following the
  '.').  To maintain these invariants, it is necessary to keep track of tokens
  that delimit expressions and to eat them where appropriate.
 -In other words, each parsing function assumes that the input stream of tokens
  has been prepared for it, and it in turn prepares the input stream for
  whatever parsing function may be called next.*/

#include "scanner.h"
#include "parser.h"

/*WHICH STANDARD HEADER FILES DO YOU NEED TO INCLUDE HERE?*/

/*Build an internal tree node, which contains an operator and points to two
  subtrees.*/
static Tree *NewTree(op, left, right)
Token op;
Tree *left, *right;
  {

/*USE MALLOC TO ALLOCATE A NEW TREE NODE, AND FILL ITS FIELDS WITH THE GIVEN
  OPERATOR AND SUBTREE POINTERS.  (USE THE MACROS DEFINED IN parser.h.)*/

  }

/*Build a new leaf, which contains an operator of NumberToken, and a number.*/
static Tree *NewLeaf(value)
int value;
  {

/*USE MALLOC TO ALLOCATE A NEW TREE NODE, GIVE IT AN OPERATOR OF NumberToken,
  AND FILL ITS VALUE FIELD WITH THE GIVEN VALUE.  (USE THE MACROS DEFINED IN
  parser.h.)*/

  }

static Tree *parse_leaf()
  {
  Tree *ptr;
  ptr = NewLeaf(number);
  next_token();
  return(ptr);
  }

static Tree *parse_arith_expr();	/*forward declaration*/

static Tree *parse_factor()
  {
/*WE'LL GIVE YOU THIS ONE :-)*/
  Tree *factor;
  if(token == LeftParenToken)
    {
    next_token();			/*eat the '('*/
    factor = parse_arith_expr();
    if(token != RightParenToken)
      {
      printf("expected \")\" in factor, found ");
      print_token(token);
      printf("\n");
      exit(1);
      }
    next_token();			/*eat the ')'*/
    return(factor);
    }
  else if(token == NumberToken)
    return(parse_leaf());
  else
    {
    printf("unexpected factor ");
    print_token(token);
    printf("\n");
    exit(1);
    }
  }

static Tree *parse_term()
  {
  Tree *left_tree, *tree;
  left_tree = parse_factor();
/*invariant: 'left_tree' points to the root of a parse tree that represents all  the tokens in the expression that are to the left of 'token'.*/
/*bound: the number of expressions that remain to be parsed*/
  while((token == TimesToken) || (token == DivideToken))
    {

/*CREATE A NEW TREE NODE CONTAINING THE CURRENT TOKEN AT ITS ROOT, left_tree ON
  ITS LEFT, AND THE RESULT OF parse_factor() ON ITS RIGHT.  MAKE THIS NEW NODE
  THE NEW VALUE OF left_tree.*/

    }
  return(left_tree);
  }

static Tree *parse_arith_expr()
  {

/*THIS IS JUST LIKE parse_term() ABOVE, EXCEPT WITH TERMS INSTEAD OF FACTORS,
  AND PlusToken AND MinusToken INSTEAD OF TimesToken AND DivideToken.  IN FACT,
  WITH A LITTLE WORK YOU CAN WRITE A SINGLE, PARAMETRISED FUNCTION THAT DOES
  THE WORK OF parse_term() AND parse_arith_expr().  THE PROTOTYPE FOR THAT
  FUNCTION WOULD BE SOMETHING LIKE THIS:
  static Tree *parse_expressions(Tree *(*parsing_fn)(), Token op0, Token op1);
  (FOR NOW, WRITE IT THE MORE OBVIOUS WAY.  YOU CAN COME BACK AND DO IT THE
  COOL WAY AFTER WE TALK ABOUT POINTERS TO FUNCTIONS.)*/

  }

/*This is the top-level parsing function.*/
Tree *parse_expr()
  {
  Tree *expr;
  init_scanner();
  next_token();
  expr = parse_arith_expr();
  if(token != PeriodToken)
    {
    printf("unexpected token at end of input: ");
    print_token(token);
    printf("\n");
    exit(1);
    }
  return(expr);
  }

/*print an indented subtree - used by print_tree() below*/
static void print_subtree(t, indent)
Tree *t;
int indent;
  {
  register int spaces;
/*invariant: all nodes to the left of 't' have been printed*/
  while(TreeOper(t) != NumberToken)
    {
    for(spaces = 0; spaces != indent; spaces++)
      putchar(' ');
    print_token(TreeOper(t));
    putchar('\n');
    print_subtree(TreeLeft(t), 2+indent);
    indent += 2;
    t = TreeRight(t);
    }
  for(spaces = 0; spaces != indent; spaces++)
    putchar(' ');
  printf("%d\n", TreeValue(t));
  }

/*print the contents of a tree - useful for debugging*/
void print_tree(t)
Tree *t;
  {
  print_subtree(t, 0);
  }

/*ONCE YOU'RE DONE WITH THIS PROGRAM, GET parser.h AND testparse.c, AND
  COMPILE THEM AND LINK THEM ALL TOGETHER WITH YOUR SCANNER LIKE THIS:
  cc -g -o testparse testparse.c scanner.c parser.c
*/