diff options
Diffstat (limited to 'intersect.rb')
| -rw-r--r-- | intersect.rb | 209 |
1 files changed, 0 insertions, 209 deletions
diff --git a/intersect.rb b/intersect.rb deleted file mode 100644 index 64b9696..0000000 --- a/intersect.rb +++ /dev/null @@ -1,209 +0,0 @@ -#!/usr/bin/env ruby - -require_relative './grammar.rb' -STDOUT.sync = true - - -class Chart - - def initialize n - @m = [] - (n+1).times { - _ = [] - (n+1).times { _ << [] } - @m << _ - } - end - - def at i, j - @m[i][j] - end - - def add rule_or_item, i, j, right, dot=0 - item = Item.new(rule_or_item) - item.span.left = i - item.span.right = right - item.dot = dot - at(i, j) << item - end -end - -class Span - attr_accessor :left, :right - - def initialize left=nil, right=nil - @left = left - @right = right - end -end - -class Item < Rule - attr_accessor :lhs, :rhs, :span, :dot - - def initialize rule_or_item - @lhs = rule_or_item.lhs.dup - @rhs = rule_or_item.rhs.dup - if rule_or_item.class == Item - @span = Span.new rule_or_item.span.left, rule_or_item.span.right - @dot = rule_or_item.dot - else - @span = Span.new - @dot = 0 - end - end - - def to_s - "#{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 - (depth-skip).times { |i| - i += skip - 0.upto(n-(i+1)) { |j| - yield j, j+i+1 - } - } -end - -def init active_chart, passive_chart, grammar, input, n - # pre-fill passive chart w/ 0-arity rules - #grammar.rules.select { |r| r.rhs.first.class==T }.each { |r| - grammar.rules.select { |r| r.arity==0 }.each { |r| - input.each_index.select { |i| input[i].word==r.rhs.first.word }.each { |j| - k = 1 - if r.rhs.size > 1 - z = r.rhs.index { |i| i.class==NT } - if z - z -= 1 - else - z = r.rhs.size-1 - end - if input[j..j+z].map { |i| i.word } == r.rhs[0..z].map { |i| i.word } - k = z+1 - else - next - end - end - if k == r.rhs.size - passive_chart.add(r, j, j+k, j+k, k) - #else - # (j+k).upto(n) { |l| active_chart.add r, j, l, j+k, k } - end - } - } - # seed active chart - #s = grammar.rules.reject { |r| r.rhs.first.class!=NT } - #visit(n, n, 1) { |i,j| - # s.each { |r| active_chart.add(r, i, j, i) } - #} -end - -def scan item, passive_chart, input - while item.rhs[item.dot].class == T - break if item.span.right > input.size-1 - if item.rhs[item.dot].word == input[item.span.right].word - item.dot += 1 - item.span.right += 1 - break if item.dot == item.rhs.size - else - break - end - end -end - -def parse i, j, n, active_chart, passive_chart, input, grammar - grammar.rules.each { |r| - if r.rhs.first.class==T&&r.rhs.first.word==input[i].word - new_item = Item.new r - scan new_item, passive_chart, input - end - } - #active_chart.at(i,j).each { |active_item| - 1.upto(n) { |span| - break if span==(j-i) - i.upto(j-span) { |k| - STDERR.write " #{k},#{k+span}\n" - <<-DOC - passive_chart.at(k, k+span).each { |passive_item| - if active_item.rhs[active_item.dot].class==NT && passive_item.lhs.symbol == active_item.rhs[active_item.dot].symbol - next if not active_item.span.right==passive_item.span.left - new_item = Item.new active_item - new_item.span.right = passive_item.span.right - new_item.dot += 1 - scan new_item, passive_chart, input - if new_item.dot == new_item.rhs.size - passive_chart.at(i,j) << new_item if new_item.span.left==i&&new_item.span.right==j - else - # item is dead unless it has an NT to fill - active_chart.at(i,j) << new_item if new_item.span.left==i&&new_item.rhs[new_item.dot].class==NT - end - end - } - DOC - } - } - #} - # self-filling - to_add_active = [] - to_add_passive = [] - passive_chart.at(i,j).each { |passive_item| - active_chart.at(i,j).each { |active_item| - next if active_item.rhs[active_item.dot].class!=NT - if passive_item.lhs.symbol == active_item.rhs[active_item.dot].symbol - next if not active_item.span.right==passive_item.span.left - new_item = Item.new active_item - new_item.span.right = passive_item.span.right - new_item.dot += 1 - scan new_item, passive_chart, input - if new_item.dot == new_item.rhs.size - to_add_passive << new_item if new_item.span.left==i&&new_item.span.right==j - else - to_add_active << new_item - end - end - } - } - to_add_active.each { |item| active_chart.at(i,j) << item } - to_add_passive.each { |item| passive_chart.at(i,j) << item } -end - -def preprocess s - s.split.map { |i| T.new i } -end - -def main - input = preprocess 'ich sah ein kleines haus' - #input = preprocess 'lebensmittel schuld an europäischer inflation' - #input = preprocess 'offizielle prognosen sind von nur 3 prozent ausgegangen , meldete bloomberg .' - n = input.size - - puts 'reading grammar' - g = Grammar.new 'example/grammar' - #g = Grammar.new 'example/grammar.x' - #g = Grammar.new 'example/grammar.3.gz' # 4th segment of newstest2008 - - puts 'adding glue rules' - g.add_glue_rules - - #puts 'adding pass-through rules' - #g.add_pass_through_rules input - - puts 'initializing charts' - passive_chart = Chart.new n - active_chart = Chart.new n - init active_chart, passive_chart, g, input, n - - puts 'parsing' - visit(n, n, 1) { |i,j| - STDERR.write "span (#{i}, #{j})\n" - parse i, j, n, active_chart, passive_chart, input, g - } - - #puts "---\npassive chart" - #visit(n, n, 0) { |i,j| puts "#{i},#{j}"; passive_chart.at(i,j).each { |item| puts ' '+item.to_s if item.span.left==i&&item.span.right==j }; puts } -end - - -main - |