Link grammar

Encyclopedia : L : LI : LIN : Link grammar

Link grammar (LG) is a theory of syntax by Davy Temperley and Daniel Sleator which builds simple 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.

Contents

1 Syntax
2 Examples

2.1 Example 1
2.2 Example 2

3 Applications
4 Implementations
5 References
6 External 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+;

: & S+;

: & O-;

: S- & ;

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+;

: & ;

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

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

Applications

AbiWord checks grammar using Link Grammar

AbiWord, a free word processor, uses Link Grammar for on-the-fly grammar checking. Words that cannot be linked anywhere are underlined in green.

Link Grammar has also been employed for information extraction of biomedical texts, 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 a license compatible with the GNU General Public License.

There are also Perl and Ruby implementations available.

References

Schneider, Gerold (1998). A Linguistic Comparison Constituency, Dependency, and Link Grammar. Masters Thesis, University of Zurich. [PDF]
Sleator, Daniel and Temperly, Davy (1993). Parsing English with a Link Grammar. Third International Workshop on Parsing Technologies. [PDF]

External links

[The Link grammar homepage]

*[Online English demonstration]

*[Link Grammar Forum]

[Persian LG-parser extension]

*[Online Persian demonstration]

[Russian Link Grammar demonstration]

[Perl binding]

[Ruby binding]

[OCaml binding]

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.