Skip to content

回憶零.一版實作遞迴下降時,吾人曾歸納,遞迴下降函數中主要是兩種短路結構,一是「或」結構,一是「且」結構。

「或」結構對應語法的 | ,「且」結構對應語法的 。重新看一次全是「且」結構的變數宣告式,其語法規則寫為:

語法
變數宣告式 = "元"・"・"・變數・"="・算式

其對應的遞迴下降函式:

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

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

可以看到遞迴下降函式相較語法規則要長上許多,有沒有辦法做簡化呢?

前 5 行很相似,但在參數與回傳值中仍存在一些差異,如果改寫 self.消耗(游標, O詞) ,全改寫為 self.消耗某詞(游標) -> ((), usize),前 5 行的形式就會完全相同:

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

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

前 5 行已經如此相似,寫出一個巨集且!(宏/macro)來生成類似代碼也許是個好主意:

rust
fn 剖析變數宣告(&self, 游標: usize) -> Option<(O變數宣告, usize)> {
    let (_, _ , 變數名, _, _ 算式) =
!(self.消耗元, self.消耗音界, self.消耗, self.消耗等號, self.剖析算式)
    Some((O變數宣告 { 算式, 變數名 }, 游標))
}

至於這個且!具體要怎麽寫,就交由道友自行練習。除了採用宏來簡化,還有另一種函數式語言的思路。

組合式剖析器

如果仔細觀察遞迴下降函式的前 5 行,它們的共性是什麼?皆返回 Option ,且一遇失敗便回傳 None 結束函式,那能否透過 Option 內建的 and_then 函式來簡化程式呢?

and_then 簡化「且」結構

