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

Question

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

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.

Понятно, что в таких случаях желательно только первое решение, состоящее из самой длинной последовательности символов, образующих токен. Учитывая приведенный выше пример, я поэтому не согласен с "ложью": выражение //1 неоднозначно, потому что число //1 и символ //1 таковы. В Меркурии вы можете использовать объявление детерминизма cc_nondet, чтобы зафиксировать решение, если оно есть.

Answer 2

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

Многие языки программирования определяют свои токены на основе самого длинного входного совпадения. Это часто приводит к очень странным эффектам. Например, сразу за номером может следовать буква на многих языках программирования. Это касается Паскаля, Хаскеля, Пролога и многих других языков. Например if a>2then 1 else 2 действительно Haskell. Действительный Пролог: 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

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

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

 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, можно сделать отрицание весьма эффективным, он может использовать информацию, уже размещенную на графике.

С уважением