Interaction of Definite Clause Grammars and Tabling

Tabling can be used in conjunction with Definite Clause Grammars to get the
effect of a more complete parsing strategy. When Prolog is used to evaluate
DCG's, the resulting parsing algorithm is * ``recursive descent''*.
Recursive descent parsing, while efficiently implementable, is known to
suffer from several deficiencies: 1) its time can be exponential in the size
of the input, and 2) it may not terminate for certain context-free grammars (in
particular, those that are left or doubly recursive). By appropriate use of
tabling, both of these limitations can be overcome. With appropriate tabling,
the resulting parsing algorithm is a variant of * Earley's algorithm* and
of * chart parsing algorithms*.

In the simplest cases, one needs only to add the directive
` :- auto_table` (see Section 3.8.4) to the source file
containing a DCG specification. This should generate any necessary table
declarations so that infinite loops are avoided (for context-free grammars).
That is, with a ` :- auto_table` declaration, left-recursive grammars can
be correctly processed. Of course, individual ` table` directives may also
be used, but note that the arity must be specified as two more than that shown
in the DCG source, to account for the extra arguments added by the expansion.

However, due to our current implementation of structures in tabling, there are new inefficiencies that can arise. In particular, when using the standard list representation of the input string in a DCG, there may be a large amount of copying and a great deal of space used. What happens is that the input string (i.e. list) may be copied into and out of the table many times. To avoid this problem, the input list can be transformed into a set of datalog atoms. Currently this must be done manually, as explained in [47], available in the tech reports directory.