[Logo]

AbiWord Home
  Take a Tour
  Screenshots
  Download
  Plugins
  Reviews

Information
  About AbiWord
  License
  Mailing Lists
  Projects
  Planet AbiSource

Publications

Support
  System Reqs.
  User's Manual
  FAQ
  Report a Bug
  Get Help
  Knowledge Base

Contribute
  Suggest Ideas
  Triage Bugs
  Quality Assurance
  Translate

Developers


[Printer]
Printer Friendly
Version


kindly hosted by
[University of Twente]
University of Twente


Link Grammar Parser

by Davy Temperley, John Lafferty and Daniel Sleator
(this variant maintained by Dom Lachowicz - <domlachowicz@gmail.com> and Linas Vepstas - <linasvepstas@gmail.com> )

News

June, 2013: link-grammar 4.7.13 released! See below for a description of recent changes.

What is the Link Grammar?

The Link Grammar Parser is a syntactic parser of English, Russian, Arabic and Persian (and other languages as well), based on link grammar, an original theory of English syntax. Given a sentence, the system assigns to it a syntactic structure, which consists of a set of labelled links connecting pairs of words. The parser also produces a "constituent" (Penn tree-bank style phrase tree) representation of a sentence (showing noun phrases, verb phrases, etc.). The RelEx extension provides dependency-parse output.

Did the AbiWord team write Link Grammar?

In large part, no. The project is the brainchild of Davy Temperley, John Lafferty and Daniel Sleator, all university professors. It is the product of a decade of academic research into grammar, and is founded on a theory backed by numerous publications. Its original homepage is hosted by Carnegie Mellon University.

So, then what is it doing @ AbiSource.com?

The AbiWord team had a concrete need - to integrate a grammar checking feature into AbiWord. The best choice, they felt, was to build upon Temperley et. al.'s successful Link Grammar project.

However, in order for the link-grammar project to be useful to them and to the greater Free Software world, the AbiWord community felt that a variety of changes to the project would be necessary. While they did have success (a few years ago) convincing the authors to release Link Grammar under a GPL-compatible license, there was no practical way to continue project development and maintenance at the CMU website. So the AbiWord community took it under its wing and has nurtured the project since.

Ongoing development by OpenCog

Ongoing development of link-grammar is being primarily guided by the Open Cognition project, where the parser plays an important role in the OpenCog natural language processing subsystem. Research and implementation is ongoing; current work includes investigations into semantically guided parsing, grammatically induced word-sense disambiguation, and work on automatically learning new parse rules based on corpus statistics.

A sibling project, RelEx, uses constraint-grammar-like techniques to extract dependency relations and assorted additional linguistic information, including FrameNet-style framing and reference (anaphora) resolution. The dependency output is similar to that of the Stanford parser. It's performance is comparable to the Stanford PCFG parsing model, and is more than three times faster than the Stanford "lexicalized" (factored) model.

The NLGen and NLGen2 projects provide natural language generation modules, based on, and compatible with link-grammar and RelEx. They implement the SegSim ideas for NL generation. See the following NLGen demos: Demo of Virtual Dog Learning to Play Fetch via Imitation and Reinforcement, AI Virtual Dog's Emotions Fluctuate Based on Its Experiences, Demo of Embodied Anaphora Resolution and AI Virtual Dog Answers Simple Questions about Itself and Its Environment.

Notable changes from the Carnegie-Mellon Link Grammar package include:

  • Actively maintained! New releases typically happen bi-annually.
  • Many bug fixes and large performance improvements.
  • Russian dictionaries!
  • Expanded English dictionaries, with many thousands of new words; dramatically improved parse coverage for a wide variety of constructions.
  • Merger of BioLG project changes, for improved parsing of biomedical text. This includes enhanced entity recognition, and precise identification of numeric quantities.
  • New bindings, including Ruby, Python, perl, Lisp, Java and Ocaml.
  • Support for UTF8 Unicode; Arabic and Persian dictionaries; prototype German dictionary.
  • Multi-threading support; a standard build system; pkg-config integration; dynamic/shared library support; fixes for non-Linux platforms, including Windows, MacOSX, FreeBSD.

