From 9a48eeb5afbbece30b4be425c9f24649307d3ed6 Mon Sep 17 00:00:00 2001
From: Patrick Simianer <p@simianer.de>
Date: Mon, 5 May 2014 20:26:57 +0200
Subject: refactoring

---
 grammar.rb   |  24 +++++-----
 intersect.rb | 152 ++++++++++++++++++++++++++++-------------------------------
 2 files changed, 83 insertions(+), 93 deletions(-)

diff --git a/grammar.rb b/grammar.rb
index ac97fbd..b516912 100644
--- a/grammar.rb
+++ b/grammar.rb
@@ -14,22 +14,22 @@ class Terminal
 end
 
 class NonTerminal
-  attr_accessor :sym, :n
+  attr_accessor :sym, :idx
 
-  def initialize s, n=1
-    @sym = s
-    @n = n
+  def initialize sym, idx=0
+    @sym = sym
+    @idx = idx
   end
 
   def to_s
-    "NT<#{sym}>"
+    "NT<#{sym},#{idx}>"
   end
 end
 
 class Span
   attr_accessor :left, :right
 
-  def initialize left=-1, right=-1
+  def initialize left=nil, right=nil
     @left = left
     @right = right
   end
@@ -38,10 +38,9 @@ end
 class Rule
   attr_accessor :lhs, :rhs, :span
 
-  def initialize lhs=nil, rhs=nil, span=Span.new
+  def initialize lhs=nil, rhs=nil, span=nil
     @lhs = ''
     @rhs = []
-    @span = span
   end
 
   def to_s
@@ -69,7 +68,7 @@ class Rule
   def self.from_s s
     r = self.new
     r.from_s s
-    return r
+    r
   end
 end
 
@@ -78,15 +77,14 @@ class Grammar
 
   def initialize fn
     @rules = []
-    l = ReadFile.readlines_strip fn
-    l.each { |i|
-      @rules << Rule.from_s(i)
-    }
+    a = ReadFile.readlines_strip fn
+    a.each { |s| @rules << Rule.from_s(s) }
   end
 
   def to_s
     s = ''
     @rules.each { |r| s += r.to_s+"\n" }
+    s
   end
 end
 
diff --git a/intersect.rb b/intersect.rb
index c84a88c..42c4b92 100644
--- a/intersect.rb
+++ b/intersect.rb
@@ -5,16 +5,16 @@ require_relative './grammar.rb'
 
 class Chart
 
-  def initialize input
+  def initialize n
     @m = []
