/*
   buildtree.cc -- illustrate how to build an abstract syntax tree while parsing

Author:  Larry Morell

Algorithm:

   The program parses according to the following grammar

PROGRAM        ::= <scanner-list> SCANNER-LIST </scanner-list>
SCANNER-LIST ::= SCANNER | SCANNER SCANNER-LIST
SCANNER  ::= <scanner> NAME ALPHABET STATES START FINAL-STATES TRANSITION-TABLE </scanner>
NAME         ::= <name>.1.</name>
ALPHABET     ::= <alphabet> .2. </alphabet>
STATES       ::= <states> STATE-LIST </states>
STATE-LIST   ::= STATE | STATE STATE-LIST
FINAL-STATES ::= <final-states> STATE-LIST </final-states>
STATE            ::= <state> .4. </state>
START        ::= <start> .4. </final>
TRANSITION-TABLE ::= <transition-table> TRANSITION-LIST </transition-table>
TRANSITION-LIST  ::= TRANSITION | TRANSITION TRANSITION-LIST
TRANSITION       ::= <transition> INPUT STATE NEXTSTATE </transition>
INPUT            ::= <input> .3. </input>
NEXTSTATE        ::= <nextstate> .4. </nextstate>

As recursive-descent parsing progresses, each parsing procedure builds a tree and
returns it to the the calling parsing procedure.  That procedure in turn combines 
the trees that have been returned to it into a larger tree and then returns that 
larger tree.  This process continues until a tree representing the entire input file
is produced. 

The tree produced is called an abstract syntax tree (AST), comprised of a root along with 
with child AST's.  The value stored in the root note of an AST indicates the structure
abstractly represented in the child AST's.  The trees are called abstract because they
do not represent every token in the input stream.  For example, tokens that can be inferred
from the description stored in the root are not represented.

An example:
TRANSITION      ::= <transition> INPUT STATE NEXTSTATE </transition> 
BinNode* parseTransition () {
   entering("parseTransition");
   verify (otagSym, "transition");  t.get();
   BinNode *root, *c1, *c2, *c3;
   c1=parseInput();
   c2=parseState();
   c3=parseNextState();
   c1->setRight(c2); 
   c2->setRight(c3);

   root = new BinNode("transition",c1,NULL);
   verify (ctagSym, "transition");  t.get();
   cout << "Transition tree:" << endl;
   printTree(root);

   leaving("parseTransition");
   return root;
}

This parsing routine has been instrumented to build an AST for transitions.
As can be seen from the grammar rule, a TRANSITION consists of three components:
an INPUT, a STATE, and a NEXTSTATE.   The AST built by this routine 
for the input:

<transition>
  <input>a</input>
  <state>777</state>
  <nextstate>333</nextstate>
</transition>

is the following general tree:

                transition
                    |
            ------------------
            |       |        |
            a      777      333


Note the absence of all tags from this tree; their reason for existence is to
assist in the parsing and they are not needed once parsing is completed.
The 'a', '777' and '333' AST trees are built by calls to parseInput, parseState,
and parseNextState, respectively.


This general tree is represented in the usual way using binary nodes:

root---->|-------------|
         | transition  |  info
         |-------------|
      l  |  o   |  ~   |  r
         |--|----------|
            |
            |
         |-------------|       |-------------|          |-------------| 
         |     a       |       |     777     |          |     333     |  
         |-------------|       |-------------|          |-------------|
         |  ~   |  o---|-----> |   ~  |  o---|--------->|   ~  |   ~  |
         |-------------|       |-------------|          |-------------|
            ^                      ^                        ^
            |                      |                        |
            |                      |                        |
            c1                     c2                       c3

c1 was built by the call to parseInput
c2 was built by the call to parseState
c3 was built by the call to parseNextState

Then, c1 was linked to c2 and c2 was linked to c3.
Last, the root node was built and c1 linked into it.

parseTransition then returns 'root', the pointer to the constructed tree,
as its value.
Revision history:
3/15/2006 -- First version, using binary nodes (BinNodes)
3/16/2006 -- Revised to use Nodes (as leaf nodes) and BinNodes

*/
using namespace std;
#include <iostream>
#include "Envs.h"
#include "Tokens.h"
#include "Basics.h"
#include "Nodes.h"

