Problem 607620 · hard · Level 06 Heuristics & Optimization

A Parser That Waits for Every Token

py-advanced-iteration · py-generators · yield from · generator.send · recursive descent parsing

A sensor network sends its configuration as a stream of tokens that trickle in over a slow radio link, and the receiver must build the configuration while it arrives, knowing at the exact token when a document is complete. Rather than waiting for the whole stream, it uses a generator that is fed tokens one at a time.

A value is written as tokens as follows:

  • An atom is any single token other than the four bracket strings "[", "]", "{", "}" (in the tests atoms are integers and short strings). It stands for itself.
  • A list is "[", then any number of values, then "]".
  • A dictionary is "{", then any number of pairs, then "}". A pair is a key, which must be an atom, followed by a value. A key may not appear twice in one dictionary.

Write a generator function read_value(). The reader is started with next() and then receives the tokens one by one with send(token). While the value is not complete it yields None for each token. On the token that completes the value, it returns the value (so that send raises StopIteration carrying it). If a token cannot continue a valid value (a closing bracket where a value or key is expected, the wrong closing bracket, a list or dictionary used as a key, a repeated key), it raises ValueError.

Helpers you can use with Run: parse(tokens) runs one reader over a list of tokens and returns the value or a short report ("error at i", "extra at i" or "incomplete"); parse_all(tokens) reads several documents in a row; tokens_of(value) turns a value into its tokens; random_document(seed, size, depth=6) generates a value.

Examples

Input:  parse(["[", 1, "[", 2, "x", "]", "{", "id", 7, "tags", "[", "]", "}", "]"])
Output: [1, [2, "x"], {"id": 7, "tags": []}]

Input:  parse(["[", 1, "}", 2])
Output: "error at 2"

Input:  parse_all([5, "[", "]", "{", "a", "[", 3, "]", "}"])
Output: [5, [], {"a": [3]}]

Constraints

  • At most 20,000 tokens per test; values are nested at most 60 deep.
  • The reader never sees the list of tokens, only one token per send.

Goals

  • Write generators that receive their input with `send` and finish with `return value`
  • Delegate to a sub-generator with `result = yield from sub()` and use the value it returns
  • Parse a nested structure incrementally, one token at a time, without ever seeing the whole input
Starting Python…