tailieunhanh - Báo cáo khoa học: "Prediction in Chart Parsing Algorithms for Categorial Unification Grammar"

Natural language systems based on Categorial Unification Grammar (CUG) have mainly employed bottomup parsing algorithms for processing. Conventional prediction techniques to improve the efficiency of the • parsing process, appear to fall short when parsing CUG. Nevertheless, prediction seems necessary when parsing grammars with highly ambiguous lexicons or with noncanonical categorial rules. In this paper we present a lexicalist prediction technique for CUG and show thai this may lead to considerable gains in efficiency for both bottom-up and top-down parsing. . | Prediction in Chart Parsing Algorithms for Categorial Unification Grammar Gosse Bouma Computational Linguistics Department University of Groningen . box 716 NL-9700 AS Groningen The Netherlands e-mail gosse@let. Abstract Natural language systems based on Categorial Unification Grammar CUG have mainly employed bottom-up parsing algorithms for processing. Conventional prediction techniques to improve the efficiency of the parsing process appear to fall short when parsing CUG. Nevertheless prediction seems necessary when parsing grammars with highly ambiguous lexicons or with non-canonical categorial rules. In this paper we present a lexicalist prediction technique for CUG and show that this may lead to considerable gains in efficiency for both bottom-up and top-down parsing. 1 Preliminaries Categorial Unification Grammar. Unificationbased versions of Categorial Grammar known as CUG or UCG have attracted considerable attention recently see for instance Uszkoreit 1986 Karttunen 1986 Bouma 1988 Bouma et al. 1988 and Calder et al. 1988 . The categories of Categorial Grammar CG can be encoded easily as feature-structures in which the attribute cat dominates either an atomic value in case of an atomic category or a structure with attributes val dir and arg in case of a complex category . Morphosyntactic information can be added by introducing additional labels. An example of such a category represented as attribute-value matrix is presented below. 7VP -t-nom N nom s val cat np case nom cat dir r ight cat n arg case nom num sg - The combinatory rules of classical CG A A B B rightward application and A B B A leftward application can be encoded as highly schematic rewrite rules associated with an attribute-value graph Rightward Application Rule Xo -X 1 x2 xo 1 val 1 Xi cat dir right arg 2 . x2 2 Leftward Application Rule X0 X1 x2 Xo 1 Xi 2 val 1 1 x2 cat dir left arg 2 CUG is a lexicalist theory language specific information about word order subcategorization .