Downloading Link Grammar

The system can be downloaded either as a tarball, or via SVN. The current stable version is Link Grammar 4.7.13 (June, 2013). Older versions are available here. Unstable, development versions are available through AbiWord's SVN repository. Anonymous read-only access is available by issuing the command:

svn co http://svn.abisource.com/link-grammar/trunk link-grammar

General instructions for AbiWord's anonymous SVN can be found here. The Link Grammar source can be browsed online here.

Documentation

One of the best ways to obtain a solid, easy-to-understand overview of the parser is to review the original papers describing it, here, here, here and here. There is an extensive set of pages documenting the dictionary; specifically, the names of links and their meanings, as well as how to write new rules. There is also a short primer for creating dictionaries for new languages. The documentation for the programming API is here. Documentation for additions made in the 4.0 release is on the improvements page. A fairly comprehensive bibliography of papers written before 2004 is here (mirror).

Mailing Lists

The current list for Link Grammar discussion is at the link-grammar google group.

Subscribe to link-grammar:

Enter email:

Bug Tracker

Bug reports, patches, RFEs, etc. are gladly welcomed.

Disclaimer

Link grammar is a natural language parser, not an artificial intelligence. This means that there are many sentences that it cannot parse correctly, and many others for which it generates multiple parses. There are also entire classes of speech that it cannot parse, such as Valley-girl speak. Link grammar does best on "newspaper English": medium-length sentences written with good grammar, proper punctuation, and proper capitalization. It don't do 733t speek, etc. In particular, it has problems with the following "registers" and types of writing:

  • Phrases (that are not a part of a complete sentence)
  • Bullited lists, such as this.
  • Quotations within sentences (and parenthetical remarks) These can be handled by an appropriate front-end, that separates out the quotations from the rest of the text.
  • Slang speech, words, like 733t warez d00dz, although it can certainly guess from context if the slang is sufficiently grammatical.
  • Long run-on sentences. These can generate thousands of alternative parses in a combinatorial explosion.
  • Certain "registers", such as newspaper headlines; for example, "Thieves rob bank."

In addition, it has a variety of "bugs": it currently has trouble with "if...then..." constructs, compound queries ("who did it, and why?"), lists, "...not only...but also..." constructs, certain types of idiomatic phrases, certain types of "institutional utterances", and so on. The goal of the project is to eventually fix all of these cases; progress is ongoing.

Adjunct Projects

