Some doubts about BNF grammars and Prolog's DCG grammars

Question

I am studying grammars in Prolog and I have a litle doubt about conversions from the classic BNF grammars to the Prolog DCG grammars form.

For example I have the following BNF grammar:

<s> ::= a b
<s> ::= a <s> b

that, by rewriting, generates all strings of type:

ab
aabb
aaabbb
aaaabbbb
.....
.....
a^n b^n

Looking on the Ivan Bratko book Programming for Artificial Intelligence he convert this BNF grammar into DCG grammar in this way:

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

At a first look this seems to me very similar to the classic BNF grammar form but I have only a doubt related to the , symbol used in the DCG

This is not the symbol of the logical OR in Prolog but it is only a separator from the character in the generated sequence.

Is it right?

Answer 1

You can read the , in DCGs as and then or concatenated with:

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

and

t -->
  [a,b].

is the same:

?- phrase(s,X).
X = [a, b].

?- phrase(t,X).
X = [a, b].

It is different to , in a non-DCG/regular Prolog rule which means logical conjunction (AND):

a.
b.

u :-
 a,
 b.

?- u.
true.

i.e. u is true if a and b are true (which is the case here).

Another difference is also that the predicate s/0 does not exist:

?- s.
ERROR: Undefined procedure: s/0
ERROR:     However, there are definitions for:
ERROR:         s/2
false.

The reason for this is that the grammar rule s is translated to a Prolog predicate, but this needs additional arguments. The intended way to evaluate a grammar rule is to use phrase/2 as above (phrase(startrule,List)). If you like, I can add explanations about a translation from DCG to plain rules, but I don’t know if this is too confusing if you are a beginner in Prolog.

Addendum: An even better example would have been to define t as:

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

Where the evaluation with phrase results in the list [b,a] (which is definitely different from [a,b]):

?- phrase(t,X).
X = [b, a].

But if we reorder the goals in a rule, the cases in which the predicate is true never changes (*), so in our case, defining

v :-
  b,
  a.

is equivalent to u.

(*) Because prolog uses depth-first search to find a solution, it might be the case that it might need to try infinitely many candidates before it would find the solution after reordering. (In more technical terms, the solutions don't change but your search might not terminate if you reorder goals).