This assignment is due Wednesday, November 1 at 11:59PM.


Through this assignment you will:


Please review the class slides, homework slides, and readings in the textbook on dependency parsing in general and transition-based parsing in particular. 

Dependency parsing relies on a transition set which converts the current state of the parse - referred to as a "configuration" - into a new state, until some terminal state is reached.  The arc-standard paradigm employs three transitions:

where <label> is the dependency relation that holds between the head and dependent identified by the transition.

The configuration consists of the stack, buffer, and arcs as discussed in class and in the readings.  It may be most straightforward to represent these as lists of different types, as in [0 1], [2,3,4],[] for a stack with two elements (including ROOT), a buffer with three elements, and (here) an empty set of arcs.  The elements here refer to the words in the sentence by their indexes.  Of course, alternate data structures are possible as well.

You will need to implement a function that applies a specified transition to a given configuration, and have code which implements the oracle which determines which transition should be applied to the current configuration, while working through each sentence with its accompanying dependency parse.


Create a program to implement the arc-standard oracle and apply it to a set of dependency-parsed sentences. Specifically, your program should:

Note: You are only responsible for implementing the oracle.  You do not need to train a model based on the oracle transitions.


Create a program called which applies the arc-standard oracle to identify and apply the correct sequence of transitions from the dependency parses provided  invoked as: <input_dependency_parse_filename> <output_dependency_filename> <output_sequence_filename> where,


Please adhere to the naming conventions below:

Example and Test Data Files

All data and example files may be found in /dropbox/23-24/571/hw5/.

Submission Files

Handing in your work

All homework should be handed in using the Canvas submission tools.