Elamur Research
☰
home / papers / 1993 / Parsing English with a Link Grammar

Parsing English with a Link Grammar

What it is about

Link grammar is a lexical formalism: every word carries a formula of connectors, and a sentence is grammatical when its words can be joined by links that satisfy every word's requirements, do not cross and connect the whole sentence. There are no constituents or categories. The authors write roughly 800 formulas covering about 25,000 words of formal English, handling agreement, questions, relative clauses, coordination and unbounded dependencies. Their O(n^3) parser uses pruning, a hashed fast-match on connector types and power pruning, and parses typical newspaper sentences in a few seconds. The paper also shows how costly lexical ambiguity is: "cat" has 369 ways to be used and "time" 1689 in their dictionary.

Ideas

For Mova

The chapters are 19-lexicon-mwe-register (the lexicon as the place where most of the grammar lives) and 13-verbs (the verb frames a link formula encodes). The code is en/seeds/lexicon, en/seeds/errors, en/src/parse.rs and en/src/udreg.rs. Measure first: the lexical-pattern count of idea I3, which costs nothing and shows where the seeds are too broad.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/1993.iwpt-1.22.pdf

Summary

Sleator and Temperley propose link grammar, a lexical formalism that does not use constituents or phrase categories. Each word in the dictionary carries a formula of typed connectors that point left (-) or right (+), combined with "&" and "or". A word string counts as grammatical if links can be drawn between words so that three conditions hold: every word's requirements are met, no two links cross when drawn above the sentence, and the links connect all the words. The authors wrote a wide-coverage English dictionary aimed at formal, newspaper-style text, along with an exhaustive parser in ANSI-C. The parser is based on their own O(n³) algorithm plus pruning heuristics and data structures, and it handles typical newspaper sentences in a few seconds. They also describe a post-processor for constraints that are awkward to express in the formalism, and a special scheme for coordination. Finally, they show that any categorial grammar can be turned into an equivalent link grammar. Because the parser directly links words that are syntactically related, its output is useful for agreement checking, statistical modelling and other downstream tasks.

Key points

  • The English dictionary has roughly 800 formulas covering about 25,000 words. It handles:
    • agreement, questions, imperatives and irregular verbs;
    • relative clauses, possessives and unbounded dependencies;
    • commas and coordination.
  • Compact formulas hide large combinatorics. A single short formula captures the 369 distinct usages available to cat and the 1689 available to time.
  • In connector formulas, argument order matters: connectors written further left must attach to nearer words. For example, a noun's determiner must sit closer to it than the verb it attaches to as an object.
  • The parser finds every valid linkage in O(n³) time, where n is the sentence length. The program and dictionary were distributed via anonymous ftp.
  • The formalism was already used in other work:
    • Lafferty's probabilistic model combining trigrams with grammatical constraints;
    • Hunt's model of prosody and syntax;
    • Brehony's detector for English errors typical of Francophone writers.

Interesting ideas

  • Planarity as the central constraint. Requiring non-crossing links, plus full connectivity, gives a simple global well-formedness test that makes efficient exhaustive parsing possible. This could be a reasonable prior for other dependency-style analyzers.
  • Fully lexical grammar. All grammar lives in per-word entries, so editing one word only affects sentences that contain it. This makes incremental, team-based grammar writing safer, and it suits morphologically irregular vocabularies.
  • Algebraic sharing of independent requirements. Some properties are orthogonal, such as whether a noun needs a determiner and which role it plays in the sentence. These can be factored with "&" and "or" instead of listing every combination, which keeps hand-written resources small and readable.
  • A post-processing layer for awkward phenomena. Instead of forcing every constraint into the core formalism, a separate checker inspects finished linkages. One example is ruling out a normal noun in place of non-referential it. This keeps the core parser simple while still capturing subtle distinctions.
  • Compiling one formalism into another. Translating categorial grammars into link grammars with only linear growth lets one optimized parser serve several grammar families. The same trick is worth reusing whenever an efficient engine already exists.

Cite

The paper itself, not this card. BibTeX from the library's record of the work.

@inproceedings{sleator1993parsing,
  title = {{Parsing English with a Link Grammar}},
  author = {Sleator, Daniel D. and Temperley, Davy},
  booktitle = {Proceedings of the Third International Workshop on Parsing Technologies},
  year = {1993},
  url = {https://aclanthology.org/1993.iwpt-1.22/}
}

References

15 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. [1) Y. Bar-Hillel, Language and information; se lected essays on their theory and application. Addison-Wesley, 1964. find
  2. [2) Cormen, T. H . , C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press and McGraw-Hill, 1990. find
  3. [3) Fraser, N., "Parsing and dependency gram mar," In: Carston, Robyn (ed.) UCL Work ing Papers in Linguistics 1 , University Col lege London, London, 1989 Pages 296-3 19. find
  4. [4) Fraser, N. , "Prolegomena to a formal theory of dependency grammar," In: UCL Working Papers in Linguistics 2, University College London, London, 1990 Pages 298-3 19. find
  5. [5) Gaifman, H., "Dependency systems and phrase-structure systems," Information and Control 8, 1965, Pages 304-337. find
  6. [6) Hudson, R . , Word Grammar, Basil Black well, 1984. find
  7. [7) Hudson, R., "Towards a computer testable word grammar of English," In: Carston, Robyn (ed.) UCL Working Papers in Lin guistics 1 , University College London, Lon don, 1989, Pages 321-339. find
  8. [8] Hudson, R . , English Word Grammar, Basil Blackwell, 1990. find
  9. [9) Joshi, A. K . , "Natural Language Process ing," Science , Volume 253 , No. 5025, (Sept. 13 , 1991), Pages 1242-1249. find
  10. [10] Melcuk, I. A. Dependency Syntax: Theory and Practice, State University of New York Press 1988. find
  11. [11] Lafferty, J, D. Sleator , D. Temperley, "Grammatical Trigrams: A Probabilistic Model of Link Grammar," Proc. of the 1992 AAAI Fall Symp. on Probabilistic Ap proaches to Natural Language, and Techni cal report CMU-CS-92-181 , School _of Com puter Science, Carnegie Mellon University, Sept 1992. find
  12. [12) Oehrle, R. T., E. Bach, and D. Wheeler, Ed itors Categorial Grammars and Natural Lan guage Structures D. Reidel Publishing Com pany, 1988. find
  13. [13] Y. Schabes. "Stochastic lexicalized tree adjoining grammars." In Proceedings of COLING-92, Nantes, France, July 1992. find
  14. [14] Sleator, D. D., D. Temperley, "Parsing En glish with a Link Grammar," Technical re port CMU-CS-91-196, Carnegie Mellon Uni versity, School of Computer Science, October 1991. find
  15. [15) van Zuijlen, J., M., "Probabilistic methods in dependency grammar parsing," Proceed ings of the International Workshop on Pars ing Technologies, Carnegie Mellon Univer sity, 1989, Pages 142-250. find