问题-序言中的正式语言 [英] Question - formal language in prolog

问题描述

我正在尝试构建一个DCG，该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].

I am trying to build a DCG which recognizes all lists which match this form : a^n b^2m c^2m d^n.
I have written up the following rules:
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)以便我可以看到此语法返回的所有可能的字符串时，它会循环到无穷大.

When I try to evaluate a string with those specifications, like the list [a,b,b,c,c,d], it works. But when I try to evaluate the query phrase(s, X) so that I can see all the possible strings returned by this grammar, it loops to infinity.

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

Is there something wrong with the way I have build the DCG?

推荐答案

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

You can enumerate the strings fairly with iterative deepening:

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

这篇关于问题-序言中的正式语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！