技術

nomでrslogoのパーサーを書く

2024年3月18日月曜日 / , , , ,
簡体中文日本語
要約：
パーサーコンビネーターの nom を使って、COMP6991 の課題 rslogo のパーサーを実装した。Logo の式、コマンド、入れ子のブロックを解析する。

今学期は UNSW の COMP6991 を履修している。課題の一つが rslogo で、Rust で Logo 言語のインタープリターを作るというものだ。Logo は、タートルを前に進めたり、向きを変えたり、ペンを上げ下げしたりして絵を描く教育用の言語。rslogo では .lg ファイルを読み込み、その中のコマンドを実行して、タートルが描いたものを SVG として保存する。

コードを実行するには、まず解析しなければならない。全部を正規表現で処理する手もあるけれど、Logo には入れ子の [ ] や式がある。これを正規表現で書くのは頭が痛くなるし、間違えやすい。基本的な文字列操作だけで、空白ごとに分割して一つずつ判定することもできる。でも、できあがるのは大量の if と添字で、あまりきれいではないし、Rust らしさもない。

幸い、この課題では外部ライブラリを使ってよかった。もっと 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 はパーサーコンビネーターのライブラリだ。小さなパーサーをたくさん作り、積み木のように組み合わせて大きなパーサーにする。

nom では、パーサーはただの関数だ。入力を受け取り、解析に成功すると、まだ解析していない残りの入力と解析結果を返す。

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") 自体がパーサーを返すので、括弧が二つ続く書き方になる。PENUP を消費した後は、残りの " FORWARD" がそのまま返り、次のパーサーはそこから解析を続けられる。返す文字列はどれも元の入力のスライスなので、この処理でコピーは発生しない。

nom が便利なのは、組み合わせに使うコンビネーターがたくさんそろっているところだ。alt は複数のパーサーを順に試して最初に成功したものを使い、preceded、delimited、tuple は複数のパーサーを順番に実行して、必要な結果を取り出す。many0 は繰り返し、map は結果を自分の型に変換する。例えば "60 は引用符の後ろに数値が続く形なので、nom ではこう書ける。

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

ほとんど文法規則そのものを読んでいるように見える。それぞれのパーサーが小さいので単体でテストできるし、組み合わせるときは型システムが各段階のつながりも確認してくれる。

構文木

パーサーを書く前に、解析結果の形を enum で定義した。

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

パーサーの仕事は、文字列を Vec<Expr> に変えることだ。

rslogo のパーサー

空白

Logo にはあちこちに空白がある。それぞれのパーサーで毎回処理するのは面倒なので、ws を作った。パーサーを受け取って、前後の空白を消費する新しいパーサーを返す。

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 のように何段も入れ子になった式も一度に解析できる。前置記法には演算子の優先順位の問題がなく、括弧もいらないので、式のパーサー全体がこの数行に収まる。

コマンドとキーワード

コマンド呼び出しは、名前の後ろに引数がいくつか続く形だ。

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 パーサーは途中まで解析できただけでも成功を返せるので、そのままだと残りの入力を見落としてしまう。

パーサー全体で二百行ほど。それぞれの関数が、ほぼ一つの文法規則に対応している。

評価器

パーサーができると、実行部分はずっと書きやすくなった。評価器は、タートルの状態と描画用キャンバスを持つ構造体だ。キャンバスには授業で提供された unsvg を使っている。

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

中心になるのは再帰関数の eval_expr で、Expr を match する。構文木がすでに enum になっているので、それぞれの文をどう実行するかが、そのまま各分岐に対応する。変数とユーザー定義の手続きは、context と名付けた HashMap<String, Expr> に入れている。

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。

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...