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

Question

我发现prolog 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)}.

但是这不会按照我想要的方式工作，因为在这种情况下，“编译器”认为我想要一个空列表'[]'而不是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以仅描述其参数列表的sublist：

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).

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

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

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]].