El uso de búsqueda hacia delante con los generadores

Question

he implementado un escáner basado en el generador de Python que tokenizes una cadena en tuplas de la forma (tipo de token, un valor simbólico):

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

imprimiría

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

La siguiente tarea implica analizar el flujo de tokens y, para eso, necesito poder mirar un elemento por delante del actual sin mover también el puntero hacia adelante. El hecho de que los iteradores y generadores no proporcionen la secuencia completa de elementos a la vez pero que cada elemento según sea necesario hace que lookaheads sea un poco más complicado en comparación con las listas, ya que el próximo elemento no se conoce a menos que se llame al __next__().

¿Cómo podría ser una implementación sencilla de un lookahead basado en un generador? Actualmente estoy usando una solución que implica hacer una lista del generador:

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

La búsqueda hacia delante y luego se implementa fácilmente por algo así:

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

Por supuesto, esto sólo funciona bien. Pero pensando en eso, surge mi segunda pregunta: ¿realmente hay un punto de hacer que scan() sea un generador en primer lugar?

Answer 1

puede escribir un envoltorio que amortigua cierto número de elementos del generador, y proporciona una Función lookahead() para ver esos elementos almacenados en el búfer:

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 2

No es bonito, pero esto puede hacer lo que quiera:

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) 

Lienzo:

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 3

Paul's es una buena respuesta. Un enfoque basado en la clase con lookahead arbitraria podría ser algo como:

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 

Answer 4

Aquí es un ejemplo que permite que un solo artículo sea enviado de vuelta al generador

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

Bastante buenas respuestas allí, pero mi favorito el enfoque sería usar itertools.tee - dado un iterador, devuelve dos (o más si se solicita) que pueden avanzar de forma independiente. Almacena en la memoria tanto como sea necesario (es decir, no mucho, si los iteradores no se salen "demasiado" el uno del otro). Ej .:

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) 

Usted puede envolver cualquier iterador con esta clase y, a continuación, utilizar el atributo .lookahead de la envoltura para saber cuál es el siguiente elemento a ser devuelto en el futuro será. ¡Me gusta dejar toda la lógica real a itertools.tee y simplemente proporcionar este pegamento fino! -)

Answer 6

Como dice que está tokenizando una cadena y no un iterable general, le sugiero la solución más simple de simplemente expandir su tokenizador a devuelve un 3-tuple: (token_type, token_value, token_index), donde token_index es el índice del token en la cadena. Luego puede mirar hacia adelante, hacia atrás o en cualquier otro lugar de la cadena. Simplemente no pases el final.La solución más simple y más flexible, creo.

Además, no necesita usar una lista de comprensión para crear una lista de un generador. Sólo tiene que llamar la lista() constructor en él:

token_list = list(scan(string)) 

Answer 7

cómo iba a escribir de forma concisa, si sólo necesitaba un valor de 1 de elemento de búsqueda hacia delante:

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 

Ejemplo:

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

Answer 8

Construya una envoltura simple de búsqueda anticipada usando 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) 

Use la clase para envolver un iterable o iterador existente. Luego puede iterar normalmente usando siguiente o puede buscar anticipadamente con búsquedas indexadas.

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

Para ejecutar este código en Python 3, basta con cambiar el método siguiente a __next__.