Tree adjoining grammar

Tree adjoining grammar (TAG) is a grammar formalism often used in computational linguistics and natural language processing, defined by Aravind Joshi. Tree adjoining grammars are somewhat similar to context free grammars, but the elementary unit is the tree rather than the symbol. Whereas context-free grammars have rules for rewriting symbols as strings of other symbols, tree adjoining grammars have rules for inserting trees into the leaf nodes of other trees (see tree (graph theory) and tree data structure). Tree adjoining grammars are often described as "mildly context-sensitive", meaning that they possess certain properties that make them more context-sensitive than context-free grammars, but less context-sensitive than context-sensitive grammars as defined in the Chomsky hierarchy. Mildly context-sensitive grammars are (it is hoped) powerful enough to model the grammars of natural languages while remaining efficiently parseable in the general case.