PEG.js : O3noBLOG

04月 09日

PEG.js

知道這東西也好一陣子了，最近才真的第一次用，感覺還不錯，很久沒有因為東西會動而這麼高興了，大概也是太久沒努力離開舒適圈的關係吧。

總之，最近想著要做出類似一些搜尋引擎支援的條件語法，像是 and、or、not 之類的，稍微花了點時間調查一下確定要正確的處理就是要個 parser，沒錯，就是 compiler 最前面那個 parser，身為非 CS 領域出身的人，compiler 我一直是朦懂朦懂的，parser 到產生 AST 那塊算是比較清楚一些，因為像是 Babel、還有以前幫忙過的 TernJS 都是先 parse 程式碼產生 AST 才開始做事，不過這次和以前不一樣的是我要從頭開始建立一個語法的 parser，然後因為是網頁前端要用的，所以就找到了 PEG.js 這個用 JavaScript 寫的 parser generator，相較於手工的 parser，這種工具只要有定義好的語法（grammer）給它，它就可以產生出對應的 parser，至於什麼是語法（grammer）呢，例如下面這段就是：

IdentifierName ::
    IdentifierStart
    IdentifierName IdentifierPart

IdentifierStart ::
    UnicodeIDStart
    $
    _
    \ UnicodeEscapeSequence

IdentifierPart ::
    UnicodeIDContinue
    $
    _
    \ UnicodeEscapeSequence
    <ZWNJ>
    <ZWJ>

UnicodeIDStart ::
    any Unicode code point with the Unicode property &ldquo;ID_Start&rdquo;

UnicodeIDContinue ::
    any Unicode code point with the Unicode property &ldquo;ID_Continue&rdquo;

這段是從 ECMAScript Spec 內找出來的，identifier 名稱格式的語法（grammer）定義，其實還算蠻好理解的，而 PEG.js 也有自己定的語法格式，只要使用該格式定義好語法，就可以產生出 parser 來，不過當我開始寫的時候，才發現到一個問題：我不知道 parse 後要產生什麼東西，這時我才意識到，在開始定義語法之前，我應該要先想清楚後續的產出物（例如 AST）的結構，和要如何使用這個 parser 的產出物實做出真正想要的效果。

以我的目標來說，我希望可以做出簡單的邏輯組合，包括 and、or、not 和 parenthesized expression（括號包起來的），其實我一開始的想法也沒很明確，只是覺得應該可以用樹狀結構加上遞迴來實做後面的判斷，然後參考了 Kibana 裡面 Kuery 的語法，也算是慢慢的把語法和 AST 的組合方式定義出來，當時做的語法我還有放在 gist 上，語法和 AST 定義好的時候，其實後面應用端的 script 還沒寫，不過因為結構很簡單，所以我已經確信一定可以運作了，後來隔一天果然不花什麼時間就把應用端的 script 也寫好，之後還花時間作了些手工測試，修正了一些語法上的細節問題，像是支援&、|這些符號之類的，還有符號兩邊不用空格等等。

還有一點想特別說的是，其實一開始定義語法的時候，我是沒有想要去參考 Kibana 的，雖然我當時就知道 Kibana 的 Kuery 語法和我的需求很像，而且也是用 PEG.js 做的，不過我開始寫語法定義沒多久就卡關了，卡關的地方就是，一開始就是 and、or、not、parenthesized expression 都有可能出現，但是這無法用/的方式來處理，因為 PEG.js 的 parser 不會解析到一半發現不對就游標往回退（backtracking），然後我就卡關了，我可以寫出 and 加上判斷，支援以下兩種查詢：

keyword
keyword1 and keyword2

但是卻無法更進一步加上支援or，結果只好去參考 Kuery 語法，發現奇妙的寫法，以下是我後來成品的定義：

start
  = orQuery?

orQuery
  = left:andQuery Or right:orQuery
  / andQuery

andQuery
  = left:notQuery And right:andQuery
  / notQuery

notQuery
  = Not right:subQuery
  / subQuery

subQuery
  = '(' ws* query:orQuery ws* ')'
  / queryValue

如此，or查詢支援兩種內容，第一種是and查詢語句，第二種才是真的or查詢，但是他的第一個元素是and查詢，也就是說雖然是or查詢的判斷，但是卻先去看有沒有and查詢，然後and查詢也是類似的定義，實際上先去找有沒有not的語句，然後not會去看有沒有子查詢（parenthesized expression），整個讓人覺得很神奇，仔細下去推敲也確實可以理解判斷的過程，不過在邏輯上我還不太能完全通透的理解。第一次看到這種定義方式時，覺得很神妙，不過也有想說這應該是什麼常見的 grammer 寫法，後來去查了一下 ECMAScript Spec，發現也是這樣的作法，看來真的算是個 convention 了吧（看起來是 left recursive），真不知道第一個寫出這種 grammer 的人腦袋裝什麼。

最後我的成果有丟一個可以讓人用的版本上 GitHub，也有用 NPM 發佈，叫 simple-search-query，詳細用法可以參考 README，至於完整的語法定義就在query目錄內，還在補測試就是。

單篇彙整