prolog - 立即学习 Prolog! DCG实践示例

Question

我一直在Learn Prolog Now!取得进展自学，现在正在学习定子句语法。我在实践类(class)的一项任务中遇到一些困难。 The task内容如下:

The formal language aⁿb^2mc^2mdⁿ consists of all strings of the following form: an unbroken block of as followed by an unbroken block of bs followed by an unbroken block of cs followed by an unbroken block of ds, such that the a and d blocks are exactly the same length, and the c and d blocks are also exactly the same length and furthermore consist of an even number of cs and ds respectively. For example, ε, abbccd, and aaabbbbccccddd all belong to aⁿb^2mc^2mdⁿ. Write a DCG that generates this language.

我能够编写生成 aⁿdⁿ、b^2mc^2m 和甚至 aⁿb^2m 和 c^2mdⁿ...但我似乎无法加入所有这些规则转化为ⁿb^2mc^2mdⁿ。以下是我的规则，可以生成 aⁿdⁿ 和 b^2mc^2m。

s1 --> [].
s1 --> a,s1,d.
a --> [a].
d --> [d].

s2 --> [].
s2 --> c,c,s2,d,d.
c --> [c].
d --> [d].

aⁿb^2mc^2mdⁿ真的是一个CFG吗？是否可以写成仅使用类(class)中教授的内容的 DCG(没有额外的参数或代码等)？如果是这样，任何人都可以为我提供一些指导，让我如何加入这些，以便我能够解决给定的任务？

Answer 1

@Timothy，你的答案有效，但它会生成重复项:

?- length(S,_), s(S,[]).
S = [] ;
S = [a, d] ;
S = [a, d] ;            % XXX
S = [b, b, c, c] ;
S = [a, a, d, d] ;
S = [a, a, d, d] ;      % XXX

这可以通过删除一个子句并保留 DCG 来解决:

s --> x.
s --> a,s,d.

x --> [].
x --> b,b,x,c,c.

% a, b, c, d the same

这会生成:

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