Windows binary
A binary .exe for MS Windows is available at WinLinkGrammar which includes the compiled Link Grammar, Corpus Statistics, and SQlite3 files. The zip file also has the required regex2.dll and installation instructions.
RelEx Semantic Relation Extractor
RelEx is an English-language semantic relationship extractor, built on the Carnegie-Mellon link parser. It can identify subject, object, indirect object and many other relationships between words in a sentence. It will also provide part-of-speech tagging, noun-number tagging, verb tense tagging, gender tagging, and so on. RelEx includes a basic implementation of the Hobbs anaphora (pronoun) resolution algorithm. Optionally, it can use GATE for entity detection.
AutoIt bindings
AutoIt is a scripting language for Windows. This zipfile provides AutoIt bindings to Link Grammar, thanks to JRowe. Includes binary Windows DLL's for a recent link-grammar version, as well. The source code for the AutoIt bindings are now included, by default, in the base link-grammar distribution, as of version 4.6.6 (March 2010).
Delphi bindings
Delphi (Pascal) is a popular development environment for Windows. The LaKraven Page provides the source for Delphi bindings, as well as pre-compiled DLL's for Windows.
Java bindings
Java bindings are included, by default, in the base link-grammar distribution.
Lisp bindings
Lisp foregin-function interface to Link Grammar. These are now included by default in current versions of link-grammar, as of version 4.7.11 (March 2013).
Objective Caml bindings
OCaml interface to Link Grammar
Perl bindings
The perl bindings, created by Danny Brian, have been updated. See the Lingua-LinkParser page on CPAN. There is also a tutorial written against an older version of the bindings; some details may be different.
Python bindings
New python bindings can be found here.
Older Python bindings
Older, different python bindings are available on Launchpad. Install instructions here.
Ruby bindings
There are two different packages providing Ruby bindings: Ruby Link Grammar, which is up-to-date and currently maintained, and Link Grammar 4 Ruby, which is wildly out-of-date (its for version 4.2.2) and is unmaintained. You only need one!
Persian dictionaries
Persian dictionaries, by Jon Dehdari. These require the Persian stemming engine, as significant morphology analysis needs to be performed to parse Persian. [Mirror]
Pre-parsed Wikipedia
Parsed versions of various texts, including all articles from a May 2008 dump of Wikipedia, as well as a partial parse of an October 2010 dump, are available at http://gnucash.org/linas/nlp/data/
Arabic dictionaries
Arabic dictionaries, by Jon Dehdari. [download] [Mirror] These require the Aramorph stemming package, which is included.
French dictionary, Luthor
The Luthor project aims to develop a set of scripts to automatically construct Link Grammar linkage dictionaries by mining Wiktionary data. Current efforts are focusing on French.
Russian dictionaries, parser
The Russian dictionaries have been incorporated into the main distribution as of version 4.7.10 (March 2013). An older version from which these are derived, can be found at http://slashzone.ru/parser/. By Sergey Protasov. Includes link documentation (mirror) and subscript (morphology) documentation (mirror). Russian morpheme dictionaries can be had at http://aot.ru.
English dictionary extensions
LinkGrammar-WN is a lexicon expansion for the English language Link Grammar Parser. This project adds 14K new words to the dictionaries. The extended lexicon is provided under the GPL license, and thus cannot be merged back into the current project. NOTE: these extensions are rather old, and it is likely that they are no longer compatible with current link-grammar versions.
Medical Text Analysis
The MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) Clinical Decision Making Group has done work to extend the Link Grammar dictionaries by adding many new words. All but the six largest of these dictionaries have been merged into link-grammar, since version 4.3.1 (January 2008). The large dictionaries EXTRA.2, EXTRA.3, EXTRA.8, EXTRA.9, EXTRA.12, and EXTRA.17 have not been merged. These dictionaries contain 180K assorted medical, biological and biochemical terms and phrases.
BioLG
The BioLG project is a modification of the Link Grammar Parser adapted for the biomedical domain, as described in Lexical Adaptation of Link Grammar to the Biomedical Sublanguage: a Comparative Evaluation of Three Approaches (Sampo Pyysalo, Tapio Salakoski, Sophie Aubin and Adeline Nazarenko; BMC Bioinformatics 2006). Almost all of the BioLG changes have been merged back into the main line, as of version 4.5.0 (April 2009), with scattered bug-fixes after that.

Of related interest

Genia tagger
The Genia tagger is useful for named entity extraction. BSD license source.

Recent Applications and Publications

Some recent uses and applications of the Link Grammar Parser are shown below. There is also an extensive bibliography on the CMU website (mirror) referencing several dozen older (pre-2004) papers pertaining to the Link Grammar Parser.

Some miscellaneous facts:

  • Any categorical grammar can be easily converted to a link grammar; see section 6 of Daniel Sleator and Davy Temperley. 1993. "Parsing English with a Link Grammar." Third International Workshop on Parsing Technologies.
  • Link grammars can be learned by performing a statistical analysis on a large corpus: see John Lafferty, Daniel Sleator, and Davy Temperley. 1992. "Grammatical Trigrams: A Probabilistic Model of Link Grammar." Proceedings of the AAAI Conference on Probabilistic Approaches to Natural Language, October, 1992.

