Writing an rslogo Parser with nom

This term I'm taking UNSW's COMP6991. One of the assignments, rslogo, asks us to implement an interpreter for the Logo language in Rust. Logo is the educational language where you move a little turtle forward, turn it, and raise or lower its pen to draw a picture. rslogo reads a .lg file, executes its commands, and saves the turtle's drawing as an SVG.

Before executing any code, I needed to parse it. One option was to rely on regular expressions, but Logo has nested [ ] blocks and nested expressions. Writing regexes for that sounded like a headache, and an easy way to introduce bugs. Another option was basic string manipulation: split on spaces and check each piece. That would work, but the result would be a pile of if statements and indices. Not very elegant, and not very Rust-like.

Fortunately, the assignment allowed third-party libraries. I looked for a more idiomatic Rust approach and found nom and pest. pest requires a separate .pest file to describe the grammar, which means learning another set of syntax rules. With nom, I could just write ordinary Rust functions. Naturally, I chose nom.

The structure of rslogo

Here is the sort of code rslogo needs to support:

TO Box "Arg
   FORWARD :Arg
   LEFT :Arg
END

MAKE "BOXLINE "2

WHILE LT :BOXLINE "60 [
      SETPENCOLOR + COLOR "2
      Box :BOXLINE
      IF LT "8 COLOR [
         SETPENCOLOR "2
      ]
      ADDASSIGN "BOXLINE "2
]

A leading " marks a literal, a leading : marks a variable, and something like COLOR queries the turtle's current state. Operators use prefix notation: + COLOR "2 means COLOR + 2. IF and WHILE take a condition followed by a block, while TO ... END defines a procedure. Expressions and blocks can be nested arbitrarily deeply, which is exactly where regexes become awkward.

How nom works

nom is a parser combinator library. The idea is to write lots of tiny parsers, then put them together like building blocks to make a larger one.

In nom, a parser is a function. It takes some input and, if parsing succeeds, returns both the unconsumed input and the parsed result.

use nom::{bytes::complete::tag, IResult};

fn penup(input: &str) -> IResult<&str, &str> {
    tag("PENUP")(input)
}

assert_eq!(penup("PENUP FORWARD"), Ok((" FORWARD", "PENUP")));

tag("PENUP") itself returns a parser, which is why the two pairs of parentheses appear one after the other. After consuming PENUP, it returns the remaining " FORWARD" unchanged, ready for the next parser to continue. These returned strings are slices of the original input, so no copying is needed here.

What makes nom convenient is its collection of ready-made combinators. alt tries several parsers in order and uses the first one that succeeds. preceded, delimited, and tuple run parsers in sequence and keep the results you need. many0 repeats a parser, and map converts the result into your own type. For example, "60 is a quote followed by a number. In nom, that looks like this:

map(preceded(tag("\""), double), |n| Atom::Number(n as f32))

That reads almost like the grammar rule itself. Each parser is small enough to test independently, and the type system helps check that the pieces fit together when you combine them.

The syntax tree

Before writing the parser, I used enums to define what its output would look like.

pub enum Atom {
    Number(f32),
    Boolean(bool),
    String(String),
    Variable(String),
    Query(Query),
}

pub enum Expr {
    Void,
    Constant(Atom),
    Call(String, Vec<Expr>),
    Calculation(Operator, Box<Expr>, Box<Expr>),
    If(Box<Expr>, Vec<Expr>),
    While(Box<Expr>, Vec<Expr>),
    Function(String, Vec<Atom>, Vec<Expr>),
}

The parser's job is to turn a string into a Vec<Expr>.

The rslogo parser

Whitespace

There are spaces everywhere in Logo. Handling them separately in every parser would be tedious, so I wrote ws. It takes a parser and returns a new one that consumes whitespace before and after it.

