最後的成果在這個repo裡: https://github.com/brucehsu/peg/tree/leg

來龍去脈

決定要用Go寫Ruby VM之後,第一件事情當然就是尋找Go上的parser generator。
Go裡頭就包含了 自己的yacc工具 ,與原先的yacc語法完全相容,加上Ruby(MRI、mruby)都是使用yacc來作為生成parse的方式(詳見各repo底下的parse.y),所以一開始很直覺地就把goyacc列為solution。
但是goyacc在使用上有個要注意的地方,就是 c9s前輩所提到的 :它跟原先的yacc一樣,還需要跟lexer作搭配,但golex這個project卻已經無人維護許久。

之後在 唐鳳前輩的指點下 ,決定採用tinyrb中以LEG/PEG定義出的Ruby subset作為發展的基石,況且在 RubyGoLighty 這個以tinyrb為底並Go實作的project當中,除了提供一個stack-based的Ruby VM外,還手動將LEG/PEG轉換成了Go code,看來可以省下不少麻煩。

但等等…… 因為其年代久遠(四年多前),裡面的Go code看來一點都不像Go,而只是如C的直接貼上(不過我沒有build過或是認真看過,或許可以正常使用也說不準),要修改也有些難度,難不成只能重新再造輪子了?

經過一番搜尋,發現其實之前就已經 有人重新用Go實作了PEG 並加入一些Go限定的功能,而且到去年9月時仍有commit,只是事情有一好沒兩好,這位作者只有實作PEG的部份,不含LEG。

剛好我也打算再跟Go混熟一點,幫這個project加入LEG的支援看來似乎是個不錯的練習,只是我沒想到會拖那麼久…… orz

PEG

說了這麼多,還沒有介紹PEG和LEG到底是什麼。

PEG是Parsing Expression Grammar的縮寫,是由 MIT的Bryan Ford 所提出用來定義語法的context-free grammar。作者網頁上也列了根據他的研究所寫出的不同語言的實作版本,最為人所知的當然還是 C語言版 ,也就是pegleg這兩個工具的來源。

基本上的使用,如果之前有lex/yacc或Regular expression的經驗應該可以快速上手,下面稍微列一下定義:

  • name <- pattern,不同於yacc,是以<-作為assign operator
  • seq1 / seq2 / seq3,不同於yacc,是以/作為OR
  • . match任一字元
  • [characters] 括號內的任一字元, [^0-9] 開頭的^是除了特定字元外的意思
  • ( pattern ) 將括號內的pattern歸為一組
  • < > 會將兩者內的字元累積起來,放至yytext變數中供人使用
  • ? 有或無, + 至少一個或以上, * 無或一個或以上

以上是基本的語法元素,PEG也定義了如果對這些元素作條件判斷:

  • Predicate 為有著成功或失敗狀態的構詞單位,失敗時不會消耗掉input, & element以match為成功, ! element則以不能match為成功(著名的例子是!.作為EOF)。 & { action } 是特殊的predicate,如果action回傳為true,則繼續執行剩餘的element,為false則尋找是否有替代的rule。在C和Go版本的實作中,以上三種類型分別被稱為PeekFor, PeekNot, Predicate

LEG

因為yacc的悠久歷史,導致許多的project都是使用yacc所定義的語法,如果要想轉換到PEG上還會因為功能上的差異而花一番功夫,於是C版本便提供了與yacc相容性較高的leg作為解決方案。

