compiler [2.6] - 建立 variable, function declare/definition AST

Bene qui latuit, bene vixit

var_func.c

 1 #include <stdio.h>
 2
 3 int test(int i);
 4
 5 int test(int i)
 6 {
 7   printf("i: %d\n", i);
 8 }
 9
10 int main()
11 {
12   test(5);
13   printf("abc\n");
14   return 0;
15 }

繼四則運算、if/else/while 之後, 登場的是函式宣告/定義, 不是函式呼叫, 得先有了函式宣告/定義才能呼叫, 所以先處理函式宣告/定義。當然也要提一提變數的宣告。

我參考的是《手把手教你构建 C 语言编译器（5）- 变量定义》 ebnf, 不過後來我才注意到我把函式宣告和定義搞在一起了, 這個 ebnf 並沒有區分函式宣告和定義, 雖然有點遺憾, 不過這樣可以簡化整個函式相關的 parser。

所以無法寫 var_func.c L3 的語法, 只能寫 var_func.c L5 ~ 8 這樣的語法, 其實也還好, 所以就先這樣吧! 精簡版的 c 語法嘛!

note

後來發現這樣有個問題, 無法處理標準程式庫的 function prototype, 例如: printf, 無法 parse printf 的 type, 這在 code generator 上有點麻煩, 我無法知道 function 離開時, 如何把 stack 還原, 雖然知道傳入參數的個數, 但不知道傳入的參數 type, 無法計算要還原幾個 bytes。

c_parser.c

 747 // function_decl ::= type {'*'} id '(' parameter_decl ')' '{' body_decl '}'

 748 ASTNode* func_decl()
 749 {
 750   ASTNode *func_node = new ASTNode(func_token);
 751   func_node->set_obj_type(obj_type);
 752   obj_type.clear();
 753 
 754   while(is_token("*"))
 755   {
 756     pop_token();
 757   }
 758   if (is_token(NAME))
 759   {
 760     Token t = pop_token();
 761     func_node->set_str(t.str());
 762     func_map[t.str()] = func_node;
 763   }
 764   else
 765   {
 766     Token t = peek_token();
 767     err("func_decl: should NAME\n", t.str());
 768   }
 769 
 770   if (is_token("("))
 771   {
 772     Token t = pop_token();
 773   }
 774   else
 775   {
 776     Token t = peek_token();
 777     err("func_decl: should (\n", t.str());
 778   }
 779 
 780   ASTNode *func_para = parameter_decl();
 781 
 782   if (is_token(")"))
 783   {
 784     Token t = pop_token();
 785   }
 786   else
 787   {
 788     Token t = peek_token();
 789     err("func_decl: should )\n", t.str());
 790   }
 791 
 792   if (is_token("{"))
 793   {
 794     Token t = pop_token();
 795   }
 796   else
 797   {
 798     Token t = peek_token();
 799     err("func_decl: should {\n", t.str());
 800   }
 801   if (func_para)
 802     func_node->add_child(func_para);
 803 
 804   ASTNode *func_body = body_decl();
 805   if (func_body)
 806     func_node->add_child(func_body);
 807     
 808 
 809   if (is_token("}"))
 810   {
 811     Token t = pop_token();
 812   }
 813   else
 814   {
 815     Token t = peek_token();
 816     err("func_decl: should }\n", t.str());
 817   }
 818 
 819   return func_node;
 820 }

 822 // variable_decl ::= type {'*'} id { ',' {'*'} id } ';'
 823 ASTNode* var_decl(bool is_global)
 824 {
 825   ASTNode *var_node = 0;
 826 
 827   if (is_global)
 828     var_node = new ASTNode(g_var_token);
 829   else
 830     var_node = new ASTNode(var_token);
 831 
 832   int ptr_num=0;
 833   while(is_token("*")) // 處理 0 ~ 多個的 *
 834   {
 835     ++ptr_num;
 836     pop_token();
 837   }
 838   if (ptr_num > 0)
 839     obj_type.set_pointer(ptr_num);
 840 
 841   if (is_token(NAME)) // 判斷是不是 id
 842   {
 843     Token t = pop_token();
 844     ASTNode *v = new ASTNode(t);
 845 
 846     v->set_obj_type(obj_type);
 847 
 848     var_node->add_child(v);
 849   }
 850 
 851   while(is_token(",")) // 判斷 0 ~ 多個的 ,
 852   {
 853     pop_token();
 854     int ptr_num = 0;
 855     while(is_token("*")) // 判斷 0 ~ 多個的 *
 856     {
 857       ++ptr_num;
 858       pop_token();
 859     }
 860 
 861   if (ptr_num > 0)
 862     obj_type.set_pointer(ptr_num);
 863 
 864     if (is_token(NAME)) // 判斷是不是 id
 865     {
 866       Token t = pop_token();
 867       ASTNode *v = new ASTNode(t);
 868       v->set_obj_type(obj_type);
 869       var_node->add_child(v);
 870     }
 871   }
 872 
 873   if (is_token(";")) // 判斷是不是 ;
 874   {
 875     pop_token();
 876     obj_type.clear();
 877   }
 878   else
 879   {
 880     Token token = peek_token(); 
 881     err("var_decl: should ;", token.str_);
 882   }
 883   return var_node;
 884 }

