/*
   transtree.cc -- illustrate how to translate an AST into C code

Author:  Larry Morell

Algorithm:

   The program checks the semantic requirements (represented by .N. ) of 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>

Check for:
# An FA name that contains a non-letter.
# A state that is not a number.
# A state number that is not in the list of states.
# An input character that is not in the alphabet. 

Then translate the checked tree into C++;
Strategy for checking:

Create a procedure for major subtrees in the tree 
Each such procedure does one or more of the following analyses:
o Retrieves values from the subtree to support later processing
o Check values in the subtree for consistency with previously
  stored values.
o Call other checking procedures to check the components of
  the subtree.
For example:

The tree submitted as the parameter might look like:

               n -->states
                      |
         --------------------------
         |    |    |    |    |    |
         1    2    3    4    5    6

1 is linked to 2, which is linked to 3, ...  via right pointers


bool checkStates (BinNode *n) {
   BinNode *stateptr = left(n);
   while  (stateptr != NULL) {
      string info = stateptr->getInfo();
      state[statemax] = info;
      for (int i=0; i < info.length(); i++) {
         char ch = info[i];
         if (ch < '0' || ch > '9') {
            cout << "State " << info 
                 << " is not a number in scanner " 
                 << name
                 << endl;
            i= info.length();
         }
      }
      statemax = statemax + 1;
      stateptr = right(stateptr);
   }
}

This procedure is passed a root of a subtree in which the 
first-tier nodes represent the states of a scanner.  

o getInfo() -- retrieves the value of a node ("1", "2" ...)
o states[]  -- is a global array of state names being saved for
               future use in, say, `checkState()'
o statemax  -- is a global int, and holds the number of elements
  of state[].
o left(n)   -- is a macro call equal to (BinNode *)n->getLeft()
o right(n)  -- is a macro call equal to (BinNode *)n->getRight()
 

stateptr is anchored at the head of the list of states,
each node of which is linked to the next via its right pointer.
Traversing this list enables checking to ensure that each
string in the list encodes a number (i.e. consists of all
digits).  An error message is written is a state contains
a non-digit.  The variable `name' is a global string that
holds the name of the scanner, which should be filled in
when executing `checkName()'.

Strategy for translating:

Pretty much the same at the strategy for checking.  Write a set of 
recursive procedures for traversing the tree.  Only this time as
the tree is traversed, output appropriate C++ code, filled in from 
the current node.

For example, consider transTransition():


void transTransition (BinNode *n) {
   BinNode * input = left(n),
           * state = right(input),
           * nextstate = right(state);
   cout << "   if (ch == '"
        << input->getInfo()
        << "') state = " 
        << nextstate->getInfo() 
        << ";" 
        << endl; 
}

This routine names the three components of a transition, and
then prints out the statement:

   if (ch == 'a') state = 3;  

where the "a" and the "3" are filled in from the transition subtree.

As a more complicated example, consider transTransitionList():

void transTransitionList (BinNode *n) {
   BinNode *t ;
   // Process each state
   cout << "char alphabet[] = \"" << alphabet << "\"\n"; 
   cout << "string name=\"" << name << "\"\n";   
   cout << "int state = 0;\n";
   cout << "char ch ;\n" ;
   cout << "int length = s.length();\n" ;
   cout << "Token t;\n";
   cout << "t.setType(\"\");\n";
   cout << "t.setVal(\"\"); \n";
   cout << "int pos = 0;\n";
   cout << "while (pos < length && (index(alphabet,ch=s[pos]) >= 0 )  ){ \n";

   cout << "   switch(state) {\n ";
   for (int i=0; i <statemax; i++ ) {  // for each state
      cout << "   case " << state[i] << ":" << endl;
      t = n;
      while (t != NULL) {  // for every transition
         if (right(left(t))->getInfo() == state[i]  ) {  // state matches transition
             transTransition(t);
         }
         t = right(t);
      }
   }
}

This code puts out a block of code that looks like this:

char alphabet[] = "ab";         #from transTransitionList
string name="ScannerOne";       # "     "
int state = 0;                  # "     "
char ch ;                       # "     "
int length = s.length();        # "     "
Token t;                        # "     "
t.setType("");                  # "     "
t.setVal("");                   # "     "
int pos = 0;                    # "     "
while (pos < length && (index(alphabet,ch=s[pos]) >= 0 )  ){ # from transTransitionList
   switch(state) {                 # from transTransitionList
   case 1:                         # from transTransitionList
      if (ch == 'a') state = 12;       # from transTransition
      if (ch == 'b') state = 22;       # from transTransition
   case 2:                         # from transTransitionList
      if (ch == 'c') state = 32;       # from transTransition
   case 3:                         # from transTransitionList

Clearly, this is beginning to look like a generated scanner.

See http://boole.cs.atu.edu/~morell/classes/4163/code/fatrans/match.cc
for an example of what the complete output could look like, provided
FA's are implemented via loop and switch.

Revision history:
3/22/2006 -- First version to illustrate checking some characteristics of TransitionLists
 either:
3/28/2006 -- Extended the checktree version to include some translation routines
*/
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",NULL,c1);
   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->setLeft(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;
}




