How can I create this DCG in Prolog?

Question

I want to create a DCG so that these languages ​​are accepted:

• with
• bbbcbbb
• bbacbba
• abacaba
• aababacaababa

As you can see, this means that there is a certain order of a and b, then one c, and then again the same order as before c. If these conditions are not met, they will not work.

I am here with my approach (it works, but also recognizes incorrect words)

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

Can any of you help me, what do I need to change? I do not know how to do that. Thank you very much.

Answer 1

DCG is really a Prolog program, pre-processed by adding hidden arguments that implement a list of differences. 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 describe is neither regular nor contextual. Therefore, you need to resort to the Prolog extensions offered by DCG. There are some idioms you can get used to:

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

Using this nonterminal, we can describe a sequence that is repeated and shared by a single character:

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

This is clearly too general. You only need ab and c . Now you can add additional requirements:

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

So now:

  s --> rep(_,c). 

An alternative is the "hard code" of the grammar, as @CapelliC showed. Using seq//1 makes the approach more flexible.

It’s convenient enough to use double quotes for a list of characters. See this answer on how to enable the use of double quotes to represent a list of characters.