Grammar formalisms built on the notion of word-to-word dependencies make attractive alternatives to formalisms built on phrase structure representations. However, little is known about the formal properties of dependency grammars, and few such grammars have been implemented. We present results from two strands of research that address these issues. The aims of this research were to classify dependency grammars in terms of their generative capacity and parsing complexity, and to systematically explore their expressive power in the context of a practical system for grammar development and parsing.