Разбор в Prolog без разреза?

Я нашел этот хороший фрагмент для разбора 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([]) --> [].

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

Были бы также заинтересованные ответы, которые предполагали бы мягкий выбор Mercury/преданный.

Ответ 1

Сокращение не используется для эффективности, но для фиксации первого решения (см. комментарий рядом с единственным решением:/0: "single: longest input match" ). Если вы закомментируете! /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 и symbolr//1 есть. В Mercury вы можете использовать объявление детерминизма cc_nondet для фиксации решения, если оно есть.

Ответ 2

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

Многие языки программирования определяют свои токены на основе самого длинного совпадения ввода. Это часто приводит к очень странным последствиям. Например, число может быть немедленно за которым следует письмо на многих языках программирования. Что касается Паскаля, Хаскелла, Prolog и многие другие языки. Например. 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.

Ответ 3

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

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

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

Затем это переводится на:

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

Это означает, что делается попытка проанализировать цель DC DC, но фактически не потребляет входной список. Теперь это можно использовать для замены разреза, если это необходимо, и это дает немного более декларативное чувство. Чтобы объяснить идею, предположим, что с грамматикой без 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, можно сделать отрицание достаточно эффективным, оно может использовать информацию, которая уже помещена в диаграмму.

С наилучшими пожеланиями