UVA Solution 171 - Car Trialling - Solution in C++ | Volume 1

UVA Solution 171 - Car Trialling - Solution in C++ | Volume 1

UVA Online Judge Solution 171- Car Trialling | Volume 1

Problem Name: Car Trialling

Problem Number : UVA - 171

Online Judge : UVA Online Judge Solution

Volume: 1

Solution Language : C plus plus

Code Line - 851

UVA Solution 171 Code in CPP:

#include <stdio.h> 
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string.h>
#include <ctype.h>
#include <assert.h>
using namespace std;

#define HTMLProduction
// #define DEBUG

class Production {
 public:
  int    label;
  string    LHS;
  vector<string>  RHS;
  
  Production(string L = "", vector<string> R = vector<string>(), int l=0) {
   LHS = L;
   RHS = R;
   label = l;
  }

  bool operator<(const Production &p) const {
   if(LHS != p.LHS)
    return LHS < p.LHS;
   for(size_t i = 0, j = 0; i < RHS.size() && j < p.RHS.size(); i++, j++) {
    if(RHS[i] != p.RHS[i])
     return RHS[i] < p.RHS[i];
   }
   return RHS.size() < p.RHS.size();
  }
  
  bool operator==(const Production &p) const {
   if(LHS != p.LHS || RHS.size() != p.RHS.size())
    return false;
   for(size_t i = 0, j = 0; i < RHS.size(); i++, j++) {
    if(RHS[i] != p.RHS[i])
     return false;
   }
   return true;
  }
  
  bool operator!=(const Production &p) const {
   return !(*this == p);
  }
  
  void print() {
   printf("%s -> ", LHS.c_str());
   for(size_t i = 0; i < RHS.size(); i++)
    printf("%s", RHS[i].c_str());
  }
};

class Grammar {
 public:
  /* LR parsing */
  class ConfigurationSet {
   public:
    class State {
     public:
      int dot;
      vector<string> lookahead;
      
      State(int d=0, vector<string> l=vector<string>()):
       dot(d), lookahead(l) {}
      bool operator<(const State &x) const {
       return dot < x.dot;
      }
      bool operator!=(const State &x) const {
       return dot != x.dot;
      }
    };
    
    set< pair<Production, State> >  configs;
    int        label;
    ConfigurationSet() {
     label = 0;
    }
    /* method */
    static ConfigurationSet closure0(ConfigurationSet& s, Grammar& g);
    static ConfigurationSet go_to0(ConfigurationSet& s, string X, Grammar& g);
    void print(Grammar &g) {
     set< pair<Production, State> >::iterator it;
     Production p;
     
     for(it = configs.begin(); it != configs.end(); it++) {
      p = it->first;
      printf("%s ->", p.LHS.c_str());
      for(size_t i = 0; i < p.RHS.size(); i++) {
       if(i == it->second.dot)
        printf("¡E");
       printf(" %s ", p.RHS[i].c_str());
      }
      if(it->second.dot == p.RHS.size())
       printf("¡E");
      printf(" ,{");
      set<string> fset = g.follow_set[p.LHS];
      for(set<string>::iterator jt = fset.begin();
       jt != fset.end(); jt++) {
       if(jt != fset.begin())
        cout << ", ";
       cout << *jt;
      }
      printf("}");
      puts("");
     }
    }
    bool operator<(const ConfigurationSet &x) const {
     if(configs.size() != x.configs.size())
      return configs.size() < x.configs.size();
     for(set< pair<Production, State> >::iterator it = configs.begin(), jt = x.configs.begin();
      it != configs.end(); it++, jt++) {
      if(it->first != jt->first)
       return it->first < jt->first;
      if(it->second != jt->second)
       return it->second < jt->second;
     }
     return false;
     // return label < x.label;
    }
  };  
  
  static const string   lambda;
  set<string>     symbols;
  string       start_symbol;
  vector<Production>    rules;
  /* LL(1) attribute */
  map<string, set<string> >  first_set;
  map<string, set<string> >  follow_set;
  map<string, bool>    derives_lambda;
  map<string, map<string, Production> > lltable;
  /* LR attribute */
  vector<ConfigurationSet> LRstates;
  map<int, map<string, int> > go_to_table;
  map<int, int>    action_table;
  
