正文

在 src/lib.rs 補上一個函數和一個 smoke test, 如下

pub use traversal::{eval, format};

pub fn build_ast(expr: &str) -> Result<Node, String> {
    let root = syntax(lex(expr)?)?;
    Ok(root)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn smoke() {
        let expr = "1*2+(3/(4+(-5)))";
        let ast = build_ast(expr).unwrap();

        assert_eq!(-1, eval(&ast));
        assert_eq!("1 * 2 + 3 / (4 + (-5))", format(&ast));
    }
}
復制代碼

lexer

Lexer 模塊主要圍繞 DFA 展開講了很多, 具體實現的時候其實并沒有那么復雜, 主要是需要設計好存儲結構, 并理解清楚狀態轉移表的含義

parser

Parser 模塊大部分篇幅都在講文法和 Parser Combinator, 最后真正實現的時候反而非常簡單, 這里有兩點需要注意

• 文法的處理
  • 處理優先級
  • 消除左遞歸
• Parser Combinator 的封裝和設計理念

Parser Combinator 只是一種工具而已, 同類型的還有 Parser Generator, 由于筆者接觸不多, 就不好展開講了

不過這里個人認為, 比起 Parser Combinator 本身, 他的設計理念更值得關注, 尤其是這種相對比較小眾的函數式編程思維, 個人覺得很有意思

traversal

Traversal 模塊最主要的就是訪問者模式了, 根據我查到的資料來看, 普通的 AST 基本只有這一種遍歷方式

借助訪問者模式, 將所有的 visitor 單獨抽離進行實現, 代碼可讀性和耦合度得到了很大的優化, 筆者最開始其實是希望實現一個最最最簡化的表達式解析器, 因此第一版并沒有引入訪問者模式, 而在實現最后的兩個需求時發現代碼完全耦合在一起實在很惡心, 就干脆加進來了, 反正遍歷 AST 基本逃不掉這個訪問者模式

說在最后

個人感覺很多內容其實都講的有遺漏或者有不規范的地方, 但是整個編譯領域, 光入門的理論知識就太多太多了, 況且筆者只是自己寫了個玩具, 而且幾乎是個純編譯前端的項目, 也不敢說入門了, 因此就權當是學習筆記的分享了

源碼中有大量注釋, 個人感覺結合著看會更加清晰, 可以看一下, 在這里可以看