Parsing English with a Link Grammar

Daniel D. Sleator, Davy Temperley


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.
Anthology ID:
1993.iwpt-1.22
Volume:
Proceedings of the Third International Workshop on Parsing Technologies
Month:
August 10-13
Year:
1993
Address:
Tilburg, Netherlands and Durbuy, Belgium
Editors:
Harry Bunt, Robert Berwick, Ken Church, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Makoto Nagao, Anton Nijholt, Mark Steedman, Henry Thompson, Masaru Tomita, K. Vijay-Shanker, Yorick Wilks, Kent Wittenburg
Venue:
IWPT
SIG:
SIGPARSE
Publisher:
Association for Computational Linguistics
Note:
Pages:
277–292
Language:
URL:
https://aclanthology.org/1993.iwpt-1.22
DOI:
Bibkey:
Cite (ACL):
Daniel D. Sleator and Davy Temperley. 1993. Parsing English with a Link Grammar. In Proceedings of the Third International Workshop on Parsing Technologies, pages 277–292, Tilburg, Netherlands and Durbuy, Belgium. Association for Computational Linguistics.
Cite (Informal):
Parsing English with a Link Grammar (Sleator & Temperley, IWPT 1993)
Copy Citation:
PDF:
https://aclanthology.org/1993.iwpt-1.22.pdf