Parsing English with a Link Grammar
Daniel D. Sleator, David Temperley · 1995
A link grammar is a new formal grammatical system. A sequence of words is in the language of the link grammar if there is a way to draw links between words in such a way that (1) the local requirements of each word are satisfied, (2) the links do not cross, and (3) the words form a connected graph. We have encoded English grammar into such a system, and written a program (based on new algorithms) for efficiently parsing with a link grammar. Although the expressive power of (basic) link grammars is equivalent to that of context-free grammars, the breadth of English phenomena that our system handles is unusually large -- it handles: noun-verb agreement, questions, imperatives, complex and irregular verbs, many types of nouns, past- or present-participles in noun phrases, commas, a variety of adjective types, prepositions, adverbs, relative clauses, possessives, coordinating conjunctions, and many other things. A number of sophisticated and new techniques were used to allow efficient pars...