chart_parser.rb

   1 #!/usr/bin/env ruby
   2
   3 # Copyright (c) 2008 Tom Adams <tom@holizz.com>
   4 #
   5 # Permission to use, copy, modify, and distribute this software for any
   6 # purpose with or without fee is hereby granted, provided that the above
   7 # copyright notice and this permission notice appear in all copies.
   8 #
   9 # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  10 # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11 # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  12 # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13 # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14 # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  15 # OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16
  17 require 'set'
  18 require 'logger'
  19
  20 class Terminal
  21   attr_accessor :token
  22   alias_method :to_s, :token
  23   alias_method :to_tree, :token
  24   def initialize(token)
  25     @token=token
  26   end
  27   def eql?(other)
  28     other.is_a?(Terminal) and other.token==@token
  29   end
  30   alias_method :==, :eql?
  31   alias_method :===, :eql?
  32 end
  33
  34 class Edge
  35   attr_accessor :i,:j,:category,:contents,:sub
  36   def initialize(i,j,category,contents,sub=[])
  37     @i=i
  38     @j=j
  39     @category=category
  40     @contents=contents
  41     @sub=sub
  42   end
  43   def eql?(other)
  44     other.is_a? Edge and hash == other.hash
  45   end
  46   alias_method :==, :eql?
  47   alias_method :===, :eql?
  48   def hash
  49     [@i,@j,@category,@contents,@sub].hash
  50   end
  51   def to_s
  52     "#{active? ? 'A' : 'I'}"+
  53     "<#{@i},#{@j},#{@category},[%s],[%s]>" % [@contents.join(', '),
  54                                               @sub.join(', ')]
  55   end
  56   def active?
  57     unfound and unfound.length != 0
  58   end
  59   def unfound
  60     @contents[@sub.length..-1]
  61   end
  62   def nextWord
  63     unfound[0]
  64   end
  65   def to_tree
  66     #raise Exception if active?
  67     unless @sub.empty?
  68       [@category, @sub.map{|e|e.to_tree}]
  69     else
  70       [@category, @contents.map{|e|e.to_tree}]
  71     end
  72   end
  73 end
  74
  75 class Parser
  76   def initialize(grammar,log=Logger.new(STDERR))
  77     @grammar = grammar
  78     @log = log
  79   end
  80
  81   def parse(text)
  82     active = Set.new
  83     inactive = Set.new
  84     agenda = []
  85
  86     # Initialise agenda with known words
  87     text.each_with_index do |word,n|
  88       cat = nil
  89       @grammar.each do |cat,rule|
  90         for r in rule
  91           if r == [Terminal.new(word)]
  92             agenda << Edge.new(n,n+1,cat,[],[Terminal.new(word)])
  93           end
  94         end
  95       end
  96     end
  97
  98     until agenda.empty?
  99       # Move one from agenda to chart
 100       edge = agenda.delete_at(0)
 101       if edge.active?
 102         active << edge
 103       else
 104         inactive << edge
 105       end
 106       # Add to the agenda from edges in the chart
 107       new_edges(active,inactive) do |edge|
 108         unless agenda.include?(edge) or (active+inactive).include?(edge)
 109           @log.debug("new_edges adding: #{edge}")
 110           agenda << edge
 111         end
 112       end
 113
 114       agenda.each do |edge|
 115         @log.debug("agenda: #{edge}")
 116       end
 117       (active+inactive).each do |edge|
 118         @log.debug("chart: #{edge}")
 119       end
 120       #gets
 121     end
 122
 123     # Return all spanning parses as a Set
 124     inactive.select do |edge|
 125       edge.i == 0 and edge.j == text.length
 126     end.map do |edge|
 127       edge.to_tree
 128     end.to_set
 129   end
 130
 131   def new_edges(active,inactive)
 132     bottom_up(active,inactive) do |edge|
 133       yield edge
 134     end
 135     fundamental(active,inactive) do |edge|
 136       yield edge
 137     end
 138   end
 139
 140   def bottom_up(active,inactive)
 141     inactive.each do |edge|
 142       @grammar.each do |r,w|
 143         w.each do |ww|
 144           if ww[0] == edge.category
 145             newedge = Edge.new(edge.i,edge.i,r,ww)
 146             @log.debug("bottom_up: via #{edge} found #{newedge}")
 147             yield newedge
 148           end
 149         end
 150       end
 151     end
 152   end
 153
 154   def fundamental(active,inactive)
 155     for a in active
 156       for i in inactive
 157         if a.j == i.i and a.nextWord == i.category
 158           newedge = Edge.new(a.i,i.j,a.category,a.contents,a.sub+[i])
 159           @log.debug("fundamental: via #{a} and #{i} found #{newedge}")
 160           yield newedge
 161         end
 162       end
 163     end
 164   end
 165 end
 166
 167 if __FILE__ == $0
 168
 169   log = Logger.new(STDERR)
 170   log.level = Logger::DEBUG
 171   log.formatter = lambda {|sev,time,pname,msg| "#{sev}: #{msg}\n"}
 172
 173   shouldBe = Set.new([["S", [["NP", [["NP", ["time"]], ["NP", ["flies"]]]],
 174   ["VP", [["V", ["like"]], ["NP", [["Det", ["an"]], ["NP", ["arrow"]]]]]]]],
 175   ["S", [["NP", ["time"]], ["VP", [["V", ["flies"]], ["PP", [["PR", ["like"]],
 176   ["NP", [["Det", ["an"]], ["NP", ["arrow"]]]]]]]]]]])
 177   # time flies like an arrow
 178   # -> [time] [flies] [like an arrow]
 179   # -> [time flies] [like] [an arrow]
 180
 181   grammar = {'S'=>[%w{NP VP}],
 182              'VP'=>[%w{V NP},
 183                     %w{V PP}],
 184              'NP'=>[[Terminal.new('time')],
 185                     [Terminal.new('flies')],
 186                     [Terminal.new('arrow')],
 187                     %w{Det NP},
 188                     %w{NP NP}],
 189              'PP'=>[%w{PR NP}],
 190              'PR'=>[[Terminal.new('like')]],
 191              'Det'=>[[Terminal.new('an')]],
 192              'V'=>[[Terminal.new('like')],
 193                    [Terminal.new('flies')]]}
 194
 195   p = Parser.new(grammar,log)
 196   q = p.parse(%w{time flies like an arrow})
 197
 198   if q == shouldBe
 199     puts "Test succeeded!"
 200     puts "Output was #{q.inspect}"
 201   else
 202     puts "Test failed!"
 203     puts "Should have been #{shouldBe.inspect}"
 204     puts "But was actually #{q.inspect}"
 205   end
 206 end