prolog - 在 Prolog 中使用 DCG 时，有没有一种方法可以递归调用非终结符号？

Question

我一直在尝试将我创建的用于表示基本有限自动机的一段 Prolog 代码转换为 DCG。基本上，它确保可接受的输入是 0 和 1 字符串中倒数第三个元素为 1 的输入。

例如[1,0,0,1,0,1]是可以接受的，但[1,0,1,0,0,0]不是。

accept(L) :- steps(q0,L,F), final(F).

steps(Q,[],Q).

steps(Q,[H|T],Q2) :- tran(Q,H,Qn), steps(Qn,T,Q2).

final(q1).

tran(Y,0,n0) :- Y = q0; Y = q1; Y = n0.

tran(Y,1,n1) :- Y = q0; Y = q1; Y = n0. 

tran(n1,X,h1):- X = 0 ; X = 1.

tran(h1,X,q1):- X = 0 ; X = 1.

我的问题本质上是步骤谓词的第二个子句，其中“tran（Q，H，Qn）”的输出用作步骤（Qn，T，Q2）的输入，在这种情况下是变量Qn。

我想出的DCG如下：

accept(L) --> final(F),{F = steps(q,L)}.

steps(Q,[]) --> [Q].


steps(Q,[H|T]) --> steps(E,T), {E = tran(Q,H)}.

final(F)  --> [q1], {F = q1}.

tran(Y,0) --> [n0], {Y = q;Y = q1;Y = n0}.

tran(Y,1) --> [n1], {Y = q;Y = q1;Y = n0}.

tran(n1,X) -->[h1], {X = 0; X = 1}.

tran(h1,X) -->[q1], {X = 0; X = 1}.

我基本上想知道是否有另一种方法可以确保 DCG 第二行中的变量 E 可用于表示 tran(Q,H) 而不是将其定义为迄今为止尚未起作用的额外目标。

标签： prologdcg

Answer 1

DCG描述列表。与 Prolog 中的其他所有内容不同，它们隐含地描述了这些列表。您在 Prolog 中计算的每个值都需要通过参数从谓词中传递出去——DCG 描述的列表除外，您不通过参数表示。相反，它们被表示为隐式 DCG 状态。（将列表作为参数也有一些用途，但并不常见。）

这意味着当您将谓词转换为 DCG 时，您会删除列表参数。但是您必须保留所有其他参数，以便您可以与程序的其余部分进行通信。

因此，例如，如果您有以下谓词：

abc(A, B, C, [A, B, C]).

?- abc(a, b, c, ABC).
ABC = [a, b, c].

要将其转换为描述列表的 DCG，[A, B, C]请从参数中删除列表但保留所有其他参数：

abc(A, B, C) -->
    [A, B, C].

?- phrase(abc(a, b, c), ABC).
ABC = [a, b, c].

这对您的程序意味着什么是您的谓词

accept(List) :- ...

将变成没有参数的 DCG：

accept --> ...describe the list somehow...

和你的steps谓词：

steps(Q, Steps, Q2) :- ...

将保留状态Q和Q2作为参数，但将删除列表参数：

steps(Q, Q2) --> ...describe the steps somehow...

有了这些知识，翻译的第一部分就相当机械了：

accept -->
    steps(q0, F),
    { final(F) }.

steps(Q, Q) -->
    [].
steps(Q, Q2) -->
    tran(Q, Qn),
    steps(Qn, Q2).

至于其余部分，您在转换 DCG 中有些困惑，因为突然间，您看起来像是在尝试描述状态列表而不是输入符号列表. 这部分是因为您选择了错误的变量名。这不完全是你的错。许多 Prolog 文本是由具有数学背景的人编写的，并且有时是在将书籍打印在纸上（这很昂贵，因此程序必须比其他任何东西都更紧凑）或存储在又小又慢的存储设备上（这再次意味着它们必须是紧凑的高于一切）或在微型计算机屏幕上观看（这再次意味着它们必须是紧凑的高于一切）。我们不再有这些限制，因此我们可以摆脱过去的束缚。尽管过时的 Prolog 传统教给你什么，选择好的变量名是你的责任。我的意思是说：如果一个变量描述了一个状态，它应该被调用State而不是Y（或者，是的，在自动机理论Q中可以是规范的），如果一个变量描述了一个符号，它应该被调用Symbol而不是X.

反正。这是一个固定版本：

tran(Q, n0) --> [0], {Q = q0 ; Q = q1 ; Q = n0}.
tran(Q, n1) --> [1], {Q = q0 ; Q = q1 ; Q = n0}.
tran(n1, h1) --> [Symbol], {Symbol = 0 ; Symbol = 1}.
tran(h1, q1) --> [Symbol], {Symbol = 0 ; Symbol = 1}.

原始谓词的行为如下：

?- accept([1, 0, 0, 1, 0, 1]).
true ;
false.

?- accept([1, 0, 1, 0, 0, 0]).
false.

固定 DCG 版本的行为相同：

?- phrase(accept, [1, 0, 0, 1, 0, 1]).
true ;
false.

?- phrase(accept, [1, 0, 1, 0, 0, 0]).
false.