Skip to content
Publications

Article · May 1, 2002

A Left Corner Parser for Tree Adjoining Grammars

Víctor J. Díaz, Vicente Carrillo, Miguel Á. Alonso

Abstract

Introduction Tabular parsers can be dened as deduction systems where formulas, called items, are sets of complete or incomplete constituents (Sikkel, 1997; Shieber, Schabes and Pereira, 1995). Formally, given an input string w = a 1 . . . a n with n 0 and a grammar G, a parser IP is a tuple (I, H,D) is a set of items, H is a set of hypothesis ([a i , i - 1, i] with 1 n) that encodes the input string, and is a set of deduction steps that determines how items are combined in order to deduce new items. The deductive approach allows us to establish relations between two parsers in a formal way. One of the most interesting relations between parsers are lters because they can be used to improve the performance of tabular parsers in practical cases. The application of a lter to a parser yields a new parser which performs less deductions or contracts sequences of deductions to single deduction steps. One well-known example of a lter is the relation between Earley and Left

Natural Language Processing Techniquessemigroups and automata theorySyntax, Semantics, Linguistic Variationleft-corner parsingtree adjoining grammarsdeductive systems

More by Miguel Alonso