Parser combinators

A parser here is just a function: give it input and it returns the parsed value and the remaining input, or an error. Basic ones match a literal or take N bytes; combinators such as pair (one parser after another), alt (try several) and length_count (read a count, then that many items) build bigger parsers out of them. The idea comes from functional programming, and the parsers hold no mutable state, so the same input always gives the same result.

nom brought this to Rust in 2015 for binary formats first. Because a Rust slice knows its own bounds, a nom parser can hand back pieces of the input without copying them and can’t read past the end. Its streaming parsers return Incomplete with how many more bytes they need when data arrives in chunks, which is how network protocols usually arrive. Its authors used it to put memory-safe parsers inside C programs: a TLS parser for the Suricata intrusion detection system and an FLV demuxer for VLC.

The cost is that a parser is code, not a description: it reads but doesn’t write, so an encoder is a separate piece of work. Hammer, a C library from the LangSec community, offers the same combinator style with a choice of parsing algorithms behind it.