Tree-adjoining Grammar
   HOME





Tree-adjoining Grammar
Tree-adjoining grammar (TAG) is a grammar formalism defined by Aravind Joshi. Tree-adjoining grammars are somewhat similar to context-free grammars, but the elementary unit of rewriting 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 rewriting the nodes of trees as other trees (see tree (graph theory) and tree (data structure)). History TAG originated in investigations by Joshi and his students into the family of adjunction grammars (AG), the "string grammar" of Zellig Harris. AGs handle exocentric properties of language in a natural and effective way, but do not have a good characterization of endocentric constructions; the converse is true of rewrite grammars, or phrase-structure grammar (PSG). In 1969, Joshi introduced a family of grammars that exploits this complementarity by mixing the two types of rules. A few very simple rewrite rules suffice to ge ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Grammar Formalism
A formal grammar is a set of Terminal and nonterminal symbols, symbols and the Production (computer science), production rules for rewriting some of them into every possible string of a formal language over an Alphabet (formal languages), alphabet. A grammar does not describe the semantics, meaning of the strings — only their form. In applied mathematics, formal language theory is the discipline that studies formal grammars and languages. Its applications are found in theoretical computer science, theoretical linguistics, Formal semantics (logic), formal semantics, mathematical logic, and other areas. A formal grammar is a Set_(mathematics), set of rules for rewriting strings, along with a "start symbol" from which rewriting starts. Therefore, a grammar is usually thought of as a language generator. However, it can also sometimes be used as the basis for a "recognizer"—a function in computing that determines whether a given string belongs to the language or is grammatical ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Indexed Grammar
Indexed grammars are a generalization of context-free grammars in that nonterminals are equipped with lists of ''flags'', or ''index symbols''. The language produced by an indexed grammar is called an indexed language. Definition Modern definition by Hopcroft and Ullman In contemporary publications following Hopcroft and Ullman (1979), an indexed grammar is formally defined a 5-tuple ''G'' = ⟨''N'',''T'',''F'',''P'',''S''⟩ where * ''N'' is a set of variables or nonterminal symbols, * ''T'' is a set ("alphabet") of terminal symbols, * ''F'' is a set of so-called ''index symbols'', or ''indices'', * ''S'' ∈ ''N'' is the '' start symbol'', and * ''P'' is a finite set of '' productions''. In productions as well as in derivations of indexed grammars, a string ("stack") ''σ'' ∈ ''F'' * of index symbols is attached to every nonterminal symbol ''A'' ∈ ''N'', denoted by ''A'' 'σ''" and " are meta symbols to indicate the stack. Terminal symbols may not be followed by inde ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Lexicalized Tree Adjoining Grammar
In linguistics, lexicalization is the process of adding words, set phrases, or word patterns to a language's lexicon. Whether ''word formation'' and ''lexicalization'' refer to the same process is controversial within the field of linguistics. Most linguists agree that there is a distinction, but there are many ideas of what the distinction is. Lexicalization may be simple, for example borrowing a word from another language, or more involved, as in calque or loan translation, wherein a foreign phrase is translated literally, as in ''marché aux puces'', or in English, flea market. Other mechanisms include compounding, abbreviation, and blending. Particularly interesting from the perspective of historical linguistics is the process by which ''ad hoc'' phrases become set in the language, and eventually become new words (see lexicon). Lexicalization contrasts with grammaticalization, and the relationship between the two processes is subject to some debate. In psycholinguistics I ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Tree Tuple
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only plants that are usable as lumber, or only plants above a specified height. But wider definitions include taller palms, tree ferns, bananas, and bamboos. Trees are not a monophyletic taxonomic group but consist of a wide variety of plant species that have independently evolved a trunk and branches as a way to tower above other plants to compete for sunlight. The majority of tree species are angiosperms or hardwoods; of the rest, many are gymnosperms or softwoods. Trees tend to be long-lived, some trees reaching several thousand years old. Trees evolved around 400 million years ago, and it is estimated that there are around three trillion mature trees in the world currently. A tree typically has many secondary branches supported clear of t ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


