问题 - 序言中的形式语言

Question

我正在尝试构建一个识别所有符合此形式的列表的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].

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

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

Answer 1

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

?- length(Ls, _), phrase(s, Ls).
Ls = [] ;
Ls = [] ;
Ls = [a, d] ;
Ls = [a, a, d, d] ;
Ls = [b, b, c, c] ;
etc.