Counting definite clause grammar recursions in Prolog
I have the following Prolog definite clause grammar:
s-->[a],s,[b].
s-->[].
This will result in words like [a,a,b,b] being accepted in opposite to words like [a,b,a,b]. To put it in a nutshell the grammar is obviously a^n b^n. Now I want to 开发者_如何学Pythonreturn n to the user. How can I calculate n?
s(X)-->[a],s(Y),[b],{X is Y+1}.
s(0)-->[].
One needs to give parameters to the DCG non terminals. Please take care equality doesn't work exactly like assignment of imperative programming languages so X is Y + 1 was used.
Some sample outputs:
s(X,[a,b,b,b],[]).
false.
s(X,[a,a,a,b,b,b],[]).
X = 3 ;
false.
s(N, M) --> [a], {N1 is N + 1}, s(N1, M), [b].
s(N, N) --> [].
s(N) --> s(0, N).
Usage:
?- phrase(s(N), [a,a,a,b,b,b]).
N = 3
The answers by @thequark and by @LittleBobbyTables work fine when used with ground strings.
But what if they are not bounded in length, like in the following queries?
?- phrase(s(3),_). % expected: success
% observed: no answer(s)
?- phrase(s(-10),_). % expected: failure
% observed: no answer(s)
We surely want queries like the one above to terminate universally! Let's use clpfd and write:
:- use_module(library(clpfd)).
s(0) --> [].
s(N) --> {N#>0,N#=N0+1},[a],s(N0),[b].
Sample queries:
?- phrase(s(N),[a,a,a,a,b,b,b,b]).
N = 4 ; % works like in the other answers
false.
?- phrase(s(3),Xs).
Xs = [a,a,a,b,b,b] ; % now, this works too!
false. % (terminates universally)
?- phrase(s(-10),_). % fails, like it should
false.
精彩评论