Recent Changes

Version 4.7.13 (17 June 2013) Windows unicode handling fixes.

  • Remove trailing carriage return in MSVC6 filenames.
  • Performance improvement: avoid excess system timer calls.
  • Unicode fixes for Windows.
  • Fix: "... a purseful of pesos"; other currency fixes.
  • MinGW, unicode fixes from Per Larsson

Version 4.7.12 (25 May 2013) Major revision to the Russian dictionaries!

  • Large fixes to the Russian dictionaries.
  • Windows: Explicitly fail if cygwin version is too old.
  • Tweak the lt dict to work again with the modern parser.
  • Make the fat linkages code be compile-time configurable.
  • Disable fat linkages by default; mark as deprecated.
  • Fix SAT-solver build; recent changes had broken it.
  • Export read-dict.h as a public API.
  • Ongoing development of the Viterbi prototype.
  • Windows: some UTF8/widechar refactoring.
  • Java bindings: add method to set the language.
  • CMake: add version checking to the CMakefile
  • Fix: failed handling of capitalized first word for Russian.
  • Fix: stemming failures in many cases (for Russian dictionaries)
  • Add flag to suppress stem-suffix printing.
  • Windows: Fixes to MSVC6 build files.
  • Fix: hash-table bug affecting Russian dictionaries

Version 4.7.11 (23 March 2013) Emergency build break fix.

  • Fix build bug introduced recently (build_disjuncts_for_dict_node)
  • MSVC6 build environment fixes.
  • Ongoing development of the Viterbi prototype.

Version 4.7.10 (9 March 2013) Russian dictionaries!

  • New: Russian dictionaries from Sergey Protasov!
  • Improve prefix, suffix handling and stemming (needed for Russian)
  • Fix: add "gurgle.n" to dictionary.
  • Improve memory utilization (remove pointless malloc/free).
  • Fix: UTF8 multi-byte diagram printing.
  • Add UTF8 multi-byte editline support, when available.
  • Include Common Lisp bindings, from Peter Szolovits (circa 2009).
  • Ongoing work on pre-alpha Viterbi decoder.
  • Fix: Bug 55: aspell header file included even if disabled.
  • Updated MSVC6, MSVC9 project files.
  • New, improved search for java jni.h
  • Faster counting of disjuncts for the !! command.
  • The !! command now shows regex entries and stem+suffix splits.

