6

我正在尝试构建一个 DCG，它可以识别与此表单匹配的所有列表：a^n b^2m c^2m d^n。
我写了以下规则：
s --> [].
s --> ad.
ad --> a, ad, d.
ad --> bc.
bc --> b, b, bc, c, c.
bc --> [].
a --> [a].
b --> [b].
c --> [c].
d --> [d].

当我尝试评估具有这些规范的字符串时，例如 list [a,b,b,c,c,d]，它可以工作。但是，当我尝试评估查询phrase(s, X)以查看此语法返回的所有可能字符串时，它会循环到无穷大。

我构建 DCG 的方式有问题吗？

4

4 回答 4

6

您可以通过迭代深化公平地枚举字符串：

?- length(Ls, _), phrase(s, Ls).
Ls = [] ;
Ls = [] ;
Ls = [a, d] ;
Ls = [a, a, d, d] ;
Ls = [b, b, c, c] ;
etc.
于 2011-01-04T17:01:54.850 回答
1

@Simon 使用 DGC 的方法是正确的，但您的尝试有两个问题。

第一个是您在如下子句中留下了递归：

ad --> a, ad, d.

这也是它循环到无穷大的原因之一。

第二个问题是这种形式语言不能构建为上下文无关语法，因此您需要一个额外的变量，例如 count。

s(Count) --> a(Count),b(Count),c(Count),d(Count).
a(0) --> [].
a(succ(Count)) --> [a],a(Count).
b(0) --> [].
b(succ(Count)) --> [b,b],b(Count).
c(0) --> [].
c(succ(Count)) --> [c,c],c(Count).
d(0) --> [].
d(succ(Count)) --> [d],d(Count).

然后使用以下目标查询它s(_, L, []).

我知道这是一个老问题，但也许有人从现在开始会发现正确的答案很有用。

于 2019-01-27T20:40:16.343 回答
0

我没有看到这个问题的序言部分。答案很大程度上取决于您如何实现此语法。

我最好的猜测是颠倒规则的顺序，首先应用终止规则。

于 2011-01-04T15:21:51.030 回答
0

我写这个是为了帮助限制解决方案，即使有无限的解决方案。但我意识到有一种方法可以重新排列规则以首先获得更短的结果。

因为 在它试图满足before 之前ad --> a, ad, d.被评估。我会放在前面。和规则也是如此ad --> bc.ad --> a, ad, a.ad --> bc.ad --> bc.ad --> a, ad, a.bc --> b, b, bc, c, c.bc --> [].

正如 arian 指出的那样，首先应用终止规则，将确保首先找到较短的解决方案。

我还想指出，对于[]s 和 s -> ad -> bc -> [] 有两种解决方案，s --> [].因为它是多余的，所以我会消除它。

总而言之，我会尝试这个解决方案：

s --> ad.
a --> [a].
b --> [b].
c --> [c].
d --> [d].
ad --> bc.
bc --> [].
ad --> a, ad, d.
bc --> b, b, bc, c, c.

原帖：

我不得不查找如何进行计数（自从我做 prolog 以来已经有一段时间了）但是有一个无限的数字，并且由于 prolog 试图找到所有解决方案，它永远不会停止寻找，尽管我相信你会碰到一个堆栈在此之前流程或一些错误:)。

限制结果数量的一种方法是限制解决方案的大小

 phrase(s, X), length(X, 4).

获取具有恰好 4 个值的所有解决方案，即

X = [a, a, d, d]
X = [b, b, c, c]

增加到 6 将产生：

X = [a, a, a, d, d, d]
X = [a, b, b, c, c, d]

或使用范围：

 phrase(s, X), length(X, Y), Y >= 4 , Y < 10, Y != 6.
于 2011-02-02T02:31:51.927 回答