rust
fn 剖析變數宣告(&self, 游標: usize) -> Option<(O變數宣告, usize)> {
    let (算式, 游標) = self
        .消耗元(游標)
        .and_then(|(_, 游標)| self.消耗音界(游標))
        .and_then(|(_, 游標)| self.剖析變數(游標))
        .and_then(|(變數名, 游標)| self.消耗賦值(游標))
        .and_then(|(_, 游標)| self.剖析算式(游標))?;

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

這寫法有一個大問題一個小問題。

  • 大問題:變數名卡在閉包裡,外部截取不到,導致編譯失敗
  • 小問題:游標還是反覆出現,改寫後程式碼簡潔不了多少

封裝 and_then

先來解決小問題,在 and_then 方法上包裝一層就能消除掉重複使用 游標 了:

rust
// Rust 得先宣告 trait 才能給內建型別加方法
trait 組合子<U> {
    fn 且<F>(self, f: F) -> Option<(U, usize)>
    where
        F: FnOnce(usize) -> Option<(U, usize)>;
}

impl<T, U> 組合子<U> for Option<(T, usize)> {
    fn 且<F>(self, f: F) -> Option<(U, usize)>
    where
        F: FnOnce(usize) -> Option<(U, usize)>,
    {
        // 其他行都在寫類型
        // 可以先看這行就好:封裝掉游標傳遞
        self.and_then(|(_語法, 游標)| f(游標))
    }
}

在給 Option<(T, usize)> 加上方法後就能將剖析變數宣告寫成

rust
fn 剖析變數宣告(&self, 游標: usize) -> Option<(O變數宣告, usize)> {
    let (算式, 游標) = self
        .消耗元(游標)
        .且(self.消耗音界)
        .且(self.剖析變數)
        .且(self.消耗賦值)
        .且(self.剖析算式)?;

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

已經十分簡潔了。

實際上,上面這個函式編譯過不了,因為消耗音界的類型是fn(&self: Self, 游標: usize),是一個接受兩個參數的函式,而 rust 不支援柯里化,編譯器接收到了一個 self 參數,仍會抱怨缺一參數。再進一步把每個剖析函數的回傳類型都改成 (T, 游標, Self) 或許能解決這問題。現在,暫時就先把參數加上去以過編譯。

傳遞 Self 也只是為了獲取 VecDequeue<O詞> 類型的 詞流,直接開個新結構把 詞流 以及 游標 的資訊一起傳遞還比較容易點,用切片又更簡單。

TODO: 剖析器零.一版範例程式一開始就用切片而非游標來當剖析函式的參數...

傳遞剖析結果

再來解決剖析結果卡在閉包的大問題,解法一樣是透過包裝來完成,讓每個剖析函數的的回傳值都能一路傳遞下來:

rust
trait 組合子<T, U> {
    fn 且<F>(self, f: F) -> Option<((T, U), usize)>
    where
        F: FnOnce(usize) -> Option<(U, usize)>;
}

impl<T, U> 組合子<T, U> for Option<(T, usize)> {
    fn 且<F>(self, f: F) -> Option<((T, U), usize)>
    where
        F: FnOnce(usize) -> Option<(U, usize)>,
    {
        // 將之前的剖析結果與新剖析結果以 tuple 包裝
        self.and_then(|(語法, 游標)| f(游標).map(|(新語法, 游標)| ((語法, 新語法), 游標)))
    }
}

最後回傳結構是巢狀的元組:

rust
fn 剖析變數宣告(&self, 游標: usize) -> Option<(O變數宣告, usize)> {
    let ((((_, 變數名), _), 算式), 游標) = self
        .消耗元(游標)
        .且(self.消耗音界)
        .且(self.剖析變數)
        .且(self.消耗賦值)
        .且(self.剖析算式)?;

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

這種寫法就被稱為組合子剖析器(也稱 parser combinator、剖析器組合子)。組合子函式泛指 and_then, or_else, map, filter 這類型高階函式,所以鏈式應用高階函式來寫剖析器就被叫做組合子剖析器了。

組合子剖析器能接近宏的簡潔程度,又避免掉宏不易除錯的問題。近年似乎漸露頭角,有好些新興的剖析庫都以此風格寫就。

or_else 如法炮製「或」結構

類似地,「或」結構也能用高階函數來簡化,回憶的定義與遞迴下降函式:

語法
句 = 變數宣告式
   | 算式
rust
fn 剖析句(&self, 游標: usize) -> Option<(O句, usize)> {
    if let Some((變數宣告, 游標)) = self.剖析變數宣告(游標) {
        return Some((O句::變數宣告(變數宣告), 游標));
    }
    if let Some((算式, 游標)) = self.剖析算式(游標) {
        return Some((O句::算式(算式), 游標));
    }
    None
}

「且」結構還能靠 Rust 的 ? 來簡寫,「或」結構就得自己手寫 if ... return 來短路,顯得更加冗長。

先試著用 or_else 來簡化短路

rust
fn 剖析句(&self, 游標: usize) -> Option<(O句, usize)> {
    self.剖析變數宣告(游標)
        .map(|(變數宣告, 游標)| (O句::變數宣告(變數宣告), 游標))
        .or_else(|| {
            self.剖析算式(游標)
                .map(|(算式, 游標)| (O句::算式(算式), 游標))
        })
}

好像沒什麼改善空間了,「或」結構不需要傳遞之前的剖析結果,比「且」結構要來得容易,而 map 中依然有重複出現的游標,那就照樣在map之外包裝一層。

rust
fn 映射<F>(self, f: F) -> Option<(U, usize)>
where
    F: FnOnce(T) -> U,
{
    self.map(|(剖析結果, 游標)| (f(剖析結果), 游標))
}

fn 剖析句(&self, 游標: usize) -> Option<(O句, usize)> {
    self.剖析變數宣告(游標)
        .映射(|變數宣告| O句::變數宣告(變數宣告))
        .or_else(|| self.剖析算式(游標).映射(|(算式)| O句::算式(算式)))
}

「重複」結構呢?

音界咒 = 句.句* 這種「重複」結構,也可以透過組合子來達成,在 之外封上一層迴圈就能做到吧,同樣留作道友習題。

總結

組合子剖析器無非就是種風格,若嚴格地只使用組合子,那結構會很單純,風格會很一致。但想要混用原本遞迴下降平鋪直敘的寫法,或是加上一些宏也沒什麼問題。例如要結合應用前一章所說的優先級決定算法,也許遞迴下降的寫法更好寫一些喔。

零.二版的新語法脫不出這幾項結構,就不再將新的剖析代碼貼出來了。

更新:貧道試著加上了更多組合子,可參考音界咒源碼