typedef IntSet TokenTypeSet; 

Token  t;   
IntSet  ES; // empty set

// check -- true iff the current token (t) is contained in the TokenTypeSet s
int check(TokenTypeSet s, string v)
{
   entering("check");
   //cout << "s=";s.displayln();
   //cout << "v="<<v << endl;
   //cout << s.contains(t.type()) << endl;
   //cout << t.val() << endl;
   leaving("check");
  return s.contains(t.type()) && t.val() == v;
}

// verify -- if current token (t) is in in the set TokenTypeSet s, 
//           then get the next token
//           else error message and halt the program
void verify(TokenTypeSet s, string v)
{
   TokenType c,d;
   entering("verify");
   //cout << "Verifying:"; s.displayln();
   if (check(s,v)){
   }
   else {
      cout << "Error: verify: looking for:";
      c = ctagSym; //  first in TokenType
      while (! s.contains(c))
            c =  succ(c);
      cout << tokenTypeStr(c) << endl;
      if (c != stuffSym) {  // loop for commas 
         c = succ(c);
         for ( d = c ; d != stuffSym; d=succ(d)) {
             if (s.contains(d))
               cout << "," << tokenTypeStr(c) 
                           << endl;
         }
         if (s.contains(stuffSym))
            cout << "," << tokenTypeStr(c) 
                        << endl;
      }
      cout << ", " << v << " ";
      cout << "found " ;
      t.displayln();
      exit(-1);
   }
   leaving("verify");
}


/* START        ::= <start> .4. </final> */
BinNode* parseStart() { //add tree building stuff
   entering("parseStart");
   verify (otagSym, "start");
   t.getStuff();
   BinNode *startX = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "start");
   t.get();
   leaving("parseStart");
   return startX;
}

/* NAME        ::= <name>.1.</name> */
BinNode* parseName() { //add tree building stuff
   entering("parseName");
   verify (otagSym, "name");
   t.getStuff();
   BinNode *nameX = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "name");
   t.get();
   leaving("parseName");
   return nameX;
}

/* ALPHABET    ::= <alphabet> .2. </alphabet> */
BinNode* parseAlphabet() {  //add tree building stuff
   entering("parseAlphabet");
   verify (otagSym, "alphabet");
   t.getStuff();
   BinNode *alphabetX = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "alphabet");
   t.get();
   leaving("parseAlphabet");
   return alphabetX;
}

/*  INPUT           ::= <input> .3. </input> */
BinNode* parseInput() {
   entering("parseInput");
   verify (otagSym, "input");
   t.getStuff();
   BinNode *root = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "input");
   t.get();
//   cout << "Input tree:" << endl;
//   printTree(root);
   leaving("parseInput");
   return root;
}
/* NEXTSTATE       ::= <nextstate> .4. </nextstate> */
BinNode* parseNextState() {
   entering("parseNextState");
   verify (otagSym, "nextstate");
   t.getStuff();
   BinNode *root = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "nextstate");
   t.get();

//   cout << "NextState tree:" << endl;
//   printTree(root);

   return root;
   leaving("parseNextState");
}

/* STATE           ::= <state> .4. </state> */
BinNode* parseState() {
   entering("parseState");
   verify (otagSym, "state");
   t.getStuff();
   BinNode *root = new BinNode(t.val(),NULL,NULL);
   t.get();
   verify (ctagSym, "state");
   t.get();

//   cout << "State tree:" << endl;
//   printTree(root);
   return root;
   leaving("parseState");
}

/* STATE-LIST   ::= STATE | STATE STATE-LIST */
BinNode* parseStateList() {
   entering("parseStateList");
   BinNode *tmp = parseState(); 
   if (check(otagSym,"state") )
   {
     BinNode *tmp2 = parseStateList();
     tmp->setRight(tmp2);
   }
   leaving("parseStateLists");
   return tmp;
}

/* STATES       ::= <states> STATE-LIST </states>  */
BinNode* parseStates() {
   entering("parseStates");
   verify (otagSym, "states");
   t.get();
     BinNode *s_list;
//     s_list->setRight(parseStateList()); 
     s_list = parseStateList();  
   verify (ctagSym, "states");
   t.get();
   leaving("parseStates");
   return s_list;
}


