Использование Lookahead с генераторами

Question

В Python реализован генератор на основе генератора, который разбивает строку на строки в виде кортежей (тип токена, значение токена) :

for token in scan("a(b)"):
    print token

будет печатать

("literal", "a")
("l_paren", "(")
...

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

Как может выглядеть прямая реализация прогнозирующего генератора на основе генератора? В настоящее время я использую обходной путь, который подразумевает создание списка из генератора:

token_list = [token for token in scan(string)]

Тогда упростить задачу можно следующим образом:

try:
    next_token = token_list[index + 1]
except: IndexError:
    next_token = None

Конечно, это просто отлично работает. Но обдумывая этот вопрос, у меня возникает второй вопрос: есть ли смысл создавать scan() генератор в первую очередь?

Answer 1

Довольно неплохие ответы, но мой любимый подход - использовать itertools.tee - при наличии итератора он возвращает два (или больше, если требуется), которые могут быть продвинуты независимо. Он буферизует в памяти столько, сколько необходимо (то есть, не так много, если итераторы не слишком сильно «расходятся» друг с другом). E.g.:

import itertools
import collections

class IteratorWithLookahead(collections.Iterator):
  def __init__(self, it):
    self.it, self.nextit = itertools.tee(iter(it))
    self._advance()
  def _advance(self):
    self.lookahead = next(self.nextit, None)
  def __next__(self):
    self._advance()
    return next(self.it)

Вы можете обернуть любой итератор этим классом, а затем использовать атрибут .lookahead оболочки, чтобы узнать, каким будет следующий элемент, который будет возвращен в будущем. Мне нравится оставлять всю настоящую логику в itertools.tee и просто предоставлять этот тонкий клей! -)

Answer 2

Вы можете написать оболочку, которая буферизует некоторое количество элементов из генератора и предоставляет функцию lookahead () для просмотра этих буферизованных элементов:

class Lookahead:
    def __init__(self, iter):
        self.iter = iter
        self.buffer = []

    def __iter__(self):
        return self

    def next(self):
        if self.buffer:
            return self.buffer.pop(0)
        else:
            return self.iter.next()

    def lookahead(self, n):
        """Return an item n entries ahead in the iteration."""
        while n >= len(self.buffer):
            try:
                self.buffer.append(self.iter.next())
            except StopIteration:
                return None
        return self.buffer[n]

Answer 3

Это не красиво, но это может делать то, что вы хотите:

def paired_iter(it):
    token = it.next()
    for lookahead in it:
        yield (token, lookahead)
        token = lookahead
    yield (token, None)

def scan(s):
    for c in s:
        yield c

for this_token, next_token in paired_iter(scan("ABCDEF")):
    print "this:%s next:%s" % (this_token, next_token)

Печать:

this:A next:B
this:B next:C
this:C next:D
this:D next:E
this:E next:F
this:F next:None

Answer 4

Вот пример, который позволяет отправить один элемент обратно в генератор.

def gen():
    for i in range(100):
        v=yield i           # when you call next(), v will be set to None
        if v:
            yield None      # this yields None to send() call
            v=yield v       # so this yield is for the first next() after send()

g=gen()

x=g.next()
print 0,x

x=g.next()
print 1,x

x=g.next()
print 2,x # oops push it back

x=g.send(x)

x=g.next()
print 3,x # x should be 2 again

x=g.next()
print 4,x

Answer 5

Создайте простую оболочку, используя itertools.tee :

from itertools import tee, islice

class LookAhead:
    'Wrap an iterator with lookahead indexing'
    def __init__(self, iterator):
        self.t = tee(iterator, 1)[0]
    def __iter__(self):
        return self
    def next(self):
        return next(self.t)
    def __getitem__(self, i):
        for value in islice(self.t.__copy__(), i, None):
            return value
        raise IndexError(i)

Используйте класс для переноса существующего итератора или итератора. Затем вы можете либо выполнить итерацию в обычном режиме, используя next , либо выполнить поиск с индексированными поисками.

>>> it = LookAhead([10, 20, 30, 40, 50])
>>> next(it)
10
>>> it[0]
20
>>> next(it)
20
>>> it[0]
30
>>> list(it)
[30, 40, 50]

Чтобы запустить этот код в Python 3, просто измените метод next на __ next __ .

Answer 6

Поскольку вы говорите, что токенизируете строку, а не общую итерируемую, я предлагаю самое простое решение - просто расширить ваш токенизатор, чтобы получить 3-кортеж: (token_type, token_value, token_index), где token_index - индекс токена в строке. Затем вы можете посмотреть вперед, назад или куда-нибудь еще в строке. Только не проходи мимо конца. Я думаю, самое простое и гибкое решение.

Кроме того, вам не нужно использовать понимание списка для создания списка из генератора. Просто вызовите для него конструктор list ():

 token_list = list(scan(string))

Answer 7

Как бы я написал это кратко, если бы мне просто нужно было посмотреть на 1 элемент:

SEQUENCE_END = object()

def lookahead(iterable):
    iter = iter(iterable)
    current = next(iter)
    for ahead in iter:
        yield current,ahead
        current = ahead
    yield current,SEQUENCE_END

Пример:

>>> for x,ahead in lookahead(range(3)):
>>>     print(x,ahead)
0, 1
1, 2
2, <object SEQUENCE_END>

Answer 8

Пол - это хороший ответ. Подход на основе классов с произвольным прогнозом может выглядеть примерно так:

class lookahead(object):
    def __init__(self, generator, lookahead_count=1):
        self.gen = iter(generator)
        self.look_count = lookahead_count

    def __iter__(self):
        self.lookahead = []
        self.stopped = False
        try:
            for i in range(self.look_count):
                self.lookahead.append(self.gen.next())
        except StopIteration:
            self.stopped = True
        return self

    def next(self):
        if not self.stopped:
            try:
                self.lookahead.append(self.gen.next())
            except StopIteration:
                self.stopped = True
        if self.lookahead != []:
            return self.lookahead.pop(0)
        else:
            raise StopIteration

x = lookahead("abcdef", 3)
for i in x:
    print i, x.lookahead