Writing parsers
I am currently quite busy learning the ropes and architecture mapping in my day job and while drawing and mapping is fun, I am sometimes a bit afraid of getting rusty[1]. To fight this, I occasionally take a stroll through my projects and exhume some older ones in my spare time.
Among my parked project sits[2] something I’ve creatively dubbed spotql, a highly ambitious project to combine a Spotify client and psql via Postgres' wire protocol.
| I am well aware of the long list of really good libraries, like pgwire, but I ask you where is the fun, if I cannot combine two completely unrelated things and invent the wheel again? |
This whole project naturally involves writing a parser[3] and this is exactly the topic of this blog post. We are going to create three parsers with more-or-less idiomatic Rust, starting from a most naive version, hopping then over to something you probably could learn at the university to ultimately something nasty with a bit more brainfuck[4].
Om nom nom!
Example time &
Since it always good to follow some golden thread, we are using something from aforementioned project. Now, the wire protocol itself is quite lengthy and involves all the fun of network protocols and endianess, but we are going to avoid any side-tracks from my side by limiting us to a really simple SQL statement:
SELECT * FROM spotify;This should be fairly easy to parse, so here we go.
Simple tokenizer &
Since we are only naive here and not crazy, so we don’t even bother with regular expressions and plug some conditionals and a loop together:
const STMNT: &str = "SELECT * FROM spotify;";
fn main() {
let mut start: isize = -1;
let mut stop: isize = -1;
let mut verb = "";
let mut column = "";
let mut table = "";
let mut remainder = String::new();
for (i, c) in STMNT.chars().enumerate() {
match c {
'A'..='Z' | 'a'..='z' => { (1)
if -1 == start {
start = i as isize;
}
stop = i as isize + 1;
},
' ' | ';' => { (2)
if stop > start {
#[cfg(feature = "stats")]
println!("Token `{:?}` at {}-{}",
&STMNT[start as usize..stop as usize], start, stop);
if verb.is_empty() { (3)
verb = &STMNT[start as usize..stop as usize];
} else {
table = &STMNT[start as usize..stop as usize];
}
start = -1;
stop = -1;
}
#[cfg(feature = "stats")]
if ';' == c {
println!("End-of-Stmnt at {}", i);
}
},
'*' => { (4)
#[cfg(feature = "stats")]
println!("Wildcard `*` at {}", i);
column = "*";
},
_ => remainder.push(c), (5)
}
}
println!("Parsed: verb={:?}, column={:?}, table={:?}", verb, column, table);
println!("Parsed: remainder={:?}", remainder);
}| 1 | Still naive, we just handle different characters here for our token handling |
| 2 | Theses two characters have a special meaning for end of token resp. end or statement |
| 3 | Here is a good point to actually copy the values |
| 4 | Let us handle wildcards differently; could probably also be just allowed as token character |
| 5 | Just for completeness, let us collect everything we didn’t catch |
And if we run this beauty we can see we are basically done:
$ cargo run
Compiling simple-parser v0.1.0 (/home/unexist/projects/blog-examples/writing-parsers/simple-parser)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.97s
Running `target/debug/simple-parser`
Parsed: verb="SELECT", column="*", table="spotify"
Parsed: remainder=""There is no fluff, virtually no error handling and also nothing that handles the results, but hey we are talking about parsing only and I assume the code basically speaks for itself.
Tokenizer with FSM &
I guess you’ve read this far just to see another FSM and hell I don’t want to disappoint anyone here. So let us solve this again, this time with a bit of abstraction, FSM-flavor and hopefully make my former university prof happy:
use std::fmt;
const STMNT: &str = "SELECT * FROM spotify;";
#[derive(Debug)] (1)
enum State {
START,
SCAN,
TOKEN(usize, usize),
WILDCARD(usize),
BLANK(usize),
#[allow(non_camel_case_types)]
END_OF_STMNT(usize),
END,
}
impl fmt::Display for State { (2)
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self {
State::START => write!(f, "START"),
State::SCAN => write!(f, "SCAN"),
State::TOKEN(start, stop) => write!(f, "TOKEN({}, {})", start, stop),
State::WILDCARD(pos) => write!(f, "WILDCARD({})", pos),
State::BLANK(pos) => write!(f, "BLANK({})", pos),
State::END_OF_STMNT(pos) => write!(f, "END_OF_STMNT({})", pos),
State::END => write!(f, "END"),
}
}
}
fn main() {
let mut states: Vec<State> = vec![State::START]; (3)
let mut iter = STMNT.chars().enumerate();
let (mut i, mut c) = iter.next().unwrap_or((usize::MAX, char::MAX));
let mut verb = "";
let mut column = "";
let mut table = "";
let mut remainder = String::new();
'parser: loop { (4)
match states.last().unwrap_or(&State::START) {
State::START | State::SCAN => { (5)
match c {
'A'..='Z' | 'a'..='z' => {
states.push(State::TOKEN(i, i + 1));
}
' ' => { (6)
states.push(State::BLANK(i));
}
';' => {
states.push(State::END_OF_STMNT(i));
}
'*' => {
states.push(State::WILDCARD(i));
}
_ => remainder.push(c),
}
},
State::TOKEN(start, _) => { (7)
match c {
'A'..='Z' | 'a'..='z' => {
let newstate = State::TOKEN(*start, i + 1);
states.pop(); (8)
states.push(newstate);
(i, c) = iter.next().unwrap_or((usize::MAX, char::MAX)); (9)
}
_ => states.push(State::SCAN),
}
},
State::WILDCARD(_) => { (10)
states.push(State::SCAN);
(i, c) = iter.next().unwrap_or((usize::MAX, char::MAX));
},
State::BLANK(_) => {
states.push(State::SCAN);
(i, c) = iter.next().unwrap_or((usize::MAX, char::MAX));
},
State::END_OF_STMNT(_) => {
states.push(State::END);
},
State::END => {
break 'parser; (11)
}
}
}
#[cfg(feature = "debug")] (12)
for state in states.iter() {
println!("{}", state);
}
for state in states.iter() { (13)
match state {
State::TOKEN(start, stop) => {
#[cfg(feature = "stats")]
println!("Token `{}` at {}-{}", &STMNT[*start..*stop], start, stop);
if verb.is_empty() { (14)
verb = &STMNT[*start..*stop];
} else {
table = &STMNT[*start..*stop];
}
},
#[allow(unused)] (15)
State::WILDCARD(pos) => {
#[cfg(feature = "stats")]
println!("Wildcard `*`at {}", pos);
column = "*";
},
#[allow(unused)]
State::END_OF_STMNT(pos) => {
#[cfg(feature = "stats")]
println!("End-of-Stmnt at {}", pos);
},
_ => {},
}
}
println!("Parsed: verb={:?}, column={:?}, table={:?}", verb, column, table);
println!("Parsed: remainder={:?}", remainder);
}| 1 | We start with the definition of our parsing states and use enum variants |
| 2 | Deriving from Debug is nice, but let us also roll our own formatter |
| 3 | We keep our states neatly collected in a vec, so we can do some post-processing later |
| 4 | Technically not required here, but adding labels to loops make it a bit easier to follow |
| 5 | Utilizing the FSM idea basically means we step through the various states and have some checks, if something is reasonable within its boundaries |
| 6 | As before, the blank is some special case and we handle it accordingly |
| 7 | The token state is something special, because it also keeps tracks of the start and stop position |
| 8 | Handling a vector of options is sometimes a pain to modify, so we just pop/push to basically compact the many states this creates |
| 9 | Iterator are also strictly safe-guarded, so we iterate here manually whenever we have to and avoid peeking or stepping back |
| 10 | The other states are a bit of repetitive, I left them in to make it easier to follow though |
| 11 | Here is the break with the label, this is easier to follow, right? |
| 12 | Another nifty feature is the feature handling of Cargo, this allows us to see the state list when enabled |
| 13 | Since we basically decoupled handling and parsing, we still need to strep through our states and assign variables |
| 14 | Not the best way to do that through.. |
| 15 | And the rest is just boring default stuff |
That is much more code and renders basically the same thing:
$ cargo run
Compiling fsm-parser v0.1.0 (/home/unexist/projects/blog-examples/writing-parsers/fsm-parser)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.28s
Running `target/debug/fsm-parser`
Parsed: verb="SELECT", column="*", table="spotify"
Parsed: remainder=""But if we enable the debug feature with cargp run --features debug we can
also see the state changes of our FSM:
$ cargo run --features debug
Compiling fsm-parser v0.1.0 (/home/unexist/projects/blog-examples/writing-parsers/fsm-parser)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.15s
Running `target/debug/fsm-parser`
START
TOKEN(0, 6)
SCAN
BLANK(6)
SCAN
WILDCARD(7)
SCAN
BLANK(8)
SCAN
TOKEN(9, 13)
SCAN
BLANK(13)
SCAN
TOKEN(14, 21)
SCAN
END_OF_STMNT(21)
END
Parsed: verb="SELECT", column="*", table="spotify"
Parsed: remainder=""Needless to say there is much more room for improvements, but the goal here was to demonstrate how this can be done and to establish there are different ways for parsing, just to explain a totally different approach next.
Curious?
Parser combinator &
When I started spotql I did a quick check how one would write idiomatic parsers urc with Rust and I quickly discovered the create nom - a parser combinators library. It took me quite a while until it made click and the migration from version 6 to version 8, which basically deprecated every macro in favor of functions, didn’t make it easier either.
Parser combinators or in general combinatory parsing works slightly different, than how we did that in the two examples above. So far we’ve created a fancy loop, which accepts an input string and after some processing returns some kind of structure with the result.
| The first parser didn’t exactly do that, but technically the second did with its states vector - consider it as a preliminary form of AST. |
Parser combinators, on the other hand, accept one or more parsers as an input and generally return a new parser as its output - this are so called higher-order functions. I know this might sound a bit strange, but let us start from bottom and learn about this on our way. Keep in mind we just use plain Rust here, so nothing beyond std.
Carving out &
Since we need functions, a good start is to move some of the actual parsing into a function, which makes re-use dramatically easier and more DRY-ish.
We had to parse lots of things like our SQL verb or other identifiers, which is not rocket science, but looks quite nice and easy like this:
fn identifier(input: &str) -> Result<(&str, String), &str> { (1)
let mut stop: usize = 0;
let mut iter = input.chars();
match iter.next() { (2)
Some(next) if next.is_alphabetic() => stop += 1,
_ => return Err(input),
}
while let Some(next) = iter.next() { (3)
if next.is_alphanumeric() {
stop += 1;
} else {
break;
}
}
Ok((&input[stop..], String::from(&input[..stop]))) (4)
}| 1 | The return type looks odd I know, but let us ignore it for now |
| 2 | Identifiers basically always start with a letter |
| 3 | Followed by more of same including numbers this time |
| 4 | Unfortunately we have to deal with the return type now: This is basically a result, containing a tuple of 1) the remaining input we didn’t consume and 2) the actual string we’ve consumed and another string as error, we still ignore |
Higher-order functions &
Next up on our list are strings, which need to be there to keep the format, but we actually have no direct interest in, so we can just gobble them up:
fn tag(expected: &'static str) -> impl Fn(&str) -> Result<(&str, String), &str> { (1)
move |input| match input.get(0..expected.len()) { (2)
Some(next) if next == expected => { (3)
Ok((&input[expected.len()..], expected.to_string()))
},
_ => Err(input),
}
}| 1 | Here they are, higher-order functions with improved weirdness: This time we return a function (marked by the impl keyword), which returns our result from before. |
| 2 | I don’t want to throw move semantics into the mix, just pretend this is the weird syntax of Rust to define that |
| 3 | And with our dutiful guard we filter for our wanted string and slice out remaining and matched tag - this is not directly gobbled up, but if you prefer it replace it with unit. |
Adding a combinator &
Now it is getting interesting: We have two functions now, but need a way to combine them or otherwise we’d basically re-create the first parser, just more complex.
Take a seat and meet pair, our first actual combinator:
pub(crate) fn pair<P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Fn(&str) -> Result<(&str, (R1, R2)), &str>
where
P1: Fn(&str) -> Result<(&str, R1), &str>,
P2: Fn(&str) -> Result<(&str, R2), &str>, (1)
{
move |input| match parser1(input) {
Ok((next_input, result1)) => match parser2(next_input) { (2)
Ok((final_input, result2)) => Ok((final_input, (result1, result2))),
Err(err) => Err(err),
},
Err(err) => Err(err),
}
}Interim step &
Pair works exactly as the name implies:
It allows to combine two parsers and returns the result of both when called.
This is probably easer to understand with a short example:
fn main() {
let parser = pair(identifier, tag("from")); (1)
let result = parser("SELECT from"); (2)
println!("{:?}", result);
}| 1 | Throw both into a pair and receive a shiny new parser |
| 2 | This actually calls our parser with this string |
And when run:
$ cargo run
Compiling combinator-parser v0.1.0 (/home/unexist/projects/blog-examples/writing-parsers/combinator-parser)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.18s
Running `target/debug/combinator-parser`
Err(" from") (1)| 1 | D’uh.. Looks like we forgot about the whitespace in between! |
Handling whitespaces &
Like before, we need a function to collect all consecutive whitespaces and this can probably done without any surprise:
fn whitespace(input: &str) -> Result<(&str, String), &str> {
let mut stop: usize = 0;
let mut iter = input.chars();
match iter.next() {
Some(next) if ' ' == next => stop += 1,
_ => return Err(input),
}
Ok((&input[stop..], String::from(&input[..stop])))
}Actually the same approach as before works, but looks totally knocked up if you ask me:
fn main() {
let parser = pair(identifier, pair(whitespace, tag("*"))); (1)
let result = parser("SELECT *"); (2)
println!("{:?}", result);
}And when called:
$ cargo run
Compiling combinator-parser v0.1.0 (/home/unexist/projects/blog-examples/writing-parsers/combinator-parser)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.15s
Running `target/debug/combinator-parser`
Ok(("", ("SELECT", (" ", "*")))) (1)| 1 | Looks weird again, but this actually our expected output with the nested tuples |
More mathematics &
Before we can really fire this off, we need one additional element - a functor. A functor is basically something, that can map between things and in our case just calls a function on our results:
pub(crate) fn map<P, F, A, B>(parser: P, map_fn: F) -> impl Fn(&str) -> Result<(&str, B), &str>
where
P: Fn(&str) -> Result<(&str, A), &str>,
F: Fn(A) -> B,
{
move |input| match parser(input) {
Ok((next_input, result)) => Ok((next_input, map_fn(result))), (1)
Err(err) => Err(err),
}
}| 1 | We covered lots of ground today and barely start to sweat when seeing this: We just call the passed function on our result and return whatever comes back |
Mapping all the things &
Now with our functor, we can quickly add some more trivial helper functions left
and right:
pub(crate) fn left<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Fn(&str) -> Result<(&str, R1), &str>
where
P1: Fn(&str) -> Result<(&str, R1), &str>,
P2: Fn(&str) -> Result<(&str, R2), &str>,
{
map(pair(parser1, parser2), |(left, _right)| left) (1)
}
pub(crate) fn right<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Fn(&str) -> Result<(&str, R2), &str>
where
P1: Fn(&str) -> Result<(&str, R1), &str>,
P2: Fn(&str) -> Result<(&str, R2), &str>,
{
map(pair(parser1, parser2), |(_left, right)| right) (2)
}| 1 | With every building block in place and this is just piece of cake: Call both parsers from the pair and return just the result of the left one. |
| 2 | And opposite direction - call both and return right |
Handle delimited strings &
Before adding more stuff, we should focus again on what we actually want to achieve:
Getting rid of leading and trailing whitespaces in a functional and cool way.
Since we have everything in place, let us create a new parser generator
called delimited, that can use three parsers and like left and right,
return only a selection - here we go for the middle this time:
pub(crate) fn delimited<'a, P1, P2, P3, R1, R2, R3>(parser1: P1, parser2: P2, parser3: P3) -> impl Fn(&str) -> Result<(&str, R2), &str>
where
P1: Fn(&str) -> Result<(&str, R1), &str>,
P2: Fn(&str) -> Result<(&str, R2), &str>,
P3: Fn(&str) -> Result<(&str, R3), &str>,
{
map(right(parser1, left(parser2, parser3)), |middle| middle) (1)
}| 1 | We use a combination of right and left to sort this out and call map
on the result to get to the middle |
Zero or more? &
When using delimited right now we are going to face the problem of times
when there is in fact no leading or trailing space:
fn main() {
let parser = pair(delimited(whitespace, identifier, whitespace),
delimited(whitespace, tag("*"), whitespace));
let result = parser("SELECT *");
println!("{:?}", result);
}And when this is called:
Compiling combinator-parser v0.1.0 (/home/unexist/projects/blog-examples/writing-parsers/combinator-parser)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.14s
Running `target/debug/combinator-parser`
Err("SELECT *") (1)| 1 | Several whitespaces are missing |
So we need something that handles either optional or zero to many. Optional is something for another day, but the second approach sounds like it fits well:
pub(crate) fn zero_or_more<'a, P, A>(parser: P) -> impl Fn(&str) -> Result<(&str, Vec<A>), &str>
where
P: Fn(&str) -> Result<(&str, A), &str>,
{
move |mut input| {
let mut result = Vec::new();
while let Ok((next_input, next_item)) = parser(input) { (1)
input = next_input;
result.push(next_item);
}
Ok((input, result))
}
}| 1 | Another loop, storing everything in a vector and never bail out - next! |
Perfection &
Took us a while, but we have all elements in place, can finally assemble our complete parser and ultimately parse the string:
fn main() {
let verb_parser = delimited(zero_or_more(whitespace), identifier, zero_or_more(whitespace));
let column_parser = delimited(zero_or_more(whitespace), tag("*"), zero_or_more(whitespace));
let table_parser = right(
delimited(zero_or_more(whitespace), tag("FROM"), zero_or_more(whitespace)),
left(identifier, tag(";")));
let parser = pair(verb_parser, pair(column_parser, table_parser)); (1)
if let Ok(remainder) = map(parser, |(verb, (column, table))| {
println!("Parsed: verb={:?}, column={:?}, table={:?}", verb, column, table);
})(STMNT) {
println!("Parsed: remainder={:?}", remainder.1);
}
}| 1 | Isn’t it cool how easy this is to read? |
And if we run the whole example:
$ cargo run
Compiling combinator-parser v0.1.0 (/home/unexist/projects/blog-examples/writing-parsers/combinator-parser)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.13s
Running `/home/unexist/projects/blog-examples/writing-parsers/combinator-parser/target/debug/combinator-parser`
Parsed: verb="SELECT", column="*", table="spotify"
Parsed: remainder=()There are many more ways to further optimize this, like introducing proper types and a trait, to avoid repeating yourself, but this is clearly just on the ergonomics side:
pub(crate) type ParseResult<'a, Output> = Result<(&'a str, Output), &'a str>;
pub(crate) trait Parser<'a, Output> {
fn parse(&self, input: &'a str) -> ParseResult<'a, Output>;
}| If you feel adventurous have a look at the parser_trait.rs examples, if you want to see how this can be done. |
Conclusion &
I wonder if people think it is weird to write about manually writing a parser nowadays, but nevertheless I really enjoyed preparing the examples and also trying to find and hopefully to keep a golden thread.
Even so, parsing is for me an integral part of programming and I wanted to show these three versions of parsers, that I’ve written many times over during my personal and professional programming career[6],
If I had to pick a favorite I’d probably prefer number three, because playing with it was the most fun to me. If it is not just for joy, I’d probably just hack some iterative version like number one together or really throw in some FSM-magic, to have a more error-safe version.
All examples can be found here:
where clause in our function signature, how likely is that?