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.