How can I create this DCG in Prolog?

Question

I want to create a DCG that languages like this get accepted:

• c
• bbbcbbb
• bbacbba
• abacaba
• aababacaababa

As you can see this means that there is a specific order of a and b, then one c and then again the exact same order as before the c. If these conditions are not met it shall fail.

I am currently here with my approach (works, but also recognizes wrong words)

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

Can someone of you help me out what I need to change? I don't know how to go on. Thanks a lot.

Answer 1

A DCG is really just a Prolog program, preprocessed adding hidden arguments that implement a difference list. We can always add our own parameters, and use pattern matching. Then

s --> ab(X), [c], ab(X). 
ab([a|T]) --> [a], ab(T).
ab([b|T]) --> [b], ab(T).
ab([]) --> [].

?- atom_chars(aababacaababa,Cs),phrase(s, Cs).
Cs = [a, a, b, a, b, a, c, a, a|...] 

Answer 2

The language you are describing is neither regular nor context free. So you need to resort to the Prolog extensions that are offered in DCGs. There are some idioms you might get used to:

% any sequence

seq([]) -->
   [].
seq([E|Es]) -->
   [E],
   seq(Es).

With this non-terminal, we might describe a sequence that is repeated and separated by one character:

rep(Seq, Sep) --> 
   seq(Seq),
   [Sep],
   seq(Seq).

That is clearly too general. You only wanted ab and c. You may now add further requirements:

rep(Seq, Sep) -->
   seq(Seq),
   {phrase(abs,Seq)},
   [Sep],
   seq(Seq).

 abs --> [] | ("a"|"b"), abs.

So now:

 s -->
     rep(_,c).

The alternative is to "hard code" the grammar, as @CapelliC has shown. Using seq//1 makes the approach a bit more flexible.

It is quite convenient to use double quotes for list of characters. See this answer how to permit to use double-quotes to represent a list of chars.