2018年5月10日 星期四

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

上一篇我們說完如何用 Rust 的 PEG 套件 pest 生成簡單的程式碼分析器,但其實還有一些沒有解決的問題,像是 1 * 2 + 3 * 4 = 20,這是因為我們在處理 expression 時沒有處理運算子優先次序,只是從左到右掃過一遍。
真正的 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 了,可喜可賀可喜可賀。

2018年5月6日 星期日

使用 rust pest 實作簡單的 PEG simple 剖析器

上一篇我們看了 PEG 相關的內容,這篇我們就來介紹該如何用 PEG 寫一個簡單的剖析器,當初會開始這系列文章,是因為自己 computation book rust 實作中,並沒有像原作者的 ruby 實作,有用 treetop 這個 PEG parser 寫一個剖析器,剖析文法變成裡面的程式,例如 simple, regupar expression, pushdown automata, lambda calculus 等等,最近想說把這部分補上,結果在第一關 simple 上就研究了好一陣子。
本來預估一個星期寫完,根本太樂觀,回家晚上能自己寫 code 的時間估太多,到現在應該已經快一個多月了,才有初步的結果,當然我們也可以說原因是 rust pest 沒有 ruby treetop 這麼好用(炸。

要使用 rust pest,首先是透過 cargo 安裝,為了這點我一開始先花好一陣子,把整個 project改寫成 cargo 管理,詳見這篇文章,之後才開始相關的實作,整個完成的程式碼可以看這裡
接著就是安裝 pest,在 Cargo.toml 中加上:
[dependencies]
pest = "^1.0"
pest_derive = "^1.0"
pest_derive 為 pest 剖析器產生器,他會分析你指定的 PEG 文法,生成對應的剖析規則跟剖析器;pest 則是引入剖析後生成的資料結構,兩個都要引入。
接著在原始碼中加入:
#[cfg(debug_assertions)]
const _GRAMMAR: &'static str = include_str!("simple.pest");
#[derive(Parser)]
#[grammar = "the_meaning_of_programs/simple.pest"]
struct SimlpeParser;
_GRAMMAR 是用來提醒編譯器,在 simple.pest 檔案更新的時候,也要觸發重新編譯(不然就會發現改了文法,cargo build 不會重新編譯),該 pest 檔的路徑是相關於目前的原始碼檔案;grammar 後的路徑則是相對於 src 資料夾,我試過不能用 .. 的方式回到 src 上一層目錄,grammar 檔案內容就是PEG 的語法,在編譯的時候會被 pest 轉換成 parser 的實作儲存在 SimpleParser 裡面。

pest 的語法基本上跟 PEG 沒有太大差別,在文法檔案中,就是 rule = { rule content } 的方式去定義規則:
  • 匹配字串使用雙引號包住,用 ^ 設定 ASCII 為無關大小寫,例:op_add = { “+” }, const = { ^”const” }
  • 一定文字範圍的用單引號搭配 ..,例:number = { ‘0’..’9’ }
  • 選擇規則用 | ,例:alpha = { ‘a’..’z’ | ‘A’..’Z’ }
  • 連結規則用 ~,跟 PEG 定義用空白直接連接不同,空白在 pest 用做排版,例:stat_assign = { variable ~ “=” ~ expr ~ “;” }

定義規則中,可以用到其他規則,例:factor = { (variable | number) }。
另外有一些特別的規則,包括:
  • whitespace:whitespace 裡指定的字串,會自動在 ~ 連結的位置中插入 (whitespace)*,平常不需要特別指明處理 whitespace,例如上面的 stat_assign 就變得能夠剖析 ”foo = 123” 而不只是 “foo=123”。
  • comment:comment 會在規則和子規則間被執行,不需特別指明。
  • any:匹配任一字元,對應 PEG 中的 .。
  • soi, eoi:對應匹配內容的開始和結束,這兩個還滿重要的,以之前的 S = A, A = aAa | a 為例,如果直接寫 S = { A },那去匹配一個以上的 a 都會匹配成功,因為我們沒指定 S 之後要把整個字串匹配完,正確的寫法是:S = { A ~ eoi }。
  • push, pop, peek:分別 push/pop/peek 字串到 stack 上面,push(rule) 將 rule 匹配到的字串送到 stack 上; epop/peek 會用 stack 內容的字串去做匹配,但 pop 會消耗掉 stack 的內容;這個規則我還沒有實際用過,不確定哪裡會用到它。

由於 pest 的文法規則都會被轉成一個 rust enum ,所以 rule 的取名必須避開 rust 的關鍵字,我在這裡是加上一些前綴或後綴來迴避,例如 stat_while;規則在剖析過後會生成對應的 token,內含剖析到的字串,如果是直接實寫的文字就不會產生出結果,這部分等等會看到。
  • 用 // 在規則中寫註解。
  • PEG 中 ?+* 三個符號,也是直接加上,有需要特別分隔的地方,可用小括號分開,例:number = @ { (digit)+ }、stats = { (stat)* }
  • e{n},e{,n},e{m,},e{m,n}:分別是 n 個,至多 n 個,m個以上,m至n個匹配。
  • PEG 的 & 跟 ! predicate 也是直接使用(不過我沒用過XD)

每個規則前面可以加上四個 optional modifier,分別如下:
  • Silent _ :剖析的時候不產生這個規則對應的節點,例如我的 factor 是:factor = _{ (variable | number) },那在剖析完之後,會直接跳過 factor,產生 variable 或 number 的節點。
  • Atomic @:這跟上面的 whitespace 有關,像我的 variable 寫成 variable = { (alpha) ~ (alpha | digit)* } ,豈不是可以接受 “a 123” 這樣奇怪的變數名?這時候就用 @ 確保規則中不執行 whitespace 規則。
  • Compound-atomic $:這跟 atomic 一樣,只是規則的子規則,例如 expr = $ { “-” ~ term } ,則 term 仍然適用 whitespace。
  • Non-atomic !:因為一個 atomic 規則下所有規則都會是 atomic,可以用 ! 來停止這樣的效果。

我們可以把上面這些都綜合起來,寫出一個極簡的 simple language parser,當然這實在是太簡單了,簡單到會出一些問題:
alpha = { 'a'..'z' | 'A'..'Z' }
digit = { '0'..'9' }

whitespace = _{ " " | “\n” }

variable = @ { (alpha) ~ (alpha | digit)* }
number = @ { (digit)+ }

op_add = { "+" }
op_mul = { "*" }
op_lt  = { "<" }
op_binary = _ {op_add | op_mul | op_lt }

factor = _{ (variable | number) }
expr = { factor ~ (op_binary ~ factor)* }

stat_assign = { variable ~ "=" ~ expr ~ ";" }
stat_while = { "while" ~ "(" ~ expr ~ ")" ~ "{" ~ stats ~ "}" }
stat_if = { ("if" ~ "(" ~ expr ~ ")" ~ "{" ~ stats ~ "}" ~ "else" ~ "{" ~ stats ~ "}" ) |
            ("if" ~ "(" ~ expr ~ ")" ~ "{" ~ stats ~ "}") }
stat = _{ ( stat_if | stat_while | stat_assign ) }
stats = { (stat)* }

simple = _{ soi ~ stats ~ eoi }
simple 就是整個剖析的進入點,在原始碼中呼叫 SimpleParser 的 parse 函式,對字串進行剖析,參數要代入想要剖析的規則和內容,這裡我們用 expression 來舉例,畢竟寫過 parser 就知道 expression 算是最難爬的東西之一,通常搞定 expression 其他都是小菜一碟:
let pair = SimpleParser::parse(Rule::expr, "1 * 2 + 3 * 4")
                .unwrap_or_else(|e| panic!("{}", e))
                .next().unwrap();
parse 之後會得到一個 Result<Pairs<R>, Error<R>>,表示是否成功,這裡如果不成功我們就直接 panic ,成功的話取出 Pairs,用 next unwrap 將第一個 Pair 取出來,也就是剖析完的 Expr Token,因為剖析失敗的話在剛剛的 Result 就會得到 Err 了,這裡我們都可以大膽的用 unwrap 取出結果。
Pair 有幾個函式可呼叫:

  • pair.as_rule() 會得到剖析的規則,此時的 pair.as_rule() 為 Rule::expr,這可以用來判斷剖析到什麼東西。
  • pair.into_span() 會取得 token 的範圍資訊。
  • pair.into_span().as_str() 會得到 token 匹配的字串內容,像在處理 assign的時候會用這個拿到變數名稱 。
  • pair.into_inner() 會拿到下一層的 Pairs,以 expr 來說,會對應到 { factor ~ (op_binary ~ factor)* },之前有提過字串並不會產生 token,上面的 stat_if, stat_while 就是例子,在 into_inner 的時候,括號、角括號等只是匹配,但不會有 token 產生。

在這裡我們把 expr 的 Pair 直接丟下去給另一個函式 build_expr,由它把 expression 剖析成 simple language 的 Node,它會先用 into_inner 叫出 expr 的內容物,然後依序取出左值、運算符跟右值並建成 Node Tree;可以從 op 的處理方式看到如何使用 as_rule() 來看看剖析到什麼。
fn build_expr(pair: Pair<Rule>) -> Box<Node> {
    let mut inner = pair.into_inner();
    let mut lhs = build_factor(inner.next().unwrap());
    loop {
        let op = inner.next();
        match op {
            Some(op) => {
                let rhs = build_factor(inner.next().unwrap());
                lhs = match op.as_rule() {
                    Rule::op_add => Node::add(lhs, rhs),
                    Rule::op_mul => Node::multiply(lhs, rhs),
                    Rule::op_lt  => Node::lessthan(lhs, rhs),
                    _ => unreachable!(),
                }
            },
            None => break,
        }
    }
    lhs
}

因為我們沒有處理運算符優先順序的問題,所以 1 * 2 + 3 * 4 的結果會是 20,如果要正確處理就需要實作 precedence climbing 之類的方法,不過這個留待下篇文章再來解決這個問題,至少我們已經能 parse 一個 simple program,自動轉成 Rust 的 simple AST 了(其實原作者的 treetop parser 也沒有考慮這個問題,所以其實我們可以裝傻當作沒這回事XD)。

以上大概就是 pest 的介紹,基本上使用 pest,一個規則用一個單獨的函式來處理,就能把每次修改的範圍縮到最小,熟練的話應該能在短時間內魯出一個基本的 parser 來用。

2018年5月1日 星期二

剖析表達文法 PEG 簡介

剖析表達文法 PEG 為 Parsing Expression Grammar 的縮寫,2004 年由 Bryan Ford 教授所提出,相對於一般在編譯器課上教 parsing 所用的 CFG (Context Free Grammar) ,已經被鑽研數十年之久,可說是相當年輕的形式化語言。

其實 PEG 和 CFG 在本體上幾乎沒有不同,從創作概念上來看,CFG 著重的是語法的產生和定義,PEG 則專注在剖析語法上,找資料時就有在中國的知乎論壇上看到這句:「CFG 作為產生式文法,很適合用來生成內容丰富多彩的垃圾郵件」不禁會心一笑,過去定義程式語言,都是先教 CFG,通常都會有這麼一句:「寫出 CFG 就定義了一個程式語言」
生成文法的切入點在<產生>,我們定義產生文法來定義語言,討論各種文法的強度,看看它們能產生什麼,不能產生什麼;用這套文法產生出來的東西,管它到底多亂多醜多長,都符合這個文法(有點回文),從 CFG 的觀點來看,先想好怎麼產生程式語言,接下來再來看怎麼剖析它,然後再討論 LL, LR 等等剖析方法。

PEG 則沒有這麼繞圈圈,PEG 本身即是 parser 的抽象定義,PEG 定義的 parser 會由一條一條規則組成,每條規則會去匹配輸入,如果成功則消耗輸入,失敗則不會消耗輸入。
PEG 的 terminal 規則如下,大致和 CFG 相同:
* 字串即匹配字面上的字串
* eps (ε) 匹配空集合,永遠成功且不消耗輸入
* . 匹配任意字元
* [abc] [a-z] 表示符合集合中任一字元

Non-terminal 的規則是跟 CFG 較多不同之處:
* PEG 同樣提供來自 regexp 的 ? + * 三個結合符號,也就是零或一個、一個或多個、零至多個,全部都是 greedy。
* e1 e2:依序剖析 e1,在剩餘的字串上剖析 e2,如果 e1, e2 任一剖析失敗則整個規則都失敗(記得如果規則失敗則不會消耗 input)。
* e1 / e2:嘗試 e1,失敗的話就換 e2,這是 PEG 跟 CFG 最大的不同之處,CFG 的接續規則是沒有先後次序的,雖然 CFG 的剖析器,通常為了方便會加入一些先後次序來處理歧義性的問題,例如對 dangling else 採用 shift over reduce ,把多的 else 先拉進來,但在 PEG 中這樣的歧義性可以很簡單的用 / 來消除。
S <- “if” C “then” S “else” S / “if” C “then” S
* 另外有兩個 And predicate &e 跟 Not predicate !e:可以向前看之後的內容是否匹配/不匹配 e,但無論成功或失敗,predicate 都不消耗輸入;理論上的 PEG predicate 可以擁有無限的 predicate 能力,但在實作上應該都有一定的限制。

下面可以舉一些跟 non-terminal 有關的例子:
a* a:永遠會失敗,e1 會吃光所有的 a,造成 e2 失敗。
!”_” .:匹配除底線外任意字元。
“>” / “>=”:是個錯誤的寫法,要不是失敗就是 e1 成功消耗 > 字元,第二個 >= 只是裝飾用的,在運算符的匹配上,應該要依序從長到短排序:>> / << / >= / <= / > / </ =。
另外我查 PEG 時也有遇到一些詭異的文法剖析結果,例如參考資料舉出的:
S -> A $
A -> "a" A "a" / "a"
PEG 會很見鬼的匹配 2^n-1 個 a,以 5 個 a 的狀況,後三個 a 會剖析為 A = aAa,但下一步合併失敗,導致第二個 a 被剖析為 A = a,最後只剖析了前三個字元:失敗。

PEG 的好處在於簡單漂亮,每個 PEG 都是無岐義的,實作上一條規則正好對應一條處理函式,類似 parser combinator,由上而下一跟呼叫:parseExpr -> parseTerm -> parseFactor -> identifier / number 這樣的剖析順序,可以把剖析器寫得漂亮好改;也因此一些語言都有開始支援 PEG parser generator:例如 rust 的 rust-peg, pest,haskell 的 peggy,Dlang 的 pegged 等等。
PEG 並不是單純 CFG 的超集或子集,事實上兩者的概念不太一樣,我建議不要把兩者混為一談,例如知名的 a{n} b{n} c{n} 這個 CSG(n個a 接 n個b 接 n個c,這用 CFG 是產生不出來的),卻可以用 PEG 來剖析;目前是否 CFG 產生出來的文法都能用 PEG 來剖析還是一個開放問題,就留給有興趣的人去挑戰了。

會寫這篇文章,因為最近正在試著用 rust pest 寫一個簡單的剖析器,發現有關 PEG 的中文討論相當的少,就先整理一篇,其實目前要查中文,用「解析表達文法」查到的比較多,但台灣的 parse 就是剖析,所以我標題還是下「剖析表達文法」; pest 的部分因為文件有點少還在卡關當中,下一篇應該會整理相關的用法,然後用它寫個超簡單剖析器。

參考資料:
https://github.com/PhilippeSigaud/Pegged/wiki
本文基礎,大部分的例子都是裡面來的 :P
http://qnighy.hatenablog.com/entry/2015/11/12/162424
神文大推(日文就是…),用了 haskell monad 實作了 CFG, PEG parser,兩者的差距只在 Maybe 跟 list 的差別,現在還在研究當中。
https://www.zhihu.com/question/28525605
一些 CFG 跟 PEG 的比較,算簡單易懂,可以看過去

附註:
S -> A $
A -> "a" A "a" / "a"
這個問題,後來我有想通了,先假設 k 個 a 的時候是可以匹配的;在輸入 n 個 a 的時候,每一個 a 都會率先匹配為 aAa 的前一個,最後 k 個 a 則會匹配為 A,但後面已經沒有 a 了,因此倒數 k+1 個 a 開始的 A = aAa 匹配失敗,匹配為 A = a,接著如果要匹配成功,就要前後都有 k 個 a 才行。
得到結論:k 個 a 匹配則下一個為 2 * k + 1。