## 2018年5月10日 星期四

### 使用 procedence climbing 正確處理運算子優先順序

1 + 2 + 3 -> ((1 + 2) + 3) : Left associative（左相依）
1 + 2 * 3 -> (1 + (2 * 3)) : * 優先權高於 +
2 ^ 3 ^ 4 -> (2 ^ (3 ^ 4)) : Right associative（右相依）

precedence climbing 其實不難，首先我們會先讀進一個 token 作為 lhs token，優先權為 0。

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
```

```use pest::prec_climber::{Assoc, PrecClimber, Operator};
```

```let PREC_CLIMBER = PrecClimber::new(vec![
Operator::new(Rule::op_lt,  Assoc::Left),
Operator::new(Rule::op_mul, Assoc::Left)
])
```

```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
```

pairs: P 是全部要走訪的 (term (op term)*) iterator。
primary: F 會吃一個 term 將它轉為剖析後的結果。
infix: G 為結合方式，拿到兩個剖析後的結果跟一個運算子，將兩個結合起來。

```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_mul => Node::multiply(lhs, rhs),
Rule::op_lt => Node::lessthan(lhs, rhs),
_ => unreachable!(),
}
}
```

build_factor 會吃進 token，將它轉為我們 AST 的型態 Box<Node>；infix_rule

```// pair.as_rule() == Rule::expr
pub fn climb(pair: Pair<Rule>) -> Box<Node> {
PREC_CLIMBER.climb(pair.into_inner(), build_factor, infix_rule)
}
```

```#[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),
{"ft_lang_label":"__label__zh","ft_lang_prob":0.66120774,"math_prob":0.8822863,"size":3445,"snap":"2020-24-2020-29","text_gpt3_token_len":1863,"char_repetition_ratio":0.14007556,"word_repetition_ratio":0.00990099,"special_character_ratio":0.28940493,"punctuation_ratio":0.24806201,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.97953,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-07-14T00:14:18Z\",\"WARC-Record-ID\":\"<urn:uuid:8fb6cf81-5635-4e5a-a24c-e5e8ceccff41>\",\"Content-Length\":\"87957\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:2ef92772-fbe3-4b6d-b2e8-9b37d012c142>\",\"WARC-Concurrent-To\":\"<urn:uuid:0d227653-cf28-4ebf-9a39-f29ce3b389f4>\",\"WARC-IP-Address\":\"172.217.164.129\",\"WARC-Target-URI\":\"https://yodalee.blogspot.com/2018/05/procedence-climbing.html\",\"WARC-Payload-Digest\":\"sha1:4SDKQCG6TADVPQOI5JUWKS5CHYVC73EP\",\"WARC-Block-Digest\":\"sha1:C3GTBK7IUC2FCMRTU6WC6KFENXC63KBJ\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-29/CC-MAIN-2020-29_segments_1593657147031.78_warc_CC-MAIN-20200713225620-20200714015620-00474.warc.gz\"}"}