Automata-based Parsing in Dynamic Programming for Linear Indexed Grammars

Miguel Angel Alonso Pardo
Eric Villemonte de la Clergerie
Manuel Vilares Ferro

in A. S. Narin'yani (ed.), Proc. of DIALOGUE'97 Computational Linguistics and its Applications International Workshop, pp. 22-27, Moscow, Russia, 1997.


Abstract

A general framework for the development of parsing algorithms in dynamic programming for Linear Indexed Grammars (LIG) is derived from the concept of Logic Push-down Automata (LPDA), an operational device for the construction of parsers for logic grammars. By exploiting several properties of the LIG formalism, we can guarantee both termination and completeness, which is not possible in the general case of logic grammars. In this paper we center our attention on the class of weakly predictive parsing strategies, which include bottom-up algorithms. The interpretation in dynamic programming of parsing algorithms belonging to this class can be performed in O(n6) complexity, which is the lower bound achieved for LIG. In this context, a version for LIG of the LR parsing strategy is developed. The results are also applicable to other automata-based strategies, such as Left Corner.

Keywords: Linear Indexed Grammars, Logic Push-Down Automata, LR Parsing, Natural Language Processing.


Miguel Angel Alonso Pardo / alonso@dc.fi.udc.es
Eric Villemonte de la Clergerie / Eric.Clergerie@inria.fr
Manuel Vilares Ferro / vilares@dc.fi.udc.es