Fraser, Norman MacAskill; (1993) Dependency Parsing. Doctoral thesis (Ph.D), UCL (University College London).

Text Dependency_parsing.pdf Download (9MB)

Abstract

Syntactic structure can be expressed in terms of either constituency or dependency. Constituency relations hold between phrases and their constituent lexical or phrasal parts. Dependency relations hold between individual words. Almost all results in formal language theory relate to constituency grammars, of which the phrase structure grammars are best known. In the realm of natural language description, almost all major linguistic theories express syntactic structure in terms of constituency. This dominance carries over into natural language processing, where most parsers are designed to discover the vertical constituency relations which hold between words and phrases, rather than the horizontal dependency relations which hold between pairs of words. This thesis introduces dependency grammars, their formal properties, their origins in linguistic theory and, particularly, their use in parsers for natural language processing. A survey of dependency parsers - the most comprehensive to date - is presented. It includes detailed discussions of twelve published dependency parsing algorithms. The survey highlights similarities and differences between dependency parsing and mainstream phrase structure grammar parsing. In particular, it examines the hypotheses that (i) it is possible to construct a fully functional dependency parser based on an established phrase structure parsing algorithm without altering any fundamental aspects of the algorithm, and (ii) it is possible to construct a fully functional dependency parser using an algorithm which could not be applied without substantial modification in a fully functional phrase structure parser. Elements of a taxonomy of dependency parsing are outlined. These include variables in origin, manner, order, and focus of search, as well as in the number of passes made during parsing, techniques for the management of ambiguity, and the use of an adjacency constraint to limit search. Computer implementations of a number of original dependency parsing algorithms are presented in an Appendix, together with new implementations of established algorithms.

Download activity - last month

Export as JSONCSVXML

Download activity - last 12 months

Export as XMLCSVJSON

Downloads by country - last 12 months

Export as CSVJSONXML

Archive Staff Only

View Item