Paris, France
2-3 Avril 1998 / April 2-3, 1998
Organisées par / Organized by INRIA
en collaboration avec / in collaboration with CEDRIC
du / of CNAM
Keywords: TAG, TIG, CFG, Parser.
We improve Rounds' analysis in two respects: first, we introduce a modified class of language definitions that allow restricted forms of negative inductions, and second, we show how to build table-driven recognizers from such definitions. For a wide and natural class of language definitions we thereby obtain fairly efficient recognizers; we can recognize the boolean closure of context-free resp. head languages in the well-known $O(n^3)$ resp. $O(n^6)$ steps on a RAM. Our `bounded' fixed-point formulas apparently can not define an arbitrary \PTIME\ language.
Our method is based on the existence of fixed-points for a class of operators that need neither be monotone nor increasing, but assume a norm or at least a well-founded quasi-ordering on the underlying set.
PLAI, GAIA, or
AMAI), we follow the approach advocated in~\cite{CodishDemoenSagonas}
and use a logic programming system which supports tabling (namely
XSB). To obtain the results of the analysis, we directly compile the
program to be analysed into a tabled logic program such that its
execution by XSB coincides with the abstract interpretation of the
original program. We show how this approach is adapted to
abstractions which satisfy the requirements of the framework of
Bruynooghe~\cite{Bruynooghe@JLP-91} and that the approach is practical
and competitive with state-of-the-art generic abstract interpretation
systems implemented in Prolog. Our experiments are based on the
non-trivial domain of abstract equation systems which is a
parameterized domain which captures structure information together
with modes, linearity and sharing.