LEG在定義上與PEG的不同之處在於:

  • name = pattern,改用了=來作為assign operator
  • seq1 | seq2,與yacc相同用|來作OR
  • rule name可以使用 -,像是rule-name,會被轉換為rule_name,也可以單獨使用-
  • ; 可以被用來結束一個pattern (optional)
  • %{ text... %} 會將text部份全部copy到生成的go source code的開頭
  • `%% 會結束rule宣告的section,接下來所有的text會被複製到go source code的結尾
  • exp ~ {action},只有在前面失敗的時候才會呼叫 action
  • $$ = value,大概是最大也最重要的不同,LEG可以指定該rule回傳的semantic value,value type都一樣,預設是int,在C版本中是用YYSTYPE來指定
  • identifier:name,承上,因為可以指定semantic value,所以提供了自定變數名稱的方式來代表回傳的semantic value

目前我大概只剩比較次要的功能沒作(;~ {action}),其它的都已經完成。

PEG in Go的設計分析

首先,先來看看Go版本的PEG包含了哪些東西。
基本上主要使用的source code file都在根目錄底下了

  • set.go: 恰如其名是集合資料結構的實作,主要用於以switch來最佳化生成的code,因為我沒有碰到最佳化的這一塊,所以無從奉告XD
  • bootstrap.peg.go: 由PEG本身generate出來的PEG parser,待會再細談。
  • peg.go: 整個PEG的核心,定義了AST的資料結構和相關的function,將AST compile成Go code也是在這裡完成的。
  • peg.peg: 用PEG來定義PEG, 詳見C版本的man page ,值得注意的是Go版本針對部份rule作了些修改。

如果單純看bootstrap.peg.go的程式碼可能會有點摸不著頭緒,好險原作者也把當初怎麼生成bootstrap.peg.go的方式留在bootstrap/裡頭,所以我們可以透過bootstrap/main.go的內容來一窺AST的生長方式。

peg.go

AST

就如同許多compiler一樣,PEG也是先建出AST之後再將其compile成source code,樹根為Tree資料結構,除了有些額外的性質外,基本上是前面定義過的node linked list,而它的nodes一開始都會是一條條的rule(TypeRule),直至要compile前進行處理時才會有所更動。

每個TypeRule的node底下,也只會有一個屬於三種list type(TypeSequenceTypeAlternateTypeRange)的node,完整的定義則是在這個list node裡頭。

TypeSequence就是很簡單的list,一個接著另一個。
TypeAlternate是在如果rule有所分歧的時候,即是seq1 / seq2 / seq3的情況。以前面為例子,這樣的一個TypeAlternate node底下分別會有三個TypeSequence node。
TypeRange只會有兩個child node,負責a-z的情況。

除了list types外,還有另外一類的fix types,用來代表+ * ? <> ! &的情況。當你加入一個fix types的node時,它會把前一個node加為自己的child,並取代它原本所在的位置,簡而言之就是直接長在前一個node的頭上。

Complication

在compile AST之前,PEG會先作過數種處理:

  • anoymous function link(n Node)及其後的first/second pass
    基本上是幫忙建立t.Rules的清單,比較不一樣的是會再建新的rule來包裝TypeAction

  • join([]func() {...})
    內含兩個anoymous function,一個是算各條rule被用到的數目,另外一個則是檢查是否有left recursion

  • t._switch
    最佳化,此處不談,因為我也沒看 :p

  • print 系列anoymous function
    這些function是為了生成最後的source code所用的,有printSave, printRestore, printTemplate, printRule, printBegin, printEnd, printLabel, printJump, printRule,後面會再說明。

Complication的部份,是先利用Go提供的text/templateTree裡的特定變數塞至檔案開頭所定義的template PEG_HEADER_TEMPLATE中再印出成為bootstrap.peg.go的開頭,剩下的部份則由compile(n Node, ko uint)負責。
這部份我就直接留到bootstrap.peg.go時再一一說明,個人覺得有例子對照比較好了解最後會生出什麼樣的東西。

bootstrap.peg.go

這裡要談的只有兩個functions:Init()Execute(),這可以算是PEG裡面最重要、最核心的兩個functions了。

Init()顧名思義,就是PEG parsing的初始化,或許有人會納悶怎麼沒有yyparse()可用,其實是因為在Init()中就定義了一個可以被呼叫的Parse(rule ...int) error function了。
peg.go 中,最後的complication主要就是輸出到Init()的尾端,作為rules這個array的內容。
這個array包含什麼呢?其實就是一連串回傳bool的anoymous functions,每個function都代表著一個grammar rule,如果match成功的話就會回傳true,反之則false。
每個function都身兼lexical及syntax parsing,假設有條rule是這樣的:Rule <- 'Hello,' ID,那個該function內就會先用一一去比對目前的input開頭是不是Hello,,如果不是就會利用goto跳到return false的地方。當遇到需要比對另外一條rule ID時,就只要呼叫rules[ID]所對應到的function即可。
當一條rule比對成功後,就會將目前的位置連同Rule名稱加入到TokenTree裡頭,以便之後Execute()可以依序執行結果。

綜合來說,你看到的code大概會是下面這樣樣子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
{
position118, tokenIndex118, depth118 := position, tokenIndex, depth // 儲存目前的位置、token數量和深度
if buffer[position] != rune('H') {
goto l122 // when failed
}
if buffer[position] != rune('e') {
goto l122 // when failed
}
...
if buffer[position] != rune(',') {
goto l122 // when failed
}
// 呼叫其它rule作matching
if !rules[RuleID]() {
goto l122 // when failed
}
add(Rule, position118)
}
return true
l122:
position, tokenIndex, depth = position118, tokenIndex118, depth118
return false

還記得前面提到的Parse()嗎?其實它所作的就只是呼叫第一條rule所對應到的function讓程式生成TokenTree而已。

接著我們來看Execute()的內容,會發現裡面其實並不是所有的rules都會被執行,只有RulePegTextRuleAction系列,前者是TypePushTypeImplicitPush所產生的,用來指定截取文字的範圍(補充說明:TypeImplicitPush其實在編譯時會被加入在TypeRule當中,所以你才可以用buffer[begin:end]來取得rule的文字內容),後者則是使用者自行定義的行動。

LEG in Go的實作筆記

一開始我是從最基本的declarationtrailer作起(分別是加code到檔頭和檔尾),實作的方式很簡單,就是直接幫Tree加上新的string member,然後讓text/template來處理剩下來的問題。讓Rule名稱可以使用-也蠻基本的,只是在作self-illustrated的LEG時會需要注意一下,不然就會當成TypeRange去了。(我還為了這事搞了很久,因為bootstrap.peg.go雖然沒問題,但是編出來的leg指令再去編leg.leg出來的結果會噴錯 :/)

接下來才是最惱人的部份:如何加入semantic value?

敝人資質鶩鈍,故想了幾天、參考了C語言的版本許久才終於想到一個方法:

首先加入一個新的type TypeVariable,讓它成為TypeName的child(畢竟Varaible name是和呼叫rule的TypeName綁在一起)

在建立完AST之後,先作過一次AST的DFS traversal,並計算到某TypeAction node時該rule已定義的varaibles,再藉其數目來得到各semantic values於stack中的位置。由於Go沒有像C macro的功能,所以不能如C版本的leg一樣用#define var_name stack[pos]這種簡單方式來作變數取代,所以我是先用regular expression取出變數名稱後,再一一取代回原字串。

只是這樣只能處理有著固定數目的變數,如果一條rule內有像TypeAlternate的分歧,靜態分析就會錯誤百出,所以實際上還是得在建TokenTree的時候,動態去操作stack才行。於是我便加入了RuleActionPushRuleActionPop這兩個負責stack operation的類別,然後於compile時期,幫有用到variable的rule加入variableCount來統計目前執行階段有多少個variable,並於最後將所有的varialbe都pop出來;如果中間遇到TypeAlternate分歧,會另外再建一個新的variableCount{NUM}來儲存進入前的variable數目,並於離開時pop掉多出來的variable,然後把variableCount設回進入時的數值。若是rule本身有用到semantic value(如何判斷?直接看底下的actions有沒有用到$$就好了XD),最後也會將目前的semantic value給push進stack裡。

關於上面的作法,各位可以參考這幾個commits:

  1. https://github.com/brucehsu/peg/commit/9718cf5b91da4b85f483bdd29a98b202ce2768e3
  2. https://github.com/brucehsu/peg/commit/047d5e6502f6f98c5e59fa08797ce4041521e3bb