// npda.cpp  simulate a Nondeterministic Push Down Automata, NPDA
//
// A NPDA  M = (Q, Sigma, Gamma, delta, q0, Z0, F)
//   where Q is finite set of states including q0
//         Sigma is a finite set of input symbols
//         Gamma is a finite set of stack symbols including Z0
//         delta is a set of nondeterministic transitions mapping
//               Q X (Sigma union epsilon) X Gamma to { (Q X Gamma Star), ...}
//         q0 is the initial state
//         Z0 is the initial symbol on the stack
//         F is a finite set of final states (possibly empty)
//           
// Input Conventions:
//
// the file name extension is typically  .npda
// free form plain text input file
// typical execution is  npda < your_input.npda > your_output.out
//
// A comment line has "// " as the first three characters
// A line may end with a comment using whitespace "//"
// Anything after whitespace after last expected input is a comment
//
// There are only a few keywords:
//                 start, stack, final, halt, trace, limit, enddef and tape
// any line not starting with these keywords is a delta transition
// only raw input strings may follow  'enddef'
//
// there is no such thing as a continuation line
//
// A transition is a five tuple:
// from-state  input-symbol  top-of-stack  to-state  write-to-stack
//
// at least one transition is required
//
// special input-symbol #b for the blank character,
//                      #e for epsilon transition
//
// special write-to-stack  #e for no character to write
//
//
// Anything after the required field(s) is a comment
//
// if write-to-stack is "// "  then the rest of the line
// is a comment and write-to-stack becomes #e
//
// The input tape may contain only printable characters
// Use  #b  to input a blank (space) character on the input tape
//
// Method: accumulate states, do consistency checking
//         accumulate symbols, input, 
//                             note any strangeness
//         build transition map (note: no duplicates and no #e means
//         deterministic)
//         initialize stack
//         run from start-state
//         trace as user requests
//         accept or reject (also halt feature)
//
// This is one of a series of automata simulators
// dfa  deterministic finite automata (with epsilon transitions and halt)
// nfa  nondeterministic finite automata
// tm   Turing machine, deterministic (recognizer and function computation)
// ntm  nondeterministic Turing machine (language recognizer only)
//
// compile with  GNU g++  2.8.1 or later    or   Microsoft 6.0 or later
//               g++ -o npda npda.cpp       or   cl /GX /ML npda.cpp
// ANSI/ISO C++
// release JSS 3/23/01 v0.8

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <stack>

using namespace std;

static char no_write  = '\0';    // unprintable, do not write
static char epsilon   = '\0';    // unprintable, #e epsilon

class transition  // 'delta' is the set of these transitions
{
  public:
    transition(string from_state,
               char   input_symbol,
               string top_stack,
               string to_state,
               string write_stack)
               {from=from_state;
                input=input_symbol;
                top=top_stack;
                to=to_state;
                write=write_stack;}
    static bool smaller(transition a, transition b)
                   { if(a.from<b.from) return true;
                     else if(a.from>b.from) return false;
                     else if(a.input<b.input) return true;
		     else if(a.input>b.input) return false;
                     else return a.top<b.top; }
    friend ostream &operator<<(ostream &stream, transition trans);
    string from;
    char   input;
    string top;
    string to;
    string write;
};

typedef stack<string, vector<string> > stack_t;

// a queued nondeterministic transition, along some path
class nd_tran
{
  public:
    nd_tran(){state = ""; /* pstack.clear();*/ } 
    nd_tran(string s, stack_t p)
           {state = s; pstack = p;}
    string  state;
    stack_t pstack;
};

