LEG/PEG in Go實作

最後的成果在這個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語言版 ，也就是peg與leg這兩個工具的來源。

基本上的使用，如果之前有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（TypeSequence、TypeAlternate、TypeRange）的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/template將Tree裡的特定變數塞至檔案開頭所定義的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大概會是下面這樣樣子：

{
  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都會被執行，只有RulePegText及RuleAction系列，前者是TypePush和TypeImplicitPush所產生的，用來指定截取文字的範圍（補充說明：TypeImplicitPush其實在編譯時會被加入在TypeRule當中，所以你才可以用buffer[begin:end]來取得rule的文字內容），後者則是使用者自行定義的行動。

LEG in Go的實作筆記

一開始我是從最基本的declaration和trailer作起（分別是加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才行。於是我便加入了RuleActionPush及RuleActionPop這兩個負責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