Version 4.7.9 (3 November 2012) A large number of dictionary updates, plus some more MacOSX touchups.

  • Fix: Poor comma chocies: "The man, that you saw..." (issue #36)
  • Fix: Add more java jni.h search paths.
  • Fix: Warning in java JSON interface.
  • Fix: weren't constructions: "If it weren't for Sally, ..."
  • Fix: Better support for ellipsis ...
  • Fix: strangely: "He is behaving very strangely"
  • Fix: assorted usages of yes, no, maybe
  • Fix: "being" in subordinate clauses: "The blade being dull, he ..."
  • Fix: Build failure for Mac OSX.
  • Fix: "... this time for real".
  • Fix: "... the impudence to laugh."
  • Fix: "we two", "us two"
  • Fix: very old parse bug, using "enough"
  • Fix: assorted profanity as synonyms to "else"
  • Fix: whoever, whomever
  • Fix: decade possessives: "It's a 60's hit"
  • Fix: "... chances that ... could be ..."
  • Fix: "Do you have it ready?"
  • Fix: "What John wants are those cats"
  • Fix: greetings
  • Fix: misc verbs: wave, ink, kiss, bake, corral, crown, decant, rope, slice, ink, butter, proclaim, make, give, bid, bade, think
  • Fix: titles can behave as indefinite nouns.
  • Fix: somewhere, near, nearby, halfway, about
  • Fix: police-interrogation style questions

Version 4.7.8 (10 October 2012) Broke the build, in the previous release. Ooooops!

  • Ongoing work on pre-alpha Viterbi decoder.
  • Fix include file paths so that 'make install' doesn't cause recompile.
  • Fix build break due to bad include file paths in Makefiles.

Version 4.7.7 (6 October 2012) This version makes a number of significant changes to the dictionary. The most important of these is to indicate that expressions of the form ...a number of X act as if they were determiners; correspondingly, the subject and object links move to a new location. That is, the subject/object links now land on "X" instead of "number". Other changes to the dictionary are listed below.

  • Fix configure to not bomb if c++ is not found. (weird regex.h missing)
  • Fix configure to explicitly require c++ only if sat-solver enabled.
  • Dictionary: parse comma in "Monsters, Inc."
  • Update README about Viterbi algo.
  • Remove malloc-dbg.c from the MSVC6 project file.
  • Add missing source files to MSVC6 project file.
  • Use enums for constituent display style.
  • Move command-line parser to its own directory.
  • Portability fixes for Windows, from Bill Hayes.
  • Fix: "Show results from today"
  • Fix: conjoined imperatives.
  • Fix: qualified conditional clauses
  • Fix: conjoined irregular verbs: seem, appear, do, be, prove, have
  • Disable fat link code via conditional compile.
  • Fix: "a lot of", "a gaggle of" now treated as quantifying determiners
  • Fix: likewise: "gallons of", "grams of" volume measures as determiners
  • Update German dictionary so that it actually loads.
  • Fix: assorted "but not", "not very" constructions.
  • Pre-alpha implementation of Viterbi decoder started.
  • Fix: conjunctions of optionally ditransitive verbs.

Version 4.7.6 (26 April 2012) This version fixes a bungled header file in the last version: builds broke because the public header file was including an internal header file.

  • fast-match.c: unroll recursive call into loop (thx Valery Kholodkov).
  • Fix accidental inclusion of internal header file from public header file.

Version 4.7.5 (16 April 2012) This version includes fixes for a handful of dictionary bugs, an all new manual page, and several fixes and improvements for the build system.

  • Remove several duplicate given names.
  • Remove malloc-dbg.c from the MSVC9 project file.
  • Remove several dozen duplicated idioms.
  • New AM_SILENT_RULES for less noisy build!
  • Clean up misc minor compiler warnings.
  • Start using -O3 optimization for another 2% perf improvement.
  • Fix configure.in --enable/--disable flags (bug #53)
  • Some intransitive verbs are actually transitive in rare cases.
  • Use enum not int for the cost-model type.
  • Update the man page to reflect actual command usage.

Version 4.7.4 (13 February 2011) This version includes fixes for several bugs/crashes introduced in the previous version :-( It also includes changes that result in dramatic speed improvements on long sentences, with an average of 1.1x to 2.0x improvement on "typical" texts.

  • Dramatic speed improvement for long sentences (hash table fix).
  • Fix: crash on certain sentences, when fat-link parsing enabled.
  • Fix: fatal error introduced in last version (combinatorial explosion).
  • Fix: mem leak introduced in last version (combinatorial explosion).
  • Assorted fixes to the Boolean SAT solver.

Version 4.7.3 (7 February 2011) This version fixes a bug where a "combinatorial explosion" resulted in no parses being printed.

  • Fix: "level" as indefinite noun: "... at knee level".
  • Enable max disjunct cost as a controllable parser parameter.
  • Don't just give up on combinatorial explosion, show something!

Version 4.7.2 (6 January 2011) This version fixes a crash and an "almost infinite loop"; both might be hit when using the (now deprecated) fat-links, and certain overflow conditions are met.

  • Fix: crash on certain sentences, when fat-link parsing enabled
  • Fix: 3 corrupted nouns in words.n.1
  • Fix: minimize cpu spin if constituent processing and-list overflows.

Version 4.7.1 (11 December 2010) This version fixes several bugs introduced by the conjunction-handling rework of 4.7.0. Several Windows-related compile fixes are included as well.

  • Fix: dictionary: Add "x" as synonym for "times".
  • Fix: compilation failure due to lack of termios support on Windows.
  • Fix: if not set, then force-set locale to UTF-8 in the java library.
  • Fix: Explicitly include <stddef.h> for Windows builds.
  • Fix: "John imagines himself lost".
  • Fix: predicative adjectives w/misc verbs: "You are driving me crazy"
  • Fix: "judge innocent", etc.
  • Fix: many, many conjoined present tense verbs.
  • Fix: conjoined verbs with negations.
  • Fix: "to" as post-nominal modifier: "the inability to laugh"

Version 4.7.0 (12 September 2010) This version introduces a major change to the way that conjunctions are handled. The parse output for conjunctions is not compatbile with the old output, but should be easier to work with, solving many problems. The rework results in a performance improvement of 1.3x to 2.7x, depending on the text.

  • Fix: hunspell configuration on Fedora (bugtracker issue 47)
  • Fix: 'turn' with adjective: "She turned him green" from wingedtachikoma
  • Fix: comma-conjoined modifiers: "It tastes bitter, not sweet."
  • Fix: conjoined question words: "When and where is the party?"
  • Fix: recognize short, capitalized words (Los, La, etc.).
  • Treat colon as synonym for is: "The answer: yes."
  • Fix: begin with prepositions: "It all began in Chicago."
  • Fix: "What does it come to?" and related.
  • Fix: null infinitive: "I'd like to, I want to."
  • Fix: "Because I said so."
  • Fix: "sure" as preverbal adverb: "It sure is."
  • Fix: Gerunds with determiners: "a running of the bulls"
  • SJ link for conjoined nouns/noun phrases.
  • Sort linkages according to whether fat linkage was used.
  • Add flag to enable use of fat linkage during parsing. (Fat links now disabled by default).
  • Add male/female gender tags to misc nouns.
  • Fix: misc optionally transitive verbs: mix, paint, boot
  • Fix: word order: "look about fearfully", "look fearfully about", around
  • Fix: recognize simple fractions
  • Fix: "is" with uncountable nouns: "there is blood on your hands"
  • Fix: Roman numeral suffixes e.g. "Henry VIII"
  • Fix: regression in dates followed by punctuation. "In the 1950s, ..."
  • Fix: verbs drank, drunk are optionally transitive.
  • Fix: regression: "all the X", X can be plural or mass.
  • Fix: verbs paint, color may be ditranstive: "paint the car bright green"

A list of older changes can be found here.

License

The Link Grammar license is essentially the BSD license. A copy of this license can be found below, and at the original author's CMU site

Copyright (c) 2003-2004 Daniel Sleator, David Temperley, and John Lafferty. All rights reserved.
Copyright (c) 2003 Peter Szolovits
Copyright (c) 2004,2012,2013 Sergey Protasov
Copyright (c) 2006 Sampo Pyysalo
Copyright (c) 2007 Mike Ross.
Copyright (c) 2008,2009,2010 Linas Vepstas, Borislav Iordanov.
Copyright (c) 2011,2012,2013 Linas Vepstas

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

  1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
  2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
  3. The names "Link Grammar" and "Link Parser" must not be used to endorse or promote products derived from this software without prior written permission. To obtain permission, contact sleator@cs.cmu.edu

THIS SOFTWARE IS PROVIDED BY DANIEL SLEATOR, DAVID TEMPERLEY, JOHN LAFFERTY AND OTHER CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Copyright (C) 1998-2011, the AbiSource community. All rights reserved.
AbiSource, AbiSuite, and AbiWord are trademarks of Dom Lachowicz. All other product names, company names, or logos cited herein are property of their respective owners.
Site feedback to webmaster@abisource.com