| blob | 363e6d9c01db3ce84b145d65dfb592da757cb94a |
1 #!/usr/bin/env ruby
3 # Copyright (c) 2008 Tom Adams <[email protected]>
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.
17 require 'set'
18 require 'logger'
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
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
75 class Parser
76 def initialize(grammar,log=Logger.new(STDERR))
77 @grammar = grammar
78 @log = log
79 end
81 def parse(text)
82 active = Set.new
83 inactive = Set.new
84 agenda = []
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
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
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
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
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
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
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
167 if __FILE__ == $0
169 log = Logger.new(STDERR)
170 log.level = Logger::DEBUG
171 log.formatter = lambda {|sev,time,pname,msg| "#{sev}: #{msg}\n"}
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]
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')]]}
195 p = Parser.new(grammar,log)
196 q = p.parse(%w{time flies like an arrow})
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