-
Notifications
You must be signed in to change notification settings - Fork 0
/
parser_transitions.py
257 lines (215 loc) · 11.8 KB
/
parser_transitions.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Galileo Steinberg
CS115B Spring 2024 Homework 6
Neural Transition-Based Dependency Parsing
Adapted from:
CS224N 2019-20: Homework 3
parser_transitions.py: Algorithms for completing partial parsess.
Sahil Chopra <schopra8@stanford.edu>
Haoshen Hong <haoshen@stanford.edu>
"""
import sys
class PartialParse(object):
def __init__(self, sentence):
"""Initializes this partial parse.
@param sentence (list of str): The sentence to be parsed as a list of words.
Your code should not modify the sentence.
"""
# The sentence being parsed is kept for bookkeeping purposes. Do not alter it in your code.
self.sentence = sentence
### YOUR CODE HERE (3 Lines)
### Your code should initialize the following fields:
### self.stack: The current stack represented as a list with the top of the stack as the
### last element of the list.
self.stack = ["ROOT"]
### self.buffer: The current buffer represented as a list with the first item on the
### buffer as the first item of the list
self.buffer = list(sentence)
### self.dependencies: The list of dependencies produced so far. Represented as a list of
### tuples where each tuple is of the form (head, dependent).
### Order for this list doesn't matter.
###
self.dependencies = []
### Note: The root token should be represented with the string "ROOT"
### END YOUR CODE
def __repr__(self):
return f"PartialParse(Stack: {self.stack}; Buffer: {self.buffer}; Deps: {self.dependencies})"
def parse_step(self, transition):
"""Performs a single parse step by applying the given transition to this partial parse
@param transition (str): A string that equals "S", "LA", or "RA" representing the shift,
left-arc, and right-arc transitions. You can assume the provided
transition is a legal transition.
"""
### YOUR CODE HERE (~7-10 Lines)
### TODO:
### Implement a single parsing step, i.e. the logic for the following as
### described in the pdf handout:
### 1. Shift
### 2. Left Arc
### 3. Right Arc
if transition == "S":
self.stack.append(self.buffer.pop(0))
elif transition == "LA":
self.dependencies.append((self.stack[-1], self.stack[-2]))
self.stack.pop(-2)
elif transition == "RA":
self.dependencies.append((self.stack[-2], self.stack[-1]))
self.stack.pop()
### END YOUR CODE
def parse(self, transitions):
"""Applies the provided transitions to this PartialParse
@param transitions (list of str): The list of transitions in the order they should be applied
@return dependencies (list of string tuples): The list of dependencies produced when
parsing the sentence. Represented as a list of
tuples where each tuple is of the form (head, dependent).
"""
for transition in transitions:
self.parse_step(transition)
return self.dependencies
def minibatch_parse(sentences, model, batch_size):
"""Parses a list of sentences in minibatches using a model.
@param sentences (list of list of str): A list of sentences to be parsed
(each sentence is a list of words and each word is of type string)
@param model (ParserModel): The model that makes parsing decisions. It is assumed to have a function
model.predict(partial_parses) that takes in a list of PartialParses as input and
returns a list of transitions predicted for each parse. That is, after calling
transitions = model.predict(partial_parses)
transitions[i] will be the next transition to apply to partial_parses[i].
@param batch_size (int): The number of PartialParses to include in each minibatch
@return dependencies (list of dependency lists): A list where each element is the dependencies
list for a parsed sentence. Ordering should be the
same as in sentences (i.e., dependencies[i] should
contain the parse for sentences[i]).
"""
dependencies = []
### YOUR CODE HERE (~8-10 Lines)
### TODO:
### Implement the minibatch parse algorithm as described in the pdf handout
###
### Note: A shallow copy (as denoted in the PDF) can be made with the "=" sign in python, e.g.
### unfinished_parses = partial_parses[:].
### Here `unfinished_parses` is a shallow copy of `partial_parses`.
### In Python, a shallow copied list like `unfinished_parses` does not contain new instances
### of the object stored in `partial_parses`. Rather both lists refer to the same objects.
### In our case, `partial_parses` contains a list of partial parses. `unfinished_parses`
### contains references to the same objects. Thus, you should NOT use the `del` operator
### to remove objects from the `unfinished_parses` list. This will free the underlying memory that
### is being accessed by `partial_parses` and may cause your code to crash.
partial_parses = [PartialParse(sentence) for sentence in sentences]
unfinished_parses = partial_parses
while unfinished_parses:
minibatch = unfinished_parses[:batch_size]
transition = model.predict(minibatch)
for parse, transition in zip(minibatch, transition):
parse.parse_step(transition)
unfinished_parses = [parse for parse in unfinished_parses if not (len(parse.stack) == 1 and len(parse.buffer) == 0)]
dependencies = [parse.dependencies for parse in partial_parses]
### END YOUR CODE
return dependencies
def test_step(name, transition, stack, buf, deps,
ex_stack, ex_buf, ex_deps):
"""Tests that a single parse step returns the expected output"""
pp = PartialParse([])
pp.stack, pp.buffer, pp.dependencies = stack, buf, deps
pp.parse_step(transition)
stack, buf, deps = (tuple(pp.stack), tuple(pp.buffer), tuple(sorted(pp.dependencies)))
assert stack == ex_stack, \
"{:} test resulted in stack {:}, expected {:}".format(name, stack, ex_stack)
assert buf == ex_buf, \
"{:} test resulted in buffer {:}, expected {:}".format(name, buf, ex_buf)
assert deps == ex_deps, \
"{:} test resulted in dependency list {:}, expected {:}".format(name, deps, ex_deps)
print("{:} test passed!".format(name))
def test_parse_step():
"""Simple tests for the PartialParse.parse_step function
Warning: these are not exhaustive
"""
test_step("SHIFT", "S", ["ROOT", "the"], ["cat", "sat"], [],
("ROOT", "the", "cat"), ("sat",), ())
test_step("LEFT-ARC", "LA", ["ROOT", "the", "cat"], ["sat"], [],
("ROOT", "cat",), ("sat",), (("cat", "the"),))
test_step("RIGHT-ARC", "RA", ["ROOT", "run", "fast"], [], [],
("ROOT", "run",), (), (("run", "fast"),))
def test_parse():
"""Simple tests for the PartialParse.parse function
Warning: these are not exhaustive
"""
sentence = ["parse", "this", "sentence"]
dependencies = PartialParse(sentence).parse(["S", "S", "S", "LA", "RA", "RA"])
dependencies = tuple(sorted(dependencies))
expected = (('ROOT', 'parse'), ('parse', 'sentence'), ('sentence', 'this'))
assert dependencies == expected, \
"parse test resulted in dependencies {:}, expected {:}".format(dependencies, expected)
assert tuple(sentence) == ("parse", "this", "sentence"), \
"parse test failed: the input sentence should not be modified"
print("parse test passed!")
class DummyModel(object):
"""Dummy model for testing the minibatch_parse function
"""
def __init__(self, mode = "unidirectional"):
self.mode = mode
def predict(self, partial_parses):
if self.mode == "unidirectional":
return self.unidirectional_predict(partial_parses)
elif self.mode == "interleave":
return self.interleave_predict(partial_parses)
else:
raise NotImplementedError()
def unidirectional_predict(self, partial_parses):
"""First shifts everything onto the stack and then does exclusively right arcs if the first word of
the sentence is "right", "left" if otherwise.
"""
return [("RA" if pp.stack[1] == "right" else "LA") if len(pp.buffer) == 0 else "S"
for pp in partial_parses]
def interleave_predict(self, partial_parses):
"""First shifts everything onto the stack and then interleaves "right" and "left".
"""
return [("RA" if len(pp.stack) % 2 == 0 else "LA") if len(pp.buffer) == 0 else "S"
for pp in partial_parses]
def test_dependencies(name, deps, ex_deps):
"""Tests the provided dependencies match the expected dependencies"""
deps = tuple(sorted(deps))
assert deps == ex_deps, \
"{:} test resulted in dependency list {:}, expected {:}".format(name, deps, ex_deps)
def test_minibatch_parse():
"""Simple tests for the minibatch_parse function
Warning: these are not exhaustive
"""
# Unidirectional arcs test
sentences = [["right", "arcs", "only"],
["right", "arcs", "only", "again"],
["left", "arcs", "only"],
["left", "arcs", "only", "again"]]
deps = minibatch_parse(sentences, DummyModel(), 2)
test_dependencies("minibatch_parse", deps[0],
(('ROOT', 'right'), ('arcs', 'only'), ('right', 'arcs')))
test_dependencies("minibatch_parse", deps[1],
(('ROOT', 'right'), ('arcs', 'only'), ('only', 'again'), ('right', 'arcs')))
test_dependencies("minibatch_parse", deps[2],
(('only', 'ROOT'), ('only', 'arcs'), ('only', 'left')))
test_dependencies("minibatch_parse", deps[3],
(('again', 'ROOT'), ('again', 'arcs'), ('again', 'left'), ('again', 'only')))
# Out-of-bound test
sentences = [["right"]]
deps = minibatch_parse(sentences, DummyModel(), 2)
test_dependencies("minibatch_parse", deps[0], (('ROOT', 'right'),))
# Mixed arcs test
sentences = [["this", "is", "interleaving", "dependency", "test"]]
deps = minibatch_parse(sentences, DummyModel(mode="interleave"), 1)
test_dependencies("minibatch_parse", deps[0],
(('ROOT', 'is'), ('dependency', 'interleaving'),
('dependency', 'test'), ('is', 'dependency'), ('is', 'this')))
print("minibatch_parse test passed!")
if __name__ == '__main__':
args = sys.argv
if len(args) != 2:
raise Exception("You did not provide a valid keyword. Either provide 'part_c' or 'part_d', when executing this script")
elif args[1] == "part_c":
test_parse_step()
test_parse()
elif args[1] == "part_d":
test_minibatch_parse()
else:
raise Exception("You did not provide a valid keyword. Either provide 'part_c' or 'part_d', when executing this script")