Ruby Parsing (part-1)

Ruby 第二次解析程式碼的過程稱為 Parse,目的是把 Tokens 轉換成 Ruby 可以理解的形式,而執行這件事情的東西就叫 Parser。不過這個 Parser 不是直接寫在 Ruby source code 裡面,而是透過 Parser generator 產生出來的。Parser Generator是一種接受一組文法規則,然後產出對應的 Parser 程式。

一般常見的 Parser Generator 叫做 Yacc(Yet Another Compiler Compiler),不過 Ruby 用的是更新版的 Yacc ,叫做 BisonBisonYacc 都用 .y 作為副檔名的檔案定義文法規則,在 Ruby 中這隻檔案叫做 parse.y

Bison 會在 Ruby 初始化的過程中就執行,其產生出的 Parser 為 parse.c,之後 Ruby 在執行時就會用它來解析前面產生的 Token。而且由於 parse.y 以及產生出來的 parse.c 同時也包含了進行 Tokenization 的規則及程式,所以在 Tokenize 的時候也會用到 Parser(實際上 Tokenization 跟 Parsing 是同時進行的,在進行 Parsing 的過程中 Parser 隨時會往回進行 Tokenize)

LALR Parse Algorithm

LALR 的全名叫做 Look-Ahead Left Reversed Rightmost Derivation,這個演算法會從左到右掃描 Token,並確認他們是否有符合我們定義的文法規則,接下來便會用一個例子來說明他的運作方式

假設我們現在有一句西班牙文:

Me gusta el Ruby

意思是

I like Ruby

然後我們想用 Parser 把他從西班牙文轉成英文,我們可以在給 Bison 的文法規則這樣寫

SpanishPhrase : me gusta el Ruby {  
  printf("I like Ruby\n");
};

這樣產生出來的 Parser 如果遇到按照順序帶有 me gusta el Ruby 的 tokens,他就會執行大括弧裡面的指令(在這邊是印出 I like Ruby)。而這個 Parser 執行的結果就會是我們希望的 I like Ruby

接著我們來看複雜一點的例子,現在有兩個句子:

Me gusta le Ruby

Le gusta le Ruby

然後我們的文法規則變成:

SpanishPhrase: VerbAndObject el Ruby {  
  printf("%s Ruby\n", $1);
};
VerbAndObject: SheLikes | ILike {  
  $$ = $1;
};
SheLikes: le gusta {  
  $$ = "She likes";
};
ILike: me gusta {  
  $$ = "I like";
};

現在我們有四個文法規則,而且我們可以看到其中宣告了 $$$1 兩個變數,$$ 代表的是子規則要傳遞給母規則的值, $1 則是由子規則回傳的值。

接下來便是 LALR 發揮功用的時候了,首先解釋 LR 的部分:

  • L (left) 代表 parser 是 由左至右按順序 處理字串
  • R (reversed rightmost derivation) 指的是由下至上、利用 shift/reduce 的方式來找到符合的文法規則

這邊用實際例子來說明。首先我們有四個 Token:

Tokens: [le] [gusta] [el] [ruby]  

接下來,他會 shift 這些 tokens,製造出一個 grammar rule stack

Tokens: [gusta] [el] [ruby]

Grammar Rule Stack: le  

Grammer Rule Stack 是 Parser 用來記錄他解析進度的地方,實際上他會把目前解析過的文法規則的編號(或稱 state)加進 stack 中,讓他知道現在解析到哪條規則了

然後他會再往左邊 shift 這些 tokens:

Tokens: [el] [ruby]

Grammar Rule Stack: le gusta  

現在 stack 裡面有兩個 token 了,這時 parser 會開始尋找是否有對應的文法規則,之後找到 SheLikes 這條規則,並用它替換 le gusta

Tokens: [el] [ruby]

Grammar Rule Stack: SheLikes  

這個動作被稱為 reduce,因為 parser 用一條規則替換了兩個 token。Parser 會掃遍所有規則跟執行 reduce,直到沒有任何匹配的規則為止。

不過在我們的例子中他還會再執行一次 reduce,因為 SheLikes 符合了 VerbAndObject 的規則,所以現在會變成

Tokens: [el] [ruby]

Grammar Rule Stack: VerbAndObject  

但現在有個問題,parser 要怎麼知道這邊是要執行 reduce,而不是繼續 shift tokens?而且如果一組 token 符合多條規則,要怎麼決定用拿條進行 reduce?比如說如果現在有許多條規則與 le gusta 匹配,parser 要怎麼進行判斷?

這時候就會用到 LALR 中的 Look Ahead 了,為了找到正確的規則,parser 會先檢視下一個 token,也就是 el。除此之外,parser 內部會有一張 state table,裡面會記錄目前已經 parse 的規則以及視下一個 token 而定,所有可能的 state(LALR 其實就是一個非常複雜的 state machine,當你產生 parser 時,Bison 會依據你的文法規則計算出其 state table 裡面所需包含的東西)。以這個例子來說,state table 會有一個欄位標明,如果下一個 token 為 el 則 parser 應該在 shift 下一個 token 前先用 SheLikes 進行 reduce

接下來 parser 會繼續 shift 下一個 token:

Tokens: [ruby]

Grammar Rule Stack: VerbAndObject el  

這次沒有匹配的規則,所以繼續 shift 最後一個 token

Tokens:

Grammar Rule Stack: VerbAndObject el ruby  

最後 parser 就可以進行最後一次的 reduce

Grammar Rule Stack: SpanishPhrase  

然後執行對應的 function:

  # 這邊的 $1 會是 "le gusta"
  printf("%s Ruby\n", $1);

在實際運作上,Ruby 解析我們程式的方式跟這個範例一模一樣,差別只在於規模大小而已。在 parse.y 裡面,我們可以看到上百條定義 Ruby 語法跟結構的規則,裡面有許許多多的子規則跟母規則,都是利用前面提到的 $$ $1 $2 等變數來往上一層傳遞值,而高複雜度也代表了最後產生出來的 parse.c 內的 state table 會很龐大。

為了能更明確地知道 Ruby 的 state table 有多複雜,我們可以在執行 Ruby 程式的時候加上 -y 參數,他會顯示出每次 parser 的 state 改變時的所有內部資訊,看起來會像:

...
-> $$ = nterm opt_nl ()
Stack now 0 2 69 309 76 230 219 421 569 716 231 430  
Entering state 427  
Next token is token ')' ()  
Shifting token ')' ()  
Entering state 623  
Reducing stack by rule 622 (line 5143):  
   $1 = nterm opt_nl ()
   $2 = token ')' ()
-> $$ = nterm rparen ()
Stack now 0 2 69 309 76 230 219 421 569 716 231 430  
Entering state 624  
Reducing stack by rule 249 (line 2421):  
   $1 = token '(' ()
   $2 = nterm opt_call_args ()
   $3 = nterm rparen ()
-> $$ = nterm paren_args ()
...

到這邊為止就是 Parsing 過程的前半部,也就是 Parser 如何處理 token,下一篇文章會繼續介紹一些實際上常見的文法規則,以及 Parser 是如何建構 AST (Abstract Syntax Tree)

Author

Stan Luo

I'm Stan, a junior web developer. I love writing ruby program and rails application.And I'm also looking forward making some contribution the ruby community.

comments powered by Disqus