I am trying to write a dcg that accepts string of the form l0k, where l and k are strings over the alphabet {1, 2, 3} and l is k in reverse. What I have seems to work in that the first answer of a query is correct, but then it keeps going giving more and more wrong answers, and I am wondering if there is a way to fix this without using cuts. This is what I have at the moment:
s --> a(X), [0], a(X).
s --> a(X), s, a(X).
a(X) -->[X].
a --> [1].
a --> [2].
a --> [3].
For
?- s([1,2,3,3,2,1,0|L], []).
I am getting:
L = [1, 2, 3, 3, 2, 1]
L = [0, 0, 1, 2, 3, 3, 2, 1]
L = [_1364, 0, _1364, 0, 1, 2, 3, 3, 2, 1]
L = [_1364, _1370, 0, _1370, _1364, 0, 1, 2, 3, 3, 2, 1]
L = [_1364, _1370, _1376, 0, _1376, _1370, _1364, 0, 1, 2, 3, 3, 2, 1]
L = [_1364, _1370, _1376, _1382, 0, _1382, _1376, _1370, _1364, 0, 1, 2, 3, 3, 2, 1] etc.
A possible solution:
s --> [0].
s --> a(X), s, a(X).
a(1) --> [1].
a(2) --> [2].
a(3) --> [3].
Examples:
?- phrase(s, [1,2,3,3,2,1,0|L], []).
L = [1, 2, 3, 3, 2, 1] ;
false.
?- length(L,_), phrase(s,L,[]).
L = [0] ;
L = [1, 0, 1] ;
L = [2, 0, 2] ;
L = [3, 0, 3] ;
L = [1, 1, 0, 1, 1] ;
L = [1, 2, 0, 2, 1] ;
L = [1, 3, 0, 3, 1] ;
L = [2, 1, 0, 1, 2] ;
L = [2, 2, 0, 2, 2] ;
L = [2, 3, 0, 3, 2] ;
L = [3, 1, 0, 1, 3] ;
L = [3, 2, 0, 2, 3] ;
L = [3, 3, 0, 3, 3] ;
L = [1, 1, 1, 0, 1, 1, 1] ;
L = [1, 1, 2, 0, 2, 1, 1] ;
L = [1, 1, 3, 0, 3, 1, 1] ;
L = [1, 2, 1, 0, 1, 2, 1] ;
L = [1, 2, 2, 0, 2, 2, 1] ;
L = [1, 2, 3, 0, 3, 2, 1] ;
...