2017年1月13日 星期五

compiler [2.3] - 產生 if/else, while 的 AST

旦旦而學之,久而不怠焉,迄乎成。
這篇來得很晚, 在《compiler [1] - 四則運算》之後本來要發表這篇的, 不過程式碼總是比文件更新快, 再加上一些怠惰的因素在, 只寫了一小段, 最近才補完, 所以就變成現在才發表了。完成程式之後沒馬上把心得寫下來就會像這樣一直拖, 可是要把心得記錄下來又是一件累人的事情, 有怠惰之心是人之常情。

看過四則運算的 ast 之後, 應該很想知道其他結構化單元的 ast 會長什麼樣? 畢竟很多寫 AST 的文章, 幾乎只會把四則運算的 AST 秀出來, 其他結構單元的 AST 一樣很重要, 本篇文章要談的是 if/else statement AST, 再來還會有 function delcare/definition, funcion call AST, 這些都很重要, 一個都不能遺漏, 要不然在編譯器的學習上就少了一塊拼圖, 努力這麼久竟沒全功, 豈不可惜。

我做了一點修改, 把《两周自制脚本语言》的 EBNF 改成 c 的語法, 不過和 c 有點不同 if statement 的 {, } 一定要有。畢竟目標是以 c 為主, 若不能寫出自己喜歡的語言編譯器, 實在沒什麼動力。有些書用 pascal 為例子, 我一點都不想寫 pascal, 怎麼會有興趣去實作它的編譯器呢?

基本上 ebnf 寫的出來, 程式就寫的出來, 再經過幾次的實作後, 我慢慢掌握到訣竅了。就是 if 判斷式的字串比對程式碼, 還真的不難。

  • pop_token(): 會把目前的 token stream pop 出來
  • peek_token(): 不會把目前的 token stream pop 出來

概念很簡單, 是很重要, 一定要準備這樣的 2 個 function, parser 才會比較好寫。

比對一下 ebnf 和程式碼, 先不要管 expr(), block() 之類的, 會有一點具體的感覺。

ASTNode 的產生可能有點難度, 樹這樣的資料結構比較難理解與使用, 常常會跑錯 node, 而且沒有好的輸出來看這棵樹有沒有建對, 這是為什麼我想盡辦法要輸出整棵樹的原因。但弄懂之後就像打通任督二脈, 功力再上一層樓。

c_parser.cpp
 242 // block     : "{" [ statement ] { (";" | EOL) [ statement ] } "}"
 243 // modify - block     : "{" [ statement ] { ";" [ statement ] } "}"
 244 // modify 2 - block     : "{" { statement } "}"
 245 ASTNode* block()
 246 {
 247   Token token = peek_token(); 
 248 
 249   ASTNode *b = new ASTNode();
 250 
 251   if (token.str_ == "{")
 252   {
 253     pop_token();
 254   
 255     while(is_token("}") == false)
 256     {
 257       need = false;
 258       ASTNode *s = statement();
 259       need = true;
 260       if (s)
 261         b->add_child(s);
 262     }
 263 
 264 
 
 291     Token t = peek_token();
 292     if (t.str() == "}")
 293     {
 294       Token t = pop_token();
 295     }
 296     else
 297     {
 298       err("block: should '}'", t.str_);
 299     }
 300 
 301 
 302   }
 303   else
 304   {
 305     err("block: should '{'", token.str_);
 306   }
 307   return b;
 308 }

 455 /*
 456  * statement :   "if" expr block [ "else" block ] 
 457  *               | "while" expr block
 458  *               | simple
 459  */
 460 
 461 /*
 462  * modify - statement :   "if" "(" expr ")" block [ "else" block ] 
 463  *                        | "while" "(" expr ")" block
 464  *                        | "return" [expr]
 465  *                        | simple ";"
 466  */
 467 ASTNode* statement()
 468 {
 469   ASTNode *s_node = 0; // statement node
 470   Token token = peek_token(); 
 471 
 472   if (token.str_ == "if")
 473   {
 474     Token t = pop_token();
 475     t.ast_type_ = IF;
 476     s_node = new ASTNode(t);
 477 
 478     ASTNode *e = 0;
 479     t = peek_token(); 
 480     if (t.str_ == "(")
 481     {
 482       pop_token();
 483       e = expr();
 484     }
 485     else
 486     {
 487       err("statement: should '('", t.str_);
 488     }
 489     t = peek_token(); 
 490     if (t.str_ == ")")
 491     {
 492       pop_token();
 493     }
 494     else
 495     {
 496       err("statement: should ')'", t.str_);
 497     }
 498 
 499     ASTNode *then_b = block();
 500     then_b->set_token(then_block);
 501 
 502     s_node->add_child(e, then_b);
 503     //s_node->add_child(then_b->children());
 504 
 505     Token token = peek_token(); 
 506     if (token.str_ == "else")
 507     {
 508       Token t = pop_token();
 509       ASTNode *else_b = block();
 510       else_b->set_token(else_block);
 511       s_node->add_child(else_b);
 512     }
 519 
 520   }
 521   else if (token.str_ == "while")
 522        {
 523          Token t = pop_token();
 524          t.ast_type_ = WHILE;
 525          s_node = new ASTNode(t);
 526          ASTNode *e = 0;
 527          t = peek_token(); 
 528          if (t.str_ == "(")
 529          {
 530            pop_token();
 531            e = expr();
 532          }
 533          else
 534          {
 535            err("statement: should '('", t.str_);
 536          }
 537 
 538          t = peek_token(); 
 539          if (t.str_ == ")")
 540          {
 541            pop_token();
 542          }
 543          else
 544          {
 545            err("statement: should ')'", t.str_);
 546          }
 547 
 548          ASTNode *b = block();
 549          b->set_token(while_token);
 550          s_node->add_child(e, b);
 551        }
 552        else if (token.str_ == "return")
 553             {
 554               pop_token();
 555               cout << "xx return" << endl;
 556               s_node = new ASTNode(return_token);
 557               Token t = peek_token();
 558               if (t.str() == ";")
 559               { 
 560                 pop_token();
 561               }
 562               else
 563               { // expression
 564                 cout << "expr return" << endl;
 565                 ASTNode *e = 0;
 566                 e = expr();
 567                 if (e)
 568                   s_node->add_child(e);
 569 
 570                 if (is_token(";"))
 571                 {
 572                   pop_token();
 573                 }
 574                 else
 575                 {
 576                   Token t = peek_token();
 577                   err("statement|simple: should be ;", t.str());
 578                 }
 579               }
 580             }
 581             else // simple
 582             {
 583               s_node = simple();
 584               if (is_token(";"))
 585               {
 586                 pop_token();
 587               }
 588               else
 589               {
 590                 Token t = peek_token();
 591                 err("statement|simple: should be ;", t.str());
 592               }
 593             }
 594 
 595   return s_node;
 596 }

