Information flow in tabular interpretations for generalized Push-Down Automata

Eric Villemonte de la Clergerie(*)
INRIA Rocquencourt - BP 105 - 78 153 LE CHESNAY France
phone: +33 1 39 63 54 10 fax: +33 1 39 63 53 30
Eric.Clergerie@inria.fr

Fran\c{c}ois Barth\'elemy
CNAM - 192 rue Saint Martin - 75 003 PARIS France
barthe@cnam.fr

Abstract

This paper presents a general framework for deriving tabular
algorithms for a very large class of stack-based computations, not
only in context-free parsing but in logic programming as well and more
generally for all kinds of ``information'' domains (abstract domains,
constraint domains).
  Tabular algorithms store traces of computations in a table to achieve
computation sharing, which is most useful when dealing with
non-deterministic computations.
  By considering what can be naively described as partial information on
stack elements, we interpret these traces as stack fragments. Tuning
the exact amount of information present in these traces allows us to
improve tabular evaluation of stack-based computations, both by increasing
the sharing of partial computations and by unifying different tabular
algorithms within the same framework.

Key words: Information Flow, Tabulation, Push-Down Automata, Logic Programming,
Parsing.

(*) This work has been partially supported by the grant 95-B030 from CNET