Parsing The World with Rust and POM
Tags: rust, computerscience
Published: 2019-08-14 12:09:16

As programmers, we spend a lot of time dealing with strings of text. Very often, we receive text as input from users, or we read text files and try to understand their content.

In many cases, we use regular expressions to see if the text matches a certain pattern, or to extract some information from the string. For example, if you receive a username as form input, and you want to make sure that it doesn't contain any spaces, you can use a regex like `"^\S+$"` to match a string with one or more non-white space characters (`^` denotes the beginning of the string, `\S` denotes a non-white space character, `+` denotes repetition for one or more times, and `$` denotes the end of the string). You might even write a function like:

```rust
fn has_whitespaces(s: String) -> bool {
  s.contains(' ')
}
```

> Can you spot the bug in the code?

But what if you're trying to parse the contents of more complex strings. Say, a JSON string, a CSV (Coma-Separated Values) file, or even a program? If you don't use existing library functions, you're going to have a hard time using regular expressions and string methods.

In this article, we'll be exploring the [POM](https://github.com/J-F-Liu/pom) library, which offers a really cool interface for intuitively defining and combining parsers. Using this library, you can conveniently define the entire grammar of a formal language (perhaps your own new programming language?) 

POM is an implementation of a [PEG](https://en.wikipedia.org/wiki/Parsing_expression_grammar) (Parsing Expression Grammar,) which is a definition of a formal language in terms of symbols, string expressions, and rules.

For example, if we were to define a rule for parsing a variable definition such as: `let  x = 1;`, we would say that `let` is a sequence of symbols, `=`, `;`, and  spaces are symbols, and `x` and `1` are string expressions. A variable definition consists of the `let` sequence, followed by a space, followed by a **valid identifier** (`x`, for example,) followed by zero or more spaces, followed by the `=` symbol, followed by zero or more spaces, followed by a valid expression (`1` in this example,) followed by zero or more spaces and the `;` symbol. A bit verbose, isn't it? Such are the definitions of formal languages.

Thankfully, POM provides a very declarative way of defining these rules. It allows us to define different rules for parsing each small piece of text, and then combine them using arithmetic and logical operators to form more complex rules. These operators are called *parser combinators*.

POM defines a type called: `Parser`, which is used to encode parsing rules. A parser can be constructed using many of the pre-defined parsers that the library provides, such as the `sym` and `seq` functions. The above example of a variable definition can be expressed in POM as:

```rust
use pom::char_class::*;
use pom::parser::*;

fn variable_def<'a>() -> Parser<'a, u8, (String, u32)> {
  let valid_id = (is_a(alpha) + is_a(alphanum).repeat(0..))
    .map(|(first, rest)| format!("{}{}", first as char, String::from_utf8(rest).unwrap()));
  let valid_expr = one_of(b"0123456789")
    .repeat(1..10)
    .convert(String::from_utf8)
    .convert(|s| s.parse::<u32>());
  seq(b"let") * sym(b' ') * valid_id - sym(b' ') - sym(b'=') 
    - sym(b' ').repeat(0..) + valid_expr - sym(b';')
}
```

Let's break down the code:
1 - We import all the contents of `pom::char_class`, which exports 
predicates such as `alpha`, and `alphanum`. We use these predicates to 
test the type of input characters.
`pom::parser` exports `seq`, and `sym` among other functions that return 
`Parser`s.
```rust
use pom::char_class::*;
use pom::parser::*;
```
2 - The `variable_def` function takes no arguments, and return a `Parser` 
with the lifetime `'a` that accepts `u8`s (character bytes) as input, and 
outputs a tuple of `(String, u32)`. The tuple encodes the variable's 
identifier, and its value (we limit valid values to 9-digit positive 
integers for simplicity's sake.)
```rust
fn variable_def<'a>() -> Parser<'a, u8, (String, u32)> 
```
3 - A valid variable identifier consists of at least one alphabetic character, followed by zero or more alphanumeric characters. We use the `is_a` parser to test that the first character of the variable id `is_a(alpha)`, and that the rest of the id `is_a(alphanum)`.
Notice how the `+` operator is used to combine the two parts of the variable identifier. It returns a tuple containing the results of both operands, which we then destructure in the `map` method call. `map` is used to transform the result of a parser, and return a new parser. In this case: `(is_a(alpha) + is_a(alphanum).repeat(0..))` returns a `Parser<'a, u8, (u8, Vec<u8>)>` (the first character and the rest of the characters,) which we then transform into a `Parser<'a, u8, String>` (the whole identifier) by concatenating the first character and the rest of the characters using `format!`.
```rust
let valid_id = (is_a(alpha) + is_a(alphanum).repeat(0..))
    .map(|(first, rest)| format!("{}{}", first as char, String::from_utf8(rest).unwrap()));
```
4 - A valid expression is defined as 1 to 9 numbers converted to a `String` which is then parsed as a `u32`. `convert` is used here instead of `map` because `String::from_utf8` returns a `Result`, so the parser wouldn't match the expression if the result of `String::from_utf8` is `Err`.
```rust
let valid_expr = one_of(b"0123456789")
    .repeat(1..10)
    .convert(String::from_utf8)
    .convert(|s| s.parse::<u32>());
```
5 - The returned parser is a combination of the symbols mentioned above mixed with some spaces, and a valid identifier and expression. The `*` operator combines two parsers and returns the result of the right-hand parser. So `Parser<'a, u8, T> * Parser<'a, u8, U> = Parser<'a, u8, U>`.  We also see the `-` operator in use, which combines two parsers and returns a parser with the value of the left-hand parser. These operators follow the same precedence rules as normal arithmetic operators in Rust.
```rust
seq(b"let") * sym(b' ') * valid_id - sym(b' ') - sym(b'=') 
    - sym(b' ').repeat(0..) + valid_expr - sym(b';')
```

> Take a look at [this handy table of parser combinators](https://github.com/J-F-Liu/pom#list-of-predefined-parsers-and-combinators).

Now to test our parser:
```rust
#[test]
fn test_variable_parser() {
  let valid_variable_byte_string = b"let v1 = 42;";
  let parsed_variable = variable_def().parse(valid_variable_byte_string);
  assert_eq!(parsed_variable, Ok(("v1".to_string(), 42)));

  let invalid_variable_byte_string = b"let nosemicolon = 42";
  let parsed_variable = variable_def().parse(invalid_variable_byte_string);
  assert_eq!(parsed_variable, Err(pom::Error::Incomplete));

  let invalid_variable_byte_string = b"let morethan9digits = 1234567890;";
  let parsed_variable = variable_def().parse(invalid_variable_byte_string);
  assert_eq!(
    parsed_variable,
    Err(pom::Error::Mismatch {
      message: "expect: 59, found: 48".to_string(),
      position: 31
    })
  );
}
```

Using POM to parse a variable definition of a positive integer value might seem overkill, but try to imagine using it to parse an entire programming language.

I hope you found this article helpful. Now enjoy parsing every string in your way.

Special thanks to [Junfeng Liu](https://github.com/J-F-Liu) and all contributors for creating an amazing library. You deserve a cookie 🍪