先定義剖析器的輸出——抽象語法樹節點的型別。

抽象語法樹節點型別定義

pub type Ｏ語法樹 = Ｏ咒;

pub struct Ｏ咒 {
    句: Vec<Ｏ句>,
}

enum Ｏ句 {
    變數宣告(Ｏ變數宣告),
    算式(Ｏ算式),
}

struct Ｏ變數宣告 {
    變數名: String,
    算式: Ｏ算式,
}

enum Ｏ算式 {
    變數(String),
    數字(i64),
    二元運算(Ｏ二元運算),
}

struct Ｏ二元運算 {
    運算子: Ｏ運算子,
    左: Box<Ｏ算式>,
    右: Box<Ｏ算式>,
}

剖析

貧道將每個生成符規則對應到一個剖析函式，剖析函式會從詞陣列的某個位置開始，嘗試找出其對應生成符的一組展開式。

剖析函式有以下形式：

// 游標是一個索引，指到當前詞陣列尚未被剖析的最前位置
// 應用任何一條規則剖析成功時，回傳 Some(Ｏ語法樹節點)
// 所有規則都剖析不了 XXX 生成符時，回傳 None
fn 剖析XXX(&self, 游標) -> Option<Ｏ語法樹節點, 剖析後的游標位置(usize)>

先來看個簡單例子，句的剖析，句應對到兩條簡單規則

// 句        = 變數宣告式
//           | 算式

fn 剖析句(&self, 游標: usize) -> Option<(Ｏ句, usize)> {
    // 句 = 變數宣告式
    // 若匹配`變數宣告`成功，返回對應語法樹節點
    if let Some((變數宣告, 游標)) = self.剖析變數宣告(游標) {
        return Some((Ｏ句::變數宣告(變數宣告), 游標));
    }

    // 句 = 算式
    // 若匹配`算式`成功，返回對應語法樹節點
    if let Some((算式, 游標)) = self.剖析算式(游標) {
        return Some((Ｏ句::算式(算式), 游標));
    }

    // 所有規則都無法剖析，返回 None
    None
}

再來看另一個例子，變數宣告的剖析，變數宣告只對應一條規則，但是，這條規則需要匹配多個符。

// 變數宣告式 = "元"・"・"・變數・"＝"・算式
fn 剖析變數宣告(&self, 游標: usize) -> Option<(Ｏ變數宣告, usize)> {
    let 游標 = self.消耗(游標, Ｏ詞::元)?;     // 若匹配不了 "元" ，短路返回
    let 游標 = self.消耗(游標, Ｏ詞::音界)?;   // 若匹配不了 "・" ，短路返回
    let (變數名, 游標) = self.剖析變數(游標)?; // 若匹配不了 變數 ，短路返回
    let 游標 = self.消耗(游標, Ｏ詞::等號)?;  // 若匹配不了 "＝" ，短路返回
    let (算式, 游標) = self.剖析算式(游標)?;  // 若匹配不了 算式 ，短路返回

    // 
    Some((Ｏ變數宣告 { 算式, 變數名 }, 游標))
}

觀察這兩個剖析函式，可以發現它們的短路規則截然相反

• 剖析句分成兩個主要if區塊，當剖析成功，得到 Some 時短路返回語法樹節點。
  • 應對的是兩條展開規則，一條展開能匹配詞流就算成功
  • 稱此結構為「或」
• 剖析變數宣告則連續調用了 5 次剖析函式 （消耗也是種剖析函式，只是它特別簡單），在剖析失敗，得到 None 時短路返回 None。
  • 應對的是：詞流必須完整匹配整條展開式才算匹配成功，一項不匹配就是失敗。
  • 但 Rust 提供了 ? 語法糖，所以不用一直 if let 才能知道是不是 Some
  • 稱此結構為「且」

語法展開也不外乎這兩個結構，一個在語法規則裡用 | 來表示「或」，用 ・ 來表示「且」。

來看個「或」、「且」結構都用上的語法規則原子式，其實作不外乎這兩種結構的組合。

// 原子式    = 數字
//         | 變數
//         | "（"・算式・"）"
fn 剖析原子式(&self, 游標: usize) -> Option<(Ｏ算式, usize)> {
    // 原子式 = 數字
    if let Some((數字, 游標)) = self.剖析數字(游標) {
        return Some((Ｏ算式::數字(數字), 游標));
    }
    // 原子式 = 變數
    if let Some((變數, 游標)) = self.剖析變數(游標) {
        return Some((Ｏ算式::變數(變數), 游標));
    }
    // 原子式 = （算式）
    // 此處用上了閉包來讓 ? 語法糖生效
    // 也可以選擇多寫一個函式來專門生成`原子式 = （算式）`
    if let Some(結果) = (|| -> Option<(Ｏ算式, usize)> {
        let 游標 = self.消耗(游標, Ｏ詞::左括號)?;
        let (算式, 游標) = self.剖析算式(游標)?;
        let 游標 = self.消耗(游標, Ｏ詞::右括號)?;
        Some((算式, 游標))
    })() {
        return Some(結果);
    }
    None
}

其他規則基本按照這兩結構依樣畫葫蘆就行，但重複原子式、重複乘除式需要額外處理左結合的問題，用遞迴來寫比較冗長麻煩（尤其 Rust 還要處理所有權），但其實形如：

算式      = 乘除式・重複乘除式

重複乘除式 = ＋・重複乘除式
         | −・重複乘除式
         | e

用如下形式表示更加簡單，期中的 (x)* 表示 x 可重複零或多次：

算式      = 乘除式・(＋・乘除式)*
         | 乘除式・(−・乘除式)*

在實作中用一個 while 迴圈就能輕鬆實作：

fn 剖析算式(&self, 游標: usize) -> Option<(Ｏ算式, usize)> {
    let (mut 算式, mut 游標) = self.剖析乘除式(游標)?;
    while let Some((運算子, 新游標)) = self.消耗加減(游標) {
        let (右算元, 新游標) = self.剖析乘除式(新游標)?;

        算式 = Ｏ算式::二元運算(Ｏ二元運算 {
            左: Box::new(算式),
            右: Box::new(右算元),
            運算子,
        });
        游標 = 新游標
    }
    Some((算式, 游標))
}

將音界咒的 9 條語法展開規則都寫成函式後，就可以調用

剖析咒(0)

來得到整棵語法樹了。注意到，本剖析器第一個呼叫的 剖析咒() 是語法樹最頂層的規則，它自頂向下的建構語法樹，因此吾人目前採用的回溯算法可說是一種「自頂向下」的剖析算法。

「自頂向下」剖析有很多種實作方法，如前文的虛擬碼比較像是對每條規則建表，最後再寫一個函式根據表格遞迴呼叫以完成剖析。而給每一個規則都寫一份對應函式的實作法，就被稱為「遞迴下降剖析」，大約是要強調手寫的遞迴函式互相呼叫、越來越深吧。建表法就未必要用遞迴來做，可以用棧（堆疊）來模擬。

每條規則都是手寫的雖然容易有誤，但也有靈活這個優點，除錯時想打印什麼訊息直接加在函式裡就行。從具體語法樹轉換成抽象語法樹也特別好寫，例如前面剖析變數宣告的函式，很輕鬆的就只從 5 個具體語法樹節點取出 2 個有用的抽象語法樹節點。