Parsing English with a Link Grammar
Next: Introduction
Parsing English with a Link Grammar
Daniel D. Sleator
and Davy Temperley
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
email: sleator@csu.edu
Music Department
Columbia University
New York, NY 10027
email: dt3@cunixa.cc.columbia.edu
Abstract:
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.
2
Thu Oct 12 13:01:13 EDT 1995