PEG.js

pegjs

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

總之,最近想著要做出類似一些搜尋引擎支援的條件語法,像是 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目錄內,還在補測試就是。

comments powered by Disqus