From fff4dc4a763c6f7fbda61b958ab45641c638d93f Mon Sep 17 00:00:00 2001
From: Chris Dyer <redpony@gmail.com>
Date: Sun, 19 Oct 2014 15:23:31 -0400
Subject: remove json hypergraph format

---
 decoder/Makefile.am | 6 +-----
 1 file changed, 1 insertion(+), 5 deletions(-)

(limited to 'decoder/Makefile.am')

diff --git a/decoder/Makefile.am b/decoder/Makefile.am
index e46a7120..b56e4c72 100644
--- a/decoder/Makefile.am
+++ b/decoder/Makefile.am
@@ -33,7 +33,6 @@ noinst_LIBRARIES = libcdec.a
 EXTRA_DIST = test_data rule_lexer.ll
 
 libcdec_a_SOURCES = \
-  JSON_parser.h \
   aligner.h \
   apply_models.h \
   bottom_up_parser.h \
@@ -80,7 +79,6 @@ libcdec_a_SOURCES = \
   hg_union.h \
   incremental.h \
   inside_outside.h \
-  json_parse.h \
   kbest.h \
   lattice.h \
   lexalign.h \
@@ -141,7 +139,6 @@ libcdec_a_SOURCES = \
   hg_sampler.cc \
   hg_union.cc \
   incremental.cc \
-  json_parse.cc \
   lattice.cc \
   lexalign.cc \
   lextrans.cc \
@@ -157,5 +154,4 @@ libcdec_a_SOURCES = \
   tagger.cc \
   translator.cc \
   trule.cc \
-  viterbi.cc \
-  JSON_parser.c
+  viterbi.cc
-- 
cgit v1.2.3


From 13d3dd3a8dca40c3ce70c2b117964ca3bfa5f971 Mon Sep 17 00:00:00 2001
From: Chris Dyer <cdyer@allegro.clab.cs.cmu.edu>
Date: Sat, 25 Oct 2014 00:18:38 -0400
Subject: extract features from converted conll files

---
 decoder/Makefile.am |   4 +-
 decoder/ff_conll.cc | 250 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 decoder/ff_conll.h  |  45 ++++++++++
 3 files changed, 298 insertions(+), 1 deletion(-)
 create mode 100644 decoder/ff_conll.cc
 create mode 100644 decoder/ff_conll.h

(limited to 'decoder/Makefile.am')

diff --git a/decoder/Makefile.am b/decoder/Makefile.am
index b56e4c72..fcb95e65 100644
--- a/decoder/Makefile.am
+++ b/decoder/Makefile.am
@@ -44,12 +44,13 @@ libcdec_a_SOURCES = \
   ff_basic.h \
   ff_bleu.h \
   ff_charset.h \
+  ff_conll.h \
   ff_context.h \
   ff_csplit.h \
   ff_external.h \
   ff_factory.h \
   ff_klm.h \
-	ff_lexical.h \
+  ff_lexical.h \
   ff_lm.h \
   ff_ngrams.h \
   ff_parse_match.h \
@@ -108,6 +109,7 @@ libcdec_a_SOURCES = \
   ff_basic.cc \
   ff_bleu.cc \
   ff_charset.cc \
+  ff_conll.cc \
   ff_context.cc \
   ff_csplit.cc \
   ff_external.cc \
