技術

用 nom 給 rslogo 寫一個 parser

2024年3月18日星期一 / , , , ,
簡體中文正體中文
摘要：
用 Rust 的 nom parser combinator 程式庫，為 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 是個 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，用 match 比對 Expr。語法樹既然已經是列舉，每種敘述該如何執行，就能直接對應到一個分支。變數和使用者定義的程序，則都存在一個我稱為 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...