Есть ли способ или алгоритм для преобразования 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 во время компиляции в случае использования списков.