A Predictive Bottom-up Evaluator

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.