Palindrome Revisited

It is also possible to execute grammar rules in a forward manner by a chart parser. To be able to use the chart parser in a Prolog text one has first to load the chart library. Loading the chart library will install a term expansion that will convert chart rules first into forward chaining rules and then into ordinary Prolog delta rules. Loading the chart library requires the Jekejeke Minlog capability and is done as follows:

:- use_module(library(minimal/chart)).

The example is an adaption of the example already found in the language reference of the Jekejeke Prolog runtime library. It allows detecting palindromes. The way forward grammar rules are currently conceived it is not anymore possible to use them to generate text. It is only possible to detect text. In ordinary DCG rules text is passed around in the logical variables of the non-terminals. In chart DCG rules the text will be represented as facts for the predicate ‘D’/2. For the text “bert” the following facts will be temporarily added:

'D'(97, 3).
'D'(110, 2).
'D'(110, 1).
'D'(97, 0).

The facts will be supplied to the forward chaining component in the above order, from the last text element to the first text element, right-to-left. This is a little bit unusual but has certain advantages. First since the order is fixed it is possible to check for arrived facts only in the first literal of a forward grammar rule. This reduces the number of generated delta rules and speeds up the execution of the parser. Second it is possible to use auxiliary conditions as known from normal definite clause grammars since the goals will be executed left-to-right as soon as the left-most fact arrives.

But we have to see to it that the non-terminals generate ground attributes, since non-ground attributes would currently not yet be correctly preserved by the forward chaining component. This bottom-up condition is not a problem for the palindrome example. The terminal predicate 'D'/3 needs to be declared locally, so that the generated code finds locally some declaration for. Further we need a forward/1 declaration for those non-terminals that do not occur as some first non-terminal of a DCG chart rule. The DCG chart rules itself are denoted by the operator (==:)/2:

:- multifile 'D'/3.
:- thread_local 'D'/3, palin/4.
:- forward palin/5.

palin([], [Middle]) ==:
[Middle].
palin([Middle], []) ==:
[Middle, Middle].
palin([Border | List], Middle) ==:
[Border], palin(List, Middle), [Border].

The words/3 predicate or alternatively the words/4 predicate from the module chart can be used to start the chart parser. These commands will add the ‘D’/3 facts and set the forward chaining engine in motion, so that these commands will already compute the forward chaining closure. The commands will do so in a temporary manner:

?- words("bert", 0, _), listing('D'/3).
:- thread_local 'D'/3.
'D'(116, 3, 4).
'D'(114, 2, 3).
'D'(101, 1, 2).
'D'(98, 0, 1).

The chart/3 construct can then be used to query a non-terminal. The goal expansion will al-ready expand such a construct at compile time, so that as long as the first argument of chart/3 is not a variable the end-user doesn’t has to worry about performance. We can detect the same text as with the normal definite clause grammars. Both the positive and the negative example do their job also in forward chaining:

?- words("racecar", 0, N), chart(palin(X,Y), 0, N).
X = [114,97,99],
Y = [101]

?- words("bert", 0, N), chart(palin(X,Y), 0, N).
No

Forward grammar rules will loop when there are productions with a single goal in the body that form a cycle. On the other hand if this cycle condition is not met forward grammar rules can easily deal with left recursion and they can also easily identify parse chunks.

Comments