Расположение в прологе без разреза?

Question

Я нашел этот хороший фрагмент для разбора LISP в Prolog (от здесь):

ws --> [W], { code_type(W, space) }, ws.
ws --> [].

parse(String, Expr) :- phrase(expressions(Expr), String).

expressions([E|Es]) -->
    ws, expression(E), ws,
    !, % single solution: longest input match
    expressions(Es).
expressions([]) --> [].

% A number N is represented as n(N), a symbol S as s(S).

expression(s(A))         --> symbol(Cs), { atom_codes(A, Cs) }.
expression(n(N))         --> number(Cs), { number_codes(N, Cs) }.
expression(List)         --> "(", expressions(List), ")".
expression([s(quote),Q]) --> "'", expression(Q).

number([D|Ds]) --> digit(D), number(Ds).
number([D])    --> digit(D).

digit(D) --> [D], { code_type(D, digit) }.

symbol([A|As]) -->
    [A],
    { memberchk(A, "+/-*><=") ; code_type(A, alpha) },
    symbolr(As).

symbolr([A|As]) -->
    [A],
    { memberchk(A, "+/-*><=") ; code_type(A, alnum) },
    symbolr(As).
symbolr([]) --> [].

Однако выражения использует сокращение. Я предполагаю, что это для эффективности. Можно ли написать этот код так, чтобы он работал эффективно без сокращения?

Также будет заинтересованные ответы, которые включают в себя мягкий / совершенный выбор Меркурия.

Answer 1

Разрез не используется не для эффективности, а для того, чтобы посвятить себя первое решение (см. Комментарий рядом с!/0: «Одиночное решение: самое длинное входное совпадение»). Если вы прокомментируете!/0, вы получите, например:

?- parse("abc", E).
E = [s(abc)] ;
E = [s(ab), s(c)] ;
E = [s(a), s(bc)] ;
E = [s(a), s(b), s(c)] ;
false.

Ясно, что в таких случаях желательно только первое решение, состоящее из самой длинной последовательности символов, которые образуют токен. Приведенный выше пример, я поэтому не согласен с «false»: выражение // 1 является неоднозначным, потому что число // 1 и символ // 1. В Меркурии вы можете использовать детерминизм Декларацию CC_NONDET для принятия решения, если таковые имеются.

Answer 2

Вы прикасаете к довольно глубокой проблеме здесь. В месте выреза вы добавили комментарий «Самый длинный входной матч». Но что вы на самом деле сделали, чтобы посвятить себя первому решению, которое будет создавать «самый длинный входной матч» для неподметального ws//0 но не обязательно для expression//1.

Многие языки программирования определяют свои токены на основе самого длинного входного совпадения. Это часто приводит к очень странным эффектам. Например, число может быть немедленно следовать за буквой во многих языках программирования. Это относится к Паскалу, Хаскеллу, Прологу и многим другим языкам. Например if a>2then 1 else 2 действителен Хаскелл. Действительный пролог: X is 2mod 3.

Учитывая, что это может быть хорошей идеей определить язык программирования, так что он вообще не зависит от таких функций.

Конечно, вы хотели бы оптимизировать грамматику. Но я могу рекомендовать только начать с определения, которое в первую очередь является однозначным.

Что касается эффективности (и чистоты):

eos([],[]).

nows --> call(eos).
nows, [W] --> [W], { code_type(W, nospace) }.

ws --> nows.
ws --> [W], {code_type(W, space)}, ws.

Answer 3

Вы можете использовать конструкцию, которая уже нашла свое место в грамматике экспрессии (PEGS), но также доступна в DCG. А именно отрицание цели DCG. В PEGS восклицательный знак (!) С аргументом используется для отрицания, т.е.! е - В DCG отрицание цели DCG выражается оператором (+), который уже используется для обычного отрицания в качестве сбоя в обычных предложениях и запросах пролога.

Итак, давайте сначала объясним, как (+) работает в DCGS. Если у вас есть правило производства формы:

 A --> B, \+C, D.

Тогда это переведено на:

 A(I,O) :- B(I,X), \+ C(X,_), D(X,O).

Это означает, что предпринимается попытка проанализировать цель C DCG, но без фактического потребления списка ввода. Теперь это может быть использовано для замены разреза, при желании, и это дает немного больше декларативного ощущения. Чтобы объяснить эту идею, давайте предположим, что с грамматикой без WS // 0. Таким образом, исходный набор выражений // 1 будет:

expressions([E|Es]) --> expression(E), !, expressions(Es).
expressions([]) --> [].

С отрицанием мы можем превратить это в следующую форму безрешки:

expressions([E|Es]) --> expression(E), expressions(Es).
expressions([]) --> \+ expression(_).

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

expressions([E|Es]) --> expression(E), expressions(Es).
expressions([]) --> \+ symbol(_), \+ number(_), \+ "(", \+ "'".

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

?- phrase(expressions(X),"'",Y).

Вы должны получить сбой в версии отрицания, которая проверяет первый символ выражения. В вырезании и в версии бесплатно вы получите успех с пустым списком в результате.

Но вы также можете иметь дело по -другому с ошибками, я только сделал пример ошибки, чтобы немного подчеркнуть, как работает версия отрицания.

В других настройках, например, Cyk Parser, можно сделать отрицание весьма эффективным, он может использовать информацию, которая уже размещена в таблице.

С уважением