使用 prolog dcg 匹配矩阵中的模式

Question

是否可以使用 DCG 提取一些 2D 列表，以便它可以由上下文无关语法表示

S -> [ A , B ]

A -> [0,0,0,0,0]
A -> NULL

B -> [1,1,1,1,1]
B -> NULL

例如：

[[0,0,0,0,0], [1,1,1,1,1]] is valid
[[1,1,1,1,1]] is valid, where A is NULL.
[[0,0,0,0,0]] is valid, where B is NULL.

我试过这样的东西

zeros --> [].
zeros --> [0,0,0,0,0].
ones --> [].
ones --> [1,1,1,1,1]
matrix --> [A, B],
    {phrase(zeros, A)},
    {phrase(ones, B)}.

但这不会按照我想要的方式工作，因为在这种情况下，"compiler" 认为我想要一个空列表 '[]' 而不是 NULL。

所以 [[], [1,1,1,1,1]] 会工作，而 [[1,1,1,1,1]] 不会。

我该如何处理？

Answer 1

问题是一旦你写了matrix --> [A, B]，不管A和B是什么，那个规则肯定会生成一个二元列表。

因此您想要生成单元素列表 [A] 或 [B]。您可以明确地这样做：

a --> [0, 0, 0, 0, 0].

b --> [1, 1, 1, 1, 1].

matrix -->
    [A],
    { phrase(a, A) }.
matrix -->
    [B],
    { phrase(b, B) }.
matrix -->
    [A, B],
    { phrase(a, A) },
    { phrase(b, B) }.

这个有效：

?- phrase(matrix, Matrix).
Matrix = [[0, 0, 0, 0, 0]] ;
Matrix = [[1, 1, 1, 1, 1]] ;
Matrix = [[0, 0, 0, 0, 0], [1, 1, 1, 1, 1]].

但是这样打字比较多，如果要扩展的话不是很灵活

所以让我们尝试概括固定的 [A, B] 位。作为第一步，我们可以使用仅描述其自身参数列表的 list//1 DCG：

list([]) -->
    [].
list([X|Xs]) -->
    [X],
    list(Xs).

我们可以这样使用：

?- phrase(list([a, b, c]), Xs).
Xs = [a, b, c].

并用它来定义一个矩阵：

matrix_with_list -->
    list([A, B]),
    { phrase(a, A) },
    { phrase(b, B) }.

这看起来我们还没有取得进展：

?- phrase(matrix_with_list, Matrix).
Matrix = [[0, 0, 0, 0, 0], [1, 1, 1, 1, 1]].

但现在我们可以稍微更改 list//1 以仅描述其参数列表的 子列表 :

optional_list([]) -->
    [].
optional_list([_X|Xs]) -->
    % skip this X!
    optional_list(Xs).
optional_list([X|Xs]) -->
    % keep this X
    [X],
    optional_list(Xs).

其行为如下：

?- phrase(optional_list([a, b, c]), Xs).
Xs = [] ;
Xs = [c] ;
Xs = [b] ;
Xs = [b, c] ;
Xs = [a] ;
Xs = [a, c] ;
Xs = [a, b] ;
Xs = [a, b, c].

现在我们可以修改之前的定义：

matrix_with_optional_list -->
    optional_list([A, B]),
    { phrase(a, A) },
    { phrase(b, B) }.

我们得到：

?- phrase(matrix_with_optional_list, Matrix).
Matrix = [] ;
Matrix = [[1, 1, 1, 1, 1]] ;
Matrix = [[0, 0, 0, 0, 0]] ;
Matrix = [[0, 0, 0, 0, 0], [1, 1, 1, 1, 1]].

不错！但是，所有这些 phrase/2 调用都不是很好，即使它们引用的元素最终没有出现在矩阵中。

所以让我们进一步概括一些，到一个 DCG，它的参数是一个 DCG 列表，它描述了由这些 DCG 描述的列表列表的子列表：

optional_phrase([]) -->
    [].
optional_phrase([_Rule|Rules]) -->
    % skip this rule
    optional_phrase(Rules).
optional_phrase([Rule|Rules]) -->
    % apply this rule
    [List],
    { phrase(Rule, List) },
    optional_phrase(Rules).

这里的主要见解是您可以以 "higher-order" 的方式使用 phrase/2，其中它的第一个参数不是命名 DCG 的字面原子（或仿函数项），而是变量绑定到这样的原子或术语。但是，您必须确保在应用此规则时这些变量确实已绑定。

有了这个矩阵的最终定义就是：

matrix_with_optional_phrase -->
    optional_phrase([a, b]).

这现在像以前一样枚举矩阵，但它只会对实际上属于矩阵一部分的元素执行 phrase/2：

?- phrase(matrix_with_optional_phrase, Matrix).
Matrix = [] ;
Matrix = [[1, 1, 1, 1, 1]] ;
Matrix = [[0, 0, 0, 0, 0]] ;
Matrix = [[0, 0, 0, 0, 0], [1, 1, 1, 1, 1]].

Answer 2

DCG 符号在生产中保留列表来表示 'tokens' 的序列。然后，您的产生式 zeros - 例如 - 将匹配包含五个零的序列， 而不是 包含五个零的列表。这里有些混乱，只是因为您的目标语言（一系列列表）使用元语言符号（Prolog 列表表示 DCG 产品中的终端序列）。我想你可以简单地写一下

zeros --> [ [0,0,0,0,0] ].
ones --> [ [1,1,1,1,1] ].

matrix --> (zeros ; ones), matrix ; [].

test :- phrase(matrix, [ [1,1,1,1,1],[0,0,0,0,0] ]).

使用 prolog dcg 匹配矩阵中的模式

matching patterns in matrix using prolog dcg

prolog

dcg