сопоставление шаблонов в матрице с использованием пролога dcg - PullRequest
Новая
       27

сопоставление шаблонов в матрице с использованием пролога dcg

1 голос
/ 24 апреля 2020

Можно ли с помощью 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.

Я пробовал что-то вроде this 

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]] - нет.

Как мне подойти к этому?

Ответы [ 2 ]

2 голосов
/ 25 апреля 2020

Проблема в том, что как только вы напишите 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).

Основное понимание здесь заключалось в том, что вы можете использовать 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]].
1 голос
/ 25 апреля 2020

Обозначения DCG резервируют списки в производстве для представления последовательностей «токенов». Тогда ваша продукция zeros - например, - будет соответствовать последовательности из пяти нулей, не списку из пяти нулей. Здесь есть некоторая путаница, просто потому, что ваш целевой язык (последовательность списков) использует обозначение метаязыка (списки Пролога указывают последовательности терминалов в продуктах 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] ]).
...