In actuality, this way to process grammars with tabling is not as efficient as it might be. The reason is that the arguments to the tabled nonterminals consist of lists, and so each time a call is copied into the table, a long list may have to be copied. Also answers consist of tails of the list corresponding to the input string, and these may be long as well. We can use a slightly different representation for the input string to avoid this inefficiency.
Instead of representing the input string as a list, we will store it
in the database, representing it by a set of facts. We will think of
each word in the input sentence as being numbered, starting from 1.
Then we will store the string as a set of facts of the form,
word(n,word), where word is the nth word in the
input string. For example, the string used in the example above,
[1,+,2,*,3,*,'(',4,+,5,')'], would be represented by the
following facts:
word(1,1).
word(2,+).
word(3,2).
word(4,*).
word(5,3).
word(6,*).
word(7,'(').
word(8,4).
word(9,+).
word(10,5).
word(11,')').
Recall that we said that the DCG translation translates lists in the
body of DCG rules to calls to the predicate 'C'/3, which is
defined to process the list input. But we can redefine this predicate
to look at the word/2 predicate as follows:
'C'(I,W,I1) :- word(I,W), I1 is I+1.(We could alternatively use
word/3 facts and explicitly store
the two consecutive integers, so no computation would be involved.)
With this definition of 'C'/3, we can use the same DCG for
parsing but now, rather than using lists to represent positions in the
input, the system uses integers.
% grammar.P
:- table expr/3, term/3.
'C'(I,W,I1) :- word(I,W), I1 is I+1.
eval_string(String,Val) :-
retractall(word(_,_)),
assert_words(String,1,N),
abolish_all_tables,
expr(Val,1,N).
assert_words([],N,N).
assert_words([Word|Words],N,M) :-
assert(word(N,Word)), N1 is N+1, assert_words(Words,N1,M).
expr(Val) --> expr(Eval), [+], term(Tval), {Val is Eval+Tval}.
expr(Val) --> term(Val).
term(Val) --> term(Tval), [*], primary(Fval), {Val is Tval*Fval}.
term(Val) --> primary(Val).
primary(Val) --> ['('], expr(Val), [')'].
primary(Int) --> [Int], {integer(Int)}.
Here we've defined a predicate eval_string to take an input
string as a list, assert it into the database as a set of
word/2 facts and then to call expr to parse and evaluate
it. Notice that we need both to retract any facts previously stored
for word/2 and to abolish any tables that were created during
previous evaluations of strings. This is because old tables are no
longer valid, since the new input string changes the meanings of the
integers that represent positions in the input string.
We can compile and call this predicate as follows:
| ?- [grammar].
[Compiling ./grammar]
++Warning: Redefining the standard predicate: C / 3
[grammar compiled, cpu time used: 1.069 seconds]
[grammar loaded]
yes
| ?- eval_string([1,+,2,*,3,*,'(',4,+,5,')'],V).
V = 55;
no
| ?-
The warning is to alert the user to the fact that a standard predicate
is being redefined. In this case, that is exactly what we want to do,
and so we can safely ignore the warning.