tailieunhanh - Báo cáo khoa học: "Lexicalized Context-Free Grammars"

Context-free grammar (CFG) has been a well accepted framework for computational linguistics for a long time. While it has drawbacks, including the inability to express some linguistic constructions, it has the virtue of being computationally efficient, O(n3)-time in the worst case. Recently there has been a gain in interest in the so-called 'mildly' context-sensitive formalisms (Vijay-Shanker, 1987; Weir, 1988; Joshi, VijayShanker, and Weir, 1991; Vijay-Shanker and Weir, 1993a) that generate only a small superset of context-free languages. . | Lexicalized Context-Free Grammars Yves Schabes and Richard c. Waters Mitsubishi Electric Research Laboratories 201 Broadway Cambridge MA 02139 e-mail schabes@ and dick@ Lexicalized context-free grammar LCFG is an attractive compromise between the parsing efficiency of context-free grammar CFG and the elegance and lexical sensitivity of lexicalized treeadjoining grammar LTAG . LCFG is a restricted form of LTAG that can only generate context-free languages and can be parsed in cubic time. However LCFG supports much of the elegance of LTAG s analysis of English and shares with LTAG the ability to lexicalize CFGs without changing the trees generated. Motivation Context-free grammar CFG has been a well accepted framework for computational linguistics for a long time. While it has drawbacks including the inability to express some linguistic constructions it has the virtue of being computationally efficient ơ 7i3 -time in the worst case. Recently there has been a gain in interest in the so-called mildly context-sensitive formalisms Vijay-Shanker 1987 Weir 1988 Joshi Vijay-Shanker and Weir 1991 Vijay-Shanker and Weir 1993a that generate only a small superset of context-free languages. One such formalism is lex-icalized tree-adjoining grammar LTAG Schabes Abeillé and Joshi 1988 Abeillé et al. 1990 Joshi and Schabes 1992 which provides a number of attractive properties at the cost of decreased efficiency O 7ỉ6 -time in the worst case Vijay-Shanker 1987 Schabes 1991 Lang 1990 Vijay-Shanker and Weir 1993b . An LTAG lexicon consists of a set of trees each of which contains one or more lexical items. These elementary trees can be viewed as the elementary clauses including their transformational variants in which the lexical items participate. The trees are combined by substitution and adjunction. LTAG supports context-sensitive features that can capture some language constructs not captured by GFG. However the greatest virtue of LTAG is that it is lexicalized and