Lexicalized context-free grammars
Yves Schabes, Richard C. Waters · 1993
Lexicalized context-free grammar (LCFG) is an attractive compromise between the parsing efficiency of context-free grammar (CFC) and the elegance and lexical sensitivity of lexicalized treeadjoining grammar (LTAG).LCFC is a restricted form of LTAG that can only generate contextfree languages and can be parsed in cubic time.However, LCF(I supports much of the elegance of LTAG's analysis of English and shares with LTAG the ability to lexicalize CF(I;s without changing the trees generated. MotivationContext-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, Vijay-Shanker, and Weir, 1991; Vijay-Shanker and Weir, 1993a) that generate only a small superset of context-free languages.One such formalism is lexicalized tree-adjoining grammar (LTAG) (Schabes, Abeill~, and Joshi, 1988; Abeillfi et al., 1990;Joshi and Schabes, 1992), which provides a number of attractive properties at the cost of decreased efficiency, O(n6)-time in the worst case (Vijay-Shanker, 1987;Schabes, 1991;Lang, 1990;Vijay-Shanker and Weir, 1993b).