A Finite-state Parser with Dependency Structure Output
David Elworthy · 2000
Dependency parsers and finite-state parsers are both capable of rapid and robust parsing of natural language. Dependency parsers produce richer output structures, while finitestate parsers can be more efficient. We show how a finite-state parser can be used to produce dependency structures for most phrase types, with an O(n 2 ) complexity in the number of words. The parser allows syntactically ambiguous structures to be packed into a single representation. The parser has been used as a component of a natural-language information retrieval system, operating in English and Japanese. 1 Dependency parsing and finite-state parsing Recent work in parsing natural language has shown a shift away from the heavy-weight theories of syntax and semantics, towards grammar formalisms which can be parsed efficiently and which make it easy to write robust grammars. Many of the lightweight techniques use either finite-state parsing, or some variant of dependency grammars. Finite-state parsing ...