Module chart

This Jekejeke Minlog module allows executing definite clause grammars(DCGs) in a forward manner. The ordinary DCG rules of Jekejeke Prolog are not suitable for this purpose since they model terminals by [T|O] = I. We therefore provide special chart DCG rules as part of which model terminals by ‘D’(T,I,O). Chart DCG rules are identified by the (==:)/2 operator:

Syntax:
P ==: Q.      % chart DCG rule

Chart DCG rules do currently not allow for push backs. The term expansion augments the head and body by two additional parameters that are to represent the sentence position before and after the parsing. A predicate identifier p/n will thus be turned into a predicate identifier p/n+2. Further the DCG chart operator (==:)/2 is replaced by the forward chaining operator (<=)/2:

Translation:
chart_post(P, I, O) <= chart_posted(Q, I, O).

The expansion will then go to work and tackle the head and the body. Compared to ordinary DCG rules, the chart DCG rules support fewer constructs. For example we do not yet support the conditional (->)/2 and the higher order calls call/n. On the other hand the look-ahead negation (\+) is already supported.

Let us consider the following example chart DCG rule:

Example:
p(X) ==: "a", q(X), {r(X)}.  % chart DCG rule

As an intermediate results the chart DCG rule will be turned into:

Result:
post(p(X, I, O)) <= posted('D'(97, I, H)), q(X, H, O), r(X)

The above rule will then be turned into a delta computation for the predicate ’D’/3. In general only the first literal of a DCG chart rule will be translated into a delta computation rule, improving efficiency. The words/3 construct can be used to generate the ‘D’/3 facts and the chart/3 construct can be used to query the result of parsing. See the palindrom example for more details.

The following chart DCG predicates are provided:

words([A1, ..., An], I, O):
words([A1, ..., An], I, O, G):
Post the words A1, .., An from index I to index O before further solving.
chart(A, I, O):
Succeeds when there is a phrase A from index I to index O.

The following chart DCG goal expansions are provided:

P:
The non-terminal P is checked.
fail:
The grammar fails.
A, B:
The output of A is conjoined with the input of B.
A; B:
The grammar succeeds when A succeeds or when B succeeds.
[A1, …, An]:
The terminals A1, ..., An are checked.
!:
The choice points are removed.
{A}:
The auxiliary condition is checked.
\+ A:
The negation of A is checked. The output of A is left loose.

The following chart DCG  term expansions are provided:

H ==: B:
Chart DCG rule with chart head H and chart body B.

Kommentare