diff options
| -rw-r--r-- | example/toy/grammar | 10 | ||||
| -rw-r--r-- | grammar.rb | 3 | ||||
| -rw-r--r-- | parse.rb | 36 |
3 files changed, 26 insertions, 23 deletions
diff --git a/example/toy/grammar b/example/toy/grammar index 81d41c7..313a4f2 100644 --- a/example/toy/grammar +++ b/example/toy/grammar @@ -1,11 +1,11 @@ -[S] ||| [NP,1] [VP,2] ||| [1] [2] ||| logp=0 +[S] ||| [NP,1] [VP,2] ||| [NP,1] [VP,2] ||| logp=0 [NP] ||| ich ||| i ||| logp=-0.5 use_i=1.0 -[NP] ||| ein [NN,1] ||| a [1] ||| logp=0 use_a=1.0 +[NP] ||| ein [NN,1] ||| a [NN,1] ||| logp=0 use_a=1.0 [NN] ||| kleines haus ||| small house ||| logp=0 use_house=1 [NN] ||| kleines haus ||| little house ||| logp=0 use_house=1 -[NN] ||| [JJ,1] haus ||| [1] house ||| logp=0 use_house=1 -[NN] ||| [JJ,1] haus ||| [1] shell ||| logp=0 use_shell=1 +[NN] ||| [JJ,1] haus ||| [JJ,1] house ||| logp=0 use_house=1 +[NN] ||| [JJ,1] haus ||| [JJ,1] shell ||| logp=0 use_shell=1 [JJ] ||| kleines ||| small ||| logp=0 use_small=1.0 [JJ] ||| kleines ||| little ||| logp=0 use_little=1.0 -[VP] ||| [V,1] [NP,2] ||| [1] [2] ||| logp=0 +[VP] ||| [V,1] [NP,2] ||| [V,1] [NP,2] ||| logp=0 [V] ||| sah ||| saw ||| logp=-0.25 use_saw=1.0 @@ -33,7 +33,8 @@ class NT end def to_s - "NT<#{@symbol},#{@index}>" + return "NT<#{@symbol},#{@index}>" if @index>=0 + return "NT<#{@symbol}>" end end @@ -30,14 +30,18 @@ class Chart end end +Span = Struct.new(:left, :right) + class Item < Grammar::Rule - attr_accessor :spans, :dot + attr_accessor :left, :right, :tail_spans, :dot def initialize rule_or_item, left, right, dot @lhs = Grammar::NT.new(rule_or_item.lhs.symbol, rule_or_item.lhs.index) - @spans = {} - @spans[0] = [left, right] + @left = left + @right = right @rhs = [] + @tail_spans = {} + @map = (rule_or_item.map ? rule_or_item.map.dup : []) rule_or_item.rhs.each_with_index { |x,i| if x.class == Grammar::T @rhs << Grammar::T.new(x.word) @@ -45,9 +49,9 @@ class Item < Grammar::Rule if x.class == Grammar::NT @rhs << Grammar::NT.new(x.symbol, x.index) begin - @spans[i] = rule_or_item.spans[i].dup + @tail_spans[i] = rule_or_item.tail_spans[i].dup rescue - @spans[i] = [-1, -1] + @tail_spans[i] = Span.new(-1, -1) end end } @@ -56,7 +60,7 @@ class Item < Grammar::Rule end def to_s - "#{lhs} -> #{rhs.map{|i|i.to_s}.insert(@dot,'*').join ' '} [dot@#{@dot}] [arity=#{arity}] (#{@spans[0][0]}, #{@spans[0][1]}) ||| #{@target.map{|x|x.to_s}.join ' '}" + "(#{@left}, #{@right}) [#{tail_spans.map{|k,v| k.to_s+'('+v.left.to_s+','+v.right.to_s+')'}.join ' '}] {#{@map.to_s.delete('[]')}} #{lhs} -> #{rhs.map{|i|i.to_s}.insert(@dot,'*').join ' '} [dot@#{@dot}] ||| #{@target.map{|x|x.to_s}.join ' '}" end end @@ -72,10 +76,10 @@ end def scan item, input, limit, passive_chart while item.rhs[item.dot].class == Grammar::T - return false if item.spans[0][1]==limit - if item.rhs[item.dot].word == input[item.spans[0][1]] + return false if item.right==limit + if item.rhs[item.dot].word == input[item.right] item.dot += 1 - item.spans[0][1] += 1 + item.right += 1 else return false end @@ -116,19 +120,18 @@ def parse input, n, active_chart, passive_chart, grammar advanced = false visit(1, i, j, 1) { |k,l| if passive_chart.has active_item.rhs[active_item.dot].symbol, k, l - if k == active_item.spans[0][1] - new_item = Item.new active_item, active_item.spans[0][0], l, active_item.dot+1 - new_item.spans[new_item.dot-1][0] = k - new_item.spans[new_item.dot-1][1] = l + if k == active_item.right + new_item = Item.new active_item, active_item.left, l, active_item.dot+1 + new_item.tail_spans[new_item.dot-1] = Span.new(k,l) if scan new_item, input, j, passive_chart if new_item.dot == new_item.rhs.size - if new_item.spans[0][0] == i && new_item.spans[0][1] == j + if new_item.left == i && new_item.right == j new_symbols << new_item.lhs.symbol if !new_symbols.include? new_item.lhs.symbol passive_chart.add new_item, i, j advanced = true end else - if new_item.spans[0][1]+(new_item.rhs.size-(new_item.dot)) <= j + if new_item.right+(new_item.rhs.size-(new_item.dot)) <= j active_chart.at(i,j) << new_item advanced = true end @@ -149,8 +152,7 @@ def parse input, n, active_chart, passive_chart, grammar next if active_item.rhs[active_item.dot].class!=Grammar::NT if active_item.rhs[active_item.dot].symbol == s new_item = Item.new active_item, i, j, active_item.dot+1 - new_item.spans[new_item.dot-1][0] = i - new_item.spans[new_item.dot-1][1] = j + new_item.tail_spans[new_item.dot-1] = Span.new(i,j) if new_item.dot==new_item.rhs.size new_symbols << new_item.lhs.symbol if !new_symbols.include? new_item.lhs.symbol passive_chart.add new_item, i, j |