计算 Prolog 中的定子句语法递归

发布于 2024-09-10 14:07:42 字数 171 浏览 3 评论 0原文

我有以下 Prolog 定子句语法：

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

这将导致像 [a,a,b,b] 这样的单词与 [a,b,a,b] 这样的单词相反被接受。简而言之，语法显然是a^nb^n。现在我想将 n 返回给用户。我如何计算n？

原文

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 return n to the user. How can I calculate n?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

苍暮颜 2024-09-17 14:07:42

s(X)-->[a],s(Y),[b],{X is Y+1}.
s(0)-->[].

需要给DCG非终端提供参数。请注意，相等并不像命令式编程语言的赋值那样工作，因此使用了 X is Y + 1。

一些示例输出：

s(X,[a,b,b,b],[]).
false.

s(X,[a,a,a,b,b,b],[]).
X = 3 ;
false.

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.

回复收藏 0 原文

止于盛夏 2024-09-17 14:07:42

s(N, M) --> [a], {N1 is N + 1}, s(N1, M), [b].
s(N, N) --> [].
s(N) --> s(0, N).

用法：

?- phrase(s(N), [a,a,a,b,b,b]).
N = 3

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

回复收藏 0 原文

撩起发的微风 2024-09-17 14:07:42

@thequark 和的答案@LittleBobbyTables 与地面字符串一起使用时效果很好。

但是，如果它们的长度不受限制，就像下面的查询一样，该怎么办？

?- phrase(s(3),_).               % expected: success   
%                                  observed: no answer(s)

?- phrase(s(-10),_).             % expected: failure
%                                  observed: no answer(s)

我们当然希望像上面这样的查询普遍终止！
让我们使用 clpfd 并编写：

:- use_module(library(clpfd)).

s(0) --> [].
s(N) --> {N#>0,N#=N0+1},[a],s(N0),[b].

示例查询：

?- 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.

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.

回复收藏 0 原文

~没有更多了~