Питон - водитель вперед на разбор цепь


Это обратный отклик (то есть, по логике это продолжение, хронологически это не так) на этот вопрос: ссылка.

Я пишу библиотеки парсер-комбинаторов в Python. Важная вещь, которая должна быть в библиотеке-это способность анализатора цепей для выполнения некоторых впередсмотрящим, так аналоги регулярное выражение (.*)foo Это 1) полезно, 2) работает, как ожидалось, и не потому что (.*) сожрала все входные.

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

  1. Правильность - странные края-случаи, сопровождаемые к тому же мой алгоритм?
  2. Производительность - это может быть быстрее?

Есть еще пара незначительных моментов, которые я хотел бы знать:

  1. Просто подключая дополнительные поля для функции greedy и reluctant не приемлемо, или я должен обернуть изменен функций в классе а?
  2. Я делаю except ParsingEnd as end: raise end в паре мест как визуальную подсказку, что я помню о них. Я должен бросить его?

Алгоритм выглядит следующим образом:

  1. Траверс цепочке парсеров, подавая выход одного к другому
  2. Если перестал работать парсер, который должен выполнить упреждение это, начать добавлять все Парсеры в цепи повторов', выполняют ли они вперед или нет.
  3. Если парсер не удается, прибегают к последнему парсер с впередсмотрящим и изменить часть входного разрешается работать на.
  4. Ограничения на вход сброса для всех парсеров справа от этого синтаксического анализа и повторите анализ с этой точки.
  5. Если все комбинации входных ограничения были безуспешно, не получится.

Теперь для кода. Весь проект можно увидеть в этом РЕПО: ссылка, в замороженном ветку review-03022018 (основной файл). Я выложу критических точек ниже.

Вот chain функция, где впередсмотрящим драйвер. Он ожидает итерируемый парсеров в качестве первого аргумента, где парсер-это просто дежурный, который принимает один государственный объект и возвращает новый. Если парсер не удается, предполагается поднять ParsingFailure исключение. Парсер отмечается как предвидение возможности greedy и reluctant функции.

def chain(funcs, combine=True, stop_on_failure=False):
    """
    Create a parser that chains a given iterable of parsers together, using
    output of one parser as input for another.

    If 'combine' is truthy, combine 'parsed's of the parsers in the chain,
    otherwise use the last one.

    If 'stop_on_failure' is truthy, stop parsing instead of failing it when a
    parser in the chain raises a ParsingFailure exception. Note that this also
    includes parsers with lookahead, effectively disabling it.

    A note on using iterators in chains: if supplied 'funcs' is an iterator,
    there is a possibility of 'funcs' being exausted on the first attempt to
    parse, with subsequent attempts silently succeeding because that's the
    default behaviour for empty 'funcs'. If you want to run your chain several
    times - be it because of lookahead or for different reasons - make sure to
    wrap the iterator in list or some other *reusable* iterable (or call
    'reuse_iter' on it, if it comes from a function).
    """
    def res(state):
        """ A chain of parsers. """
        pieces = _CachedAppender() if combine else None
        def maybe_combine(state):
            """ Concatenate 'parsed's if 'combine' is truthy. """
            if combine:
                state.parsed = "".join(pieces)
            return state
        lookahead_chain = None
        for parser in funcs:
            if lookahead_chain is None and has_lookahead(parser):
                lookahead_chain = _CachedAppender()
            if lookahead_chain is not None or has_lookahead(parser):
                parser = _restrict(parser)
                lookahead_chain.append(parser)
            try:
                state = parser(state)
                if combine:
                    pieces.append(state.parsed)
            except ParsingEnd as end:
                raise end
            except ParsingFailure as failure:
                if stop_on_failure:
                    return maybe_combine(state)
                if lookahead_chain is None:
                    raise failure
                pos = len(lookahead_chain) - 1
                while True:
                    try_shift = _shift(lookahead_chain, pos)
                    if try_shift is None:
                        raise ParsingFailure(
                            "Failed to find a combination of inputs that allows  "
                            "successful parsing")
                    _reset_chain(lookahead_chain, try_shift)
                    state, failed = _try_chain(lookahead_chain, try_shift, pieces)
                    if state is None:
                        pos = failed
                        continue
                    break
        return maybe_combine(state)
    return res

Есть пара вспомогательные вещи, которые chain использует (прямо или нет). Самое главное _RestrictedParser, который является оберткой над парсер, который помнит две вещи: государство-это взял в качестве аргумента в последний раз и какую часть входного разрешается работать на:

class _RestrictedParser():
    """ A parser that only operates on a restricted portion of input. """

    def __init__(self, parser):
        self.parser = parser
        self.lookahead = get_lookahead(parser)
        self.delta = 0
        self.state_before = None

    def __call__(self, state):
        self.state_before = state
        if self.lookahead is None:
            return self.parser(state)
        if self.lookahead is Lookahead.GREEDY:
            return _subparse(state, self.parser, len(state.left) - self.delta)
        # is reluctant
        return _subparse(state, self.parser, self.delta)

    def overrestricted(self):
        """
        Return True if restrictions have reached their maximum - that is, if
        either allowed input portion is shrinked into an empty string, or has
        extended beyond the bounds of leftover input.
        """
        return self.delta > len(self.state_before.left)

    def reset(self):
        """ Reset restrictions. """
        self.delta = 0
        self.state_before = None

    def restrict_more(self):
        """ Increase restriction level on the input. """
        self.delta += 1

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

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

_reset_chain вспомогательные функции, используемые chain просто сбрасывает ограничения на анализаторы, начиная с заданной позиции и права.

Наконец, _try_chain пытается анализировать состояние своей первой _RestrictedParser используя текущую конфигурацию ограничений в сети:

def _try_chain(parsers, from_pos, pieces):
    """
    Try to parse the state the first parser in the chain remembers.

    Return a tuple (state, index of the first parser to fail).
    In case of failure, 'state' will be None.

    Also, if 'pieces' is not None, append every parsed chunk to it, having
    first dropped every invalidated piece. If an attempt to parse fails,
    'pieces' will not be affected.
    """
    state = parsers[from_pos].state_before
    i = from_pos
    new_pieces = None if pieces is None else deque()
    for i in range(from_pos, len(parsers)):
        try:
            state = parsers[i](state)
            if pieces is not None:
                new_pieces.append(state.parsed)
        except ParsingFailure:
            return (None, i)
        except ParsingEnd as end:
            raise end
    if pieces is not None:
        # '-1' is here because the last parser does not contribute a piece, as
        # it has failed
        pieces.drop(len(parsers) - from_pos - 1)
        pieces.extend(new_pieces)
    return state, i

Остальные используемые помощники:

  1. _CachedAppender - просто обертка над deque это вроде как позволяет быстрее индексировать, если дека меняется не очень часто.
  2. _restrict - обертывания парсер с впередсмотрящим в _RestrictedParser и ничего не делает, чтобы парсер без упреждения.

Упоминается greedy и reluctant просто:

def greedy(parser):
    """ Return a greedy version of 'parser'. """
    try:
        if parser.lookahead is Lookahead.GREEDY:
            return parser
    except AttributeError:
        pass
    res = lambda state: parser(state)
    res.lookahead = Lookahead.GREEDY
    return res

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



143
4
задан 3 февраля 2018 в 06:02 Источник Поделиться
Комментарии