/* TRANSITION      ::= <transition> INPUT STATE NEXTSTATE </transition> */
BinNode* parseTransition () {
   entering("parseTransition");
   verify (otagSym, "transition");  t.get();
   BinNode *root, *c1, *c2, *c3;
   c1=parseInput();
   c2=parseState();
   c3=parseNextState();
   c1->setRight(c2); 
   c2->setRight(c3);

   root = new BinNode("transition",c1,NULL);
   verify (ctagSym, "transition");  t.get();
//   cout << "Transition tree:" << endl;
//   printTree(root);

   leaving("parseTransition");
   return root;
}

/* TRANSITION-LIST  ::= TRANSITION | TRANSITION TRANSITION-LIST */
BinNode* parseTransitionList () {
   entering("parseTransitionList");
   BinNode *root, *c1=NULL;
   root = parseTransition(); 
   if ( check(otagSym,"transition") )
     c1 = parseTransitionList();

   root->setRight(c1);
//   cout << "TransitionList tree:" << endl;
//   printTree(root);
   
   leaving("parseTransitionLists");
   return root;
}

//prototype parseScanner()
BinNode *parseScanner();

/* SCANNER-LIST ::= SCANNER | SCANNER SCANNER-LIST  */
BinNode* parseScannerList()
{
   entering("parseScannerList");
   BinNode *root, *c1=NULL;
   root = parseScanner();
   if ( check(otagSym,"scanner") )
     c1 = parseScannerList();

   root->setRight(c1);
//   cout << "ScannerList tree:" << endl;
//   printTree(root);
   leaving("parseScannerList");
   return root;
}

/*  PROGRAM        ::= <scanner-list> SCANNER-LIST </scanner-list> */
BinNode* parseProgram() 
{
  verify(otagSym, "scanner-list");
  t.get();
  BinNode *root = parseScannerList(); //point root to the total tree
  verify(ctagSym, "scanner-list");
  t.get();
  leaving("parseProgram");
  return root;
}


/* FINAL-STATES ::= <final-states> STATE-LIST </final-states>   */
BinNode* parseFinalStates()
{
   entering("parseFinalStates");
   verify (otagSym, "final-states");
   t.get();
   BinNode *finalX = parseStateList();

   verify (ctagSym, "final-states");
   t.get();
   leaving("parseFinalStates");
   return finalX;
}

/* TRANSITION-TABLE ::= <transition-table> TRANSITION-LIST </transition-table>  */
BinNode* parseTransitionTable()
{ 
  entering("parseTransitionList");
  verify(otagSym, "transition-table");
  t.get();
  
  BinNode *trans_t = parseTransitionList();
  
  verify(ctagSym, "transition-table");
  t.get();
  leaving("parseTransitionTable");
  return trans_t;
}

/* SCANNER  ::= <scanner> NAME ALPHABET STATES START FINAL-STATES TRANSITION-TABLE </scanner>  */
BinNode* parseScanner()
{ 
  entering("parseScanner");
  verify(otagSym, "scanner");
  t.get();
  
  BinNode *name = parseName(); //parseName()
  BinNode *alphabet = parseAlphabet();
  BinNode *states = parseStates();
  BinNode *start = parseStart();
  BinNode *final_states = parseFinalStates();
  BinNode *trans_table = parseTransitionTable();  
  
  BinNode *scanner_root = new BinNode(name->getInfo(),NULL,NULL);

  scanner_root->setLeft(alphabet); //set alphabet to left of root
  alphabet->setLeft(states);
  states->setLeft(start);
  start->setLeft(final_states);
  final_states->setLeft(trans_table);

  verify(ctagSym, "scanner");
  t.get(); 
  
  leaving("parseScanner");
  return scanner_root;
}

int main(int argc, char *argv[])
{
   BinNode *tree; 
   DEBUG=0;
   if (argc == 2) 
     setTokenSource(argv[1]); // set input to kbd
   else
     setTokenSource(""); // set input to kbd

   t.init(initSym);
   t.get();
   //cout << "first token:"; 
   //t.write(stdout);
   //parseNextState(); 
   //parseStateList();
   // parseInput();
   //tree = parseTransition();
   //tree = parseTransitionList();
   tree = parseProgram();
//   cout << "Final tree:" << endl;
//   printTree(tree); 
   return 0;
}