Link grammar

Link grammar (LG) is a theory of syntax by Davy Temperley and Daniel Sleator which builds relations between pairs of words, rather than constructing constituents in a tree-like hierarchy. There are two basic parameters: directionality and distance. Dependency grammar is similar to link grammar, but dependency grammar includes a head-dependent relationship, as well as lacking directionality in the relations between words.

For example, in an Subject Verb Object language like English, the verb would look left to form a subject link, and right to form an object link. Nouns would look right to complete the subject link, or left to complete the object link.

In an Subject Object Verb language like Persian, the verb would look left to form an object link, and a more distant left to form a subject link. Nouns would look to the right for both subject and object links.

Syntax

Rightward links are represented as a +, and leftward links with a -. Optional links are contained in curly brackets {...}. Undesirable links are contained in any number of square brackets [...] . Multiple links are joined either by a conjunction & or a disjunction or. Each rule ends with a semicolon ;.

Examples

Example 1

A basic rule file for an SVO language might look like:

:: D+;:: {D-} & S+;:: {D-} & O-;:: S- & {O+};

Thus the English sentence, “The boy painted a picture” would appear as:

+-----O-----+ +-D-+--S--+ +--D--+
| | |
The boy painted a picture

Example 2

While a rule file for a null subject SOV language might consist of the following links:

:: S+;:: O+;:: {O-} & {S-};

And a simple Persian sentence, "man nAn xordam" (من نان خوردم) 'I ate bread' would look like:

+-----S-----+
+--O--+
|
man nAn xordam

Applications

