Prolog dcg generating all words from language

Question

I'm trying to write some dcg grammar in prolog which will describe language of
a^nb^n n>=0
"",ab,aabb,aaabbb itd

All what I wrote is

s --> slowo.
slowo --> [a],slowo,[b],!.
slowo --> [].  

And its good as long as all I want to do is just check if word is correct, but how should dcg grammar look in prolog for ?-phrase(s,X) which will generate all words from my language?

Answer 1

If you're beginning with Prolog, try to avoid the use of !/0. You can generally do better without it.

Here for example, your grammar could be written as follows:

s --> [].
s --> [a], s, [b].

and queried as follows:

?- phrase(s, X).

Note that prolog clauses are picked from left to right and top to bottom, so a rule written at the top of another one will be prioritized when the backtracking is involved.

Answer 2

In addition to @Mog's answer, let us consider the more general case:

What, if the grammar is so complex, that reordering DCG-rules will not help? How can we still enumerate all sentences? If the grammar is formulated in such a manner, that it terminates for a fixed length, we get all sentences with

?- length(Xs, N), phrase(s, Xs).

The goal length alone will enumerate all lists in a fair manner. That is, starting with the shortest [] all lists are enumerated:

?- length(Xs, N).
Xs = [],
N = 0 ;
Xs = [_G307],
N = 1 ;
Xs = [_G307, _G310],
N = 2 ;
Xs = [_G307, _G310, _G313],
N = 3 ;
Xs = [_G307, _G310, _G313, _G316],
N = 4 ; ...

And now, the length being fixed, the goal phrase(s, Xs) will find all answers for that fixed length. As an example, look at Mat's answer to this grammar.

So this is a general method to inspect a grammar's sentences. However - there is a price to pay for this generality! For grammars with finitely many sentences, out method will not terminate:

:- use_module(library(double_quotes)).

s --> "a"|"b".

?- phrase(s, Xs).
Xs = "a" ;
Xs = "b".

This grammar works out of the box, but together with length/2 we get now:

?- length(Xs, N),phrase(s, Xs).
Xs = "a",
N = 1 ;
Xs = "b",
N = 1 ;
**loops**

This method is often called iterative deepening, although this term more precisely imposes a bound to the depth of the derivation. But we are imposing a bound to the actual "output". So iterative deepening is also able to handle left-recursion, whereas length/2 works only for grammars that terminate for a fixed input length.

What makes this technique so particularly interesting in Prolog is that it meshes perfectly with Prolog's chronological backtracking mechanism.

Answer 3

In SWI Prolog, I could use:

s(X, []).

or

phrase(s, X).

(as you suggested) to get all of the strings. In order for that to produce any answers without a stack overflow, however, I needed to reverse the order of the two rules for slowo and remove the cut from the recursive rule.