diff --git a/decoder/ff_conll.cc b/decoder/ff_conll.cc
new file mode 100644
index 00000000..8ded44b7
--- /dev/null
+++ b/decoder/ff_conll.cc
@@ -0,0 +1,250 @@
+#include "ff_conll.h"
+
+#include <stdlib.h>
+#include <sstream>
+#include <cassert>
+#include <cmath>
+#include <boost/lexical_cast.hpp>
+
+#include "hg.h"
+#include "filelib.h"
+#include "stringlib.h"
+#include "sentence_metadata.h"
+#include "lattice.h"
+#include "fdict.h"
+#include "verbose.h"
+#include "tdict.h"
+
+CoNLLFeatures::CoNLLFeatures(const string& param) {
+  //  cerr << "initializing CoNLLFeatures with parameters: " << param;
+  kSOS = TD::Convert("<s>");
+  kEOS = TD::Convert("</s>");
+  macro_regex = sregex::compile("%([xy])\\[(-[1-9][0-9]*|0|[1-9][1-9]*)]");
+  ParseArgs(param);
+}
+
+string CoNLLFeatures::Escape(const string& x) const {
+  string y = x;
+  for (int i = 0; i < y.size(); ++i) {
+    if (y[i] == '=') y[i]='_';
+    if (y[i] == ';') y[i]='_';
+  }
+  return y;
+}
+
+// replace %x[relative_location] or %y[relative_location] with actual_token
+// within feature_instance
+void CoNLLFeatures::ReplaceMacroWithString(
+  string& feature_instance, bool token_vs_label, int relative_location, 
+  const string& actual_token) const {
+
+  stringstream macro;
+  if (token_vs_label) {
+    macro << "%x[";
+  } else {
+    macro << "%y[";
+  }
+  macro << relative_location << "]";
+  int macro_index = feature_instance.find(macro.str());
+  if (macro_index == string::npos) {
+    cerr << "Can't find macro " << macro.str() << " in feature template " 
+	 << feature_instance;
+    abort();
+  }
+  feature_instance.replace(macro_index, macro.str().size(), actual_token);
+}
+
+void CoNLLFeatures::ReplaceTokenMacroWithString(
+  string& feature_instance, int relative_location, 
+  const string& actual_token) const {
+
+  ReplaceMacroWithString(feature_instance, true, relative_location, 
+				actual_token);
+}
+
+void CoNLLFeatures::ReplaceLabelMacroWithString(
+  string& feature_instance, int relative_location, 
+  const string& actual_token) const {
+
+  ReplaceMacroWithString(feature_instance, false, relative_location, 
+				actual_token);
+}
+
+void CoNLLFeatures::Error(const string& error_message) const {
+  cerr << "Error: " << error_message << "\n\n"
+
+       << "CoNLLFeatures Usage: \n"			     
+       << "  feature_function=CoNLLFeatures -t <TEMPLATE>\n\n" 
+
+       << "Example <TEMPLATE>: U1:%x[-1]_%x[0]|%y[0]\n\n" 
+
+       << "%x[k] and %y[k] are macros to be instantiated with an input\n" 
+       << "token (for x) or a label (for y). k specifies the relative\n" 
+       << "location of the input token or label with respect to the current\n"
+       << "position. For x, k is an integer value. For y, k must be 0 (to\n" 
+       << "be extended).\n\n";
+
+  abort();
+}
+
+void CoNLLFeatures::ParseArgs(const string& in) {
+  which_feat = 0;
+  vector<string> const& argv = SplitOnWhitespace(in);
+  for (vector<string>::const_iterator i = argv.begin(); i != argv.end(); ++i) {
+    string const& s = *i;
+    if (s[0] == '-') {
+      if (s.size() > 2) { 
+	stringstream msg;
+	msg << s << " is an invalid option for CoNLLFeatures.";
+	Error(msg.str());
+      }
+
+      switch (s[1]) {
+
+      case 'w': {
+        if (++i == argv.end()) {
+          Error("Missing parameter to -w");
+        }
+        which_feat = boost::lexical_cast<unsigned>(*i);
+        break;
+      }
+      // feature template
+      case 't': {
+	if (++i == argv.end()) { 
+	  Error("Can't find template."); 
+	}
+	feature_template = *i;
+	string::const_iterator start = feature_template.begin();
+	string::const_iterator end = feature_template.end();
+	smatch macro_match;
+
+        // parse the template
+	while (regex_search(start, end, macro_match, macro_regex)) {
+	  // get the relative location
+	  string relative_location_str(macro_match[2].first, 
+				       macro_match[2].second);
+	  int relative_location = atoi(relative_location_str.c_str());
+	  // add it to the list of relative locations for token or label
+	  // (i.e. x or y)
+	  bool valid_location = true;
+          if (*macro_match[1].first == 'x') {
+	    // add it to token locations
+	    token_relative_locations.push_back(relative_location);
+	  } else {
+	    if (relative_location != 0) { valid_location = false; }
+	    // add it to label locations
+	    label_relative_locations.push_back(relative_location);
+	  }
+	  if (!valid_location) {
+	    stringstream msg;
+	    msg << "Relative location " << relative_location
+		<< " in feature template " << feature_template
+		<< " is invalid.";
+	    Error(msg.str());
+	  }
+	  start = macro_match[0].second;
+	}
+	break;
+      }
+
+      // TODO: arguments to specify kSOS and kEOS
+
+      default: {
+	stringstream msg;
+	msg << "Invalid option on CoNLLFeatures: " << s;
+	Error(msg.str());
+	break;
+      }
+      } // end of switch
+    } // end of if (token starts with hyphen)
+  } // end of for loop (over arguments)
+
+  // the -t (i.e. template) option is mandatory in this feature function
+  if (label_relative_locations.size() == 0 || 
+      token_relative_locations.size() == 0) {
+    stringstream msg;
+    msg << "Feature template must specify at least one" 
+	 << "token macro (e.g. x[-1]) and one label macro (e.g. y[0]).";
+    Error(msg.str());
+  }
+}
+
+void CoNLLFeatures::PrepareForInput(const SentenceMetadata& smeta) {
+  const Lattice& sl = smeta.GetSourceLattice();
+  current_input.resize(sl.size());
+  for (unsigned i = 0; i < sl.size(); ++i) {
+    if (sl[i].size() != 1) {
+      stringstream msg;
+      msg << "CoNLLFeatures don't support lattice inputs!\nid=" 
+	   << smeta.GetSentenceId() << endl;
+      Error(msg.str());
+    }
+    current_input[i] = sl[i][0].label;
+  }
+  vector<WordID> wids;
+  string fn = "feat";
+  fn += boost::lexical_cast<string>(which_feat);
+  string feats = smeta.GetSGMLValue(fn);
+  if (feats.size() == 0) {
+    Error("Can't find " + fn + " in <seg>\n");
+  }
+  TD::ConvertSentence(feats, &wids);
+  assert(current_input.size() == wids.size());
+  current_input = wids;
+}
+
+void CoNLLFeatures::TraversalFeaturesImpl(
+  const SentenceMetadata& smeta, const Hypergraph::Edge& edge,
+  const vector<const void*>& ant_contexts, SparseVector<double>* features,
+  SparseVector<double>* estimated_features, void* context) const {
+
+  const TRule& rule = *edge.rule_;
+  // arity = 0, no nonterminals
+  // size = 1, predicted label is a single token
+  if (rule.Arity() != 0 ||
+      rule.e_.size() != 1) { 
+    return; 
+  }
+
+  // replace label macros with actual label strings
+  // NOTE: currently, this feature function doesn't allow any label
+  // macros except %y[0]. but you can look at as much of the source as you want
+  const WordID y0 = rule.e_[0];
+  string y0_str = TD::Convert(y0);
+
+  // start of the span in the input being labeled
+  const int from_src_index = edge.i_;   
+  // end of the span in the input
+  const int to_src_index = edge.j_;
+
+  // in the case of tagging the size of the spans being labeled will
+  //  always be 1, but in other formalisms, you can have bigger spans
+  if (to_src_index - from_src_index != 1) {
+    cerr << "CoNLLFeatures doesn't support input spans of length != 1";
+    abort();
+  }
+
+  string feature_instance = feature_template;
+  // replace token macros with actual token strings
+  for (unsigned i = 0; i < token_relative_locations.size(); ++i) {
+    int loc = token_relative_locations[i];
+    WordID x = loc < 0? kSOS: kEOS;
+    if(from_src_index + loc >= 0 && 
+       from_src_index + loc < current_input.size()) {
+      x = current_input[from_src_index + loc];
+    }
+    string x_str = TD::Convert(x);
+    ReplaceTokenMacroWithString(feature_instance, loc, x_str);
+  }
+    
+  ReplaceLabelMacroWithString(feature_instance, 0, y0_str);
+
+  // pick a real value for this feature
+  double fval = 1.0; 
+
+  // add it to the feature vector
+  //   FD::Convert converts the feature string to a feature int
+  //   Escape makes sure the feature string doesn't have any bad
+  //     symbols that could confuse a parser somewhere
+  features->add_value(FD::Convert(Escape(feature_instance)), fval);
+}
diff --git a/decoder/ff_conll.h b/decoder/ff_conll.h
new file mode 100644
index 00000000..b37356d8
--- /dev/null
+++ b/decoder/ff_conll.h
@@ -0,0 +1,45 @@
+#ifndef FF_CONLL_H_
+#define FF_CONLL_H_
+
+#include <vector>
+#include <boost/xpressive/xpressive.hpp>
+#include "ff.h"
+
+using namespace boost::xpressive;
+using namespace std;
+
+class CoNLLFeatures : public FeatureFunction {
+ public:
+  CoNLLFeatures(const string& param);
+ protected:
+  virtual void TraversalFeaturesImpl(const SentenceMetadata& smeta,
+                                     const HG::Edge& edge,
+                                     const vector<const void*>& ant_contexts,
+                                     SparseVector<double>* features,
+                                     SparseVector<double>* estimated_features,
+                                     void* context) const;
+  virtual void PrepareForInput(const SentenceMetadata& smeta);
+  virtual void ParseArgs(const string& in);
+  virtual string Escape(const string& x) const;
+  virtual void ReplaceMacroWithString(string& feature_instance, 
+				      bool token_vs_label, 
+				      int relative_location, 
+				      const string& actual_token) const;
+  virtual void ReplaceTokenMacroWithString(string& feature_instance, 
+					   int relative_location, 
+					   const string& actual_token) const;
+  virtual void ReplaceLabelMacroWithString(string& feature_instance, 
+					   int relative_location, 
+					   const string& actual_token) const;
+  virtual void Error(const string&) const;
+
+ private:
+  vector<int> token_relative_locations, label_relative_locations;
+  string feature_template;
+  vector<WordID> current_input;
+  WordID kSOS, kEOS;
+  sregex macro_regex;
+  unsigned which_feat;
+};
+
+#endif
-- 
cgit v1.2.3