String Grammar
The term "string grammar" in computational linguistics (and computer languages) refers to the structure of a specific language, such that it can be formatted as a single continuous string of text, without the need to have line-breaks (or newlines) to alter the meaning. The appearance of any text in "column 1" (or any column) of a line does not change the meaning of that text in a string grammar. A string grammar can be used to describe the structure of some natural languages, such as English or French, as well as for some computer languages. Note that the string-based structure is for defining the grammar of a language, rather than the formatting of the language itself. The production rules, of the grammar, are in the form of continuous text strings. Benefits of using a string grammar When a ''string grammar'' is used to define a computer language, some string-grammar parsing tools and compiler-generator tools can be used to more easily create a compiler software system ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Weak Equivalence (formal Languages)
In formal language theory, weak equivalence of two formal grammars, grammars means they generate the same set of strings, i.e. that the formal language they generate is the same. In compiler theory the notion is distinguished from strong (or structural) equivalence, which additionally means that the two parse trees are reasonably similar in that the same semantic interpretation can be assigned to both. Vijay-Shanker and Weir (1994) demonstrates that Indexed grammar, Linear Indexed Grammars, Combinatory categorial grammar, Combinatory Categorial Grammars, Tree-adjoining grammar, Tree-adjoining Grammars, and Head grammar, Head Grammars are weakly equivalent formalisms, in that they all define the same string languages. On the other hand, if two grammars generate the same set of derivation trees (or more generally, the same set of abstract syntactic objects), then the two grammars are strongly equivalent. Chomsky (1963) introduces the notion of strong equivalence, and argues that onl ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Head Grammar
Head grammar (HG) is a grammar formalism introduced in Carl Pollard (1984) Pollard, C. 1984. ''Generalized Phrase Structure Grammars, Head Grammars, and Natural Language''. Ph.D. thesis, Stanford University, CA. as an extension of the context-free grammar class of grammars. Head grammar is therefore a type of phrase structure grammar, as opposed to a dependency grammar. The class of head grammars is a subset of the linear context-free rewriting systems. One typical way of defining head grammars is to replace the terminal strings of CFGs with indexed terminal strings, where the index denotes the "head" word of the string. Thus, for example, a CF rule such as A \to abc might instead be A \to (abc, 0), where the 0th terminal, the ''a'', is the head of the resulting terminal string. For convenience of notation, such a rule could be written as just the terminal string, with the head terminal denoted by some sort of mark, as in A \to \widehatbc. Two fundamental operations are then a ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Combinatory Categorial Grammar
Combinatory categorial grammar (CCG) is an efficiently parsable, yet linguistically expressive grammar formalism. It has a transparent interface between surface syntax and underlying semantic representation, including predicate–argument structure, quantification and information structure. The formalism generates constituency-based structures (as opposed to dependency-based ones) and is therefore a type of phrase structure grammar (as opposed to a dependency grammar). CCG relies on combinatory logic, which has the same expressive power as the lambda calculus, but builds its expressions differently. The first linguistic and psycholinguistic arguments for basing the grammar on combinators were put forth by Steedman and Szabolcsi. More recent prominent proponents of the approach are Pauline Jacobson anJason Baldridge In these new approaches, the combinator B (the compositor) is useful in creating long-distance dependencies, as in "Who do you think Mary is talking about?" and th ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Parser
Parsing, syntax analysis, or syntactic analysis is a process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar by breaking it into parts. The term ''parsing'' comes from Latin ''pars'' (''orationis''), meaning part (of speech). The term has slightly different meanings in different branches of linguistics and computer science. Traditional sentence parsing is often performed as a method of understanding the exact meaning of a sentence or word, sometimes with the aid of devices such as sentence diagrams. It usually emphasizes the importance of grammatical divisions such as subject and predicate. Within computational linguistics the term is used to refer to the formal analysis by a computer of a sentence or other string of words into its constituents, resulting in a parse tree showing their syntactic relation to each other, which may also contain semantic information. Some parsing a ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Natural Language
A natural language or ordinary language is a language that occurs naturally in a human community by a process of use, repetition, and change. It can take different forms, typically either a spoken language or a sign language. Natural languages are distinguished from constructed and formal languages such as those used to program computers or to study logic. Defining natural language Natural languages include ones that are associated with linguistic prescriptivism or language regulation. ( Nonstandard dialects can be viewed as a wild type in comparison with standard languages.) An official language with a regulating academy such as Standard French, overseen by the , is classified as a natural language (e.g. in the field of natural language processing), as its prescriptive aspects do not make it constructed enough to be a constructed language or controlled enough to be a controlled natural language. Natural language are different from: * artificial and constructed la ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]