int main() //  npda < input-file > output-file
{
  // primary objects
  set<string>  states;         // Q =all named states
  set<string>  from_states;    // source states for checking
  set<string>  to_states;      // target states for checking
  string       start="";       // q0 = staring state
  string       istack="";      // Z0 = initial stack
  set<string>  final;          // F = set of final states
  set<string>  symbols;        // Gamma set of stack symbols
  set<string>  from_symbols;   // Gamma set of stack symbols
  set<string>  trace;          // set of states to trace 
  vector<char> tape;           // input tape
  int tape_position=0;         // input tape position
  vector<transition> t_table;  // delta transitions
  typedef pair<string, int> c_index; // to make t_index
  typedef multimap<string, int, less<string> > t_map;
  t_map t_index;               // t_table index
  deque<nd_tran> tran_que;     // transition queue
  nd_tran nd_object;           // a popped state, stack
  pair<t_map::iterator, t_map::iterator> p_pair; // for t_index
  stack_t pstack;              // working stack
  
  // primary iterators
  vector<transition>::const_iterator x;      // for t_table
  int tx;                                    // for t_table
  t_map::iterator pt;                        // for t_index
  set<string>::const_iterator        iter;   // for sets
  set<string>::const_iterator        iter2;  // for sets
  vector<char>::iterator             it;     // for tape
  string::iterator                   its;    // for string
  
  // control variables
  int limit = 10000;        // max number of transitions (user settable)
  int step;                 // transition step
  bool halted = false;      // can not simulate more, halted
  bool halt_mode = false;   // stop upon any 'final' state
  bool accepted = false;    // reached a final state and input right-end
  bool no_simulate = false; // set true by various errors
  string state;             // present state
  char input_char = ' ';    // input tape character read
  string next_state;        // transition to next state
  char write_char;          // '\0' means no write
  int i;                    // loop index
  string prev_from = " ";   // for detecting nondeterministic
  char prev_input = ' ';    // for detecting nondeterministic
  bool have_enddef = false; // may have to read "tape"
  bool nondeterministic = false; // use the pda simulator (some day)
  bool debug = false;       // for development debugging
  
  // input variables
  string keyword;          // for inputting candidate keyword
  string from_state;       // for inputting one from state
  string input_symbol;     // character extracted later
  string top_stack;        // for inputting one top-stack
  string to_state;         // for inputting one to-state
  string write_stack ;     // for inputting one write_stack
  string final_state;      // for inputting one final or halt state
  string trace_state;      // for inputting one trace state
  string initial_tape="";  // check for #b (may read more than 1)
  string check;            // check for // that ends data on a line
  string input_str;        // temp string
  string write_str;        // temp string for #e, no write

  // keywords and special symbols
  string key_start = "start";  // followed by initial state q0
  string key_stack = "stack";  // followed by initial stack Z0
  string key_tape  = "tape";   // followed by a string, may have #b
  string key_final = "final";  // followed by a final state name
  string key_halt  = "halt";   // followed by a final state name, halt mode
  string key_trace = "trace";  // followed by "all" or a state
  string key_limit = "limit";  // followed by an integer
  string key_sigma = "sigma";  // followed by a state (unused input)
  string key_gamma = "gamma";  // followed by a stack symbol (unused input)
  string key_enddef= "enddef"; // only a "tape" may follow this
  string comm      = "//";     // start comment
  string empty     = "";       // empty string

  cout << "npda v0.8 starting" << endl;

  while(!cin.eof()) // main input loop
  {
    cin >> keyword;
    if(cin.eof()) break;
    if(keyword==key_start)
    {
      if(start!=empty) cout << "Over writing a previous start state."
                            << endl;
      cin >> start;
      states.insert(start);
      if(start=="//") cout << "start looks like a comment?" << endl;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_stack)
    {
      if(istack!=empty) cout << "Over writing a previous initial stack."
                            << endl;
      cin >> istack;
      symbols.insert(istack);
      if(istack=="//") cout << "stack looks like a comment?" << endl;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_tape)
    {
      cin >> initial_tape;
      if(initial_tape=="//") initial_tape="";
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_final)
    {
      cin >> final_state;
      final.insert(final_state);
      if(final_state=="//") cout << "final looks like a comment?" << endl;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_halt)
    {
      halt_mode = true; // halt upon entering any final state
      cin >> final_state;
      if(final_state!=comm && final_state!=empty)
      {  // allow stand alone "halt" just to set flag
        final.insert(final_state);
      }
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_trace)
    {
      cin >> trace_state;
      trace.insert(trace_state);
      if(trace_state=="//") cout << "trace state looks like a comment?" << endl;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_limit)
    {
      cin >> limit;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_sigma)
    {
      cin >> input_str; // ignored
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_gamma)
    {
      cin >> input_str; // ignored
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_enddef) // stop inputting
    {                            // now may only read "tape"
      cin.ignore(255,'\n');
      have_enddef = true;
      break;
    }
    else if(keyword=="//") // skip comment "// "
    {
      cin.ignore(255,'\n');
      continue;
    }
    else
    {
      from_state = keyword;
      states.insert(from_state);
      from_states.insert(from_state);
    }
    cin >> input_symbol; if(cin.eof()) break;
    if(input_symbol=="#b") input_symbol[0]=' ';        // a space
    if(input_symbol=="#e") input_symbol[0]=epsilon; // epsilon
    cin >> top_stack;     if(cin.eof()) break;
    symbols.insert(top_stack);
    from_symbols.insert(top_stack);
    cin >> to_state;     if(cin.eof()) break;
    states.insert(to_state);
    to_states.insert(to_state);
    write_stack=string(1, no_write);
    cin >> check;   if(cin.eof()) break;
    if(check!=comm)
    {
      write_stack=check;
      if(write_stack=="#b") write_stack[0]=' ';      // blank
      if(write_stack=="#e") write_stack[0]=no_write; // no write
    }
    cin.ignore(255,'\n'); // delete trailing comments
    t_table.push_back(transition(from_state, input_symbol[0], top_stack,
                                 to_state, write_stack));
    
  } // end main input loop

  cout << "reading input finished." << endl;

  // print primary data objects, check for errors and warnings
  if(states.size()==0)
  {
    cout << "No states input prevent simulation. Stopping." << endl;
    return 1;
  }

  cout << "start state " << start << endl;

  cout << "states:";
  for(iter=states.begin(); iter!=states.end(); iter++) cout << *iter << " ";
  cout << endl;

  iter = from_states.find(start); // check that start is a legal state
  if(iter==states.end())
  {
    cout << start << " is not a legal starting state." << endl;
    no_simulate=true;
  }
  cout << endl;
  
  if(symbols.size()==0)
  {
    cout << "No stack symbols input prevent simulation. Stopping." << endl;
    return 1;
  }

  cout << "initial stack " << istack << endl;

  cout << "stack symbols:";
  for(iter=symbols.begin(); iter!=symbols.end(); iter++) cout << *iter << " ";
  cout << endl;

  iter = from_symbols.find(istack); // check that initial stack symbol
                                    // is on from side
  if(iter==symbols.end())
  {
    cout << istack << " is not a valid initial stack symbol." << endl;
    no_simulate=true;
  }
  cout << endl;
  
  cout << "final states:";
  if(final.size()==0)
  {
    cout << "   No final states" << endl;
  }
  else if(to_states.size()!=0)
  {
    for(iter=final.begin(); iter!=final.end(); iter++) cout << *iter << " ";
    cout << endl;

    for(iter=final.begin(); iter!=final.end(); iter++) // check final states
    {
      iter2 = to_states.find(*iter);
      if(iter2==to_states.end() && (*iter!=start))
      {
        cout << *iter << " is not a valid final state." << endl;
        no_simulate=true;
      }
    }
    cout << endl;
  }

  if(trace.size()==1 && *trace.begin() == "all") trace = states;
  cout << "trace states:";
  if(trace.size()==0)
  {
    cout << "No states to trace" << endl;
  }
  else
  {
    for(iter=trace.begin(); iter!=trace.end(); iter++) cout << *iter << " ";
    cout << endl << endl;

    for(iter=trace.begin(); iter!=trace.end(); iter++) // check trace states
    {
      iter2 = states.find(*iter);
      if(iter2==states.end())
      {
        cout << *iter << " is not a valid trace state." << endl;
      }
    }
    cout << endl;
  }

  if(t_table.size()!=0)
  {
    sort(t_table.begin(), t_table.end(), transition::smaller );
    cout << "Sorted transition table:" << endl;
    for(x=t_table.begin(); x!=t_table.end(); x++)
    {
      cout << *x << endl;
      if(x->from==prev_from && (x->input==prev_input ||
         prev_input==epsilon))
      {
        nondeterministic = true;
      }
      prev_from=x->from;
      prev_input=x->input;
    }
  }
  else
  { 
    cout << "No transitions (five tuples)" << endl;
    no_simulate=true;
  }

  if(!nondeterministic)
  {
    cout << "deterministic 'delta' transition table" << endl;
    cout << "you could use the tm simulator"
         << endl;
  }
  if(no_simulate)
  {
    cout << "Errors in input prevent simulation. Stopping." << endl;
    return 1;
  }

  // build map for state+input_character to transition table index
  for(tx=0; tx<t_table.size(); tx++)
  {
    t_index.insert(c_index(t_table[tx].from+t_table[tx].input, tx));
  }
  

  // main simulation loop for each tape
  do // may read zero or more "tape" lines
  {
    if(initial_tape.size()==0 && have_enddef) // expect to read a "tape"
    {
      cin >> keyword; // only "tape" and comment is allowed
      if(!cin.eof() && keyword=="//")
      {
        cin.ignore(255,'\n');
        continue;
      }
      if(!cin.eof() && keyword==key_tape)
      {
        cin >> initial_tape;
        if(initial_tape=="//") initial_tape = ""; // null tape
        cin.ignore(255,'\n');
      }
      else
      {
        cout << " No more input tapes. Stopping." << endl;
        return 1;
      }
    }
    
    // clean up initial_tape into tape
    tape.clear(); // may come around again
    for(its=initial_tape.begin(); its!=initial_tape.end(); its++)
    {
      if((its+1)!=initial_tape.end())
      {
        if(*its=='#' && *(its+1)=='b')
        {
          tape.push_back(' ');
          its++;
        }
        else
        {
          tape.push_back(*its); // allows '#' sometimes    
        }
      }
      else
      {
        tape.push_back(*its);        
      }
    }
    tape_position = 1; // start past #[ on first user character
    cout << endl << "tape = ";
    for(it=(tape.begin()); it!=(tape.end()); it++) cout << *it;
    cout << endl; 
  
    state=start;          // state set to next_state when popped
    tran_que.push_back(nd_tran(state, pstack));
    if(debug) cout << "queuing " << state << " at " << tape_position
                   << endl << endl;
    // loop to limit total transition steps                   
    for(step=1; step<limit; step++)
    {
      if(tran_que.empty())
      {
        if(debug) cout << "tran_que is empty" << endl;
        break; // no more transitions available
      }
      nd_object = tran_que.front();
      tran_que.pop_front();
      state = nd_object.state; // restart a path from a nd_object
      pstack = nd_object.pstack;
      input_char = tape[tape_position]; // input_char set also at bottom
      if(debug) cout << "popped " << state << " at " << tape_position
                     << " input_char=" << input_char 
                     << " top_stack="  << pstack.top() << endl;
                     
      if(trace.size()!=0 && trace.find(state)!=trace.end())
      {
        input_str = input_char;
        if(input_char==epsilon)   input_str="#e";
        cout << "step " << step << "  " << state << "  "
             << input_str << " at pos " << tape_position << endl;
        cout << "tape=";
        for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
        cout << endl;
        cout << "    ";
        for(i=0; i<tape_position; i++) cout << ' ';
        cout << '^' << endl;
      }
  
      // test for epsilon transition first
      p_pair = t_index.equal_range(state+epsilon);
      for(pt=p_pair.first; pt!=p_pair.second && pt!=t_index.end(); pt++)
      {
        tx = pt->second; // process epsilon transitions, just que next
        tran_que.push_back(nd_tran(t_table[tx].to, pstack));
        if(debug) cout << "queuing epsilons" << t_table[tx].to << " at "
                       << tape_position << endl;
      }
      
      // check for halt and termination
      if(final.size()!=0 && final.find(state)!=final.end())
      {
        if(input_char=='?') // ??? end of input tape
        {
           accepted = true;
           if(debug) cout << "terminated and accepted" << endl;
           break; // out of 'step' loop
        }
        else if(halt_mode)
        {
          if(debug) cout << "this path dies, halt mode" << endl;
          continue; // this path dies
        }
      }

      // pull up next normal transition (in loop)
      p_pair = t_index.equal_range(state+input_char);
      if(p_pair.first==t_index.end() || p_pair.first==p_pair.second)
      {
        if(debug) cout << "no more transitions on path" << endl;
        continue; // no more transitions on path
      }

      for(pt=p_pair.first; pt!=p_pair.second && pt!=t_index.end(); pt++)
      {
        tx = pt->second; // restore path state
        next_state=t_table[tx].to;
        write_str=t_table[tx].write;          // may be no_write
        
        if(write_str!=string(1,no_write)) // check for no_write to stack
        {
          // tape[tape_position]=write_char; // write to pstack
        }
        
        tran_que.push_back(nd_tran(next_state, pstack));
        if(debug)
        {
          cout << "queuing " << next_state << " at "
               << tape_position << endl;
          cout << "tape=";
          for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
          cout << endl;
          cout << "    ";
          for(i=0; i<tape_position; i++) cout << ' ';
          cout << '^' << endl << endl;
       }
      } // finished this batch of nondeterministic transitions
    } // step limit loop
  
  
    // final messages to the user
    if(halted)
    {
      cout << "tm halted after " << step << " steps, at "
           << state << " with output:" << endl ;
      for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
      cout << endl;
    } 
    else if(accepted)
    {
      cout << "tape accepted after " << step << " steps, at " 
           << state << endl ;
      if(debug)
      {
        cout << "tape=";
        for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
        cout << endl;
      }
    }
    else
    {
      cout << "tape rejected after " << step << " steps" << endl;
      if(debug)
      {
        cout << "tape=";
        for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
        cout << endl;
      }
    }

    initial_tape = "";
    accepted = false;
    tran_que.clear();
    
  }while(!cin.eof() && have_enddef); // close out tape read 'do'

  return 0;
} // end of main

// for outputting objects of class  transition
ostream &operator<<(ostream &stream, transition trans)
{
  string input_token=string(1,trans.input);
  if(trans.input==epsilon)   input_token=string("#e");
  if(trans.input==' ')       input_token=string("#b");
  string write_token=trans.write;
  if(trans.write==string(1,no_write)) write_token=string("#e");
  if(trans.write==string(1,' '))      write_token=string("#b");

  stream << trans.from  << '\t' 
         << input_token << '\t'
         << trans.top   << '\t'
         << trans.to    << '\t'
         << write_token       ;   
  return stream;
}

// end npda.cpp