Skip to content

零・二版新增了「若」、「術」兩語句,並增加了比較、餘數運算子。

運算子優先級語法定義

零・一版的算式語法如下:

語法
算式      = 乘除式・(+・乘除式)*
         | 乘除式・(-・乘除式)*

乘除式    = 原子式・(*・原子式)*
         | 原子式・(/・原子式)*

原子式    = 數字
         | 變數
         | "("・算式・")"

為了區分乘除加減以及括號的優先級,吾人生造了乘除式原子式以讓剖析器自動以正確層級構造算式。

新增的比較、餘數運算子也可依照此法,再切分出更多運算子的語法:

語法
算式      = 加減式・(==・加減式)*
         | 加減式・(!=・加減式)*
         | 加減式・(>=・加減式)*
         | 加減式・(>・加減式)*
         | 加減式・(<=・加減式)*
         | 加減式・(<・加減式)*

加減式    = 餘數式・(+・餘數式)*
         | 餘數式・(-・餘數式)*

餘數式    = 乘除式・(%・乘除式)*

乘除式    = 原子式・(*・原子式)*
         | 原子式・(/・原子式)*

原子式    = 數字
         | 變數
         | "("・算式・")"

以此語法手寫遞迴下降自然可以剖析算式,但仔細一想,在回溯過程中,算式能展開的方式越多種,就越常需要回到過去重試,當運算子種類越來越多,就有可能拖累到剖析器的效能。

而手寫遞迴下降中充斥大量為了處理優先級而生的函數,也會降低可讀性。那有沒有其他方法能決定優先級呢?

決定優先級的算法

道友們可能在煉氣時就學過或自己想到過該如何巧用棧,從左到右掃過一個算式求其值。該算法名為調車場算法,而其遞迴版本(遞迴跟棧關係密切啊!)有另一個名字,叫優先級爬升算法

算法並不難,首先來觀察一個算式

c
1 == 5 - 3 % 2 * 4 - 1

從左到右來讀取,當讀取到

c
1 == 5

時,能確定 1 與 5 以 == 結合嗎?不能,若 5 的右側算子優先級比 == 還大,那 == 不會結合。

再來往右讀取 - 3

c
1 == 5 - 3

時,能確定 5 與 3 以 - 結合嗎?不能,若 3 的右側算子優先級比 - 還大,那 - 不會結合。

同理,一直向右讀取到

c
1 == 5 - 3 % 2 * 4

時,都無法確定任何一個算子結合,注意到,無法結合是因為,至今遇到的所有算子中,新算子總是比舊算子優先級高。(發現維護的序列具有單調特徵時,往往意味能用棧來解題。)

但再往右讀取一個算子就不一樣了

c
1 == 5 - 3 % 2 * 4 - 1

- 的優先級小於 2 * 4 ,故 2 * 4 必先結合。結合後密不可分,僅以代數 x 表示,可視為

c
1 == 5 - 3 % x - 1

- 比較的對象變為 % ,% 仍比 - 優先級高,故 3 % x 先結合,現在式子為

c
1 == 5 - x - 1

x 兩側的 - 優先級相等,但 - 是左結合,優先往左側結合,故 5 - x 先結合

c
1 == x - 1

此時 - 的優先級大於 == ,如果右側還有算子的話,倒是無法確定 x - 1 會結合,但現在右側已經沒東西了,故 x - 1 結合,最後輪到 == 。

用虛擬碼來表述該過程:

虛擬
想像吾人先蓋住整個算式,再從左到右慢慢展露整個算式。

持續向右讀取新算子:
    將新算子與已知算式最右側的算子做比較
    若新算子優先級較低:
        則最右側已知算子可結合,此時再與結合後算式中的最右側算子比較。
        重複此動作直到已知算子優先級低於新算子,此時沒有一個算子的優先級能確認,將新算子丟回已知算式
    若新算子優先級較高:
        沒有一個算子的優先級能確認,將新算子丟進已知算式

當算子讀取完畢,從右往左結合。

該算法稍作加強,也能處理括號,基本想法是每當遇到右括號時,就當做算子已經暫時讀取完畢,算子算式由右一直向左結合直到碰到左括號。

以棧實作:調車場算法

此過程能以棧輕易模擬,具體作法可參照下方源碼:

rust
fn 優先級(運算子: &O運算子) -> u64 {
    match 運算子 {
        O運算子::=> 4,
        O運算子::=> 4,

        O運算子::=> 3,

        O運算子::=> 2,
        O運算子::=> 2,

        O運算子::等於 => 1,
        O運算子::異於 => 1,
        O運算子::小於 => 1,
        O運算子::小於等於 => 1,
        O運算子::大於 => 1,
        O運算子::大於等於 => 1,
    }
}

struct 調車場 {
    算元棧: VecDeque<O算式>,
    算子棧: VecDeque<O運算子>,
}

impl 調車場 {
    fn new(首個算元: O算式) -> Self {
        Self {
            算元棧: vec![首個算元].into(),
            算子棧: vec![].into(),
        }
    }
    fn 結合棧中算子(&mut self) {
        let 右算元 = self.算元棧.pop_back().unwrap();
        let 左算元 = self.算元棧.pop_back().unwrap();
        let 運算子 = self.算子棧.pop_back().unwrap();
        self.算元棧.push_back(O算式::二元運算(O二元運算 {
            運算子,
: Box::new(左算元),
: Box::new(右算元),
        }));
    }
    fn 讀取(&mut self, 新算子: O運算子, 新算元: O算式) {
        // 讀取到新算子,進行棧操作
        while !self.算子棧.is_empty() && 優先級(self.算子棧.back().unwrap()) >= 優先級(&新算子)
        {
            // 新算子優先級較低,代表棧中的算子算元可以先結合了。
            self.結合棧中算子();
        }
        // 棧中能結合的算子跟算元都結合了,推入新算子跟算元
        self.算子棧.push_back(新算子);
        self.算元棧.push_back(新算元);
    }

    fn 結束(&mut self) -> O算式 {
        while !self.算子棧.is_empty() {
            self.結合棧中算子();
        }
        assert_eq!(self.算子棧.len(), 0);
        assert_eq!(self.算元棧.len(), 1);

        self.算元棧.pop_back().unwrap()
    }
}

遞迴實作:優先級爬升算法

TODO:

混用回溯剖析與優先級決定算法

那吾人不妨在剖析器中將算子、算元與括號順序保留,再由此優先級爬升算法來處理優先級。

語法
算式      = 原子式・(算子・原子式)*

原子式    = 數字
         | 變數
         | "("・算式・")"

由於括號已經由原子式處理,在剖析算式中不需要處理括號,應用前述的調車場算法即可。

rust
fn 剖析算式(&self, 游標: usize) -> Option<(O算式, usize)> {
    let (原子式, mut 游標) = self.剖析原子式(游標)?;

    let mut 調車場 = 調車場::new(原子式);

    while let Some((新算子, 新游標)) = self.消耗運算子(游標) {
        let (新算元, 新游標) = self.剖析原子式(新游標)?;

        調車場.讀取(新算子, 新算元);

        游標 = 新游標
    }

    Some((調車場.結束(), 游標))
}