From 448b451aa481b1509566ddb11abc3476466def6a Mon Sep 17 00:00:00 2001
From: Chris Dyer <redpony@gmail.com>
Date: Sun, 30 Nov 2014 21:30:09 -0500
Subject: implementation of Rico Sennrich's CKY+ variant; it currently doesn't
 support span limits so it is not enabled, but it seems to be functional.

---
 decoder/Makefile.am            |   2 +
 decoder/bottom_up_parser-rs.cc | 341 +++++++++++++++++++++++++++++++++++++++++
 decoder/bottom_up_parser-rs.h  |  29 ++++
 3 files changed, 372 insertions(+)
 create mode 100644 decoder/bottom_up_parser-rs.cc
 create mode 100644 decoder/bottom_up_parser-rs.h

(limited to 'decoder/Makefile.am')

diff --git a/decoder/Makefile.am b/decoder/Makefile.am
index fcb95e65..78ab4d63 100644
--- a/decoder/Makefile.am
+++ b/decoder/Makefile.am
@@ -36,6 +36,7 @@ libcdec_a_SOURCES = \
   aligner.h \
   apply_models.h \
   bottom_up_parser.h \
+  bottom_up_parser-rs.h \
   csplit.h \
   decoder.h \
   earley_composer.h \
@@ -99,6 +100,7 @@ libcdec_a_SOURCES = \
   aligner.cc \
   apply_models.cc \
   bottom_up_parser.cc \
