真正的 parsing 要考慮運算子優先權跟括號等等，例如：
1 + 2 + 3 -> ((1 + 2) + 3) : Left associative（左相依）
1 + 2 * 3 -> (1 + (2 * 3)) : * 優先權高於 +
2 ^ 3 ^ 4 -> (2 ^ (3 ^ 4)) : Right associative（右相依）
在這裡我們要介紹 precedence climbing 這套演算法，假設我們已經有了 Term (op Term)* 這樣的序列，現在要將它 parse 成 syntax tree，可以參考這篇的內容：
precedence climbing 其實不難，首先我們會先讀進一個 token 作為 lhs token，優先權為 0。
接著持續取得下一個 operator 的優先權和 associative，如果運算子優先權 >= 目前優先權，則：
right associative，以同樣的優先權，遞迴呼叫 parse。
left associative ，則以高一級的優先權遞迴呼叫 parse。
虛擬碼大概如下：
climb (min_precedence)
lhs = get_token()
while next_op precedence >= min_precedence
op associative is left:
next_precedence = min_precedence + 1
op associative is right:
next_precedence = min_precedence
rhs = climb (next_precedence)
lhs = op (lhs, rhs)
return lhs
來個簡單的範例：如果所有運算子都是 left associative 、同樣優先權，例如 1+2+3+4，lhs 剖析出 1 之後，以高一級的優先權呼叫 climb，所有遞迴呼叫的 climb 都不會進到 while，而是直接回傳剖析到的第一個 token 給第一次呼叫 climb 的 while loop 作為 rhs， parse 成 (((1+2)+3)+4)。如果是遇到更高權限的運算子，則呼叫的 climb 會進到 while loop ，把後面的 token 都消耗掉再回傳其 lhs，可能因為這樣因此取名為 precedence climbing。
當然，比起我們自己實作，pest 裡面已經幫我們實作好了，只是在文件裡面都沒有提及，我也是看了用 huia-parser 這個用 pest 作 parsing 的 project ，才知道原來有這個功能可以用。
廢話不多說直接來寫，首先我們要在 Project 中引入 pest 的 precedence climbing 實作：
use pest::prec_climber::{Assoc, PrecClimber, Operator};
我們需要建好一個 PrecClimber 的物件，這個物件會儲存一個 Operator 的 Vec，優先權依順序增加，如果有相同優先權的運算子，則用 | 連接，每個 Operator 中會保存 parser 中定義的 Rule 跟 Assoc::Left 或 Assoc::Right，例如我們的 simple 的定義（這裡我加上一個 op_sub 來示範 | 的用法）：let PREC_CLIMBER = PrecClimber::new(vec![
Operator::new(Rule::op_lt, Assoc::Left),
Operator::new(Rule::op_add, Assoc::Left) | Operator::new(Rule::op_sub, Assoc::Left),
Operator::new(Rule::op_mul, Assoc::Left)
])
要剖析的時候則是呼叫 PrecClimber 的 climb 函式，它的型態乍看之下有點複雜：pub fn climb<'i, P, F, G, T>(&self, mut pairs: P, mut primary: F, mut infix: G) -> T
where
P: Iterator<Item = Pair<'i, R>>,
F: FnMut(Pair<'i, R>) -> T,
G: FnMut(T, Pair<'i, R>, T) -> T
其實也不難理解，它只是將上面的 precedence climbing 虛擬化為幾個函式：pairs: P 是全部要走訪的 (term (op term)*) iterator。
primary: F 會吃一個 term 將它轉為剖析後的結果。
infix: G 為結合方式，拿到兩個剖析後的結果跟一個運算子，將兩個結合起來。
這裡的 primary 其實就是我們寫過的 build_factor：
fn build_factor(pair: Pair<Rule>) -> Box<Node> {
match pair.as_rule() {
Rule::variable => Node::variable(pair.into_span().as_str()),
Rule::number => Node::number(pair.into_span().as_str().parse::<i64>().unwrap()),
_ => unreachable!(),
}
}
infix_rule 其實也只是把我們之前 build_expr 的東西給取出來：fn infix_rule(lhs: Box<Node>, pair: Pair<Rule>, rhs: Box<Node>) -> Box<Node> {
match pair.as_rule() {
Rule::op_add => Node::add(lhs, rhs),
Rule::op_mul => Node::multiply(lhs, rhs),
Rule::op_lt => Node::lessthan(lhs, rhs),
_ => unreachable!(),
}
}
build_factor 會吃進 token，將它轉為我們 AST 的型態 Box<Node>；infix_rule
使用 climb ，當我們拿到一個 expression token，要做的就只剩下把它丟給 climb 去爬，into_inner 將 expression token 轉為下層的 token iterator；：
// pair.as_rule() == Rule::expr
pub fn climb(pair: Pair<Rule>) -> Box<Node> {
PREC_CLIMBER.climb(pair.into_inner(), build_factor, infix_rule)
}
最後一小步，我們想要避免每次要 climb 的時候，還要重新產生 PREC_CLIMBER 這個物件，反正語法固定之前 PREC_CLIMBER 沒理由會變動，因此我們用了 lazy_static 這個套件，將它變成 static 的物件：#[macro_use]
extern crate lazy_static;
lazy_static! {
static ref PREC_CLIMBER: PrecClimber<Rule> = build_precedence_climber();
}
fn build_precedence_climber() -> PrecClimber<Rule> {
PrecClimber::new(vec![
Operator::new(Rule::op_lt, Assoc::Left),
Operator::new(Rule::op_add, Assoc::Left),
Operator::new(Rule::op_mul, Assoc::Left)
])
}
這麼一來我們的 simple 剖析器就完成了，現在 1 * 2 + 3 * 4 會是正確的 14 了，可喜可賀可喜可賀。