  /* common method */
  static bool isNonterminal(string token);
  void buildSymbols();
  /* LL(1) method */
  map<string, bool> mark_lambda();
  void fill_first_set();
  void fill_follow_set();
  set<string> compute_first(vector<string> rhs);
  set<string> get_predict_set(Production p);
  void fill_lltable();
  void lldriver(queue<string> tokens);
  /* LR method*/
  void build_CFSM();
  void build_action();
  void lr0driver(queue<string> tokens);
  int slr1driver(queue<string> tokens);
  void lalr1driver(queue<string> tokens);
  /* homework */
  void hw_build_CFSM();
};
/* ------------------------
ConfigurationSet method
-------------------------- */
Grammar::ConfigurationSet Grammar::ConfigurationSet::closure0(ConfigurationSet& s, Grammar& g) {
 ConfigurationSet  r = s;
 bool    changes;
 string    A;
 Production   P;
 int     dotPos;
 
 set< pair<Production, State> >::iterator it;
 do {
  changes = false;
  for(it = r.configs.begin(); it != r.configs.end(); it++) {
   P = it->first;
   dotPos = it->second.dot;
   if(dotPos >= P.RHS.size() || P.RHS[dotPos] == Grammar::lambda)
    continue;
   A = P.RHS[dotPos];
   if(Grammar::isNonterminal(A)) {
    /* B -> x.Ay */
    /* Predict productions with A as the left-hand side */
    for(size_t i = 0; i < g.rules.size(); i++) {
     if(g.rules[i].LHS == A) {
      if(r.configs.find(make_pair(g.rules[i], State(0))) == r.configs.end()) {
       r.configs.insert(make_pair(g.rules[i], State(0)));
       changes = true;
      }
     }
    }
   }
  }
 } while(changes);
 return r;
}
Grammar::ConfigurationSet Grammar::ConfigurationSet::go_to0(ConfigurationSet& s, string X, Grammar& g) {
 ConfigurationSet sb;
 set< pair<Production, State> >::iterator it;
 Production  P;
 int   dotPos;
 
 for(it = s.configs.begin(); it != s.configs.end(); it++) {
  P = it->first;
  dotPos = it->second.dot;
  if(dotPos >= P.RHS.size() || P.RHS[dotPos] == Grammar::lambda)
   continue;
  if(P.RHS[dotPos] == X) {
   State state(dotPos + 1, it->second.lookahead);
   sb.configs.insert(make_pair(P, state));
  }
 }
 return closure0(sb, g);
}
/* ------------------------
Grammar method
-------------------------- */
const string Grammar::lambda("l");

set<string> Grammar::compute_first(vector<string> rhs) {
 set<string> result;
 size_t   i;
 
 if(rhs.size() == 0 || rhs[0] == Grammar::lambda) {
  result.insert(Grammar::lambda);
 } else {
  result = first_set[rhs[0]];
  for(i = 1; i < rhs.size() && 
   first_set[rhs[i-1]].find(Grammar::lambda) != first_set[rhs[i-1]].end(); i++) {
   set<string> f = first_set[rhs[i]];
   f.erase(Grammar::lambda);
   result.insert(f.begin(), f.end()); 
  }
  if(i == rhs.size() 
   && first_set[rhs[i-1]].find(Grammar::lambda) != first_set[rhs[i-1]].end()) {
   result.insert(Grammar::lambda);
  } else {
   result.erase(Grammar::lambda);
  }
 }
 
 return result;
} 
/*
 * please call get_predict_set() after fill_follow_set() and fill_first_set()
 */
set<string> Grammar::get_predict_set(Production p) {
 set<string> result;
 set<string> rfirst;
 
 rfirst = compute_first(p.RHS);
 if(rfirst.find(Grammar::lambda) != rfirst.end()) {
  rfirst.erase(Grammar::lambda);
  result.insert(rfirst.begin(), rfirst.end());
  rfirst = follow_set[p.LHS];
  result.insert(rfirst.begin(), rfirst.end());
 } else {
  result.insert(rfirst.begin(), rfirst.end());
 }
 
 return result;
}
/*
 * 
 */
