Skip to content

parsing

2 posts with the tag “parsing”

The Shunting Yard

Turning a boolean query into something a machine can walk, in one pass over two stacks.

Infix is how people write boolean queries and the worst way to evaluate them, because precedence and parentheses mean you cannot just read left to right. Dijkstra's shunting-yard algorithm fixes that in a single pass with two stacks, reshuffling 'a OR (b AND NOT c)' into a form a machine walks without ever recursing. The eleventh familiar is that algorithm, and the query language it feeds never needs the parse tree at all.

Sixteen Bytes Too Far

A streaming HTTP parser that never copies, and the one place it read past the buffer.

Bytes arrive off a socket in whatever sizes the network felt like: a whole request in one read, or one byte at a time, or a header split down the middle. A streaming parser has to produce the same result regardless, without copying and without ever reading a byte it was not handed. The eighth familiar does exactly that, except for the one line where it reached sixteen bytes past the end of the buffer, and only the sanitizer noticed.