DCG reversing a string of binary bits

Question

I want to write a (Prolog) DCG which takes in strings of the form a2rev(a) where a is a string of binary bits, e.g. 1012101, 001121100, 0111002001110. My idea was the following :

reverse([])    --> [].
reverse([H|T]) --> reverse(T), [H].

s--> [2].
s--> a,2,b.
a--> [0];[1].
reverse(a,b).

This doesn't work - I am unsure whether I am calling the reverse function incorrectly or if a --> [0];[1] makes sense. Any help appreciated

rajashekar rajashekar · Accepted Answer · 2020-12-17T16:02:50

You are not mixing the dcg and code properly. Here b//1 extracts a binary sequence and s//1 extracts a binary sequence which has your required property.

b([]) --> [].
b([0 | X]) --> [0], b(X).
b([1 | X]) --> [1], b(X).
s(X) --> b(X), [2], {reverse(X, Y)}, b(Y).

The reverse constraint is added in a {} block using the reverse/2 predicate. If instead you want to use reverse//1 dcg itself you can replace s//1 above with:

s(X) --> b(X), [2], reverse(X).

This gives

?- phrase(s(X), [1, 1, 0, 2, 0, 1, 1]).
X = [1, 1, 0]

For better clarity of what is going on when mixing code and dcg try checking listing(b) and listing(s).

DCG reversing a string of binary bits

1 Answers