Реализация "cut" в парсере рекурсивного спуска

Я внедряю генератор синтаксического анализатора PEG в Python, и до сих пор добился успеха, за исключением функции "вырезать", о которой знает тот, кто знает Пролог.

Идея в том, что после разреза (!) символ был проанализирован, поэтому никакие альтернативные варианты не должны предприниматься на том же уровне.

expre = '(' ! list ')' | atom.

Означает, что после ( видно, синтаксический анализ должен завершиться успешно или потерпеть неудачу без попытки второго варианта.

Я использую (очень эффективную) систему исключений Python для принудительного возврата, поэтому я попытался FailedCut Исключение, которое отменяет включающий выбор, но это не сработало.

Любые указатели на то, как эта функциональность реализована в других генераторах синтаксического анализатора, были бы полезны.

Может быть, у меня была проблема с отсутствием местного населения. Код, сгенерированный для левой части правила, будет выглядеть примерно так:

cut_seen = False
try:
    self.token('(')
    cut_seen = True 
    self.call('list')
    self.token(')')
except FailedParse as e:
    if cut_seen:
         raise FailedCut(e)
    raise

Тогда код сгенерированный для выбора (|) оператор пропустит следующие варианты, если перехватит FailedCut, Что я имею в виду под отсутствием локальности, так это то, что выбор FailedCut может быть глубоко в звонках, таким образом, эффект слишком трудно различить.

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

Мне просто пришло в голову, что если код, сгенерированный для правила / предиката, ловит FailedCut и переводит его в нормальный FailedParse Исключение, то разрезы будут иметь правильную область.

Что касается вопроса @false, вот полный пример того, что я хочу работать:

start = expre ;

expre = named | term ;

named = word ':' ! term;

term = word ;

В этой грамматике word может быть достигнуто через named или же term, но я бы хотел, чтобы синтаксический анализатор зафиксировал named ветвь после того, как он увидел :,

Решение

Честно говоря, я опубликовал свою работу до сих пор на https://bitbucket.org/apalala/grako/.

В конечном решении последовательности заключены в этот менеджер контекста:

@contextmanager
def _sequence(self):
    self._push_cut()
    try:
        yield
    except FailedParse as e:
        if self._cut():
            self.error(e, FailedCut)
        else:
            raise
    finally:
        self._pop_cut()

И опции в функции выбора заключены в это:

@contextmanager
def _option(self):
    p = self._pos
    try:
        self._push_ast()
        try:
            yield
            ast = self.ast
        finally:
            self._pop_ast()
        self.ast.update(ast)
    except FailedCut as e:
        self._goto(p)
        raise e.nested
    except FailedParse:
        self._goto(p)

Что заставляет выход из выбора вместо возврата, чтобы попробовать следующий вариант.

Сами порезы реализуются таким образом:

def _cut(self):
    self._cut_stack[-1] = True

Полный исходный код может быть найден на Bitbucket.

Источник

3 ответа

Решение

Решение, предложенное в конце моего вопроса, сработало:

cut_seen = False
try:
    self.token('(')
    cut_seen = True 
    self.call('list')
    self.token(')')
except FailedParse as e:
    if cut_seen:
         raise FailedCut(e)
    raise

Затем, каждый раз, когда оценивается выбор или опционально, код выглядит так:

p = self.pos
try:
   # code for the expression
except FailedCut:
    raise
except FailedParse:
    self.goto(p)

редактировать

Фактическое решение требовало сохранения "отрезанной стопки". Исходный код int Bitbucket.

Источник

В Прологе с обработкой исключений ISO Пролог (catch/3 а также throw/1), разрез может быть реализован как:

cut. % Simply succeeds
cut :-
   throw(cut). % on backtracking throws an exception

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

catchcut(Goal) :-
   catch(Goal,cut,fail).

Это не самый эффективный способ реализации резки, поскольку он не освобождает ресурсы при успешном !, но этого может быть достаточно для ваших целей. Кроме того, этот метод теперь может мешать пользовательскому использованию catch/3, Но вы, вероятно, не хотите эмулировать весь язык Пролог в любом случае.

Также рассмотрите возможность использования dcg-grammars Пролога напрямую. Существует много мелкого шрифта, который не проявляется при реализации этого на другом языке.

Источник

Просто прочитайте это.

Я бы предложил глубокий cut_seen (как с изменением состояния парсера) и состояние сохранения и восстановления с локальными переменными. Это использует стек потока какcut_seen стек".

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

Кстати: хороший компилятор - это прямо противоположно тому, что я делаю с pyPEG, поэтому я могу многому научиться;-)

Источник
Другие вопросы по тегам