fn ws<'a, F: 'a, O>(inner: F) -> impl FnMut(&'a str) -> IResult<O>
where
    F: FnMut(&'a str) -> IResult<O>,
{
    delimited(multispace0, inner, multispace0)
}

This is just a custom combinator. You use it in exactly the same way as nom's built-in ones.

Values

Each kind of value has a prefix followed by its contents. The parsers look much the same, and alt combines them.

fn parse_atom(input: &str) -> IResult<Atom> {
    alt((
        parse_number,
        parse_boolean,
        parse_string,
        parse_variable,
        parse_query,
    ))(input)
}

The order matters here. alt uses the first successful result, and "TRUE could be either a Boolean value or a name called TRUE. That means parse_boolean has to come before parse_string.

Prefix expressions

This is the part I find most elegant about nom. A calculation is an operator followed by two values, and either value can itself be another calculation.

fn parse_calculation(input: &str) -> IResult<Expr> {
    let parser = ws(tuple((
        alt((
            tag("EQ"), tag("NE"), tag("GT"), tag("LT"),
            tag("AND"), tag("OR"),
            tag("+"), tag("-"), tag("*"), tag("/"),
        )),
        parse_unvoid,
        parse_unvoid,
    )));
    map(parser, |(operator, left, right)| {
        // Map strings such as "EQ" and "+" to Operator variants; omitted here
        Expr::Calculation(to_operator(operator), Box::new(left), Box::new(right))
    })(input)
}

fn parse_unvoid(input: &str) -> IResult<Expr> {
    alt((parse_calculation, parse_constant))(input)
}

parse_calculation and parse_unvoid are mutually recursive, so an expression with several levels of nesting, such as AND GT XCOR "0 GT YCOR "0, can be parsed in one go. Prefix notation also avoids operator-precedence issues and does not need parentheses. Those few lines are the entire expression parser.

Commands and keywords

A command call is a name followed by zero or more arguments.

fn parse_call(input: &str) -> IResult<Expr> {
    let parser_args = ws(many0(parse_unvoid));
    let parser_command = ws(verify(alphanumeric_underline1, |s: &str| {
        not_reserved_word(s)
    }));
    let parser = ws(pair(parser_command, parser_args));
    map(parser, |(command, args)| Expr::Call(command.to_string(), args))(input)
}

Command names and keywords look the same: both are strings of letters. Without a restriction, the parser would consume END as a command, and TO ... END would never find its closing keyword. I use verify to check a name after matching it and reject reserved words. That way, many0(parse_expr) inside a procedure definition naturally stops at END, leaving the surrounding delimited to match it.

fn parse_function(input: &str) -> IResult<Expr> {
    let parser_name = ws(alphanumeric_underline1);
    let parser_args = ws(many0(parse_atom));
    let parser_body = ws(many0(parse_expr));
    let parser_inner = ws(tuple((parser_name, parser_args, parser_body)));
    let parser = ws(delimited(ws(tag("TO")), parser_inner, ws(tag("END"))));
    map(parser, |(name, args, body)| {
        Expr::Function(name.to_string(), args, body)
    })(input)
}

IF and WHILE work similarly. After the condition, delimited(tag("["), many0(parse_expr), tag("]")) parses the block. Since the block contains parse_expr again, nesting comes along with it.

The entry point

Finally, I combine all the statement parsers.

fn parse_expr(input: &str) -> IResult<Expr> {
    alt((
        parse_function,
        parse_while,
        parse_if,
        parse_constant,
        parse_call,
    ))(input)
}

pub fn parse(input: &str) -> Result<Vec<Expr>, ErrorTree<&str>> {
    final_parser(many0(ws(parse_expr)))(input)
}

ErrorTree and final_parser come from nom-supreme. ErrorTree records the branches tried along the way, making it easier to see what went wrong. final_parser requires the entire input to be consumed. Without that check, a regular nom parser can return success after parsing only part of the input, leaving the rest silently unhandled.

The whole parser is only about two hundred lines, and almost every function corresponds to a grammar rule.

The evaluator

Once the parser was done, execution was much more straightforward. The evaluator is a struct holding the turtle's state and a drawing canvas. For the canvas, I use the course-provided unsvg library.

pub struct Evaluater {
    pub image: Image,
    pen_down: bool,
    x: f32,
    y: f32,
    heading: i32,
    color: i32,
}

At its core is a recursive eval_expr that uses match on Expr. Since the syntax tree is already an enum, each kind of statement maps directly to a match arm. Variables and user-defined procedures live in a HashMap<String, Expr> that I call context.

fn eval_expr(
    &mut self,
    expr: Expr,
    context: &mut HashMap<String, Expr>,
) -> Result<Expr, String> {
    match expr {
        Expr::Constant(ref atom) => match atom {
            // Look up variables in context; queries return the turtle's current state
            Atom::Variable(v) => /* ... */,
            Atom::Query(q) => /* ... */,
            _ => Ok(expr),
        },
        Expr::Call(name, args) => match name.as_str() {
            "PENDOWN" => { /* ... */ }
            "FORWARD" => { /* ... */ }
            "MAKE" => { /* ... */ }
            // If not built in, look up a user-defined procedure in context
            _ => { /* ... */ }
        },
        Expr::Calculation(op, left, right) => { /* ... */ }
        Expr::If(condition, body) => { /* ... */ }
        Expr::While(condition, body) => { /* ... */ }
        Expr::Function(name, parameters, body) => { /* ... */ }
        Expr::Void => Ok(expr),
    }
}

eval_expr also returns an Expr. Evaluating an expression produces an Expr::Constant; executing a command with no value returns Expr::Void. For a calculation, I recursively evaluate both sides, then check whether they are two numbers or two Boolean values.

Expr::Calculation(op, left, right) => {
    let left = self.eval_expr(*left, context)?;
    let right = self.eval_expr(*right, context)?;
    let res = match (left, right) {
        (Expr::Constant(Atom::Number(l)), Expr::Constant(Atom::Number(r))) => match op {
            Operator::Add => Atom::Number(l + r),
            Operator::LessThan => Atom::Boolean(l < r),
            // ...
        },
        (Expr::Constant(Atom::Boolean(l)), Expr::Constant(Atom::Boolean(r))) => match op {
            Operator::And => Atom::Boolean(l && r),
            Operator::Or => Atom::Boolean(l || r),
            // ...
        },
        _ => return Err("Invalid calculation".to_string()),
    };
    Ok(Expr::Constant(res))
}

Matching both sides together with match means any incompatible combination falls through to the final error arm. Something like + "1 "TRUE is rejected.

IF and WHILE first evaluate their condition. If it is TRUE, they execute the block; if it is not a Boolean, they return an error. WHILE evaluates the condition again on every iteration, so a variable changed inside the loop is seen on the next check.

Executing a procedure definition, TO ... END, does not run its body. It simply stores it in context. When a command is not built in, the evaluator looks in context for a procedure with the same name. If it finds one, it clones the current context to create a new scope, binds the argument values, and runs the body in that scope. Changes to variables inside the procedure therefore do not affect the outer scope.

_ => match context.get(&name).cloned() {
    Some(Expr::Function(_, parameters, body)) => {
        let mut scope = context.clone();
        for (parameter, arg) in parameters.into_iter().zip(args.into_iter()) {
            match parameter {
                Atom::String(s) => {
                    let expr = self.eval_expr(arg, context)?;
                    scope.insert(s.clone(), expr);
                }
                _ => return Err("Invalid parameter".to_string()),
            }
        }
        for expr in body {
            self.eval_expr(expr.clone(), &mut scope)?;
        }
    }
    _ => return Err(format!("Function {name} not found")),
},

Drawing lines is simpler still. Commands such as FORWARD and BACK calculate the endpoint. If the pen is down, unsvg draws a line between the two points, then the turtle's position is updated. Errors propagate through Result all the way to main, where color-eyre reports them.

Repository: xxxbrian/unsw-comp6991-rslogo.