在prolog中编写上下文无关语法

Question

假设我有以下上下文无关语法.

S -> A
A -> mAn
A -> o

这怎么看prolog？这是我尝试过但它不起作用.第二行似乎是问题所在.

S(Z) :- A(Z).
A(Z) :- append([m],X,Z2), A(X), append(Z2,[n],Z).
A([o]).

Answer 1

由于语法不是左递归的，我们可以使用DCG：

s --> a.
a --> [m], a, [n].
a --> [o].

然后我们可以解析或生成所有接受的序列。例如，生成：

?- length(L, _), phrase(s, L).
L = [o] 
L = [m, o, n] 
L = [m, m, o, n, n] 
...

检查 Prolog 代码：

?- listing(s).
s(A, B) :-
    a(A, B).

?- listing(a).
a([m|A], C) :-
    a(A, B),
    B=[n|C].
a([o|A], A).

由于有差异列表，不需要append/3

使用append/3进行编辑

s(Z) :- a(Z).
a(Z) :- append([m|X],[n],Z), a(X).
a([o]).

SWI-Prolog 有append/2（简单地基于正确链接的append/3），它提供了一个更具可读性的替代方案

a(Z) :- append([[m],X,[n]], Z), a(X).

无论如何，我们必须在列表构建/拆分后递归调用 a/1