-    (input.size+1).times {
+    (n+1).times {
       _ = []
-      (input.size+1).times { _ << [] }
+      (n+1).times { _ << [] }
       @m << _
     }
   end
 
-  def at i,j
+  def at i, j
     return @m[i][j]
   end
 end
@@ -22,22 +22,19 @@ end
 class Item < Rule
   attr_accessor :lhs, :rhs, :span, :dot
 
-  def initialize rule, dot=-1
+  def initialize rule
     @lhs = rule.lhs.dup
     @rhs = rule.rhs.dup
     @span = Span.new rule.span.left, rule.span.right
-    @dot = dot
-    if rule.class==Item
-      @dot = rule.dot
-    end
+    @dot = rule.dot if rule.class==Item
   end
 
   def to_s
-    "#{lhs} -> #{rhs.map{|i|i.to_s}.insert(@dot,'*').join ' '} dot:#{@dot} a:#{arity} (#{@span.left}, #{@span.right})"
+    "#{lhs} -> #{rhs.map{|i|i.to_s}.insert(@dot,'*').join ' '} [dot@#{@dot}] [arity=#{arity}] (#{@span.left}, #{@span.right})"
   end
 end
 
-def visit n, depth, skip=0 
+def visit n, depth, skip=0
   (depth-skip).times { |i|
     i += skip
     0.upto(n-(i+1)) { |j|
@@ -46,60 +43,55 @@ def visit n, depth, skip=0
   }
 end
 
-# set-up
-g = Grammar.new 'grammar'
-input = "ich sah ein kleines haus".split.map { |i| Terminal.new i }
-n = input.size
-passive_chart = Chart.new input
-active_chart = Chart.new input
-
-# pre-fill passive chart w/ 0-arity rules
-g.rules.select { |r| r.rhs.first.class==Terminal }.each { |r|
-  input.each_index.select{ |j| input[j].w==r.rhs.first.w }.each { |j|
-    k = 1
-    if r.rhs.size > 1
-      z = r.rhs.index { |i| i.class==NonTerminal }
-      if z
-        z -= 1
-      else
-        z = r.rhs.size-1
+def init active_chart, passive_chart, grammar, input, n
+  # pre-fill passive chart w/ 0-arity rules
+  s = grammar.rules.select { |r| r.rhs.first.class==Terminal }
+  s.each { |r|
+    input.each_index.select { |j| input[j].w==r.rhs.first.w }.each { |j|
+      k = 1
+      if r.rhs.size > 1
+        z = r.rhs.index { |i| i.class==NonTerminal }
+        if z
+          z -= 1
+        else
+          z = r.rhs.size-1
+        end
+        slice = input[j..j+z].map { |i| i.w }
+        if slice == r.rhs[0..z].map { |i| i.w }
+          k = z+1
+        else
+          next
+        end
       end
-      slice = input[j..j+z].map { |i| i.w }
-      if slice == r.rhs[0..z].map { |i| i.w }
-        k = z+1
+      if k == r.rhs.size
+        passive_chart.at(j,j+k) << Item.new(r)
+        passive_chart.at(j,j+k).last.span.left = j
+        passive_chart.at(j,j+k).last.span.right = j+k
+        passive_chart.at(j,j+k).last.dot = k
       else
-        next
+        (j+k).upto(input.size) { |l|
+        active_chart.at(j,l) << Item.new(r)
+        active_chart.at(j,l).last.span.left = j
+        active_chart.at(j,l).last.span.right = j+k
+        active_chart.at(j,l).last.dot = k
+        }
       end
-    end
-    if k == r.rhs.size
-      passive_chart.at(j,j+k) << Item.new(r)
-      passive_chart.at(j,j+k).last.span.left = j
-      passive_chart.at(j,j+k).last.span.right = j+k
-      passive_chart.at(j,j+k).last.dot = k
-    else
-      (j+k).upto(input.size) { |l|
-      active_chart.at(j,l) << Item.new(r)
-      active_chart.at(j,l).last.span.left = j
-      active_chart.at(j,l).last.span.right = j+k
-      active_chart.at(j,l).last.dot = k
-      }
-    end
+    }
   }
-}
-
-# seed active chart
-s = g.rules.reject { |r| r.rhs.first.class!=NonTerminal }
-visit(n, n, 1) { |i,j|
-  s.each { |r|
-    active_chart.at(i,j) << Item.new(r)
-    active_chart.at(i,j).last.span.left = i
-    active_chart.at(i,j).last.span.right = i
-    active_chart.at(i,j).last.dot = 0
+  # seed active chart
+  s = grammar.rules.reject { |r| r.rhs.first.class!=NonTerminal }
+  visit(n, n, 1) { |i,j|
+    s.each { |r|
+      active_chart.at(i,j) << Item.new(r)
+      active_chart.at(i,j).last.span.left = i
+      active_chart.at(i,j).last.span.right = i
+      active_chart.at(i,j).last.dot = 0
+    }
   }
-}
+end
 
 def scan item, passive_chart, input, i, j
-  while item.rhs[item.dot].class == Terminal 
+  while item.rhs[item.dot].class == Terminal
     if item.rhs[item.dot].w == input[item.span.left+item.dot].w
       item.dot += 1
       item.span.right += 1
@@ -111,38 +103,38 @@ def scan item, passive_chart, input, i, j
   end
 end
 
-# parse
 def parse i, j, sz, active_chart, passive_chart, g, input
-  puts "| #{i},#{j}"
   1.upto(sz) { |span|
     break if span==(j-i)
     i.upto(j-span) { |k|
-    puts "  #{k},#{k+span} (##{span})"
-    # complete 
-    active_chart.at(i,j).each { |active_item|
-      passive_chart.at(k, k+span).each { |passive_item|
-        if active_item.rhs[active_item.dot].class==NonTerminal && passive_item.lhs.sym == active_item.rhs[active_item.dot].sym
-          next if not active_item.span.right==passive_item.span.left
-          active_item.span.right = passive_item.span.right
-          active_item.dot += 1
-          scan active_item, passive_chart, input, i, j
-          if active_item.dot == active_item.rhs.size
-            passive_chart.at(i,j) << Item.new(active_item)
+      active_chart.at(i,j).each { |active_item|
+        passive_chart.at(k, k+span).each { |passive_item|
+          if active_item.rhs[active_item.dot].class==NonTerminal && passive_item.lhs.sym == active_item.rhs[active_item.dot].sym
+            next if not active_item.span.right==passive_item.span.left
+            active_item.span.right = passive_item.span.right
+            active_item.dot += 1
+            scan active_item, passive_chart, input, i, j
+            if active_item.dot == active_item.rhs.size
+              passive_chart.at(i,j) << Item.new(active_item)
+            end
           end
-        end
+        }
       }
     }
   }
-  }
 end
 
-visit(n, n, 1)  { |i,j|
-   parse i, j, n, active_chart, passive_chart, g, input
-}
+def main
+  g = Grammar.new 'grammar'
+  input = "ich sah ein kleines haus".split.map { |i| Terminal.new i }
+  n = input.size
+  passive_chart = Chart.new n
+  active_chart = Chart.new n
+  init active_chart, passive_chart, g, input, n
+  visit(n, n, 1)  { |i,j| parse i, j, n, active_chart, passive_chart, g, input }
+  passive_chart.at(0,5).each { |item| puts item.to_s }
+end
 
 
-puts "---"
-passive_chart.at(0,5).each { |item|
-  puts item.to_s
-}
+main
 
-- 
cgit v1.2.3