在 Prolog 中使用 DCG 时，有没有办法递归调用非终结符？
我一直在尝试将我创建的一段 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) 而不是将其定义为迄今为止尚未起作用的额外目标。
DCG描述列表。与 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.