algorithms: shift reduce dependency parsing

1 files changed, 127 insertions, 0 deletions

diff --git a/algorithms/shift_reduce_parser.cc b/algorithms/shift_reduce_parser.cc
new file mode 100644
index 0000000..563c8e4
--- /dev/null
+++ b/algorithms/shift_reduce_parser.cc
@@ -0,0 +1,127 @@
+#include <vector>
+#include <map>
+#include <utility>
+#include <vector>
+#include <iostream>
+
+
+using namespace std;
+
+typedef std::pair<char,char> Key;
+
+struct E
+{
+  vector<char> h;
+
+  Key get() {
+    char second = h.back();
+    h.pop_back();
+    char first = h.back();
+    h.pop_back();
+    return make_pair(first, second);
+  }
+  bool good() { return h.size() > 1; }
+  char add(char c) { h.push_back(c); }
+};
+
+struct P
+{
+  std::map<Key, char> actionTable_;
+
+  P()
+  {
+    createActionTable();
+  }
+
+  void r(E& e)
+  {
+    cout << "before: ";
+    for (auto it: e.h)
+      cout << it;
+    cout << endl;
+    bool stop = false;
+    while (e.good() && !stop) {
+      pair<char,char> k = e.get();
+      char action = actionTable_[k];
+      switch (action) {
+        case 'L':
+          e.add('f');
+          break;
+        case 'R':
+          e.add('f');
+          stop = true;
+          break;
+        case 'S':
+          e.add(k.first);
+          e.add(k.second);
+          stop = true;
+          break;
+        case 'I':
+        default:
+          e.add('u');
+          stop = true;
+          break;
+      }
+    }
+    cout << " after: ";
+    for (auto it: e.h)
+      cout << it;
+    cout << endl;
+    cout << "--" << endl;
+  }
+
+  void createActionTable()
+  {
+    // u ->
+    actionTable_[Key('u','u')] = 'S'; // Shift
+    actionTable_[Key('u','f')] = 'S';
+    actionTable_[Key('u','l')] = 'S';
+    actionTable_[Key('u','r')] = 'I'; // Illegal
+
+    // f ->
+    actionTable_[Key('f','f')] = 'S'; // ambiguous
+    actionTable_[Key('f','l')] = 'S';
+    actionTable_[Key('f','r')] = 'R'; // Right-reduce
+
+    // l ->
+    actionTable_[Key('l','f')] = 'L'; // Left-reduce
+    actionTable_[Key('l','l')] = 'S';
+    actionTable_[Key('l','r')] = 'I';
+
+    // r ->
+    actionTable_[Key('r','f')] = 'I';
+    actionTable_[Key('r','l')] = 'I';
+    actionTable_[Key('r','r')] = 'I';
+  }
+};
+
+
+int main(void)
+{
+  E e;
+  P p;
+
+  /*e.add('u');
+  p.r(e);
+
+  e.add('l');
+  p.r(e);
+
+  e.add('l');
+  p.r(e);
+
+  e.add('f');
+  p.r(e);
+
+  e.add('r');
+  p.r(e);*/
+
+ string s("frllllfrlllllllf");
+ for (auto it: s) {
+   e.add(it);
+   p.r(e);
+ }
+
+  return 0;
+}
+