+  bottom_up_parser-rs.cc \
   cdec.cc \
   cdec_ff.cc \
   csplit.cc \
diff --git a/decoder/bottom_up_parser-rs.cc b/decoder/bottom_up_parser-rs.cc
new file mode 100644
index 00000000..fbde7e24
--- /dev/null
+++ b/decoder/bottom_up_parser-rs.cc
@@ -0,0 +1,341 @@
+#include "bottom_up_parser-rs.h"
+
+#include <iostream>
+#include <map>
+
+#include "node_state_hash.h"
+#include "nt_span.h"
+#include "hg.h"
+#include "array2d.h"
+#include "tdict.h"
+#include "verbose.h"
+
+using namespace std;
+
+static WordID kEPS = 0;
+
+struct RSActiveItem;
+class RSChart {
+ public:
+  RSChart(const string& goal,
+               const vector<GrammarPtr>& grammars,
+               const Lattice& input,
+               Hypergraph* forest);
+  ~RSChart();
+
+  void AddToChart(const RSActiveItem& x, int i, int j);
+  void ConsumeTerminal(const RSActiveItem& x, int i, int j, int k);
+  void ConsumeNonTerminal(const RSActiveItem& x, int i, int j, int k);
+  bool Parse();
+  inline bool GoalFound() const { return goal_idx_ >= 0; }
+  inline int GetGoalIndex() const { return goal_idx_; }
+
+ private:
+  void ApplyRules(const int i,
+                  const int j,
+                  const RuleBin* rules,
+                  const Hypergraph::TailNodeVector& tail,
+                  const float lattice_cost);
+
+  // returns true if a new node was added to the chart
+  // false otherwise
+  bool ApplyRule(const int i,
+                 const int j,
+                 const TRulePtr& r,
+                 const Hypergraph::TailNodeVector& ant_nodes,
+                 const float lattice_cost);
+
+  void ApplyUnaryRules(const int i, const int j, const WordID& cat, unsigned nodeidx);
+  void TopoSortUnaries();
+
+  const vector<GrammarPtr>& grammars_;
+  const Lattice& input_;
+  Hypergraph* forest_;
+  Array2D<vector<int>> chart_;   // chart_(i,j) is the list of nodes (represented
+                                 // by their index in forest_->nodes_) derived spanning i,j
+  typedef map<int, int> Cat2NodeMap;
+  Array2D<Cat2NodeMap> nodemap_;
+  const WordID goal_cat_;    // category that is being searched for at [0,n]
+  TRulePtr goal_rule_;
+  int goal_idx_;             // index of goal node, if found
+  const int lc_fid_;
+  vector<TRulePtr> unaries_; // topologically sorted list of unary rules from all grammars
+
+  static WordID kGOAL;       // [Goal]
+};
+
+WordID RSChart::kGOAL = 0;
+
+// "a type-2 is identified by a trie node, an array of back-pointers to antecedent cells, and a span"
+struct RSActiveItem {
+  explicit RSActiveItem(const GrammarIter* g, int i) :
+    gptr_(g), ant_nodes_(), lattice_cost(0.0), i_(i) {}
+  void ExtendTerminal(int symbol, float src_cost) {
+    lattice_cost += src_cost;
+    if (symbol != kEPS)
+      gptr_ = gptr_->Extend(symbol);
+  }
+  void ExtendNonTerminal(const Hypergraph* hg, int node_index) {
+    gptr_ = gptr_->Extend(hg->nodes_[node_index].cat_);
+    ant_nodes_.push_back(node_index);
+  }
+  // returns false if the extension has failed
+  explicit operator bool() const {
+    return gptr_;
+  }
+  const GrammarIter* gptr_;
+  Hypergraph::TailNodeVector ant_nodes_;
+  float lattice_cost;  // TODO: use SparseVector<double> to encode input features
+  short i_;
+};
+
+// some notes on the implementation
+// "X" in Rico's Algorithm 2 roughly looks like it is just a pointer into a grammar
+// trie, but it is actually a full "dotted item" since it needs to contain the information
+// to build the hypergraph (i.e., it must remember the antecedent nodes and where they are,
+// also any information about the path costs).
+
+RSChart::RSChart(const string& goal,
+                           const vector<GrammarPtr>& grammars,
+                           const Lattice& input,
+                           Hypergraph* forest) :
+    grammars_(grammars),
+    input_(input),
+    forest_(forest),
+    chart_(input.size()+1, input.size()+1),
+    nodemap_(input.size()+1, input.size()+1),
+    goal_cat_(TD::Convert(goal) * -1),
+    goal_rule_(new TRule("[Goal] ||| [" + goal + "] ||| [1]")),
+    goal_idx_(-1),
+    lc_fid_(FD::Convert("LatticeCost")),
+    unaries_() {
+  for (unsigned i = 0; i < grammars_.size(); ++i) {
+    const vector<TRulePtr>& u = grammars_[i]->GetAllUnaryRules();
+    for (unsigned j = 0; j < u.size(); ++j)
+      unaries_.push_back(u[j]);
+  }
+  TopoSortUnaries();
+  if (!kGOAL) kGOAL = TD::Convert("Goal") * -1;
+  if (!SILENT) cerr << "  Goal category: [" << goal << ']' << endl;
+}
+
+static bool TopoSortVisit(int node, vector<TRulePtr>& u, const map<int, vector<TRulePtr> >& g, map<int, int>& mark) {
+  if (mark[node] == 1) {
+    cerr << "[ERROR] Unary rule cycle detected involving [" << TD::Convert(-node) << "]\n";
+    return false; // cycle detected
+  } else if (mark[node] == 2) {
+    return true; // already been 
+  }
+  mark[node] = 1;
+  const map<int, vector<TRulePtr> >::const_iterator nit = g.find(node);
+  if (nit != g.end()) {
+    const vector<TRulePtr>& edges = nit->second;
+    vector<bool> okay(edges.size(), true);
+    for (unsigned i = 0; i < edges.size(); ++i) {
+      okay[i] = TopoSortVisit(edges[i]->lhs_, u, g, mark);
+      if (!okay[i]) {
+        cerr << "[ERROR] Unary rule cycle detected, removing: " << edges[i]->AsString() << endl;
+      }
+   }
+    for (unsigned i = 0; i < edges.size(); ++i) {
+      if (okay[i]) u.push_back(edges[i]);
+      //if (okay[i]) cerr << "UNARY: " << edges[i]->AsString() << endl;
+    }
+  }
+  mark[node] = 2;
+  return true;
+}
+
+void RSChart::TopoSortUnaries() {
+  vector<TRulePtr> u(unaries_.size()); u.clear();
+  map<int, vector<TRulePtr> > g;
+  map<int, int> mark;
+  //cerr << "GOAL=" << TD::Convert(-goal_cat_) << endl;
+  mark[goal_cat_] = 2;
+  for (unsigned i = 0; i < unaries_.size(); ++i) {
+    //cerr << "Adding: " << unaries_[i]->AsString() << endl;
+    g[unaries_[i]->f()[0]].push_back(unaries_[i]);
+  }
+    //m[unaries_[i]->lhs_].push_back(unaries_[i]);
+  for (map<int, vector<TRulePtr> >::iterator it = g.begin(); it != g.end(); ++it) {
+    //cerr << "PROC: " << TD::Convert(-it->first) << endl;
+    if (mark[it->first] > 0) {
+      //cerr << "Already saw [" << TD::Convert(-it->first) << "]\n";
+    } else {
+      TopoSortVisit(it->first, u, g, mark);
+    }
+  }
+  unaries_.clear();
+  for (int i = u.size() - 1; i >= 0; --i)
+    unaries_.push_back(u[i]);
+}
+
+bool RSChart::ApplyRule(const int i,
+                        const int j,
+                        const TRulePtr& r,
+                        const Hypergraph::TailNodeVector& ant_nodes,
+                        const float lattice_cost) {
+  Hypergraph::Edge* new_edge = forest_->AddEdge(r, ant_nodes);
+  //cerr << i << " " << j << ": APPLYING RULE: " << r->AsString() << endl;
+  new_edge->prev_i_ = r->prev_i;
+  new_edge->prev_j_ = r->prev_j;
+  new_edge->i_ = i;
+  new_edge->j_ = j;
+  new_edge->feature_values_ = r->GetFeatureValues();
+  if (lattice_cost && lc_fid_)
+    new_edge->feature_values_.set_value(lc_fid_, lattice_cost);
+  Cat2NodeMap& c2n = nodemap_(i,j);
+  const bool is_goal = (r->GetLHS() == kGOAL);
+  const Cat2NodeMap::iterator ni = c2n.find(r->GetLHS());
+  Hypergraph::Node* node = NULL;
+  bool added_node = false;
+  if (ni == c2n.end()) {
+    //cerr << "(" << i << "," << j << ") => " << TD::Convert(-r->GetLHS()) << endl;
+    added_node = true;
+    node = forest_->AddNode(r->GetLHS());
+    c2n[r->GetLHS()] = node->id_;
+    if (is_goal) {
+      assert(goal_idx_ == -1);
+      goal_idx_ = node->id_;
+    } else {
+      chart_(i,j).push_back(node->id_);
+    }
+  } else {
+    node = &forest_->nodes_[ni->second];
+  }
+  forest_->ConnectEdgeToHeadNode(new_edge, node);
+  return added_node;
+}
+
+void RSChart::ApplyRules(const int i,
+                         const int j,
+                         const RuleBin* rules,
+                         const Hypergraph::TailNodeVector& tail,
+                         const float lattice_cost) {
+  const int n = rules->GetNumRules();
+  //cerr << i << " " << j << ": NUM RULES: " << n << endl;
+  for (int k = 0; k < n; ++k) {
+    //cerr << i << " " << j << ": R=" << rules->GetIthRule(k)->AsString() << endl;
+    TRulePtr rule = rules->GetIthRule(k);
+    // apply rule, and if we create a new node, apply any necessary
+    // unary rules
+    if (ApplyRule(i, j, rule, tail, lattice_cost)) {
+      unsigned nodeidx = nodemap_(i,j)[rule->lhs_];
+      ApplyUnaryRules(i, j, rule->lhs_, nodeidx);
+    }
+  }
+}
+
+void RSChart::ApplyUnaryRules(const int i, const int j, const WordID& cat, unsigned nodeidx) {
+  for (unsigned ri = 0; ri < unaries_.size(); ++ri) {
+    //cerr << "At (" << i << "," << j << "): applying " << unaries_[ri]->AsString() << endl;
+    if (unaries_[ri]->f()[0] == cat) {
+      //cerr << "  --MATCH\n";
+      WordID new_lhs = unaries_[ri]->GetLHS();
+      const Hypergraph::TailNodeVector ant(1, nodeidx);
+      if (ApplyRule(i, j, unaries_[ri], ant, 0)) {
+        //cerr << "(" << i << "," << j << ") " << TD::Convert(-cat) << " ---> " << TD::Convert(-new_lhs) << endl;
+        unsigned nodeidx = nodemap_(i,j)[new_lhs];
+        ApplyUnaryRules(i, j, new_lhs, nodeidx);
+      }
+    }
+  }
+}
+
+void RSChart::AddToChart(const RSActiveItem& x, int i, int j) {
+  // deal with completed rules
+  const RuleBin* rb = x.gptr_->GetRules();
+  if (rb) ApplyRules(i, j, rb, x.ant_nodes_, x.lattice_cost);
+
+  //cerr << "Rules applied ... looking for extensions to consume for span (" << i << "," << j << ")\n";
+  // continue looking for extensions of the rule to the right
+  for (unsigned k = j+1; k <= input_.size(); ++k) {
+    ConsumeTerminal(x, i, j, k);
+    ConsumeNonTerminal(x, i, j, k);
+  }
+}
+
+void RSChart::ConsumeTerminal(const RSActiveItem& x, int i, int j, int k) {
+  //cerr << "ConsumeT(" << i << "," << j << "," << k << "):\n";
+  
+  const unsigned check_edge_len = k - j;
+  // long-term TODO preindex this search so i->len->words is constant time rather than fan out
+  for (auto& in_edge : input_[j]) {
+    if (in_edge.dist2next == check_edge_len) {
+      //cerr << "  Found word spanning (" << j << "," << k << ") in input, symbol=" << TD::Convert(in_edge.label) << endl;
+      RSActiveItem copy = x;
+      copy.ExtendTerminal(in_edge.label, in_edge.cost);
+      if (copy) AddToChart(copy, i, k);
+    }
+  }
+}
+
+void RSChart::ConsumeNonTerminal(const RSActiveItem& x, int i, int j, int k) {
+  //cerr << "ConsumeNT(" << i << "," << j << "," << k << "):\n";
+  for (auto& nodeidx : chart_(j,k)) {
+    //cerr << "  Found completed NT in (" << j << "," << k << ") of type " << TD::Convert(-forest_->nodes_[nodeidx].cat_) << endl;
+    RSActiveItem copy = x;
+    copy.ExtendNonTerminal(forest_, nodeidx);
+    if (copy) AddToChart(copy, i, k);
+  }
+}
+
+bool RSChart::Parse() {
+  size_t in_size_2 = input_.size() * input_.size();
+  forest_->nodes_.reserve(in_size_2 * 2);
+  size_t res = min(static_cast<size_t>(2000000), static_cast<size_t>(in_size_2 * 1000));
+  forest_->edges_.reserve(res);
+  goal_idx_ = -1;
+  const int N = input_.size();
+  for (int i = N - 1; i >= 0; --i) {
+    for (int j = i + 1; j <= N; ++j) {
+      for (unsigned gi = 0; gi < grammars_.size(); ++gi) {
+        RSActiveItem item(grammars_[gi]->GetRoot(), i);
+        ConsumeTerminal(item, i, i, j);
+      }
+      for (unsigned gi = 0; gi < grammars_.size(); ++gi) {
+        RSActiveItem item(grammars_[gi]->GetRoot(), i);
+        ConsumeNonTerminal(item, i, i, j);
+      }
+    }
+  }
+
+  // look for goal
+  const vector<int>& dh = chart_(0, input_.size());
+  for (unsigned di = 0; di < dh.size(); ++di) {
+    const Hypergraph::Node& node = forest_->nodes_[dh[di]];
+    if (node.cat_ == goal_cat_) {
+      Hypergraph::TailNodeVector ant(1, node.id_);
+      ApplyRule(0, input_.size(), goal_rule_, ant, 0);
+    }
+  }
+  if (!SILENT) cerr << endl;
+
+  if (GoalFound())
+    forest_->PruneUnreachable(forest_->nodes_.size() - 1);
+  return GoalFound();
+}
+
+RSChart::~RSChart() {}
+
+RSExhaustiveBottomUpParser::RSExhaustiveBottomUpParser(
+    const string& goal_sym,
+    const vector<GrammarPtr>& grammars) :
+  goal_sym_(goal_sym),
+  grammars_(grammars) {}
+
+bool RSExhaustiveBottomUpParser::Parse(const Lattice& input,
+                                     Hypergraph* forest) const {
+  kEPS = TD::Convert("*EPS*");
+  RSChart chart(goal_sym_, grammars_, input, forest);
+  const bool result = chart.Parse();
+
+  if (result) {
+    for (auto& node : forest->nodes_) {
+      Span prev;
+      const Span s = forest->NodeSpan(node.id_, &prev);
+      node.node_hash = cdec::HashNode(node.cat_, s.l, s.r, prev.l, prev.r);
+    }
+  }
+  return result;
+}
diff --git a/decoder/bottom_up_parser-rs.h b/decoder/bottom_up_parser-rs.h
new file mode 100644
index 00000000..2e271e99
--- /dev/null
+++ b/decoder/bottom_up_parser-rs.h
@@ -0,0 +1,29 @@
+#ifndef RSBOTTOM_UP_PARSER_H_
+#define RSBOTTOM_UP_PARSER_H_
+
+#include <vector>
+#include <string>
+
+#include "lattice.h"
+#include "grammar.h"
+
+class Hypergraph;
+
+// implementation of Sennrich (2014) parser
+// http://aclweb.org/anthology/W/W14/W14-4011.pdf
+class RSExhaustiveBottomUpParser {
+ public:
+  RSExhaustiveBottomUpParser(const std::string& goal_sym,
+                             const std::vector<GrammarPtr>& grammars);
+
+  // returns true if goal reached spanning the full input
+  // forest contains the full (i.e., unpruned) parse forest
+  bool Parse(const Lattice& input,
+             Hypergraph* forest) const;
+
+ private:
+  const std::string goal_sym_;
+  const std::vector<GrammarPtr> grammars_;
+};
+
+#endif
-- 
cgit v1.2.3