Разбор в прологе без среза? - PullRequest
Новая
       22

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

19 голосов
/ 15 июня 2011

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

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

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

Ответы [ 3 ]

8 голосов
/ 15 июня 2011

Срез используется не для эффективности, а для принятия первого решения (см. Комментарий рядом с! / 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 для фиксации решения, если оно есть.

8 голосов
/ 15 июня 2011

Вы касаетесь довольно глубокой проблемы здесь.На месте разреза вы добавили комментарий «самое длинное совпадение ввода».Но то, что вы на самом деле сделали, - это совершили первое решение, которое даст «самое длинное совпадение ввода» для нетерминала 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.
4 голосов
/ 21 июня 2011

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

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

...