An LALR Extension for DCGs in Dynamic Programming

Manuel Vilares Ferro
Miguel Angel Alonso Pardo

Proc. of APPIA-GULP-PRODE'96 Joint Conference on Declarative Programming, pp. 79-88, Donostia-San Sebastián, Spain, July 1996.


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