AbiWord, a free word processor, uses Link Grammar for on-the-fly grammar checking. [http://www.abisource.com/projects/link-grammar/] Words that cannot be linked anywhere are underlined in green.

The [http://opencog.org/wiki/RelEx RelEx semantic relationship extractor] , layered on top of the Link Grammar library, makes explicit the semantic relationships between words in a sentence. It also provides framing/grounding, anaphora resolution, head-word identification, lexical chunking, part-of-speech identification, and tagging, including entity, date, money, gender, etc. tagging.

Link Grammar has also been employed for information extraction of biomedical texts [Cite conference
author = Jing Ding, Daniel Berleant, Jun Xu, Andy W. Fulmer
title = Extracting biochemical interactions from MEDLINE using a link grammar parser
booktitle = Tools with Artificial Intelligence, 2003. Proceedings. 15th IEEE International Conference on
year = 2003
month = November
pages = 467–471
isbn = 0-7695-2038-3
url = http://www.bcb.iastate.edu/courses/JingDing.pdf
] and events described in news articles [Cite conference
author = Harsha V. Madhyastha, N. Balakrishnan, K. R. Ramakrishnan
title = Event Information Extraction Using Link Grammar
booktitle = 13th International WorkShop on Research Issues in Data Engineering: Multi-lingual Information Management (RIDE'03)
pages = 16
doi = 10.1109/RIDE.2003.1249841
year = 2003
] , as well as experimental machine translation systems from English to German and Turkish.

Implementations

The Link grammar syntax parser is a library for natural language processing written in C. It is available under the BSD license, which is compatible with the GNU General Public License. The parser is an ongoing project, [http://www.abisource.com/projects/link-grammar/ located here] . Recent versions include improved sentence coverage, various bug and security fixes, and Java language bindings.

There are also Perl, Ruby, and OCaml bindings available. [http://search.cpan.org/~dbrian/Lingua-LinkParser1.08/LinkParser.pm] [http://vee-r2.blogspot.com/2005/11/rubylink-grammar-binding.html] [http://ramamurthy.ramu.googlepages.com/ocamllinkgrammar]

The "link-grammar" program along with rules and word lists for English may be found in standard Linux distributions, e.g., as a Debian package. [ [http://packages.debian.org/link-grammar Debian - Package Search Results - link-grammar ] ]

Notes

Further reading

*cite paper
author = Schneider, Gerold
title = A Linguistic Comparison Constituency, Dependency, and Link Grammar
date = 1998
url = http://www.ifi.unizh.ch/cl/study/lizarbeiten/lizgerold.pdf
version = Masters Thesis, University of Zurich
accessdate = 2007-12-26

*Cite conference
author = Sleator, Daniel & Davy Temperly
year = 1993
title = Parsing English with a Link Grammar
booktitle = Third International Workshop on Parsing Technologies
url = http://www.cs.cmu.edu/afs/cs.cmu.edu/project/link/pub/www/papers/ps/LG-IWPT93.pdf

External links

* [http://www.link.cs.cmu.edu/link/ The Link grammar homepage] :* [http://www.link.cs.cmu.edu/link/submit-sentence-4.html Online English demonstration] :* [http://groups.google.com/group/link-grammar?hl=en Link Grammar Forum]
* [http://www.abisource.com/projects/link-grammar/ AbiWord Link Grammar Project]
* [http://www.eturner.net/linkgrammar-wn/ LinkGrammar-WN] , lexicon expansion for the Link Grammar Parser

Language Extensions

* [http://www.ling.ohio-state.edu/~jonsafari/arabiclg/bin/arabiclg.html Arabic Link Grammar extension] ( [http://www.ling.ohio-state.edu/~jonsafari/arabiclg/arabiclg.20060829.tar.bz2 Source package] )
* [http://www.ling.ohio-state.edu/~jonsafari/persianlg/persianlg-0.8.5.tar.gz Persian Link Grammar extension] :* [http://students.cs.byu.edu/~jonsafar/persianlg.html Online Persian demonstration]
* [http://sz.ru/parser/ Russian Link Grammar demonstration]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Link Grammar Parser — The Link Grammar Parser or LinkParser is a parser for English which analyzes sentences using the Link Grammar framework.It was written by Davy Temperley, Daniel Sleator, and John Lafferty of Carnegie Mellon University. Examples * Find the verb in …   Wikipedia

  • Grammar checker — In computing terms, a grammar checker is a program, or part of a program, that attempts to verify written text for grammatical correctness. Grammar checkers are most often implemented as a feature of a larger application, such as a word processor …   Wikipedia

  • Grammar framework — In theoretical linguistics, the following fundamental approaches towards constructing grammar frameworks for natural languages are distinguished:*Generative grammar: algorithmic (phrase structure grammars) **Transformational grammar (1960s)… …   Wikipedia

  • Grammar Explorer — is a language learning resource that was co funded by the European Commission as part of its [http://ec.europa.eu/education/programmes/socrates/lingua/index en.html Lingua programme] within the SOCRATES programme. The grammar is based on the… …   Wikipedia

  • link — 01. Detectives were able to [link] the murderer to the crime using DNA evidence. 02. The [link] between smoking and cancer is too strong to ignore. 03. The kids [linked] arms, and skated around the rink laughing and shouting. 04. There is a… …   Grammatical examples in English

  • Dependency grammar — Hybrid constituency/dependency tree from the Quranic Arabic Corpus Dependency grammar (DG) is a class of syntactic theories developed by Lucien Tesnière. It is distinct from phrase structure grammars, as it lacks phrasal nodes. Structure is… …   Wikipedia

  • Formal grammar — In formal semantics, computer science and linguistics, a formal grammar (also called formation rules) is a precise description of a formal language ndash; that is, of a set of strings over some alphabet. In other words, a grammar describes which… …   Wikipedia

  • Chatham House Grammar School — CHGS redirects here. For the radio station originally known as CHGS, see CJRW FM. For the non governmental organization formally known as the Royal Institute of International Affairs, see Chatham House. Chatham House Grammar School Chatham House… …   Wikipedia

  • Hungarian grammar — Hungarian language Closeup view of a Hungarian keybo …   Wikipedia

  • HEBREW GRAMMAR — The following entry is divided into two sections: an Introduction for the non specialist and (II) a detailed survey. [i] HEBREW GRAMMAR: AN INTRODUCTION There are four main phases in the history of the Hebrew language: the biblical or classical,… …   Encyclopedia of Judaism


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.