c_parser.cpp L472 ~ L520 就是在處理 if/else statement, 並產生 AST 中的 if/else node, 對照著 L462 的 ebnf 看, 簡單的不得了吧, 誰說 parser 很難的? 只要寫得出 ebnf, 幾乎就寫得出程式碼。不過自己改寫 enbf 要注意左遞迴的問題, 這也不是太難, 反正遇到左遞迴的話, 就會發現程式一直在 recursive 沒有結束的一天, 遇到就知道怎麼改了, 我沒遇到所以無法提供個例子, 請自己參閱相關書籍。

if 這部份就是要產生 if node, 特別的部份是 if 區塊和 if 條件式, if 條件式是 expression, 想成「四則運算」就好, 「四則運算」的 AST 很久之前就完成了, 沒問題, if 區塊剩下的 if statement 也可以想成 expression -> 又可以想成「四則運算」, 等於只要處理 if node 而已, 實在輕鬆, 真實世界當然不是這麼簡單, 不過這樣想的話, 似乎就沒那麼難了。

現在你知道為什麼要先處理「四則運算」了吧, 處處都是「四則運算」。

list 1. if/else AST
 1 int main()
 2 {
 3   int i,j;
 4 
 5   i=5;
 6   j= i + 2;
 7   if (i>1)
 8   {
 9     printf("i>1\n");
10   }
11   else
12   {
13     printf("i<=1\n");
14   }
15 
16   return 0;
17 }
18 
19                                                     root
20                                                      |
21                                                     prog
22                                               _______|________
23                                               |              |
24                                    main |int |func |global  main
25                                               |
26                                           func_body
27       ________________________________________|________________________________________
28       |                   |                   |                   |                   |
29      var                  =                   =                   if                return
30   ____|____              _|__                _|__     ____________|____________       |
31   |       |              |  |                |  |     |           |           |       0
32 i |int  j |int           i  5                j  +     >       then_block  else_block
33                                                _|__  _|__         |           |
34                                                |  |  |  |       printf      printf
35                                                i  2  i  1         |           |
36                                                                 i>1\n       i<=1\n

fig1 list 1 範例的 AST, if/else statement AST

如果 else 對你有點難的話, 不要實作 else 也無所謂, 用 if 就夠了, 難度又可以再減少一些。

while node 該怎麼建立呢? if node 會, while 就會, 這是一樣的, 只是關鍵字改成 while 而已嘛! 他們的不同在 eval 階段, if 的 eval 只要執行一次, 而 while 的 eval 可能要執行 0 次或是多次, 但 AST node 是很類似的。

學習的重點在精神, 不在完整, 不然光是要處理 int *********i, 就累死你了, 目前的程式是可以 parse int *********i, 但是無法 eval 它, 要怎麼紀錄這樣的型別, 難倒我。

沒有留言:

張貼留言

使用 google 的 reCAPTCHA 驗證碼, 總算可以輕鬆留言了。

我實在受不了 spam 了, 又不想讓大家的眼睛花掉, 只好放棄匿名留言。這是沒辦法中的辦法了。留言的朋友需要有 google 帳號。