A Predictive Bottom-up Evaluator

Manuel Vilares Ferro
Miguel Angel Alonso Pardo

Logic Programming Newsletter, 8(4):9-10, 1995.


This paper presents a recursive query processing strategy on Horn Clauses which plays, with respect to classic context-free parsing algorithm, a similar role to the well known LALR compilation schemes. Over a base structure equipped with an efficient context-free parsing algorithm based on dynamic programming techniques, we define a logic push-down automaton which breaks computations into combinable, shareable and storable sub-computations. The latter provides computation sharing ans operational completeness and solves most of the problemas posed by classic depth-first left-to-right traversals.

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