Using lookahead with generators

user_184088 0
Viewed 3774

I have implemented a generator-based scanner in Python that tokenizes a string into tuples of the form (token type, token value):

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

would print

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

The next task implies parsing the token stream and for that, I need be able to look one item ahead from the current one without moving the pointer ahead as well. The fact that iterators and generators do not provide the complete sequence of items at once but each item as needed makes lookaheads a bit trickier compared to lists, since the next item is not known unless __next__() is called.

What could a straightforward implementation of a generator-based lookahead look like? Currently I'm using a workaround which implies making a list out of the generator:

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

The lookahead then is easily implemented by something like that:

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

Of course this just works fine. But thinking that over, my second question arises: Is there really a point of making scan() a generator in the first place?

lookahead generator python
9 Answers

You can use lazysequence, an immutable sequence that wraps an iterable and caches consumed items in an internal buffer. You can use it like any list or tuple, but the iterator is only advanced as much as required for a given operation.

Here's how your example would look like with lazy sequences:

from lazysequence import lazysequence

token_list = lazysequence(token for token in scan(string))

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

And here's how you could implement lazy sequences yourself:

from collections.abc import Sequence


class lazysequence(Sequence):
    def __init__(self, iterable):
        self._iter = iter(iterable)
        self._cache = []

    def __iter__(self):
        yield from self._cache
        for item in self._iter:
            self._cache.append(item)
            yield item

    def __len__(self):
        return sum(1 for _ in self)

    def __getitem__(self, index):
        for position, item in enumerate(self):
            if index == position:
                return item

        raise IndexError("lazysequence index out of range")

This is a naive implementation. Some things that are missing here:

  • The lazy sequence will eventually store all items in memory. There's no way to obtain a normal iterator that no longer caches items.
  • In a boolean context (if s), the entire sequence is evaluated, instead of just the first item.
  • len(s) and s[i] require iterating through the sequence, even when items are already stored in the internal cache.
  • Negative indices (s[-1]) and slices (s[:2]) are not supported.

The PyPI package addresses these issues, and a few more. A final caveat applies both to the implementation above and the package:

  • Explicit is better than implicit. Clients may be better off being passed an iterator and dealing with its limitations. For example, clients may not expect len(s) to incur the cost of consuming the iterator to its end.

Disclosure: I'm the author of lazysequence.

user_13557540
Related