diff options
| -rw-r--r-- | grammar.rb | 24 | ||||
| -rw-r--r-- | intersect.rb | 152 |
2 files changed, 83 insertions, 93 deletions
@@ -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 |