void Grammar::fill_lltable() {
 string  A; // nonterminal
 Production  p;
 
 for(size_t i = 0; i < rules.size(); i++) {
  p = rules[i];
  A = p.LHS;
  set<string> predict_set = get_predict_set(p);
  
  for(set<string>::iterator it = predict_set.begin();
   it != predict_set.end(); it++) {
   assert(lltable[A].find(*it) == lltable[A].end());
   lltable[A][*it] = p;
  }
 }
 
}
void Grammar::buildSymbols() {
 symbols.clear();
 for(size_t i = 0; i < rules.size(); i++) {
  symbols.insert(rules[i].LHS);
  for(size_t j = 0; j < rules[i].RHS.size(); j++) {
   symbols.insert(rules[i].RHS[j]);
  }
 }
}
bool Grammar::isNonterminal(string token) {

#ifdef HTMLProduction
 if(token == Grammar::lambda)
  return false;
 if(token[0] == '<' && token[token.length() - 1] == '>')
  return true;
 return false;
#else
 if(token == Grammar::lambda)
  return false;
 for(size_t i = 0; i < token.length(); i++) {
  if(isupper(token[i]))
   return true;
 }
 return false;
#endif
}
/* ------------------------
Grammar LL method
-------------------------- */
map<string, bool> Grammar::mark_lambda() {
 bool     rhs_derives_lambda;
 bool     changes;
 Production    p;
 
 derives_lambda.clear();
 
 /* initially, nothing is marked. */
 for(size_t i = 0; i < rules.size(); i++) {
  derives_lambda[rules[i].LHS] = false;
 }
 do {
  changes = false;
  for(size_t i = 0; i < rules.size(); i++) {
   p = rules[i];
   if(!derives_lambda[p.LHS]) {
    if(p.RHS.size() == 0 || p.RHS[0] == Grammar::lambda) {
     changes = derives_lambda[p.LHS] = true;
     continue;
    }
    /* does each part of RHS derive lambda ? */
    rhs_derives_lambda = derives_lambda[string(p.RHS[0])];
    for(size_t j = 1; j < p.RHS.size(); j++) {
     rhs_derives_lambda &= derives_lambda[p.RHS[j]];
    }
    if(rhs_derives_lambda) {
     changes = true;
     derives_lambda[p.LHS] = true;
    }
   }
  }
 } while(changes);
 return derives_lambda;
}
void Grammar::fill_first_set() {
 
 string   A; // nonterminal
 string   a; // terminal
 Production  p;
 bool   changes;
  
 mark_lambda();
 first_set.clear();
 
 for(size_t i = 0; i < rules.size(); i++) {
  A = rules[i].LHS;
  if(derives_lambda[A])
   first_set[A].insert(Grammar::lambda);
 }
 
 for(size_t i = 0; i < rules.size(); i++) {
  for(size_t j = 0; j < rules[i].RHS.size(); j++) {
   a = rules[i].RHS[j];
   if(!isNonterminal(a)) {
    if(a != Grammar::lambda)
     first_set[a].insert(a);
    if(j == 0) { // A -> aXX
     first_set[rules[i].LHS].insert(a);
    }
   }
  }
 }
 
 do {
  changes = false;
  for(size_t i = 0; i < rules.size(); i++) {
   p = rules[i];
   set<string> rfirst = compute_first(p.RHS);
   size_t oldsize = first_set[p.LHS].size();
   first_set[p.LHS].insert(rfirst.begin(), rfirst.end());
   size_t newsize = first_set[p.LHS].size();
   if(oldsize != newsize)
    changes = true;
  }
 } while(changes);
} 

void Grammar::fill_follow_set() {
 string  A, B; // nonterminal
 Production  p;
 bool  changes;
 
 for(size_t i = 0; i < rules.size(); i++) {
  A = rules[i].LHS;
  follow_set[A].clear();
 }
 
 follow_set[start_symbol].insert(Grammar::lambda);
  
 do {
  changes = false;
  for(size_t i = 0; i < rules.size(); i++) {
   /* A -> a B b
    * I.e. for each production and each occurrence
    * of a nonterminal in its right-hand side. 
    */
   p = rules[i];
   A = p.LHS;
   for(size_t j = 0; j < p.RHS.size(); j++) {
    B = p.RHS[j];
    if(isNonterminal(B)) {
     vector<string> beta(p.RHS.begin() + j + 1, p.RHS.end());
     set<string> rfirst = compute_first(beta);
     size_t oldsize = follow_set[B].size();
     
     if(rfirst.find(Grammar::lambda) == rfirst.end()) {
      follow_set[B].insert(rfirst.begin(), rfirst.end()); 
     } else {
      rfirst.erase(Grammar::lambda);
      follow_set[B].insert(rfirst.begin(), rfirst.end()); 
      rfirst = follow_set[A];
      follow_set[B].insert(rfirst.begin(), rfirst.end());
     }
     size_t newsize = follow_set[B].size();   
     if(oldsize != newsize)
      changes = true;
    }
   }
  }
 } while(changes);
}

