Making a new parser from scratch

Writing a parser is a very fun, interactive process, but sometimes a daunting task. How do you test it? How to see ambiguities in specifications?

nom is designed to abstract data manipulation (counting array offsets, converting to structures, etc) while providing a safe, composable API. It also takes care of making the code easy to test and read, but it can be confusing at first, if you are not familiar with parser combinators, or if you are not used to Rust macros.

This document is here to help you in getting started with nom. If you need more specific help, please ping geal on IRC (mozilla, freenode, geeknode, oftc), go to #nom on Mozilla IRC, or on the Gitter chat room.

First step: the initial research

A big part of the initial work lies in accumulating enough documentation and samples to understand the format. The specification is useful, but specifications represent an "official" point of view, that may not be the real world usage. Any blog post or open source code is useful, because it shows how people understand the format, and how they work around each other's bugs (if you think a specification ensures every implementation is consistent with the others, think again).

You should get a lot of samples (file or network traces) to test your code. The easy way is to use a small number of samples coming from the same source and develop everything around them, to realize later that they share a very specific bug.

Code organization

While it is tempting to insert the parsing code right inside the rest of the logic, it usually results in unmaintainable code, and makes testing challenging. Parser combinators, the parsing technique used in nom, assemble a lot of small functions to make powerful parsers. This means that those functions only depend on their input, not on an external state. This makes it easy to parse the input partially, and to test those functions independently.

Usually, you can separate the parsing functions in their own module, so you could have a src/lib.rsfile containing this:

#[macro_use]
extern crate nom;

pub mode parser;

And use the methods and structure from parser there. The src/parser.rs would then import nom functions and structures if needed:

use nom::{be_u16, be_u32};

Writing a first parser

Let's parse a simple expression like (12345). nom parsers are functions that use the nom::IResult type everywhere. As an example, a parser taking a byte slice &[u8] and returning a 32 bits unsigned integer u32 would have this signature: fn parse_u32(input: &[u8]) -> IResult<&[u8], u32>.

The IResult type depends on the input and output types, and an optional custom error type. This enum can either contain Done(i,o) containing the remaining input and the output value, an error, or an indication that more data is needed.

#[derive(Debug,PartialEq,Eq,Clone)]
pub enum IResult<I,O,E=u32> {
  Done(I,O),
  Error(Err<I,E>),
  Incomplete(Needed)
}

nom uses this type everywhere. Every combination of parsers will pattern match on this to know if it must return a value, an error, consume more data, etc. But this is done behind the scenes most of the time.

nom provides a macro for function definition, called named!:

named!(my_function( &[u8] ) -> &[u8], tag!("abcd"));

named!(my_function<&[u8], &[u8]>, tag!("abcd"));

named!(my_function, tag!("abcd"));

But you could as easily define the function yourself like this:

fn my_function(input: &[u8]) -> IResult<&[u8], &[u8]> {
  tag!(input, "abcd")
}

Note that we pass the input to the first parser in the manual definition, while we do not when we use named!. This is a macro trick specific to nom: every parser takes the input as first parameter, and the macros take care of giving the remaining input to the next parser. As an example, take a simple parser like the following one, which recognizes the word "hello" then takes the next 5 bytes:

named!(prefixed, preceded!(tag!("hello"), take!(5)));

Once the macros have expanded, this would correspond to:

fn prefixed(i: &[u8]) -> ::nom::IResult<&[u8], &[u8]> {
    {
        match {
                  #[inline(always)]
                  fn as_bytes<T: ::nom::AsBytes>(b: &T) -> &[u8] {
                      b.as_bytes()
                  }
                  let expected = "hello";
                  let bytes = as_bytes(&expected);
                  {
                      let res: ::nom::IResult<&[u8], &[u8]> =
                          if bytes.len() > i.len() {
                              ::nom::IResult::Incomplete(::nom::Needed::Size(bytes.len()))
                          } else if &i[0..bytes.len()] == bytes {
                              ::nom::IResult::Done(&i[bytes.len()..],
                                                   &i[0..bytes.len()])
                          } else {
                              ::nom::IResult::Error(::nom::Err::Position(::nom::ErrorKind::Tag,
                                                                         i))
                          };
                      res
                  }
              } {
            ::nom::IResult::Error(a) => ::nom::IResult::Error(a),
            ::nom::IResult::Incomplete(i) => ::nom::IResult::Incomplete(i),
            ::nom::IResult::Done(i1, _) => {
                match {
                          let cnt = 5 as usize;
                          let res: ::nom::IResult<&[u8], &[u8]> =
                              if i1.len() < cnt {
                                  ::nom::IResult::Incomplete(::nom::Needed::Size(cnt))
                              } else {
                                  ::nom::IResult::Done(&i1[cnt..],
                                                       &i1[0..cnt])
                              };
                          res
                      } {
                    ::nom::IResult::Error(a) => ::nom::IResult::Error(a),
                    ::nom::IResult::Incomplete(i) =>
                    ::nom::IResult::Incomplete(i),
                    ::nom::IResult::Done(i2, o2) => {
                        ::nom::IResult::Done(i2, o2)
                    }
                }
            }
        }
    }
}

While this may look like a lot of code, the compiler and the CPU will happily optimize everything, do not worry. You can see that the function matches on the result of the first parser, stops there if it returned an error or incomplete, and if it returned a value, takes the remaining input i1, applies the second parser on it, then matches on the result (and returns the value o2 and the remaining input i2).

A lot of complex patterns are implemented that way: generic macros combining other macros or functions. This will handle partial consumption and passing data slices for you.