Fruits Example

The higher order programming of Jekejeke Prolog is also available for grammar rules. The given example shows how to define a list construct. In the following we will explore how to define a custom grammar construct for repetition, which in turn will be used to define a list. Repetition is not found in definite clause grammar. Other grammar formalisms typically define a construct for repetition since it is a recurring pattern.

For instance the Extended Backus-Naur Form (EBNF) allows curly braces to denote repetitions. Our working example will be the grammar for a fruit list:

fruits :== fruit { "," fruit }. /* EBNF */

In definite clause grammars curly braces do not denote repetition. They are reserved for auxiliary conditions. We will pick the non-terminal repetition//1 and give it the phrase that will be repeated as an argument. The corresponding code looks as follows:

repetition(G) --> G, repetition(G).
repetition(_) --> [].

We can now remodel the EBNF grammar in DCG. We omit the fruit non-terminal. The details of it can be found in the appendix. The fruits non-terminal then reads as follows:

fruits --> fruit, repetition((",", fruit)).

Here are some example queries:

?- phrase(fruits,"appleorange").
No
?- phrase(fruits,"apple,orange,apple").
Yes

In a next step we will extend the DCG by attributes. The repetition construct should take as an argument a phrase G(X) with a parameter X and it should yield the list [X1, .., Xn] of parameter instances that occur during the repetition. Instead of G(X) we can only write call(G,X) in Prolog. Therefore we will formulate repetition//2 as follows:

repetition(G,[X|Y]) --> call(G,X), repetition(G,Y).
repetition(_,[]) --> [].

The fruits production starts with one fruit and the repeats zero, one or many fruits. We can access the first one fruit by fruit(X). The fruits in the repetition of (“,”, fruit(Z)) are identified by the parameter Z. We will use the binder Z\ to pass the parameter to the repetition construct. The new fruits non-terminal then reads as follows:

fruits([X|Y]) --> fruit(X), repetition(Z\(",", fruit(Z)),Y).

By using higher order we don’t lose the bi-directionality of DCG productions. We can use the new non-terminal to parse fruit texts:

?- phrase(fruits(L),"appleorange").
No
?- phrase(fruits(L),"apple,orange,apple").
L = [apple, orange, apple]

And we can use the new non-terminal to generate fruit texts:

?- phrase(fruits([apple, orange]),X), atom_codes(A,X).
A = 'apple,orange',
X = [97, 112, 112, 108, 101, 44, 111, 114, 97, 110, 103, 101]

The example without attributes should work across a great range of Prolog systems. Although there is not yet a definite DCG standard most of the Prolog systems support DCGs with goal parameters.

On the other hand the example with attributes might not immediately work in a Prolog system different from Jekejeke Prolog. Even if the Prolog system has higher order programming in the form of call/n and some variable binder, the higher order constructs might still fail inside a DCG grammar.

Kommentare