不過先談一般的變數宣告, 像 int a; 就是變數宣告, char (*(*x[3])())[5] 這種也是變數宣告, 不過很抱歉, 本篇的 ebnf 無法解析這麼複雜的宣告, 也沒打算支援這麼恐怖的宣告, 頂多是 int *********i; 這種。

c_parser.c L823 的 var_decl() 就已經很長了, 已經不容易和 ebnf 對應了, 這是因為我加了不少的東西, 掩蓋了本質, 我需要區分 global/local variable, 並且用一個資料結構紀錄這個變數的型別, 這不容易, 你要怎麼紀錄 char (*(*x[3])())[5] 的型別呢? 我沒想到好方法, 先用個 ObjType 檔一檔。

本質就是

ex1

int i;
char c;
char *pc;
int *pi;

這樣而已, 感覺沒那麼難, 應該寫的出來, 但就算只有支援指標, 也很困難, 看看 ex2 的例子:

ex2

int *******i;
int ********************i;

這就有點難了吧! 你說沒什麼多個迴圈去跑而已, 但要怎麼把型別記錄下來呢?

* 是指標
** 是指標的指標
***
****

要用怎麼樣的方式紀錄這是幾顆星的指標呢?

這便是 {'*'} ebnf 對應的部份, L833 的程式碼就是在對付這個 ebnf, L851 開始的部份則是在對付 { ',' {'*'} id } ebnf, 再來一次而已, 如果這樣的程式碼對你來說很難看, 試試用 gdb 跑一次, 邊跑邊觀察 ASTNode 怎麼長出來, 就會有感覺了, 我也是這樣開始的, 當然如果你找得到朋友詢問, 那是最好的, 如果你在某聚會上遇到我, 也歡迎找我聊聊。

如果還是看不懂, 那該怎麼辦, 沒辦法了, 先放棄吧, 編譯器沒那麼重要, 可以先玩玩別的東西, 等過了一段時間記得回來, 也許就看懂了。有這麼好的事情嗎? 難說, 搞不好就有這樣的好事發生在你身上。

ex1, ex2 解決之後, 就可以來處理函式宣告與定義了。

和變數比較起來, 函式多了後面的 (), 以及 () 裡頭的變數宣告, 所以得要先能處理變數宣告才行。

L748 func_decl() 在處理函式宣告, 和變數不同的是多了

'(' parameter_decl ')' '{' body_decl '}'

L780 parameter_decl() 在處理 parameter, 和變數有點像, 只是沒有 ';' 結尾, 再來是 function body, 裡頭可以想成由變數宣告、四則運算、if/else、while 的組成結構, 越來越複雜了哦, 不過這些之前都對付過了, 把他們組合起來即可。


這就是為什麼我是依照這樣的順序來學習這些項目, 他們有一點點的相互關聯, 而拆解這些項目, 才能專住在某一個小部份, 也才能用零散的時間來學習, 感覺上也沒有那麼難了。

list 1 是這次的成果, 有了函式/變數的 AST, 酷吧!

list 1, function myfun declare/definition, variable declare AST

51 
52 int myfun(int ***p3, int a, char *p1)
53 {
54   int i,j;
55 
56   1+2;
57 }
58 
59 
60  ./c_parser < test_pattern/var_1.c | ./tree
 1                                           root
 2                                            |
 3                                           prog
 4                                    ________|________
 5                                    |               |
 6                         myfun |int |func |global  main
 7                     _______________|_______________
 8                     |                             |
 9                    para                       func_body
10        _____________|_____________           _____|______
11        |            |            |           |          |
12 p3 |ptr<3> |int   a |int  p1 |ptr<1> |char  var         +
13                                          ____|____     _|__
14                                          |       |     |  |
15                                        i |int  j |int  1  2

function 分為 para, func_body; func_body 又分為 "變數宣告" 和 "執行的程式碼" (可以想成四則運算) 兩部份。

list 1 L12 myfunc parameter 的部份是:
變數名稱是 p3, type 是 3 顆星的 int 指標
變數名稱是 a, type 是 int
變數名稱是 p1, type 是 1 顆星的 char 指標

list 1 L12 myfunc func body 的部份是:
變數宣告:
變數名稱是 i, type 是 int
變數名稱是 j, type 是 int

執行的程式碼的部份:
1+2

這樣就把 function, variable 用 AST 表示出來了。

ref:

• c decl
• How to interpret complex C/C++ declarations