An LALR Extension for DCGs in Dynamic Programming

Manuel Vilares Ferro
Miguel Angel Alonso Pardo

in C. Martín Vide (ed.), Mathematical and Computational Analysis of Natural Language, volume 45 of Studies in Functional and Structural Linguistics, John Benjamins Publishing Company, Amsterdam and Philadelphia, 1998. ISBN 90-272-1554-5.


Abstract

We propose a parsing model for DCGs. Our work embodies in a common frame a dynamic programming construction developed for logical push-down automata, and techniques that restrict the computation to a useful part of the search space inspired by LALR parsing. Unlike preceding approaches, our proposal avoids backtracking in all cases, providing computational sharing and operational completeness for DCG without functional symbols.

Key Words: DCG, Dynamic Programming, LALR Parsing, Push-Down Automata.


Manuel Vilares Ferro / vilares@dc.fi.udc.es
Miguel Angel Alonso Pardo / alonso@dc.fi.udc.es