I found out the issue was that the feature set that I had defined was not enough to let the parser choose a different action than starting an arc. Once I added a feature to indicate if an arc was started, the parser now starts and ends arcs until the stop condition is reached. The code looks somewhat different than the example that I first posted, but it is similar. For example, the while-loop in the parse() method continues indefinitely (while True:) but there is a break condition that comes into effect when the number of arcs reached the number of tokens in the sentence (since the number of arcs including the root arc is the same as the number of tokens). Note that I also switched from using the perceptron code to a SVM from the scikit-learn library.