Module dcg [Preloaded]

Definite clause grammars (DCG) are an extension of context free grammars [5]. DCGs allow arbitrary tree structures to be built in the course of parsing and they allow extra conditions dependent on auxiliary computations. A grammar rule can have one of the following two forms. The second form is known as a push-back grammar rule, since it will complete with reinstalling R:

P    --> Q.   % DCG rule without push back
P, R --> Q. % DCG rule with push back

The term expansion augments the head by two additional parameters that are to represent the sentence position before and after the non-terminal that is defined. A grammar head with predicate identifier p/n will be turned into a normal Prolog head with predicate identifier p/n+2. The new predicate identifier can be used in system predicates such as listing/1, spy/1, etc... The outcome of this first expansion is basically:

phrase(P, I, O) :- phrase(Q, I, O).
phrase(P, I, O) :- phrase(Q, I, H), phrase(R, O, H).

The term expansion will then go to work and tackle the head of the new Prolog rule, whereas the goal expansion will tackle the body. The goal expansion will introduce unifications (=)/2 here and then to keep the expansion steadfast. One requirement is that the two queries phrase(G, I, O) and (phrase(G, I, H), H = O) should return the same results. This allows for example for a consistent definition of phrase(G, I) as an expansion to phrase(G, I, []).

Example:
?- [user].
factor(X) --> "(", expr(X), ")".

Yes
?- listing(factor/3).
factor(B, [40|A], C) :- expr(B, A, [41|C]).

We see in the example that the translation does not make use of the connection predicate ‘C’/3 for terminals. Instead terminals are directly based on the list definition of ‘C’/3 and translated into corresponding list equations. If possible these equations are merged into the head or into the body goals of the grammar rule. This gives better performance but renders the grammar mechanism not anymore customizable via ‘C’/3.

The DCG grammar mechanism is extensible. The invocation part can be extended by simul-taneously adding custom clauses to the multi-file predicates phrase/3 and phrase_abnormal/1. The expansion part can be extended by simultaneously adding custom clauses to the multi-file predicates phrase_expansion/4, phrase_expansion_abnormal/1 and sys_phrase_expansion/4. The module tecto is an example where this mechanism is used to define additional grammar constructs that are not strictly non-terminals.

The following grammar rule predicates are provided. The (grammar) marking indicates that this operator is only understood in the context of the push back or body position of the grammar operator (-->)/2:

phrase(A, I, O):
Succeeds when the list I starts with the phrase A giving the remainder O. Can be used for parsing when I is input and for un-parsing when I is output. The predicate is multi-file and can be extended by the end-user.
phrase_abnormal(A):
Succeeds for those phrases A that are extended in phrase/3. The predicate is multi-file and can be extended by the end-user.
phrase(A, I):
Succeeds when the list I starts with the phrase A giving the empty remainder.
phrase_expansion(A, I, O, G):
Succeeds when the phrase A extended by the input I and the output O results in the steadfast goal G. The predicate is multi-file and can be extended by the end-user.
P (grammar):
The grammar non-terminal P succeeds whenever the callable P extended by the current input and output succeeds.
A, B (grammar):
The grammar connective succeeds whenever A and B succeed. The output of A is conjoined with the input of B.
A ; B (grammar):
The grammar connective succeeds whenever A or B succeeds. The goal arguments A and B are cut transparent.
A -> B; C (grammar):
The grammar connective succeeds when A succeeds and then whenever B succeeds, or else whenever C succeeds. The goal arguments B and C are cut transparent. The output of A is conjoined with the input of B.
A *-> B; C (grammar):
The grammar connective succeeds whenever A succeeds and then whenever B succeeds, or else whenever C succeeds. The goal arguments B and C are cut transparent. The output of A is conjoined with the input of B.
A -> B (grammar):
The grammar connective succeeds when A succeeds and then whenever B succeeds. The goal argument B is cut transparent. The output of A is conjoined with the input of B.
A *-> B (grammar):
The grammar connective succeeds whenever A succeeds and then whenever B succeeds. The goal argument B is cut transparent. The output of A is conjoined with the input of B.
call(A) (grammar):
Whenever the goal argument A succeeds then the grammar connective succeeds.
fail (grammar):
The grammar connective fails.
{A} (grammar):
The grammar connective succeeds whenever the goal argument A succeeds. The goal argument A is cut transparent and not grammar translated.
\+ A (grammar):
When the goal argument A succeeds, then the grammar connective fails. Otherwise the grammar connective succeeds. The second argument is left loose.
! (grammar):
The grammar connective removes pending choice and then succeeds once.
[A1, …, An] (grammar):
The grammar connective succeeds when the terminals A1, …, An can be consumed.
phrase_expansion_abnormal(A):
Succeeds for those phrases A that are extended in phrase_expansion/4 and sys_phrase_expansion/4. The predicate is multi-file and can be extended by the end-user.
sys_phrase_expansion(A, I, O, G):
Succeeds when the phrase A extended by the input I and the output O results in the not-necessarily steadfast goal G. The predicate is multi-file and can be extended by the end-user.

The following grammar rule operators are provided. The (grammar) marking indicates that this operator is only understood in the context of the head position of the grammar operator (-->)/2:

P (grammar):
The grammar non-terminal P is defined with the callable P extended by the current input and output.
H --> B:
The construct defines a grammar rule with grammar head H and grammar body B.
H, P --> B:
The construct defines a push back with grammar head H, push back P and grammar body B.

Comments