There are quite a few statistical parsers but I'm interested in rule-based dependency parsing. I have a lexicon, i.e., a list of words with lemmas, POS, and morphological features. What is the best parsing algorithm in terms of accuracy and efficiency?

1 Answer 1


Dependency parsing with ID/LP rules is trivial if you have a lexicon. One uses a (declarative) generate-and-test approach. Dependency trees are rooted spanning trees on a graph with n nodes where n is the length of the processed sentence. One can declare what a tree is and - now comes the linguistic part - where an edge (that is, a dependency) may be. The result are all spanning trees composed of the possible dependencies. Thus dependency parsing is constraint solving.

A naïve implementation of the algorithm would have a terrible time complexity. On a complete graph, there are n^(n-2) trees, whence there are n^(n-1) rooted trees. The only viable way is to use the constraints to compute stable models of the underlying theory (there is a one-to-one correspondence between stable models and dependency trees). On Linux one can use clingo (an AI tool downloadable from package repositories). On OS X, the tool can be installed via MacPorts.

There are a few issues. For languages with case, one needs additional constraints. In Latin, for example, "Metellam vidit" would be parsed using the rule n<-v, that is, a noun can depend on a verb, but the case of the noun decides what role the noun plays in the verb's predicate (in this example, accusative implies direct object). In a sentence like "I gave Mary the book", word order is what decides that Mary is the indirect object in this sentence. Thus LP rules are needed. One could analyze both objects at once (with one rule) but this runs counter to the idea of dependency grammar as it was originally conceived.

The computation of stable models is generally very fast but it may take some time when the sentence is long and complex. One could add constraints that enforce projectivity. Most sentences are projective, that is, one can speed up the parser by considering only projective sentences at the first try (no sane theory of dependency syntax would assign nonprojective trees to unmarked sentences). Actually, projectivity is a scale, one can thus try to infer a projective tree, then a planar one, then a well-nested one, etc. But this is only an optimization and no difference would be observable for short sentences.

By adding feature structure unification to the rules it is possible to create deep syntax trees (which are better for further processing such as machine translation or discourse interpretation). For example, auxiliaries are only tense and agreement carriers, they contribute features to the morphosytactic description of a verb phrase, but they have no meaning of their own and are useless for further processing. On the other hand, one needs to add semantic content (the subject) in a sentence like "veni, vidi, vici". Thus the sketched algorithm builds up surface trees, deep trees, and logical forms in parallel. I can provide source code with a toy grammar.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.