#define right(n) ((BinNode *) n->getRight())
#define left(n) ((BinNode *) n->getLeft())
string start;
string alphabet = "ab";
string name = "ScannerOne";  // Simulated scanner name
string state[100] = {};//"1", "2", "3"};   // simulate 3 states
int statemax = 0;  //simulate 3 states

bool checkStart(BinNode *n) {}
bool checkName(BinNode *n) {
   string nm = n->getInfo();
   //cout << "Check Name  ->" << nm << "<-" << endl;
   for (int i = 0; i < nm.length(); i++) 
   {
     char ch = nm[i];
     if ( !((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z' ))) 
     { // illegal character
          cout << "Name " << nm << " contains a non-letter:'" << ch << "'"<< endl;
     }
   }
   name = nm;
}

bool checkAlphabet(BinNode *n) {
   entering("checkAlphabet");
   alphabet = n->getInfo();
}

//WRITE ME
bool checkInput(BinNode *n) 
{ //edited 2006.04.02
  //Check that the input adheres to the grammar
   string tmp = n->getInfo();
   for (int i = 0; i < tmp.length(); i++) 
   {
     char ch = tmp[i];
     if ( !((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z' )) ) 
     { // illegal character
        cout << "Input " << tmp <<  " contains a non-letter:'" << ch << "'"<< endl;
      }
   }
}

bool checkNextState(BinNode *n) 
{  //edited 2006.04.02
   string tmp = n->getInfo();
   for (int i = 0; i < name.length(); i++)
   {
       char ch = tmp[i];
       if ( !((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z' )))
      { // illegal character
          cout << "Input " << tmp
               << " contains a non-letter:'" << ch << "'"<< endl;
       }
   }
}

bool checkState(BinNode *n) {
   string st = n->getInfo();
   int i = 0;
   // cout << "Checking: \n" << endl;
   // printTree(n);
   while (i < statemax && state[i] != st ) {
      // cout << "Comparing " << st << " with " << state[i] << endl;
      i++;
   }
   if ( i >= statemax) { // not found
       cout << "State \"" << st << '"' << " not in state list: " ;
       for (int i=0; i < statemax; i++) {
           cout << state[i]  << " " ;
       }
       cout << " in scanner " << name<< endl;
   }

}

bool checkStateList(BinNode *n) 
{ //edited 2006.04.02
    entering("checkStateList");
    checkState(n);
    if (check(otagSym,"state") )
       checkStateList(n);
    leaving("checkStateLists");

}

bool checkStates (BinNode *n) {
   BinNode *stateptr = n; //left(n);
statemax = 0;
   while  (stateptr != NULL) 
  {
      string info = stateptr->getInfo();
      state[statemax] = info;
      for (int i=0; i < info.length(); i++) {
         char ch = info[i];
         if (ch < '0' || ch > '9') {
            cout << "State " << info 
                 << " is not a number in scanner " 
                 << name
                 << endl;
            i= info.length();
         }
      }
      statemax = statemax + 1;
      stateptr = right(stateptr);
   }
}

bool checkTransition (BinNode *n) {
   entering("checkTransition");
//   BinNode *tmp  = right(n); //check tree format
//   cout << "Printing Tree starting @ transition: " << endl;
//   printTree(n);
//   cout << "node = " << n->getInfo() << endl;
   BinNode *input,
           *state,
           *nextstate;
   input = right(n);
   checkInput(input);
   state  = right(input);
   checkState(state);
   nextstate = right(state);
   checkState(nextstate);
   leaving("checkTransition");
}

bool checkTransitionList (BinNode *n) {
  entering("checkTransitionList");
  BinNode *t = n;
   while (t != NULL) {
      checkTransition (t); 
      t = left(t);
   }
}


bool checkTransitionTable (BinNode *n) 
{ //edited 2006.04.02
  entering("checkTransitionTable");
  checkTransitionList(n);
  leaving("checkTransitionTable");
}

bool checkFinalStates (BinNode *n) 
{ //edited 2006.04.02
  entering("checkFinalStates");
  checkStateList(n);
  leaving("checkFinalStates");
}

bool checkScanner (BinNode *n) {
   entering("checkScanner");
//   n = left(n); 
   BinNode *name, 
           *alphabet, 
           *states, 
           *start, 
           *finals,
           *transitions; 
   name = n;
   alphabet = left(name);
   states = left(alphabet);
   start = left(states);
   finals = left(start);
   transitions = left(finals);
   checkName(name);
   checkAlphabet(alphabet);
   checkStates(states);
   checkStart(start);
   checkFinalStates(finals);
   checkTransitionList(transitions);
}

bool checkScannerList (BinNode *n) {
   entering("checkScannerList");
   BinNode *t = n;
   while (t != NULL) {
      checkScanner (t);
      t = right(t);
   }
}

bool checkProgram (BinNode *n){
  entering("checkProgram");
  return checkScannerList(n); //checkScannerList(left(n))  originally
}


// Translation routines

void transStart(BinNode *n) 
{
   cout << "int state = " <<  n->getInfo() << ";\n";
}

void transName(BinNode *n) 
{
  cout << "string name = \"" << n->getInfo() << "\";\n";
}

void transAlphabet(BinNode *n) 
{
  cout << "char alphabet[] = \"" << n->getInfo() << "\";\n";
}

void transInput(BinNode *n) 
{
  cout << "string input = \"" << n->getInfo() << "\";\n";
}

void transNextState(BinNode *n) 
{

}

void transState(BinNode *n) 
{

}

void transStateList(BinNode *n) {}
void transStates (BinNode *n) 
{
  transStateList(n);
}

void transTransition (BinNode *n) {
   BinNode * input = right(n),
           * state = right(input),
           * nextstate = right(state);
   cout << "        if (ch == '"
        << input->getInfo()
        << "') state = " 
        << nextstate->getInfo() 
        << ";" 
        << endl; 
}

void transTransitionList (BinNode *n) {
   BinNode *t ;
   // Process each state
   cout << "    char alphabet[] = \"" << alphabet << "\";\n"; 
   cout << "    string name=\"" << name << "\";\n";   
   cout << "    int state = 0;\n";
   cout << "    char ch ;\n" ;
   cout << "    int length = s.length();\n" ;
   cout << "    Token t;\n";
   cout << "    t.setType(\"\");\n";
   cout << "    t.setVal(\"\"); \n";
   cout << "    int pos = 0;\n";
   cout << "    while (pos < length && (index(alphabet,ch=s[pos]) >= 0 )  ){ \n";

   cout << "      switch(state) {\n ";
   for (int i=0; i <statemax; i++ ) {  // for each state build cases inside switch
      cout << "       case " << state[i] << ":" << endl;
      t = n;
      while (t != NULL) 
      {  // for every transition
         if(right(right(t))->getInfo() == state[i]) 
         {  // state matches transition
             transTransition(t);
         }
         t = left(t); 
      }
      cout << "       break;\n";
   }
  cout << "     } //close switch \n"; //close SWITCH
  cout << "     pos++; //increment position \n"; //increment position
  cout << "   } //close while \n\n"; //close WHILE
}
void transTransitionTable (BinNode *n) 
{
  transTransitionList(n);
}

void transFinalStates (BinNode *n) 
{
  BinNode *f_state = n;//right(n);
  bool first_loop = true;
  
  cout << "   if(state == " << f_state->getInfo() << ") { //final state checkers \n";
  cout << "      t.setType(name);\n";
  cout << "      t.setVal(s.substr(0,pos));\n";
  cout << "      s = s.substr(pos);\n";
  cout << "   }\n";
  
  while(right(f_state) != NULL)
  {
    cout << "   else if(state == " << f_state->getInfo() << ") { //final state checkers \n";
    cout << "      t.setType(name);\n";
    cout << "      t.setVal(s.substr(0,pos));\n";
    cout << "      s = s.substr(pos);\n";
    cout << "   }\n";

    first_loop = false;
    f_state = right(f_state);
  }
}


void transScanner (BinNode *n) 
{
  BinNode * nameptr = n, //left(n),
           * alphabetptr = left(nameptr),
           * statesptr = left(alphabetptr),
           * startptr = left(statesptr),
           * finalstatesptr = left(startptr),
           * transitionsptr = left(finalstatesptr);
   name = nameptr -> getInfo();
   alphabet = alphabetptr -> getInfo();
   start = startptr -> getInfo();
  
//i added this junk
  cout << "Token " << name << "(string &s) {\n";
  cout << "   cout << \"Matching \\\"\" << s << \"\\\" in " << name << "\";\n";
/*  transAlphabet(alphabetptr);
  transName(nameptr);
  transStart(startptr);
  cout << "char ch;\n";
  cout << "int length = s.length();\n";
  cout << "Token t;\n";
  cout << "t.setType("");\n t.setVal("");\n";
  cout << "int pos = 0;\n";*/
  transTransitionList(transitionsptr);
  transFinalStates(finalstatesptr);
  cout << "   return t;\n";
  cout << "}\n\n";
}
void transScannerList (BinNode *n) 
{
   BinNode *t = n;
   while (t != NULL) 
  {
      transScanner(t);
      t = right(t);
  }

   //Add main here
  cout << "int main() {\n";
  cout << "   string input = \"\";\n";
  cout << "   string line;\n\n";
  cout << "   while (getline(cin,line)) {\n";
  cout << "      input = input + line + \"\\n\";\n";
  cout << "   };\n";
  cout << "   cout << \"Processing input \" << input << endl;\n\n";
  cout << "   Token t;\n";
  cout << "   bool done = false;\n";
  cout << "   while (!done && input != \"\") {\n";
  cout << "      done = true;\n";

  BinNode *tmp = n;
    name = tmp->getInfo();
   //do the following for each scanner 
  cout << "      t = " << name << "(input);\n";
  cout << "      if (t.getType() != \"\")  {\n";
  cout << "         done = false;\n";
  cout << "         cout << \"Found token:\";\n";
  cout << "         cout << t.toString() << endl;\n";
  cout << "         cout << \"Remaining string is \\\"\" << input << \'\\\"';\n";
  cout << "         continue;\n";
  cout << "      }\n\n";
   
   while(right(tmp) != NULL)
   {
    tmp = right(tmp);
    name = tmp->getInfo();
    cout << "      t = " << name << "(input);\n";
    cout << "      if (t.getType() != \"\")  {\n";
    cout << "         done = false;\n";
    cout << "         cout << \"Found token:\";\n";
    cout << "         cout << t.toString() << endl;\n";
    cout << "         cout << \"Remaining string is \\\"\" << input << \'\\\"';\n";
    cout << "         continue;\n";
    cout << "      }\n\n";
    }
  cout << "   } // close while \n\n";
  cout << "   return 0;\n";
  cout << "}\n"; 
  /*
   BinNode *tmp = n;
   name = tmp->getInfo();
         
   cout << "Token match(string &s){\n";
   cout << "  Token tok;\n";
   cout << "  tok.setType(\"ErrorToken\");\n";
   cout << "  tok.setVal(\"\");\n";
   cout << "  tok = " << name << "(s);\n";
   cout << "  if(tok.getVal() != \"\"){\n";
   cout << "    cout << \"Match Found in " << name << "\";\n";
   cout << "    return tok;\n";
   cout << "  }\n";
   while(right(tmp) != NULL)
   {
      tmp = right(tmp);
      name = tmp->getInfo();
      cout << "  tok = " << name << "(s);\n";
      cout << "  if(tok.getVal() != \"\"){\n";
      cout << "    cout << \"Match Found in " << name << "\";\n";
      cout << "    return tok;\n";
      cout << "  }\n";
   }
  cout << "    return tok;\n"; 
  cout << "}\n"; */
}


void transProgram (BinNode *n)
{
  //output header stuff & token class
  cout << "using namespace std;\n#include <iostream>\n#include <string>\n\nusing namespace std;\nclass Token {\n";
   cout << "   private:\n";
   cout << "      string type;\n";
   cout << "      string val;\n";
   cout << "   public:\n";
   cout << "      string getType() {return type;}\n";
   cout << "      string getVal() {return val;}\n";
   cout << "      void setType(string t) {type = t;}\n";
   cout << "      void setVal(string v) {val = v;}\n";
   cout << "      string toString () { return \"[\" + type + \",\" + val + \"]\"; }\n";
   cout << "}; //End of Token Class\n\n\n";
         
  // output index function
   cout << "int index(char s[], char ch) {\n";
   cout << "  int i=0;\n";
   cout << "  int len = strlen(s);\n";
   cout << "  int ans = -1;\n";
   cout << "  while (i < len && ch != s[i]) i++;\n";
   cout << "  if (i < len) ans = i;\n";
   cout << "  // cout << \"Returning ans= \" << ans << endl;\n";
   cout << "  return ans;\n";
   cout << "} \n\n";
  
  transScannerList(n);

}

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.displayln();
   //tree = parseStates();
   //parseNextState(); 
   //parseStateList();
   // parseInput();
   // tree = parseTransition();

   // tree = parseTransitionList();
   // tree = parseFinalStates();
   //tree = parseScanner();
   // tree = parseScannerList();
   tree = parseProgram();
   // cout << "Final tree:" << endl;
   // printTree(tree); 
   // The tree has now been built ... let's check it to make sure it is valid
   checkProgram(tree);
   
   // printTree(tree);
   // checkTransitionList(tree);
   transProgram(tree);
   return 0;
}