Есть ли способ или алгоритм для преобразования DCG в обычные определенные предложения в Прологе?

Я новичок в Прологе, и я пытаюсь понять, как грамматика может быть переведена в обычное определенное предложение из DCG. Я понял, что нотация DCG - просто синтаксический сахар для нормальных определенных предложений в Прологе. Я начал изображать некоторые сходства между обычными определенными грамматиками и DCG, но не смог применить тот же шаблон, поэтому я спрашиваю, есть ли какие-то правила, которые мне не хватает, или алгоритм преобразования, который может работать.

Вот грамматика, над которой я работаю, и вот что я сделал, чтобы перевести эту грамматику:

expr --> term, addterm.
addterm --> [].
addterm --> [+], expr.
term --> factor, multfactor.
multfactor --> [].
multfactor --> [*], term.
factor --> [I], {integer(I)}.
factor --> ['('], expr, [')'].

Эта грамматика фактически проверяет синтаксическую правильность арифметических операций. Первое правило на самом деле легко преобразовать, поскольку его шаблон похож на обычные определенные грамматики, как и четвертое. Однако я не имею понятия о других четырех. Вот как я преобразовал правило:

expr(E0,E) :- term(E0,E1), addterm(E1,E).
Источник

3 ответа

Решение

Ты на правильном пути! Продолжайте, и вы получите что-то вроде этого:

expr(Xs0,Xs) :-                         % expr -->
   term(Xs0,Xs1),                       %    term,
   addterm(Xs1,Xs).                     %    addterm.

addterm(Xs0,Xs) :-                      % addterm --> 
   Xs0 = Xs.                            %    [].
addterm(Xs0,Xs) :-                      % addterm -->
   Xs0 = [+|Xs1],                       %    [+], 
   expr(Xs1,Xs).                        %    expr. 

term(Xs0,Xs) :-                         % term --> 
   factor(Xs0,Xs1),                     %    factor,
   multfactor(Xs1,Xs).                  %    multfactor.

multfactor(Xs0,Xs) :-                   % multfactor -->
   Xs0 = Xs.                            %    [].
multfactor(Xs0,Xs) :-                   % multfactor -->
   Xs0 = [*|Xs1],                       %    [*],
   term(Xs1,Xs).                        %    term.  

factor(Xs0,Xs) :-                       % factor --> 
   Xs0 = [I|Xs],                        %    [I],
   integer(I).                          %    {integer(I)}.
factor(Xs0,Xs) :-                       % factor --> 
   Xs0 = ['('|Xs1],                     %    ['('], 
   expr(Xs1,Xs2),                       %    expr,
   Xs2 = [')'|Xs]. `                    %    [')'].
Источник

Если ваша система Prolog обеспечивает expand_term/2 встроенный предикат, вы можете обычно использовать для расширения правил грамматики в предложения. Например:

?- expand_term((a --> b, c), Clause).
Clause = (a(_G1012, _G1013):-b(_G1012, _G1028), c(_G1028, _G1013)).

Для более читабельного вывода (и только для этой цели) попробуйте:

?- expand_term((a --> b, c), Clause), numbervars(Clause, 0, _).
Clause = (a(A, B):-b(A, C), c(C, B)).

numbervars/3 является де-факто стандартным предикатом, встречающимся в большинстве систем Prolog.

Источник

Некоторые системы Prolog переводят DCG в предложения способом, отличным от того, который содержится в ответах @repeat и @PauloMoura: прямое объединение терминалов с членами анализируемого / генерируемого списка заменяется вызовом предиката 'C'/3, Например

a(X) --> b(X), [x, y], c(X).

переводится на

a(A,B,C) :-
  b(A,B,D),
  'C'(D,x,E),
  'C'(E,y,F),
  c(A,F,C).

Этот предикат предопределен в этих системах для объединения, как в этих ответах, в соответствии с предложением

'C'([X|S],X,S).

но он может быть переопределен пользователем при необходимости.

Это является частью определения DCG, впервые выдвинутого в статье Фернандо Перейры и Дэвида Уоррена " Грамматика с определенным предложением для анализа языка", в " Искусственном интеллекте", 13, 1980, и является одним из отличий от Alain Colmerauer et al. предыдущая статья Метаморфозы Грамматики. Использование 'C'/3 предикат, оригинально названный connects, делает DCG независимым от способа представления / анализа генерируемой строки: в приведенном выше переводе нет ничего, что требовало бы, чтобы переменные B в F стоять за списки, и 'C'/3 может быть переопределено, чтобы интерпретировать их как другие виды терминов. Чтобы избежать потери эффективности, в статье рекомендуется предварительная обработка предложений DCG во время компиляции в случае использования списков.

Источник
Другие вопросы по тегам