In this thesis we experimentally evaluate the performance of a Stochastic extension of the Extensible Dependency Grammar (SXDG) solver, a constrained-based dependency parser. We test the performance of the parser on sentences and grammars automatically acquired from the Penn Treebank and evaluate how the stochastic guidance helps the parser to prune the search tree. Our experimental study reveals that the stochastically enhanced parser (SXDG) is able to prune the search tree considerably, but that the current setup of SXDG still has potential for improvements. We also give directions for future improvements of the current SXDG parser.