Parsing English with a Link Grammar

next up previous
Next: Introduction

Parsing English with a Link Grammar

Daniel D. Sleator and Davy Temperley

School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
Music Department
Columbia University
New York, NY 10027


We define a new formal grammatical system called a link grammar. A sequence of words is in the language of a 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. The formalism is lexical and makes no explicit use of constituents and categories. The breadth of English phenomena that our system handles is quite large. A number of sophisticated and new techniques were used to allow efficient parsing of this very complex grammar. Our program is written in C, and the entire system may be obtained via anonymous ftp. Several other researchers have begun to use link grammars in their own research.


Thu Oct 12 13:01:13 EDT 1995