algorithms: shift reduce dependency parsing

1 files changed, 101 insertions, 0 deletions

diff --git a/algorithms/shift_reduce_parser.rb b/algorithms/shift_reduce_parser.rb
new file mode 100755
index 0000000..948d8c1
--- /dev/null
+++ b/algorithms/shift_reduce_parser.rb
@@ -0,0 +1,101 @@
+#!/usr/bin/env ruby
+
+
+class Item
+  attr_accessor :word, :type, :link
+  def initialize word, type
+    @word = word
+    @type = type
+    @link = nil
+  end
+end
+
+class MockShiftReduceParser
+  attr_accessor :state
+
+  def initialize
+    @state = nil
+    
+    @a = {}
+    @a[nil] = {}
+    @a[nil][nil] = 'S'
+    @a[nil]['f'] = 'S'
+    @a[nil]['l'] = 'S'
+    @a[nil]['r'] = 'illegal'
+
+    @a['f'] = {}
+    @a['f']['f'] = 'S' # FIXME conflict
+    @a['f']['l'] = 'S'
+    @a['f']['r'] = 'R'
+
+    @a['l'] = {}
+    @a['l']['f'] = 'L'
+    @a['l']['l'] = 'S'
+    @a['l']['r'] = 'illegal'
+
+    @a['r'] = {}
+    @a['r']['f'] = 'illegal'
+    @a['r']['l'] = 'illegal'
+    @a['r']['r'] = 'illegal'
+  end
+
+  def advance type
+    if    !@state 
+      @state = type
+      puts "-/- -> S -> #{@state}"
+      return
+    end
+    action = @a[@state][type]
+    prev_state = @state
+    if action == 'S'
+      @state = type
+    elsif action == 'L' or action == 'R'
+      @state = 'f'
+    end
+    puts "#{prev_state}/#{type} -> #{action} -> #{@state}"
+
+    return action
+  end
+end
+
+
+parser = MockShiftReduceParser.new
+
+items = []
+head = nil
+stack = []
+
+while line = STDIN.gets
+  word, type = line.split
+  item = Item.new word, type
+  items << item
+  stack << item
+
+  head = item if !head
+
+  action = parser.advance item.type
+  if action == "S"
+    head = item
+  elsif action == "R"
+    _ = stack.pop
+    _.link = head
+  elsif action == "L"
+    head = item
+    puts stack.size
+    del = []
+    stack.each_with_index { |i,j|
+      if i.type == 'l'
+        i.link = head
+        del << j
+      end
+    }
+    del.reverse.each { |d| stack.delete_at(d) }
+    puts stack.size
+  end
+end
+
+stack.each { |i| i.link = head }
+
+puts "---"
+items.each { |j| if j.link then puts "#{j.word} #{j.link.word}" else puts "#{j.word} ?" end }
+