旦旦而學之，久而不怠焉，迄乎成。
這篇來得很晚, 在《
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 帳號。