立即学习Prolog!DCG实践示例

Question

我一直在学习Prolog Now!作为自学,我现在正在学习有限的条款语法.我对其中一个实践课程的任务有些困难.任务内容如下:

形式语言a ⁿ b ^2m c ^2m d ⁿ由以下形式的所有字符串组成:一个完整的 s 块后跟一个完整的b s 块,然后是一个完整的c s 块,接着是一个不间断的d s 块使得a和d块的长度完全相同,并且c和d块也是完全相同的长度,并且还分别由偶数个c s和d s组成.例如,ε,abbccd和aaabbbbccccddd都属于ⁿ b ^2m c ^2m d ⁿ.写一个生成这种语言的DCG.

我能够编写生成ⁿ d ⁿ,b ^2m c ^2m,甚至ⁿ b ^2m和c ^2m d ^n的规则 ......但我似乎无法将所有这些规则加入到ⁿ b ^2m c ^2m中 d ^ñ.以下是我可以生成ⁿ d ⁿ和b ^2m c ^2m的规则.

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

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

是ⁿ b ^2m c ^2m d ⁿ真的是CFG,是否可以仅使用课程中教授的内容编写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] ;