This work describes a new multi-stage dependency parsing framework that relies on stochastic probabilistic models, such as the Maximum- Entropy Markov Model. It proposes an original compromise between locally optimal parsers with global features, and globally optimal models with local features. The main advantage of this framework is its ability to choose the desired compromise over the full range between both extreme models, by modifying the topology of the underlying automaton. Thanks to its probabilistic definition, it further gives access to several powerful classical probabilistic algorithms, and in particular to marginalization and Bayesian inference of, for instance, missing or corrupted observations. The rank-1 model has been evaluated on a French broadcast news parsing task, and has obtained comparable performance to state-of-the-art transition-based parsers.