如何在Prolog中创建此DCG？

Question

我想创建一个像这样的语言被接受的DCG:

• C
• bbbcbbb
• bbacbba
• abacaba
• aababacaababa

正如您所看到的,这意味着a和b的特定顺序,然后是c,然后再次与c之前的顺序完全相同.如果不满足这些条件,它将失败.

我目前在这里采用我的方法(工作,但也识别错误的单词)

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

你们有人可以帮我解决我需要改变的问题吗？我不知道该怎么做.非常感谢.

Answer 1

DCG实际上只是一个Prolog程序,预处理添加了实现差异列表的隐藏参数.我们总是可以添加自己的参数,并使用模式匹配.然后

s --> ab(X), [c], ab(X). 
ab([a|T]) --> [a], ab(T).
ab([b|T]) --> [b], ab(T).
ab([]) --> [].

?- atom_chars(aababacaababa,Cs),phrase(s, Cs).
Cs = [a, a, b, a, b, a, c, a, a|...] 

Answer 2

您描述的语言既不是常规语言也不是上下文.因此,您需要求助于DCG中提供的Prolog扩展.你可能习惯了一些习语:

% any sequence

seq([]) -->
   [].
seq([E|Es]) -->
   [E],
   seq(Es).

使用这个非终端,我们可能会描述一个重复并由一个字符分隔的序列:

rep(Seq, Sep) --> 
   seq(Seq),
   [Sep],
   seq(Seq).

这显然太笼统了.你只想ab和c.您现在可以添加更多要求:

rep(Seq, Sep) -->
   seq(Seq),
   {phrase(abs,Seq)},
   [Sep],
   seq(Seq).

 abs --> [] | ("a"|"b"), abs.

所以现在:

 s -->
     rep(_,c).

另一种方法是"硬编码"语法,正如@CapelliC所示.使用seq//1使方法更灵活.

使用双引号作为字符列表非常方便.请参阅此答案如何允许使用双引号来表示字符列表.