用 nom 给 rslogo 写一个 parser - Bojin Li

这学期在上 UNSW 的 COMP6991，课程的一个 assignment 叫 rslogo，要用 Rust 实现一个 Logo 语言的解释器。Logo 就是那个让小海龟往前走、转弯、抬笔落笔，最后画出一张图的教学语言，rslogo 要做的是读入一个 .lg 文件，执行里面的命令，把海龟画出来的东西保存成 SVG。

既然要执行代码，首先得把它解析出来。要么全靠正则，但是 Logo 里有嵌套的 [ ] 和嵌套的表达式，用正则写这种东西太烧脑了，还很容易出错。要么就靠最基础的字符串操作，按空格切开再一个个判断，这样能做，可是写出来会是一大堆 if 和下标，非常不优雅，也一点都不 Rust。

好在这个 assignment允许使用第三方库，所以我就去找了一下有没有更 Rust 一点的做法，于是找到了 nom 和 pest。由于 pest 要单独写一个 .pest 文件来描述语法，还得额外学一套它自己的语法规则，而 nom 写的就是普通的 Rust 函数，那么理所当然地，我选了 nom。

rslogo 结构

以下是 rslogo 要支持的代码：

TEXT

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
]

以 " 开头的是字面量，以 : 开头的是变量，COLOR 这种是查询海龟当前的状态。运算符是前缀的，+ COLOR "2 就是 COLOR + 2。IF 和 WHILE 后面跟一个条件和一个代码块，TO ... END 则是定义一个过程。表达式和代码块都可以无限嵌套，这正是正则最不擅长的东西。

nom 是怎么工作的

nom 是一个 parser combinator 库，思路是先写很多很小的 parser，再像搭积木一样把它们组合成一个大的。

在 nom 里，一个 parser 就是一个函数。它接收一段输入，解析成功的话，就返回剩下还没解析的输入，以及解析出来的结果。

Rust

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") 本身返回的就是一个 parser，所以写法上是两个括号连在一起。PENUP 被吃掉之后，剩下的 " FORWARD" 原样返回，下一个 parser 就可以从这里接着往下解析。而且返回的字符串都是原输入上的切片，整个过程不需要复制任何东西。

nom 很好用的地方，在于那一堆现成的组合子。alt 依次尝试几个 parser，用第一个成功的，preceded、delimited、tuple 按顺序匹配几个 parser，再挑出需要的结果，many0 重复匹配，map 把结果转换成自己的类型。比如 "60 是一个引号后面跟一个数字，写成 nom 就是这样。

Rust

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

这读起来几乎就是语法规则本身。而且每个 parser 都很小，可以单独测试，组合的时候类型系统还会帮你检查每一步对不对得上。

语法树

动手写 parser 之前，我先用枚举定义好了解析出来的东西长什么样。

Rust

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>),
}

parser 要做的，就是把一段字符串变成一个 Vec<Expr>。

rslogo 的 parser

空白

Logo 里到处都是空格，如果每个 parser 都自己处理一遍就太啰嗦了。所以我写了一个 ws，它接收一个 parser，返回一个会先吃掉前后空白的新 parser。

Rust

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)
}

这其实就是一个自己写的组合子，用起来和 nom 自带的没有区别。

值

各种值都是一个前缀加上内容，写法都差不多，最后用 alt 组合起来。

Rust

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

不过这里的顺序是有讲究的。alt 会用第一个成功的结果，而 "TRUE 既能当成布尔值，也能当成一个叫 TRUE 的名字，所以 parse_boolean 必须放在 parse_string 前面。

前缀表达式

这一段是我觉得 nom 最漂亮的地方。一个计算就是一个运算符，后面跟两个有值的东西，而这两个东西本身又可以是一个计算。

Rust

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)| {
        // 把 "EQ"、"+" 这些字符串对应到 Operator 的各个变体，这里省略
        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 和 parse_unvoid 互相递归，所以像 AND GT XCOR "0 GT YCOR "0 这种嵌套了好几层的表达式，也能一次解析出来。而且前缀表达式没有优先级的问题，也不需要括号，整个表达式的 parser 就只有这么几行。

命令和关键字

命令调用是一个名字，后面跟着若干个参数。

Rust

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)
}

因为命令名和关键字长得一样，都是一串字母，如果不加限制，END 也会被当成一个命令吃掉，那么 TO ... END 就永远找不到结尾了。所以我用 verify 在匹配到名字之后再检查一下，是保留字就当作失败。这样过程定义里的 many0(parse_expr) 遇到 END 自然就停下来了，外面的 delimited 再去匹配它。

Rust

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 和 WHILE 也是类似的写法，条件后面用 delimited(tag("["), many0(parse_expr), tag("]")) 解析代码块，代码块里又是 parse_expr，所以嵌套也就顺带支持了。

入口

最后把所有语句组合起来。

Rust

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 和 final_parser 来自 nom-supreme。ErrorTree 会把一路上尝试过的分支都记下来，出错的时候更容易看出问题在哪。final_parser 则要求输入必须被完全吃掉，不然普通的 nom parser 解析了一半也会返回成功，剩下的内容就被悄悄忽略了。

整个 parser 加起来也就两百行左右，每个函数基本就对应着一条语法规则。

执行器

parser 写完之后，执行就顺利多了。执行器是一个结构体，保存着海龟的状态，以及用来画图的画布，画布用的是课程提供的 unsvg。

Rust

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

核心是一个递归的 eval_expr，对 Expr 做 match。因为语法树已经是枚举了，所以每一种语句该怎么执行，直接对应着一个分支。变量和用户定义的过程，则都存在一个 HashMap<String, Expr> 里，我叫它 context。

Rust

fn eval_expr(
    &mut self,
    expr: Expr,
    context: &mut HashMap<String, Expr>,
) -> Result<Expr, String> {
    match expr {
        Expr::Constant(ref atom) => match atom {
            // 变量从 context 里取，查询返回海龟当前的状态
            Atom::Variable(v) => /* ... */,
            Atom::Query(q) => /* ... */,
            _ => Ok(expr),
        },
        Expr::Call(name, args) => match name.as_str() {
            "PENDOWN" => { /* ... */ }
            "FORWARD" => { /* ... */ }
            "MAKE" => { /* ... */ }
            // 不是内置命令，就去 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 的返回值也是一个 Expr。表达式求值之后得到的是一个 Expr::Constant，而命令执行完没有值，就返回 Expr::Void。所以计算的时候，只要先递归地求出左右两边，再看它们是不是两个数字或者两个布尔值就行。

Rust

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))
}

用 match 同时匹配左右两边，类型对不上的组合直接落到最后一个分支报错，像 + "1 "TRUE 这种就过不去。

IF 和 WHILE 是先求出条件，是 TRUE 就执行代码块，不是布尔值就报错。WHILE 每一轮都会重新求一次条件，所以条件里用到的变量在循环里被改了之后，下一轮就能看到新的值。

过程定义 TO ... END 执行的时候并不会运行函数体，只是把它原样存进 context。等到某个命令不是内置命令时，再去 context 里找有没有同名的过程。找到的话，先复制一份当前的 context 作为新的作用域，把参数的值放进去，然后在这个作用域里执行函数体，这样过程里对变量的修改就不会影响到外面。

Rust

_ => 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")),
},

画线就更简单了，FORWARD、BACK 这些命令算出终点的坐标，如果笔是落下的，就用 unsvg 在两点之间画一条线，然后更新海龟的位置。所有的错误都用 Result 一层层往上传，最后在 main 里用 color-eyre 输出。

仓库： xxxbrian/unsw-comp6991-rslogo。