void Grammar::lldriver(queue<string> tokens) {
 stack<string>  stk;
 string    X;
 string   a;
 Production  p;
 /* Push the Start Symbol onto an empty stack */
 stk.push(start_symbol);
 
 while(!stk.empty() && !tokens.empty()) {
  X = stk.top();
  a = tokens.front();
  // cout << X << " " << a << endl;
  if(isNonterminal(X) && lltable[X].find(a) != lltable[X].end()) {
   p = lltable[X][a];
   stk.pop();
   for(int i = p.RHS.size() - 1; i >= 0; i--) {
    if(p.RHS[i] == Grammar::lambda)
     continue;
    stk.push(p.RHS[i]);
   }
  } else if(X == a) {
   stk.pop();
   tokens.pop();
  } else if(lltable[X].find(Grammar::lambda) != lltable[X].end()) {
   stk.pop();
  } else {
   /* Process syntax error. */
   puts("Bad!");
   return;
  }
 }
 while(!stk.empty()) {
  X = stk.top();
  if(lltable[X].find(Grammar::lambda) != lltable[X].end())
   stk.pop();
  else
   break;
 }
 if(tokens.size() == 0 && stk.size() == 0)
  puts("Good");
 else
  puts("Bad!");
 return;
}
/* ------------------------
Grammar LR method
-------------------------- */
void Grammar::build_action() {
 ConfigurationSet  s;
 Production    P;
 int     dotPos;
 set< pair<Production, ConfigurationSet::State> >::iterator it;
 
 for(size_t i = 0; i < LRstates.size(); i++) {
  s = LRstates[i];
  int reduce = 0, rule = 0, accept = 1;
  for(it = s.configs.begin(); it != s.configs.end(); it++) {
   P = it->first, dotPos = it->second.dot;
   if(dotPos == P.RHS.size())
    reduce++, rule = P.label;
   accept &= P.LHS == Grammar::start_symbol;
  }
  if(accept == 1)
   action_table[i] = 0;
  else if(reduce == 1)
   action_table[i] = -1;
  else
   action_table[i] = 1;
 }
#ifdef DEBUG
 printf("State |");
 for(size_t i = 0; i < LRstates.size(); i++)
  printf("%5d|", i);
 puts("");
 printf("Action|");
 for(size_t i = 0; i < action_table.size(); i++) {
  printf("%5d|", action_table[i]);
 }
 puts("");
#endif
}
void Grammar::build_CFSM() {
 set<ConfigurationSet>  S;
 queue<ConfigurationSet> Q;
 ConfigurationSet   s0, sb;
 int      label = 0;
 ConfigurationSet::State state;
 
 state.dot = 0;
 state.lookahead = vector<string>();
 state.lookahead.push_back(Grammar::lambda);
 for(size_t i = 0; i < rules.size(); i++) {
  if(rules[i].LHS == this->start_symbol) {
   s0.configs.insert(make_pair(rules[i], state));
  }
 }
 s0 = ConfigurationSet::closure0(s0, *this);
 s0.label = label++;
 
 S.insert(s0);
 Q.push(s0);
 
 buildSymbols();
 /* hw need */
 map<int, vector< pair<int, string> > > hwPrint;
 /* hw need */
 while(!Q.empty()) {
  s0 = Q.front(), Q.pop();
  LRstates.push_back(s0);
  for(set<string>::iterator it = symbols.begin();
   it != symbols.end(); it++) {
   sb = ConfigurationSet::go_to0(s0, *it, *this);
   if(sb.configs.size() > 0) {
    if(S.find(sb) == S.end()) {
     sb.label = label++;
     S.insert(sb);
     Q.push(sb);
    }
    
    go_to_table[s0.label][*it] = (* S.find(sb)).label;
    /* hw need */
    hwPrint[(* S.find(sb)).label].push_back(make_pair(s0.label, *it));
   }
  }
 }
 // build_action();
#ifdef DEBUG 
 printf("Total State: %d\n", label);
 for(int i = 0; i < label; i++) {
  if(hwPrint[i].size() > 0) {
   printf("State %d from", i);
   for(vector< pair<int, string> >::iterator it = hwPrint[i].begin();
    it != hwPrint[i].end(); it++) {
    printf("%cState %d(%s)", it == hwPrint[i].begin() ? ' ' : ',', it->first, it->second.c_str());
   }
   puts("");
  } else {
   printf("State %d\n", i);
  }
  LRstates[i].print(*this);
  puts("");
 }
#endif
}
int Grammar::slr1driver(queue<string> tokens) {
 stack<int>   stateStk;
 stack<string>  tokenStk;
 int    state;
 string   X;
 
 stateStk.push(0); /* push start state */
 while(!tokens.empty()) {
  state = stateStk.top();
  X = tokens.front();
#ifdef DEBUG 
  puts("");
  printf("state %d front %s\n", state, X.c_str());
  LRstates[state].print(*this);
  for (std::stack<int> dump = stateStk; !dump.empty(); dump.pop())
         std::cout << "state stack "<< dump.top() << '\n';
  for (std::stack<string> dump = tokenStk; !dump.empty(); dump.pop())
         std::cout << "token stack "<< dump.top() << '\n';
#endif
  int reduce = 0, shift = 0;
  Production P;
  for(set< pair<Production, ConfigurationSet::State> >::iterator it = LRstates[state].configs.begin(); 
   it != LRstates[state].configs.end(); it++) {
   Production q = it->first;
   ConfigurationSet::State s = it->second;
   if(follow_set[q.LHS].find(X) != follow_set[q.LHS].end() && 
     (s.dot == q.RHS.size() || q.RHS[0] == Grammar::lambda)) {
    reduce++;
    P = q;
   }
  }
  if(go_to_table[state].find(X) != go_to_table[state].end())
   shift++;
  if(reduce + shift >= 2)
   assert(false); // grammar can't use simple LR.
  if(reduce + shift == 0)
   return 0;
  if(reduce == 1) { // Reduce
   for(size_t i = 0; i < P.RHS.size(); i++) 
    tokenStk.pop(), stateStk.pop();

   tokenStk.push(P.LHS);
   state = stateStk.top();
   if(go_to_table[state].find(P.LHS) == go_to_table[state].end()) {
    return 0;
   }
   state = go_to_table[state][P.LHS];
   stateStk.push(state);
  } else { // shift
   state = go_to_table[state][X];
   stateStk.push(state);
   tokenStk.push(X);
   tokens.pop();
  }
 }
 while(!stateStk.empty()) {
  state = stateStk.top();
  X = Grammar::lambda;
#ifdef DEBUG 
  puts("");
  printf("state %d front %s\n", state, X.c_str());
  LRstates[state].print(*this);
  for (std::stack<int> dump = stateStk; !dump.empty(); dump.pop())
         std::cout << "state stack "<< dump.top() << '\n';
  for (std::stack<string> dump = tokenStk; !dump.empty(); dump.pop())
         std::cout << "token stack "<< dump.top() << '\n';
#endif
  int reduce = 0, shift = 0;
  Production P;
  for(set< pair<Production, ConfigurationSet::State> >::iterator it = LRstates[state].configs.begin(); 
   it != LRstates[state].configs.end(); it++) {
   Production q = it->first;
   ConfigurationSet::State s = it->second;
   if(follow_set[q.LHS].find(X) != follow_set[q.LHS].end() && 
     (s.dot == q.RHS.size() || q.RHS[0] == Grammar::lambda)) {
    reduce++;
    P = q;
   }
  }
  if(go_to_table[state].find(X) != go_to_table[state].end())
   shift++;
  if(reduce + shift >= 2)
   assert(false); // grammar can't use simple LR.
  if(reduce + shift == 0)
   return 0;
  if(reduce == 1) { // Reduce
   for(size_t i = 0; i < P.RHS.size(); i++) 
    tokenStk.pop(), stateStk.pop();

   tokenStk.push(P.LHS);
   state = stateStk.top();
   if(go_to_table[state].find(P.LHS) == go_to_table[state].end()) {
    if(P.LHS == Grammar::start_symbol)
     return 1;
    return 0;
   }
   state = go_to_table[state][P.LHS];
   stateStk.push(state);
  } else { // shift
   state = go_to_table[state][X];
   stateStk.push(state);
   tokenStk.push(X);
   tokens.pop();
  }
 }
 return 0;
}
void parsingProduction(string r, Grammar &g) {
 static int   production_label = 0;
 stringstream  sin(r);
 string    lhs, foo;
 vector<string>  tokens;
 sin >> lhs >> foo;
 while(sin >> foo)
  tokens.push_back(foo);
 Production p(lhs, tokens);
 p.label = ++production_label;
 g.rules.push_back(p);
}
bool isNumber(string str) {
 for(int i = 0; i < str.length(); i++) {
  if(!isdigit(str[i]))
   return false;
 }
 return true;
}
int scanTokens(char s[], queue<string>& tokens, vector<string>& val) {
 string keyword[18] = {"AND", "THEN", "GO", "KEEP", 
   "RIGHT", "LEFT", "FIRST", "SECOND", "THIRD", 
   "AT", "RECORD", "TIME", "TO", "KMH", "CHANGE",
   "AVERAGE", "SPEED", "CAS"};
 for(int i = 0; s[i]; i++) {
  if(s[i] == '"') {
   // s-word can't empty, and after the opening speech marks no more space.
   if(s[i + 1] == '"' || isspace(s[i + 1])) 
    return 0;
   i++;
   while(s[i] != '"') {
    if(isupper(s[i])) {}
    else if(isspace(s[i])) {s[i] = '_';}
    else if(s[i] == '.') {
     if(isspace(s[i - 1]) || s[i - 1] == '_') {
      return 0;
     }
    } else {
     return 0;
    }
    i++;
   }
   if(s[i] == '\0' || isspace(s[i - 1]) || s[i - 1] == '_')
    return 0;
  }
 }
 stringstream  sin(s);
 string    token;
 while(sin >> token) {
  int f = 0;
  for(int i = 0; i < 18; i++) {
   if(token == keyword[i])
    tokens.push(token), val.push_back(token), f = 1;
  }
  if(f) continue;
  if(token[0] == '"')
   tokens.push("SIGNWORDS"), val.push_back(token), f = 1;
  if(f) continue;
  if(isNumber(token))
   tokens.push("NNN"), val.push_back(token), f = 1;
  if(f) continue;
  return 0;
 }
 return 1;
}
int main() {
// freopen("in.txt", "r+t", stdin);
// freopen("out.txt", "w+t", stdout);
 Grammar g;
 parsingProduction("<instruction>  -> <navigational>", g);
 parsingProduction("<instruction>  -> <time-keeping>", g);
 parsingProduction("<instruction>  -> <navigational> AND <time-keeping>", g);
 parsingProduction("<navigational>  -> <directional>", g);
 parsingProduction("<navigational>  -> <navigational> AND THEN <directional>", g);
 parsingProduction("<directional>  -> <how> <direction>", g);
 parsingProduction("<directional>  -> <how> <direction> <where>", g);
 parsingProduction("<how>    -> GO", g);
 parsingProduction("<how>    -> GO <when>", g);
 parsingProduction("<how>   -> KEEP", g);
 parsingProduction("<direction>   -> RIGHT", g);
 parsingProduction("<direction>  -> LEFT", g);
 parsingProduction("<when>   -> FIRST", g);
 parsingProduction("<when>   -> SECOND", g);
 parsingProduction("<when>   -> THIRD", g);
 parsingProduction("<where>    -> AT <sign>", g);
 parsingProduction("<sign>   -> SIGNWORDS", g);
 parsingProduction("<time-keeping>  -> <record>", g);
 parsingProduction("<time-keeping> -> <change>", g);
 parsingProduction("<record>   -> RECORD TIME", g);
 parsingProduction("<change>   -> <cas> TO NNN KMH", g);
 parsingProduction("<cas>   -> CHANGE AVERAGE SPEED", g);
 parsingProduction("<cas>    -> CAS", g);
 g.start_symbol = "<instruction>";
  
 g.fill_first_set();
 g.fill_follow_set();
 g.build_CFSM();
 
 char  line[1024];
 int  cases = 0;
 while(gets(line)) {
  if(!strcmp(line, "#"))
   break;
  queue<string> tokens;
  vector<string> val;
  int f = scanTokens(line, tokens, val);
  printf("%3d.", ++cases);
  if(!f) {
   puts(" Trap!");
   continue;
  }
  f = g.slr1driver(tokens);
  if(!f) {
   puts(" Trap!");
   continue;
  }
  for(int i = 0; i < val.size(); i++) {
   if(val[i][0] == '"')
    for(int j = 0; j < val[i].length(); j++)
     if(val[i][j] == '_')
      val[i][j] = ' ';
   printf(" %s", val[i].c_str());
  }
  puts("");
 }
 return 0;
}