yacc/bison 系列 (3) - c parser

看人挑擔不吃力, 自己挑擔壓斷肩。

馬上就要挑戰 c parser 嗎? 是也不是, 最主要只處理合法的 c 語言輸入, 並沒有要輸出組合語言、AST 或是語意分析之類的動作, 這樣就簡單很多。

麻煩的是 c yacc 語法規則要怎麼寫, 我自己是寫不出來的, The c programming language 附錄 A 有一個這樣的 yacc 語法, 稍加修改就可以用了。但我不會修改, 也不想輸入那麼多字, 在網路上找到了範例。至於為什麼 The c programming language 附錄 A 會有 yacc 文法, 因為 yacc 也是那時候開發出來的, Dennis MacAlistair Ritchie 沒理由不用的, 不只 c 用了, 連 c++ 也有用 yacc, 畢竟是同時期的貝爾實驗室同事。

https://www.lysator.liu.se/c/ANSI-C-grammar-y.html, 只有這個當然不行, 還得有搭配的 lexer, 在這邊 https://www.lysator.liu.se/c/ANSI-C-grammar-l.html。

我本來想找 usenet/net.sources/ansi.c.grammar.Z, 但是找了 ftp.uu.net mirror 站台都找不到, 只好自己拼湊了。只要補上相關的 code 就可以了,

完成這個不難, 最難的部份人家都寫好了, 我只是補上可以編譯的 code 而已, 測試了一些很複雜的宣告, 例如:

list 1. pthread_create

1 int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg);

A, 有錯耶, 奇怪, 失敗了嗎? 後來發現是 pthread_attr_t, 這些都不是內建型別, 需要先用 typedef 宣告之後才能用, 然後我就發現 typedef 也不能用。思考一下之後就發現問題了, 之後稍加改 code, typedef 可以用了, 證實是我想的那樣。不過不用管 typedef, 先把這些非內建型別換成 int 就好, 這就通過 c 語法檢查了。

之前的 simple_compiler 我有一點沒有做好, 型別紀錄, 就是符號表 (symbol table), 每個符號有其屬性, 這邊我沒有特別處理, 舉例來說 str="xyz";, "xyz" type 是 const char*, str type 也要是 const char *, 所以做 assign (=) 是一個合法的 statement, 如果沒有紀錄 type, 就無法判定是不是正確的 assign。另外還有 scope 的問題, str 這時候是在合法的 scope 嗎?

{
  {
    const char *str;
  }
  str = "abc";
}

像這樣就不合法了。

型別的另外一個難點是怎麼用程式碼紀錄這些型別, 我想不到一個好的辦法, 畢竟型別的組合是無限多種。

list 1 在處理 int xyz;, 開啟 debug mode, 可以觀察到僅僅是這麼簡單的宣告, 就執行了好多次的文法規則。

list 1 d.txt

 1 descent@debian64:hoc$ ./c -d 1
 2 enable bison debug mode
 3 Starting parse
 4 Entering state 0
 5 Reading a token: int
 6 Next token is token INT ()
 7 Shifting token INT ()
 8 Entering state 9
 9 Reducing stack by rule 95 (line 243):
10    $1 = token INT ()
11 int
12 cc INT
13 -> $$ = nterm type_specifier ()
14 Stack now 0
15 Entering state 24
16 Reading a token: 
17 xyz
18 Next token is token IDENTIFIER ()
19 Reducing stack by rule 79 (line 208):
20    $1 = nterm type_specifier ()
21 -> $$ = nterm declaration_specifiers ()
22 Stack now 0
23 Entering state 22
24 Next token is token IDENTIFIER ()
25 Shifting token IDENTIFIER ()
26 Entering state 32
27 Reducing stack by rule 132 (line 327):
28    $1 = token IDENTIFIER ()
29 xyz
30 dd IDENTIFIER: xyz, type_data.storage_class_: (null), type_data.type_specifier_: 291
31 -> $$ = nterm direct_declarator ()
32 Stack now 0 22
33 Entering state 39
34 Reading a token: 
35 ;
36 Next token is token ';' ()
37 Reducing stack by rule 131 (line 323):
38    $1 = nterm direct_declarator ()
39 -> $$ = nterm declarator ()
40 Stack now 0 22
41 Entering state 38
42 Next token is token ';' ()
43 Reducing stack by rule 85 (line 223):
44    $1 = nterm declarator ()
45 -> $$ = nterm init_declarator ()
46 Stack now 0 22
47 Entering state 37
48 Reducing stack by rule 83 (line 218):
49    $1 = nterm init_declarator ()
50 -> $$ = nterm init_declarator_list ()
51 Stack now 0 22
52 Entering state 36
53 Next token is token ';' ()
54 Shifting token ';' ()
55 Entering state 55
56 Reducing stack by rule 76 (line 202):
57    $1 = nterm declaration_specifiers ()
58    $2 = nterm init_declarator_list ()
59    $3 = token ';' ()
60 -> $$ = nterm declaration ()
61 Stack now 0
62 Entering state 21
63 Reading a token: ;

source code:

• https://bitbucket.org/dsung/hoc/src/master/c.l
• https://bitbucket.org/dsung/hoc/src/master/c.y

yacc/bison 系列 (2) - 輸出 AST, if statement

今天是 2022/2/1 是農曆 2022 大年初一, 照例發篇文章來慶祝一下。

黑暗越是深邃, 顯現出來的光芒就越是璀璨耀眼

可以 eval if statement 之後, 我想要印出 if AST, 這個比 eval if statement 還要難。本來應該先寫 eval if statement, 但是我剛做完 if AST, 印象深刻, 先發此文。

找了 ref 列出的參考資料, 看過之後還是覺得難, 程式太完整, 不容易看, 在我自己的經驗中, 教學文必須要簡單, 怎麼樣才能簡單, 拆解, 所以我這篇只做 「if statement」加上「四則運算」, 當然如果只做「四則運算」的 ast 會更簡單, 但 ... 就讓我偷懶一下。

然後範例程式也簡單, 一個檔案就包含全部, 再來是編譯指令也要提供, 這樣看的人才能完整測試。

範例程式雖然簡單, 但不代表這個主題很簡單, bison 我挑戰好幾次了, 直到這次才有一點小進展, 我相信 bison 帶來的回報是可觀的, 所以我願意花時間在上面。

搭配參考資料的範例加上我自己一步一步分析之後, 終於搞出一個版本, 很簡單, 只針對 if statement, 本來更簡單應該要先嘗試四則運算, 但這次我懶得從這裡開始, 跳個一小步, 從「if statement」加上「四則運算」開始。

所謂的一步一步分析是什麼麼意思? 就是修改 bison 檔案之後, 觀察輸出的 .cpp 是長什麼樣, 會有哪些資料結構, 文法規則的程式碼怎麼執行, 推敲出這些執行順序。

我有自信這個範例是最小集合, 只有一個 .y 檔案, 也很容易理解, 程式也沒用上什麼難懂的技巧, 使用 c++ 來搭配 bison, bison 原本是和 c 搭配使用, 但 c++ 憑藉了與 c 的相容性, 輕鬆搭上 bison 列車, 也順便展示 bison 和 c++ 的搭配。c++ 也來到了 c++20 的標準, 還沒能搭上 c++20 的列車, 目前學的 c++ 技能還算夠用。fig 1 是我辛苦後的成果, 當然比之前手工寫法輕鬆很多。

parser 是什麼意思呢? 就是根據輸入的字串分析之後產生對應的動作, 以 if statement 來說:

if (6-3) {2-(1+5);}

分析之後要做什麼動作?

得到 -4 嗎? 不一定哦, 像我是想得到一個 ast, 我並不想 eval 這個敘述句。另外也可能輸出某個機器的組合語言來完成這個 if statement, 這是 bison 另外一個難的地方, bison 幫你處理文法了, 你要怎麼寫程式達到你要的目的呢? 只是要求值 -4 簡單很多。

fig 1. 使用 bison 輸出 AST

hoc_if_ast.y

  1 %{
  2 #include <stdio.h>
  3 #include <ctype.h>
  4 #include <stdlib.h>
  5 #include <unistd.h>
  6 
  7 #include <string>
  8 #include <vector>
  9 #include <iostream>
 10 
 11 using namespace std;
 12 
 13 //#define YYSTYPE double
 14 #define YYDEBUG 1
 15 
 16 
 17 enum NodeType 
 18 {
 19   IF_TYPE,
 20   PLUS,
 21   MINUS,
 22   MUL,
 23   DIV
 24 };
 25 
 26 //#define YYSTYPE AstNode
 27 
 28 class AstNode
 29 {
 30   public:
 31     AstNode(const string str):str_(str), val_(0)
 32     {
 33     }
 34     string str_;
 35     void set_val(const double val)
 36     {
 37       val_ = val;
 38     }
 39     int add_child(AstNode *n)
 40     {
 41       children_.push_back(n);
 42       return 0;
 43     }
 44     double val_;
 45     vector<AstNode *> children_;
 46   private:
 47     NodeType node_type_;
 48 };
 49 
 50 AstNode root{"root"};
 51 
 52 static int cnt;
 53 
 54 int yylex();
 55 int yyerror(const char *s);
 56 %}
 57 
 58 
 59 %union
 60 {
 61   AstNode *node_;
 62   double num_;
 63 }
 64 
 65 %token <num_> NUMBER
 66 %token IF
 67 %left '+' '-'
 68 %left '*' '/'
 69 
 70 %type <node_> expr selection_statement
 71 
 72 %%
 73 
 74 
 75 selection_statement: {}
 76                    | selection_statement IF '(' expr ')' '{' expr ';' '}' '\n'
 77                    {
 78                      // if (6-3) {2-(1+5);}
 79                      AstNode *n = new AstNode{"if"};
 80                      n->add_child($4);
 81                      n->add_child($7);
 82                      cout << "$4->str_: " << $4->str_ << endl;
 83                      cout << "$7->str_: " << $7->str_ << endl;
 84 
 85                      $$ = n;
 86                      root.add_child(n);
 87                      
 88                      printf("new if/then node, cnt: %d\n", cnt);
 89                      ++cnt;
 90                    }
 91 
 92 expr: NUMBER 
 93       {
 94         AstNode *n = new AstNode{"num"};
 95         n->set_val($1);
 96         $$ = n;
 97 
 98       }
 99        | expr '+' expr 
100          {
101            AstNode *n = new AstNode{"plus"};
102            n->add_child($1);
103            n->add_child($3);
104            cout << "$1.val: " << $1->val_ << endl;
105            cout << "$3.val: " << $3->val_ << endl;
106            $$ = n;
107            ++cnt;
108          }
109        | expr '-' expr 
110          {
111            AstNode *n = new AstNode{"minus"};
112            n->add_child($1);
113            n->add_child($3);
114            cout << "$1.val: " << $1->val_ << endl;
115            cout << "$3.val: " << $3->val_ << endl;
116            $$ = n;
117            ++cnt;
118          }
119        | '(' expr ')'
120        {
121         $$ = $2;
122        }
123 
124 %%
125 char *progname;
126 int lineno = 1;
127 
128 
129 int yylex()
130 {
131   int c;
132   while ((c=getchar()) == ' ' || c == '\t')
133     ;
134   
135   if (c == EOF)
136     return 0;
137   if (c == '.' || isdigit(c) )
138   {
139     ungetc(c, stdin);
140     scanf("%lf", &yylval.num);
141     return NUMBER;
142   }
143 
144   if (c == 'i')
145   {
146     int ch;
147 
148     ch = getchar();
149     if (ch == 'f')
150       return IF;
151     else
152     {
153       ungetc(ch, stdin);
154     }
155   }
156 
157   if (c == '\n')
158     ++lineno;
159   return c;  
160 }
161 
162 int warning(const char *s, const char *t)
163 {
164   fprintf(stderr, "%s: %s", progname, s);
165   if (t)
166     fprintf(stderr, " %s", t);
167 
168   fprintf(stderr, " near line %d\n", lineno);
169   return 0;
170 }
171 
172 int yyerror(const char *s)
173 {
174   return warning(s, 0); 
175 }
176 
177 void print_node(const AstNode *n)
178 {
179   cout << "n: ("  << n->str_ << ", "<< n->val_ << ")" << endl;
180   for (auto i: n->children_)
181   {
182     print_node(i);
183   }
184 }
185 
186 void print_tree(const AstNode *n)
187 {
188   if (n->children_.size() == 0) // leaf node
189   {
190     cout << "("  << n->str_ << ", "<< n->val_;
191     cout << ")";
192   }
193   else
194   {
195     cout << "("  << n->str_ << ", "<< n->val_;
196     for (auto i: n->children_)
197     {
198       print_tree(i);
199     }
200     cout << ")";
201   }
202 
203 }
204 
205 
206 int main(int argc, char *argv[])
207 {
208   int opt;
209   progname = argv[0];
210 
211   while ((opt = getopt(argc, argv, "d:h?")) != -1)
212   {
213     switch (opt)
214     {
215       case 'd':
216       {
217         yydebug = strtol(optarg, 0, 10);
218         if (yydebug == 1)
219           printf("enable bison debug mode\n");
220         break;
221       }
222     }
223   }
224 
226   yyparse();
227   cout << "\\tree";
228   print_tree(&root);
229   cout << endl;
230 }      

list 1 編譯指令

bison -y hoc_if_ast.y -o hoc_if_ast.cpp
g++ -g -std=c++17 -Wall hoc_if_ast.cpp -o hoc_if_ast

執行 hoc_if_ast 輸入 if (6-3) {2-(1+5);} 就可以看到結果, 如果要輸出 fig 1 的樹狀圖, 需要 tree 這個工具, 之前也介紹過了。

hoc_if_ast.y L28 定義一個 class AstNode, 用來處理 ast node, 之前做過, 弄個簡化版, 這個要怎麼用呢? 在規則內指定給 $$, 問題來了, $$ 要怎麼指定成 AstNode type, 目的想做 $$ = new AstNode 這樣。

hoc_if_ast.y L59 ~ 63, L70 就是在做這件事, 把 node_ type 也就是 AstNode 指定給 expr, selection_statement 這些規則, 之前一直搞不懂 %type 的意思, 原來是這樣用。

NUMBER 這個希望 $1 是 double type, 得用 hoc_if_ast.y L65 token 語法來定義。

 65 %token <num_> NUMBER
 59 %union
 60 {
 61   AstNode *node_;
 62   double num_;
 63 }
 70 %type <node_> expr selection_statement

對照 bison 寫法轉出來的 c++ code。

 92 expr: NUMBER
 93       {
 94         AstNode *n = new AstNode{"num"};
 95         n->set_val($1);
 96         $$ = n;
 98       }

轉出的 c++ code。

1202   case 4: /* expr: NUMBER  */
1203 #line 93 "hoc_if_ast.y"
1204       {
1205         AstNode *n = new AstNode{"num"};
1206         n->set_val((yyvsp[0].num_));
1207         (yyval.node_) = n;
1209       }

有點感覺了吧, 來看看 yyvsp, yyval type 是什麼? YYSTYPE, 這個 YYSTYPE 是什麼? hoc_if_ast.y L59 ~ L63 union 定義出來的資料結構。

 181 /* Value type.  */
 182 #if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED
 183 union YYSTYPE
 184 {
 185 #line 60 "hoc_if_ast.y"
 186
 187   AstNode *node_;
 188   double num_;
 189
 190 #line 191 "hoc_if_ast.cpp"
 192 };

再來看看 if (6-3) {2-(1+5);} bison 是怎麼處理的, 參考 list 2。

list 2. if (6-3) {2-(1+5);} 處理順序

1 if (6-3) {1+5;}
2 6
3 3
4 -
5 1
6 5
7 +
8 if minus plus

bison 會依序處理 6, 3, -, 1, 5, +, if, 所以想法是這樣, 在處理 6 的地方, 產生一個 6 的 AstNode, 在 3 的地方產生一個 AstNode, 在 - 的地方產生一個 - AstNode 並把 6, 3 這 2 個 AstNode 加入到 - AstNode。這個就是四則運算的 AST。 加入 if statement 之後, 麻煩的是怎麼把這個 - AstNode 接到 if AstNode 的子 node。我是看了參考資料的程式碼才知道要這麼寫的, 但我想不透為什麼是這樣。

不過也不用想的太複雜, 反正 $$ 就是規則的傳回值, 我在 expr '+' expr 回傳 + node, expr '-' expr 回傳 - node, selection_statement IF '(' expr ')' '{' expr ';' '}' '\n' 也照樣做就好, $4 就是 - node, $7 就是 + node, 不用管 bison 是怎麼做的, 然後把 - node 放在第一個子 node, then 的部份放在第二個子 node, 如果有 else 的話就放在第三個子 node, 這樣就搞定了。

使用 gdb debug bison 產生的 .c 或是 .cpp 時, 吃到的 source file 是 .y, 有時候你可能不想這樣, 想要對應的是 .c 或是 .cpp 檔案, 這時候可以在 bison 使用 -l, bison 就不會產生 #line, 這樣 gdb 的 source file 就會是 .c 檔。

另外, 使用 --graph 就可以輸出 .dot 檔案, 搭配 dot 這個工具, 就可以輸出一個 svg 圖, 展示 bison grammer 是如何工作的。使用以下指令就可以輸出對應的圖檔。

dot -Tpng hoc_if_ast.dot -o hoc_if_ast.png
dot -Tsvg hoc_if_ast.dot -o hoc_if_ast.svg

最後來談談這個 if 文法規則, 這是我胡亂自己湊出來的, 不是正規的文法, 不過由於符合我的需求, 就這麼用了。參考連結 3 提供了 if 文法規則, 可以參考看看。

ref:

1. How to use C++ with Bison, V 1.0.2
2. How to create an abstract syntax tree while parsing an input stream.
3. if 陳述式 (C)
4. 5 The Bison Parser Algorithm
5. 8 Debugging Your Parser

yacc/bison 系列 (1) - 四則運算, 靠文法規則來處理優先順序

行是知之始，知是行之成。

hoc_arithmetic.y

 1 %{
 2 #include <stdio.h>
 3 #include <ctype.h>
 4 #include <stdlib.h>
 5 #include <unistd.h>
 6 #define YYSTYPE double
 7 #define YYDEBUG 1
 8 
 9 int yylex();
10 int yyerror(const char *s);
11 %}
12 
13 %token NUMBER
14 %%
15 list:    {printf("\taaempty\n");}
16      | list '\n' {printf("list \\n\n");}
17      | list expr '\n' { printf("%.8g\n", $2); }
18 
19 expr: term
20     | expr '+' term {$$ = $1 + $3;}
21     | expr '-' term {$$ = $1 - $3;}
22 
23 term: primary_expr
24     | term '*' primary_expr {$$ = $1 * $3;}
25     | term '/' primary_expr {$$ = $1 / $3;}
26 
27 primary_expr: NUMBER
28        | '(' expr ')'
29 
30 %%
31 char *progname;
32 int lineno = 1;
33 
34 
35 int yylex()
36 {
37   int c;
38   while ((c=getchar()) == ' ' || c == '\t')
39     ;
40   
41   if (c == EOF)
42     return 0;
43   if (c == '.' || isdigit(c) )
44   {
45     ungetc(c, stdin);
46     scanf("%lf", &yylval);
47     return NUMBER;
48   }
49 
50   if (c == '\n')
51     ++lineno;
52   return c;  
53 }
54 
55 int warning(const char *s, const char *t)
56 {
57   fprintf(stderr, "%s: %s", progname, s);
58   if (t)
59     fprintf(stderr, " %s", t);
60 
61   fprintf(stderr, " near line %d\n", lineno);
62 }
63 
64 int yyerror(const char *s)
65 {
66   return warning(s, 0); 
67 }
68 
69 int main(int argc, char *argv[])
70 {
71   int opt;
72   progname = argv[0];
73 
74   while ((opt = getopt(argc, argv, "d:h?")) != -1)
75   {
76     switch (opt)
77     {
78       case 'd':
79       {
80         yydebug = strtol(optarg, 0, 10);
81         if (yydebug == 1)
82           printf("enable bison debug mode\n");
83         break;
84       }
85     }
86   }
87 
88   //yydebug = 1;
89   yyparse();
90 }      

「前一篇」提到使用的四則運算是依靠 bison 的運算符定義來達成優先順序, 這篇介紹使用文法定義來處理運算符號優先權, 可以看出文法規則 hoc_arithmetic.y (L15 ~ 28) 比之前複雜不少, 雖然只是簡單的四則運算, 但這文法規則還是蠻燒腦了, 我花了一些功夫才弄懂, 不過若是要自己寫出這些規則, 我沒有這個本事。

藉助 bison 這樣的神兵利器, 只要把文法規則重新編寫之後, 再次執行 bison, 就有了一樣的四則運算功能。

本篇沒打算說明文法規則, 如果你沒有修過編譯器課程, 這些文法規則可能會難倒你 (其實也難倒我), 文法規則可以參考「自己动手写编译器」。

編譯器相關文章

今天是 20180101 (台灣時間), 新年新希望, 來把之前的編譯器文章集合起來。

• 幾本編譯器書籍
• 學習編譯系統的心得
• compiler [0] - lexer, lexical analyzer, scanner, tokenizer, 詞法分析器
• compiler [1] - 四則運算
• compiler [2] - 四則運算 + 運算符號優先法
• compiler [2.3] - 產生 if/else, while 的 AST
• compiler [2.6] - 建立 variable, function declare/definition AST
• compiler [2.9] - 建立 function call AST
• compiler [3] eval 運算式
• compiler [4] 環境與變數 => 環境變數
• compiler [5] eval printf
• compiler [6] - code generator - 四則運算
• compiler [7] - code generator - funcall call, pass argument

compiler [7] - code generator - funcall call, pass argument

倦怠期中, 無限取材休刊

這陣子有點懶懶的, 突然失去寫技術文章的熱情, 我花了一些時間重溫 c++ virtual function, 卻提不起勁把這些東西整理成一篇文章, 可能真有些倦怠感, 沒意外的話這篇應該會是倦怠期最後一篇的技術文章。不只這樣, 連正在進行的組譯器我也提不起勁繼續下去, 而好不容易理清的 elf section 我竟然也沒動力整理寫下來, 所以才跑去寫俄羅斯方塊。也許該暫停一下這些東西, 轉換一下學習方向。

倦怠期間沒什麼在學習, 看了 jojo 動畫、王牌大律師, 這樣的生活蠻開心的, 也很舒服, 但不知怎麼的, 就是覺得哪裡怪怪的 ... 「學如逆水行舟不進則退」如果一天下來都沒進步, 這樣的生活令我惶恐, 不過適度的放鬆也是必要的, 我懷疑我放鬆過了頭。

在四則運算告一個段後之後, 本來應該是 if/else, 不過 if/else 不是太難, 就先跳過, 來看看 c function 的呼叫應該怎麼產生對應的組合語言。本篇文章介紹怎麼產生 c function 參數傳遞的組合語言。也許有人知道用 stack 用來傳遞參數, 由右而左的順序放進 stack, 除了這些, 還需要其他的知識才能產生對應的組合語言。

把 char c, 傳給 fun1(int a) 時, c 需要做什麼特別的事情嗎?

依照慣例, 先來一個很簡短的 c 程式, 是簡單的 c 函式呼叫, 來看 gcc 會輸出什麼樣的組合語言?

f.c 是 source code, list 1 則是 gcc 輸出的 x86 32bit 組合語言。

fc.c

 1 
 2 char func678(char c)
 3 {
 4   return c;
 5 }
 6 int main(int argc, char *argv[])
 7 {
 8   char func678(char c);
 9   func678(5);
10   return 0;
11 }

list 1. gcc -m32 -S fc.c => fc.s

 1  .file "fc.c"
 2  .text
 3  .globl func678
 4  .type func678, @function
 5 func678:
 6  pushl %ebp
 7  movl %esp, %ebp
 8  subl $4, %esp
 9  movl 8(%ebp), %eax
10  movb %al, -4(%ebp)
11  movzbl -4(%ebp), %eax
12  leave
13  ret
14  .size func678, .-func678
15  .globl main
16  .type main, @function
17 main:
18  pushl %ebp
19  movl %esp, %ebp
20  pushl $5
21  call func678
22  addl $4, %esp
23  movl $0, %eax
24  leave
25  ret
26  .size main, .-main
27  .ident "GCC: (GNU) 5.4.0"
28  .section .note.GNU-stack,"",@progbits

function 參數的傳遞比想像中複雜, 當 function 沒有 prototype 時或是使用 K&R style 的宣告或是 ... 這種參數 - ex: printf(const char *format, ...), 會發動 integer promtion, 這很好理解, 可以參考《“对于那些没有原型的函数，传递给函数的实参将进行缺省参数提升”是什么意思？》, 請不要小看中文世界的知識量, 你的問題說不定並沒特別需要到英文世界找答案, 知乎上的回答很有水準, 有這樣的平台, 是中文使用者的福氣, 讓我們別輸懂英文的人太多, 但請不要把這些話理解成我覺得英文不重要, 英文的重要性是已經到不需要特別指出來了。

fc.s L20 那行是 integer promotion 嗎? 因為有 fc.c L8 那行 (有 function prototype), 所以上述規則並不是用在這個情況, 由於 push 4 byte 長度的 5 (list 1 L20), 應該可以輸出 pushb $5, 這樣只要 push 一個 byte 就好, 而 pushl $5, 看起來很像做了 integer promotion, 把 5 傳給 char c 提升到 int。

真相是怎麼樣呢?

為了找到答案, 我參閱了:

1. c11 spec
2. C 語言參考手冊
3. C 編譯器剖析
4. Linux C 编程一站式学习
5. C 語言程序設計 - 現代方法
6. 標準 C 語言指南: p166, p307。

並在

• [問題]函式傳進的參數需要做integer promotion嗎?
• c 有 prototype 的函式, 實參還需要做 integer promotion 嗎？
• https://www.facebook.com/groups/441041979282906/permalink/1290666850987077/

發問, 結合這些回答以及找到的資料再加上 c11 spec 6.5.2.2 function call 查到的

c11 spec 6.5.2.2

If the expression that denotes the called function has a type that does
include a prototype, the arguments are implicitly converted,
as if by assignment, to the types of the corresponding parameters,
taking the type of each parameter to be the unqualified version
of its declared type. The ellipsis notation in a function prototype
declarator causes argument type conversion to stop after
the last declared parameter. The default argument
promotions are performed on trailing arguments

我得出了結論:
把 5 傳給 char c, 相當於 char c=5, 這會用到 assign 那條轉換規則, 參考《第 15 章 数据类型详解/3. 类型转换 3.3. 由赋值产生的类型转换 (implicit conversion)》, 5 的 type 是 int (不是 short, 也不是 unsinged int), 所以會做 implicit conversion (所以若傳入 300, 就爆了, 翻出來的組合語言會傳入 44, 300 = 0x12c, 0x2c = 44), 而 function 的參數傳遞則是 facebook 討論區說的 ABI, 需要用 4 byte alignment 方式傳入。

節錄: https://developer.apple.com/library/content/documentation/DeveloperTools/Conceptual/LowLevelABI/130-IA-32_Function_Calling_Conventions/IA32.html

The caller places arguments in the parameter area in reverse order, in 4-byte chunks. That is, the rightmost argument has the highest address.

Figure 2  Argument assignment with arguments of the fundamental data types


由於這些巧合, 看起來就像 integer promotion。

知道了這些之後, 就知道該如何輸出函式參數傳遞的組合語言了。

我一開始並不知道這些規則, 而是在寫到這部份時, 自然就會有這些疑問, 我要根據哪些規則產生對應的程式碼呢? 才開始找尋問題的答案。比想像中難得多。

最後再回到沒有 prototype 時, 看看有什麼不同。

no_prototype.c

 1 
 6 int main(int argc, char *argv[])
 7 {
 9   func678(300);
10   return 0;
11 }

no_prototype.s

 1  .file "c.c"
 2  .text
 3  .globl main
 4  .type main, @function
 5 main:
 6  leal 4(%esp), %ecx
 7  andl $-16, %esp
 8  pushl -4(%ecx)
 9  pushl %ebp
10  movl %esp, %ebp
11  pushl %ebx
12  pushl %ecx
13  call __x86.get_pc_thunk.ax
14  addl $_GLOBAL_OFFSET_TABLE_, %eax
15  subl $12, %esp
16  pushl $300
17  movl %eax, %ebx
18  call func678@PLT
19  addl $16, %esp
20  movl $0, %eax
21  leal -8(%ebp), %esp
22  popl %ecx
23  popl %ebx
24  popl %ebp
25  leal -4(%ecx), %esp
26  ret
27  .size main, .-main
28  .section .text.__x86.get_pc_thunk.ax,"axG",@progbits,__x86.get_pc_thunk.ax,comdat
29  .globl __x86.get_pc_thunk.ax
30  .hidden __x86.get_pc_thunk.ax
31  .type __x86.get_pc_thunk.ax, @function
32 __x86.get_pc_thunk.ax:
33  movl (%esp), %eax
34  ret
35  .ident "GCC: (Debian 7.2.0-8) 7.2.0"
36  .section .note.GNU-stack,"",@progbits

no_prototype.s L16 的 300 出現了, 不會被截斷為 44。

compiler [6] - code generator - 四則運算

合抱之木，生於毫末；九層之臺，起於累土；千里之行，始於足下。

終於到這一步了, code generator 就是常聽到的程式碼產生器, 在編譯系統中, 就是用來產生組合語言。由於對 x86 32bit 模式比較熟悉, 我輸出的是 x86 32bit 的組合語言, 有點過時, 我知道; 現在都是 x64 耶! 我知道, 那你還用 x86 32bit, 就老人懶的學新東西嘛!

code generator 比直譯器難很多, 我想大家都知道, 但難上多少呢? 光四則運算的部份大概就是 1:20 這樣的難度, 只處理四則運算 (Elementary arithmetic) 就讓我花了不少時間, 也吃了不少苦頭, 遇到很多平常沒想到的細節。

如果還要加入變數的支援, 難度可能會來到 1:40, 相當難, 我已經簡化某些細節, 例如: 有號或是無號整數, signed, unsigned, 數字長度是 4 byte 還是 1 byte, 若把這些細節都考慮進來, 那得花很久的時間。對於開發編譯器的人, 我實在相當佩服。os kernel 的開發也很難, 他們屬於兩種不同的難, 並不會因為寫過 os kernel, 就讓學習編譯系統簡單些, 也是得從頭學習。

和 interpreter 一樣, 尋訪那個 AST, 在看到 1+2 時, 想辦法產生對應的組合語言, 說來簡單, 但光是加法就讓我絞盡腦汁才想出怎麼實作, 到了這步, 我刻意不參考任何書籍、網路資料, 我想測試一下自己的程度, 靠自己土砲出來, 很有成就感。原來我也寫的出來嘛!

以下是一些心得:

[暫時物件]
這不是指 c++ 的 "物件", 雖然在 c++ 書籍中很常聽到這個詞彙, 但直到我寫了 code generator 的四則運算, 我才真的體會到什麼是 "暫時物件"; 也不是指 "物件導向" 中的那個 "物件", 在寫 interpreter 就知道這個概念, 但那時還很模糊, 我現在有了新的體認。如果 "暫時物件" 迷惑了你, 那用 "中間結果" 這個詞彙也許更能貼近其意思。

1+2 在 interpreter 會產生一個暫時物件, 如果用 ASTNode 來存這個 3, 3 這個 ASTNode 就是運算 1+2 之後的暫時物件 (中間結果), 由於是 "暫時" 的而且也在記憶體佔據了空間, 所以要還回去, 重點來了, 該怎麼還, 什麼時候還呢?

哎呀, 真是難倒人, GC 就是在搞定這個, 我沒有提怎麼處理 interpreter 產生的暫時物件, 因為我根本沒處理。所以我那個玩具 c interpreter 會有 memory leak 的問題, 怎麼解, 交給 os gc 了。

但如果是在 code generator 上呢? 要如何產生這個暫時物件的程式, 又要產生歸還記憶體的程式碼呢? 沒 gc 那麼複雜, 比你想像中的還簡單。

mov $1, %eax
add $2, %eax

以 x86 32bit 組合語言為例子, 這樣就搞定 1+2, 疑! 暫時物件在哪裡? 這個例子不容易看出暫時物件 (因為根本就沒有暫時物件), 來看看下個例子:

1+2+5

mov $1, %eax
add $2, %eax
add $5, %eax

疑! 好像也沒看到暫時物件。

再看一個

(1+2)+(3+4)

1+2
mov $1, %eax
add $2, %eax

3+4
mov $3, %eax
add $4, %eax

eax 的值被覆蓋了, 這樣怎麼把他們加起來呢?

3+4 改用 ebx

mov $3, %ebx
add $4, %ebx

然後把 eax, ebx 加起來

add ebx, eax

有點政治程式敏感的人應該會開始覺得有點不對勁, 再來看下一個例子。

(1+2)+((3+4)+(5+6))

沒辦法很快寫出來吧
照前面的想法, 這個得用到 ecx 了, 如果有更長的運算式, 可能得用到 ezx 了, 但是 x86 沒有 ezx 可以用。暫存器也不是無限的, 回頭來看 1+2+5 的例子, 來看看引入暫時物件後的組合語言, 先算 1+2,

1+2+5

mov $1, %eax
add $2, %eax

然後產生暫時物件 3, 要把 3 存在哪裡呢? 都可以, 你想得到的地方都可以, 但其實選擇不多, 不是 stack 就是 heap。我選擇了 stack, 這樣比較容易釋放這個暫時物件。

push %eax # 把 3 這個暫時物件放到 stack, 再來做 +5 的動作。

pop %eax
add $5, %eax

這個組合語言很漂亮, 把暫時物件 3 所佔用的 stack 記憶體清掉 (因為 pop 出來了), 並做了剩下的 +5 計算。結束了嗎? 還沒, 產生的 8 (3+5) 也是暫時物件, 存到 stack 中吧!

push %eax

這時候的 stack 有一個 8 的暫時物件, 什麼時候要用到, 什麼時候要歸還這個 stack 佔用的記憶體, 就看程式碼怎麼寫, 以這個例子來說, 由於不用存到其他變數中, 就 pop 掉它吧。

由於產生的暫時物件我放在 stack, 所以在進入函式的開頭, 要產生留下這個 stack 空間的組合語言, 這可不容易, 要怎麼知道這個 stack 要留下多少 byte 呢? 當然要計算產生的暫時物件需要幾個 byte? 很難吧, 我放棄這部份的計算, 先 hard code 一個值。

光是搞定加法運算如: 1+2+5 就花了我很長的時間, 依樣畫葫蘆, 乘法沒那麼難了, 好不容易搞定 3*5*7, 來把他們組合起來, 1+2*3 馬上就出錯了, 讓我之前絞盡腦汁想的方法完全破功, 得從頭開始再想一個方法, 後來我又加入了 <, >, =, 複雜度又提高了。程式碼開始變得醜陋了。

比起 interpreter 的四則運算, code generator 的細節多很多, 很容易就產生錯誤的組合語言, 當然運算的結果也是錯的。

如果你用 gcc -S 看 1+2+5 產生後的組合語言程式碼, 肯定是看不到這樣的作法的, 因為 gcc 會很聰明的產生 8, 而不會如我說的產生那麼多組合語言, 若說 gcc 是聰明的 c compiler, 那我這個 simple c compiler 就是傻瓜編譯器, 他傻瓜我聰明。

另外有一個比較不傷腦筋的作法是完全使用 stack。

1+2+3
mov $1, %eax
mov $2, %ebx
push %eax
push %ebx
pop %ebx
pop %eax
add %eba, %eax

push %eax
mov 3, %ebx
push %ebx
pop %ebx
pop %eax
add %eba, %eax

把 1 和 2 push 到 stack, 然後做相加的動作, 再 push 到 stack, 再做 + 3 的動作, 這方法比較容易理解, 其實就是 postorder 或是 stack base machine 的作法, 我不想用這個作法, 看起來不厲害阿, 自己胡亂想了上述的方法。

看完暫時物件後, 再來看其他問題, 我把四則運算分為幾個部份:

• immediate value
• variable
• type

[immediate value]
就是做 1+2 這種, 在暫時物件那段說完了。

[變數]

prog 1.

0 func1()
1 int c;
2 c=5;
3 c+2;

這種運算式就是用到了變數, 引入了變數會帶來很多問題, 這個變數在哪裡? 是 global 還是 local 變數。

所以要分配 c 的位址, 並且紀錄這個資訊, 這樣在 prog 1. L3 的 c+2 才知道 c 的位置是什麼, 才能去那個位址把值拿出來和 2 相加, 你肯定無法理解我的意思, 有興趣做一次看看吧!

一樣要用表格紀錄起來, 本科系的朋友應該知道這就是 symbol table, 陷阱在於, 在 function 開頭要保留 stack (eps = eps-4), 用來分配給 c 這個變數 (ebp-4 的位址保留給 c 變數)。

high address	return address	上一個函式
new ebp esp	old ebp  (上一個 fcuntion 的 ebp)	的 stack frame
esp (esp-4 的 esp)	c (epb-4)	func1 的
		stack frame

func1:
push %ebp
mov %esp, %ebp
subl $4, %esp # 留給 c 變數的記憶體空間

push %ebp 的行為: 先把 esp-4, 再把 %ebp 放入 stack

[型別大小]

int i
char x;

x = 5678; // 超過 255, 會做 implicit conversion, 5678 的值會被截掉

i=300;
x=20;
i+x; // 將 x 提升到 int 大小

節錄 Linux C 编程一站式学习 表 15.2 來說明, 在 c 語言的 3+5; statement 中的 3, 是什麼型別? int 嗎? unsigned int? char ? 到底是那個呢? 有組合語言經驗的朋友馬上就聯想到這和暫存器有關系, 我應該產生

mov $3, %ah
mov $3, %ax
mov $3, %eax

中的那個呢?

顆顆, 我沒考慮這問題, 直接產生 mov $3, %eax 這個版本, 這是對的嗎? 3 對應到表 15.2 的 1A 欄位, 3 用 int 就可以存起來, 所以 3 的型別就是 int, 1234U 呢? 自己看連結的內容吧, 我要表達的是四則運算的型別部份沒想像中的簡單, 在我的簡單版本中, 是完全不考慮這些的, 現在你可以體會我說的難度來到 1:40 感覺吧, 事實上還有 conversion, integer promotion 要處理, 很複雜的。我的版本還沒考慮 float/double。

表 15.2. 整数常量的类型

后缀	A 十进制常量	B 八进制或十六进制常量
1 无	int long int long long int	int unsigned int long int unsigned long int long long int unsigned long long int
2 u或U	unsigned int unsigned long int unsigned long long int	unsigned int unsigned long int unsigned long long int
2 l或L	long int long long int	long int unsigned long int long long int unsigned long long int
4 既有u或U，又有l或L	unsigned long int unsigned long long int	unsigned long int unsigned long long int
5 ll或LL	long long int	long long int unsigned long long int
6 既有u或U，又有ll或LL	unsigned long long int	unsigned long long int

以上的幾個問題都被我部份簡化了, 但難度還是很高, code generator 真的不簡單。

最後, 終於來到最後了, 再忍耐一下, 這篇文章快結束了。

1 > 2 的 > 是輸出 cmp 這個指令, 雖然不是四則運算但是得提一下, 因為 if node 需要做 > 的運算, 所以要先支援 > 的 code gen, 才能處理 if node。

1 > 2 要產生什麼樣的組合語言呢? 難倒我也, gcc 編譯器依然不產生 1 > 2 的組合語言, 沒的抄, 我用了一個辦法得知這件事:

rel.c

1 int gr(int c)  
2 {      
3   return c<2;
4 }      

gcc -m32 -S rel.c = rel.s

 1       .file   "rel.c"
 2       .text
 3       .globl  gr
 4       .type   gr, @function
 5 gr:
 6       pushl   %ebp
 7       movl    %esp, %ebp
 8       cmpl    $1, 8(%ebp)
 9       setle   %al
10       movzbl  %al, %eax
11       popl    %ebp
12       ret
13       .size   gr, .-gr
14       .ident  "GCC: (GNU) 5.4.0"
15       .section        .note.GNU-stack,"",@progbits

終於得知要用 cmpl, setle 來得到 1 > 2 的運算結果:

1>2 得到 0
1<2 得到 1

這個 0, 1 是什麼 type 呢? C 標準規定要是 int, 所以要以 int 的大小回傳這個結果, 如果用 char type 來接 int 這個結果, 要做 implicit conversion, 別擔心, 我都沒做。

compiler [2.9] - 建立 function call AST

有匪君子, 如切如磋, 如琢如磨。

有了函式定義之後, 再來就是要呼叫這個函式。function call 的 AST 應該長什麼樣子呢? 像 list 1 這樣。

list 1. function call AST

21 int f1(char c, int i)
22 {
23 }
24 
25 int main()
26 {
27   f1('c', 6);  
28   return 0;
29 }
30
31
 5                                   root
 6                                    |
 7                                   prog
 8            ________________________|________________________
 9            |                       |                       |
10  f1 |int |func |global  main |int |func |global           main
11        ____|_____                  |
12        |        |              func_body
13       para  func_body           ___|___
14    ____|____                    |     |
15    |       |                    f1  return
16 c |char  i |int                _|__   |
17                                |  |   0
18                                c  6

list 2, list 3 是我早期的版本, 那時候還可以這樣寫, 現在已經不行了。得用 list 1 的寫法才行, 也更像 c 語言了。

list 2. test_pattern/fc1.tree

 1 f1(1)
 2 token: f1
 3 token: (
 4 token: 1
 5 token: )
 6 
 7    root
 8     |
 9    prog
10     |
11 func call
12     |
13     1

list 3. test_pattern/fc2.tree

 1 f1(1, 2, x+y, "abc", 1+2*3)
 2 token: f1
 3 token: (
 4 token: 1
 5 token: ,
 6  token: 2
 7 token: ,
 8  token: x
 9 token: +
10 token: y
11 token: ,
12  token: abc
13 token: ,
14  token: 1
15 token: +
16 token: 2
17 token: *
18 token: 3
19 token: )
20 
21        root
22         |
23        prog
24         |
25     func call
26 ________|________
27 |   |   |   |   |
28 1   2   +  abc  +
29        _|__    _|__
30        |  |    |  |
31        x  y    1  *
32                  _|__
33                  |  |
34                  2  3

test_pattern/fc3.tree

 1 f1()
 2 token: f1
 3 token: (
 4 token: )
 5 
 6    root
 7     |
 8    prog
 9     |
10 func call

c_parser.cpp L334 是 function call 的 EBNF, 比較麻煩的是 function 的參數可不見得只是變數或是整數, 還可能是一個 function 或是運算式。當然, 如果想簡化, 就不要處理這些, 程式會簡單些, 不過我就是不爽不能用 function 或是運算式, 堅持把這個加了進去。

一樣對照著 ebnf 看, ebnf 怎麼寫, 程式就怎麼寫, 難不倒你的。

一開始先判斷目前的 token 是不是 NAME (變數名稱), 再來的 token 是不是 (, 再來有點麻煩, 因為參數可以沒有, 若接下來的 token 是 ), 表示沒有參數, 這個就簡單了, parse 完成。

如果不是 ), 表示有參數, 看看是不是 function call 還是運算式, 再接著判斷是不是還有下一個參數 (L371), 再來看下一個 token 是不是 ',', 再來就和前面一樣, 看看是不是 function call 還是運算式, 我寫得很輕鬆, 你應該混亂了, 請慢慢欣賞, 不要心急, 平心靜氣一定看得懂, 在看不懂就出動 gdb 吧!

c_parser.cpp

 159 /*!
 160  * primary   : "(" expr ")" | NUMBER | IDENTIFIER | STRING | func_call
 161  */
 162 ASTNode* primary()
 163 {
 164   Token token = peek_token(); 
 165   if (is_func_call())
 166   {
 167     ASTNode *e = func_call();
 168     return e;
 169   }
 170   ...

 321 bool is_func_call()
 322 {
 323   Token t = peek_token();
 324   if (t.ast_type() == NAME)
 325   {
 326     t = peek_token(1);
 327     if (t.str() == "(") // func_call
 328       return true;
 329   }
 330 
 331   return false;
 332 }
 334 /// func_call: NAME '(' [ (expr | func_call)  { ',' (expr | func_call) } ] ')' // 這是左遞迴嗎?
 335 ASTNode* func_call()
 336 {
 337   ASTNode *fc = 0;
 338   Token t = peek_token();
 339 
 340   if (t.ast_type() == NAME)
 341   {
 342     fc = new ASTNode(func_call_token);
 343     fc->set_str(t.str());
 344 
 345     ASTNode *e=0;
 346     pop_token();
 347     t = peek_token();
 348     if (t.str() == ("("))
 349     {
 350       pop_token();
 351 
 352       //if((e = expr()) != 0)
 353       t = peek_token();
 354       if(t.str() != ")")
 355       {
 356 
 357         if (is_func_call())
 358         {
 359           e = func_call();
 360         }
 361         else
 362         {
 363           e = expr();
 364         }
 365 
 366         if (e)
 367           fc->add_child(e);
 368 
 369         Token t = peek_token();
 370 
 371         while (t.str() != ")")
 372         {
 373 
 374 
 375             if (t.str() == ",")
 376             {
 377               pop_token();
 378 
 379               if (is_func_call())
 380               {
 381                 e = func_call();
 382               }
 383               else
 384               {
 385                 e = expr();
 386               }
 387 
 388               if (e);
 389                 fc->add_child(e);
 390             }
 391             else
 392             {
 393               err("func_call: should ','", t.str());
 394             }
 395             t = peek_token();
 396         } 
 397 
 398       }
 399       else // function call passes no argument
 400       {
 401 
 402       }
 403 
 404       t = peek_token();
 405       if (t.str() == (")"))
 406       {
 407         pop_token();
 408       }
 409       else
 410       {
 411         err("func_call: should )", t.str());
 412       }
 413     }
 414     else
 415     {
 416       err("func_call: should (", t.str());
 417     }
 418   }
 419   else
 420   {
 421     err("func_call: should NAME", t.str());
 422   }
 423 
 424   return fc;
 425 }

https://github.com/descent/simple_compiler/blob/master/c_parser.cpp
source code:
git commit: 8fcfec025156ca9196c03433867fb4132acac0bd

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

學習編譯系統的心得

金字塔門檻

fig 1

fig 2

fig 3

fig 4

fig 5

fig 6

fig 7

fig 8

fig 9

fig 10

20170128 是 2017 的農曆新年 (大年初一), 就來點溫馨的學習文章好了。

在看了知乎《如何学习编译原理？》這個問題後, 我寫下這篇 (由於實名認證, 現在我已經無法在知乎 po 文), 這是個好問題, 光是發現怎麼學習編譯原理就花了不少時間, 也買了不少書, 但每本書的實作都不同, 讓學習更難了。希望這篇文章能幫助和我一樣想學習編譯器的朋友, 也紀錄著我自己的學習之路。

os 和 compiler 大概是資工本科功夫裡頭基本中的基本, 但基本可不代表他們很簡單, 一定有很多人想要掌握這兩塊, 也一定很多人失敗了, 我也曾經失敗幾次後再度挑戰, os 我已經略有小成, 編譯技術則剛開始。這篇紀錄我如何找到學習編譯原理的方法, 希望對有興趣的人有所幫助。

有人說編譯器很簡單, 有人說很難, 我是認為很難的那一派別, 也許每個人程度都不同, 所以認定方式也不同, 我之前完成了一個小型 os kernel, 但對我學習編譯器不太有幫助, 在開始的時候, 我還是覺得很難, 而就算是我完成了一個玩具型的 c 編譯器的現在, 我也還是覺得很難。

Re: [問卦] 有沒資工系畢業門坎 沒"自己的編譯器"這要求?

這篇回文也和編譯器相關, 很豐富。

真的有決心要學習編譯原理的話, 請從金字塔門檻圖一步步從底層爬上來, 所有的東西都手工打造, 絕對不要使用 flex/bison 之類的工具, 但如果是工作上的專案, 我是贊成使用這些工具的, 畢竟能減輕工作份量, 沒理由不使用的。

我似乎忽略了 debugger, debugger 嚴格來說不應歸類在編譯系統, 但實際上沒有 debugger 是很難除錯的, 要「全端」 (full stack) 地學習編譯系統, 應該要補上 debugger 的, 而 debugger 的難度, 我覺得應該是最難的。

在我最後更新本篇文章時 (20170609), 我來到了 assembler 階段, 真是令人開心, 只剩下 linker 了呢, 如果再完成 linker, 就可以完整體驗編譯原理了。當然, 在學習過程我簡化不少東西, 以下便是我的學習心得。

若以不那麼嚴謹的方式來說, 其實我已經會寫 compiler, assembler, linker, loader, 剩下 debugger。

買書一向是我的主要學習方式, fig 1 是一開始我擁有的書, 翻閱之後卻發現有一種無所適從的感覺, 每本書好像都寫的不錯 (我會過濾爛書, 但其實在繁體中文的世界沒什麼可以挑), 但又好像有什麼不足之處, 總之我沒學成。

fig 2 ~ fig 10 是我在進入簡體中文世界後所購得的書籍, 有了新武器後, 201604 我再次挑戰編譯器這個題目, 一樣感到困難, 沒有因為這些新武器而得到救贖。和學習寫 os kernel 完全不同, 我幾乎只靠 2 本書, 就可以寫出 os kernel 了, 但買了這麼多編譯器的書, 卻還是覺得困難, 找不到適合自己的書。

再繼續堅持下去後, 從中摸索如何學習編譯器就花了不少時間, 打定學習方式後, 慢慢有了進步。

學習重點一樣是簡化再簡化, 但要怎麼簡化就是學問了。

買的書中有些是實作 pascal (fig 1 右下那兩本), 有些是用 java 來實作編譯器, 但我想要用 c++ 來實作 c 語言編譯器, 其實是想寫 c++ 編譯器, 但 c++ 太複雜, 惦惦自己的斤兩, 退一步實作 c 編譯器好了。而選擇 java 實作的書是無奈之舉 (不是我沒注意到, 就是需要其內容), 我需要該書裡頭的知識, 所以只能認了, 事實上, 書單中只有一本是用 c++ 實作編譯器。

而買的書一定要有完整的範例程式, 絕對不要買理論型的書籍 (對, 就是在說那本), 對於初學者來說, 絕對不可能靠理解理論來完成編譯器, 編譯器是很難的程式, 在真實世界上, 也僅有少數人有能力寫出來。沒有一個範例在那邊讓我們參考,不是一個有效率的學習方式。

而事實上, 我發現書中對於講解程式碼的部份都很薄弱, 幾乎都要自己去追蹤這些程式碼, 才能看懂在寫什麼, 不怪作者們, 因為要怎麼講清楚這些程式碼還真的蠻難的。這應該是這類型的程式一般人很少寫過, 所以很陌生, 幸運的是, 努力追蹤這些程式碼一段時間後, 就會習慣了。

再來是要實作那個語言? 當然是實作你有在用或是喜歡的語言, 如果你喜歡 python, 那實作 python 絕對比實作你不會的 pascal 還能引起你的興趣, 我根本沒在用 pascal, 怎麼可能有興趣去實作 pascal。動力是很重要的, 因為跌跤的時間會佔了很大一部份, 沒有繼續前進的動力, 很容易就放棄了, 而興趣就是你源源不絕的動力來源。

再來是 c 很複雜, 有辦法全部實作她嗎? 可能可以, 但在 lexer 就得花上不少時間, parser 可能要更久, 像以下的宣告:

void (*f[10]) (int, int);
char (*(*x())[]) ();
char (*(*x[3])())[5];

要付出不少時間來實作, 而一開始的我, 也沒有能力可以處理這種複雜的 ebnf。

我的重點在實作整個編譯流程:

1. lexer
2. parser
3. AST
4. C preprocessor
5. interpreter
6. 輸出組合語言
7. 實作 assembler
8. 實作 linker
9. 實作 virtual machine
10. 實作 jit
11. 實作 GC

這些我都想跑過一遍, 簡化這些是很重要的, 要怎麼縮短時間, 又能完整的走過一遍。編譯系統並不是只有編譯器一項, 還有很多很多的東西一起組合起來的, 大部份的書都只著重在編譯器上, 其實是遠遠不夠的, 這樣對於編譯系統的技術就會少了一些拼圖, 神功未成, 有了死角, 豈不可惜。

我喜歡研究微小的整體, 而不是某個部份的深入, 「麻雀雖小, 五臟俱全」, 可以用來形容我的學習風格。

所以我把 c 簡化成只實作:

• if/else, while, function call
• type 只支援 char, int

當然還有指標, c 語言沒實作指標還能算是 c 嗎? 簡化時有些可以省略, 有些不行, 指標就是不能省略的部份, 別小看這些簡化後的目標, 乍看之下很簡單, 一寫下去知道, 難度還是很高的。

所以最後實作的 simple c interpreter 是有支援指標的。疑, 不是要寫編譯器嗎? 怎麼變成直譯器了, 哎呀! 功力不夠, 只好先改變目標。Joel 的邊走邊開槍你沒讀過嗎? 不過就算是 interpreter 也是存在某種難度的。

再來是 lex, parser 都一定要自己實作, 絕對不用 flex, bison, 要練習怎麼可以偷懶呢? 這些都要自己做。但如果是工作上的專案, 我建議使用 lex, bison, 這會大幅減低程式的負擔, 也會提高整體的正確性, 更擁有方便的彈性。

再來我選擇要產生 AST, 不產生 AST 的作法也有, 但我要實作 AST, 這部份我在《两周自制脚本语言》獲得此技能, 雖然這本書是使用 java, 而我是用 c++, 但這本書的 java code 依然給了我很好的參考, 讓我得以突破 lexer, parser, AST 這三道關卡。

實作出 fig 21, fig 22 的 AST 時, 那種興奮感一定很多人都可以體會。我建議最好可以把 AST 具象化, 若不能很清楚的看到自己建立的 AST, 一定會覺得很模糊, 有一種我真的把 AST 建對了的疑惑。這邊可能會是第一個卡關的地方。tree 可是一個很難搞的資料結構, 要怎麼確定建立的 AST 是對的呢? 還有比把它印出來更可靠的方法了嗎?

再來的 interpreter 我就沒靠相關的 compiler 書籍了, 因為我在 SICP 4.1 中獲得了這個技能。

在 SICP 我實作了 4.1 的 scheme (一樣用 c++ 實作), 所以接下來的 eval 我靠自己的能力就可以完成。這可不是件容易的事情, 在這裡是可能會卡住的第二關。

實作 AST 可以怎麼開始呢? 因為總共有:

list 1

1. 四則運算
2. 使用變數
3. if/else
4. while
5. function declare/definition
6. function call

要處理。

為什麼要搞定這些, 因為有了這些結構, 實作出來的簡化 c 語言就不再是玩具, 而是真的可以用來寫程式, 你總不希望辛苦搞定的語言, 什麼都不能做吧, 為此目的我還實作出 printf, 讓這個 interpreter 更有實際功用, 當可以用 recursive 算出 5! 時, 超興奮 der。

parser 要怎麼進行才能減低學習負擔呢? 先從《四則運算》開始, 能把 1+2*(9-2) 的 AST 產生出來, 就已經邁進了一大步, 很有成就感。而且在這樣的拆解後, 難度下降, 也可以用下班後的少數時間來實作, 不需要一個很大塊很完整的時間來學習。而當完成《四則運算》後, 你就會尊敬每個平台上都有的計算機程式, 這可不是容易寫的程式哦! 我不知道寫了多少張的 A4 紙, 就只是為了描述這個《四則運算》的 AST, 到寫文章的這個時候, 我已經對 AST 有所感覺了。

再來就照 list 1 的順序慢慢實作, 我就是這樣把所有功能完成的。

我買的書籍中, 有些有很嚇人的理論和資料結構, 理論很難懂, 資料結構很難實作, 很有可能實作這些資料結構就得花不少時間, 但我沒有用到這些還是把玩具等級的 interpreter 做出來了。

記得你是來學習寫編譯程式, 不是來練習資料結構的。雖然我用的是 c++, 但也沒用到特別的東西, 只用到 if/else, while, function call, 一點 class, vector, stirng, map, 也沒用到多型, 但這樣的武器就已經足夠完成一個玩具版的練習了。在提醒一次, 記得你是來學習寫編譯程式, 不是來把玩 c++ 的。

你還要把時間花在精巧的 c++ 語言特性嗎? 不, 我喜歡把時間用在實作某個東西上, c++ 語言特性有他的好處, 但不一定是必須的, 你能寫出很酷的或是讓人迷惑的 c++ 程式碼, 但我可以寫編譯器, 而裡頭只用到 if/else, function call, while loop, 沒有什麼特別的 c++ 語法, 那個厲害呢? 吾 ... 都很厲害, 看怎麼選擇而己, 當然如果可以兩個都掌握那是最棒的。

雖然寫程式很有趣, 但世界上還有很多有趣的事情, 我希望能把時間也分點給這些有趣的東西, 要能同時掌握這兩項可能要很久之後了。

fig 21

fig 22

我目前走到了《產生 asm》這塊 (在我更新本文時, 我已經在寫組譯器, 可以讓 gnu ld link 出 elf 執行檔, 不過, 我在這裡停止開發了), 還有很多部份需要努力, 而且愈來愈難。我用一樣的方式來學習《產生 asm》, 一開始還是處理《四則運算》, 不過其難度比我想像中的要難很多, code generator 比 interpreter 難了 5 倍以上, 我刻意不看書上的實作, 完全自己想, 還真的有點吃不消, 方法可能不是最好, 但這可都是我自己想出來的哦! 這樣的成就感, 實在是令人滿足, 作夢都會笑。實在想不出方法, 再來查閱書籍。

在學生時代把這些完成是比較好的, 但我在想, 如果是學生時代的我, 有能力完成定下的這些目標嗎? 大概不行, 那時候可能沒這麼多的學習資訊, 我的程式功力也很差 (這當然不是說我現在就比較好), 直接挑戰編譯器可能太難了, 對於組合語言也不熟悉, 那怎麼可能寫得出 code generator 呢? 可能連 lexer, parser 的狀態機都能難倒我, 程式真的就像砍柴一樣, 一直砍, 一直砍, 就能找到訣竅。但如果在學生時代努力過, 就算沒成功, 也不是壞事。

把這些都簡化實作過一次, 就相當於走過一輪了, 有興趣的部份再去深入。

有些書是用 LLVM 來打造自己的編譯器, 我一樣建議真正要學習的朋友不要使用 LLVM, 這樣會漏掉一些拼圖, 但如果是工作上的專案, 我是很贊成使用的, 正確性高, 有最佳化的功能, 開發速度快。

不過學習最忌諱速度快, 真正專業的東西是沒有捷徑的, 只能像螞蟻一樣, 一次爬一小步, 慢慢的累積這些專業, 一旦掌握了好幾個部份, 再把他們組合起來, 擁有這些深厚的基礎, 就是自己的優勢所在。

現在有些速食課程, 號稱在短短時間就可以怎麼樣, 也許你真的在短時間完成了什麼, 但如果要繼續下去, 該花的時間還是要補回來的, 我不相信有什麼快速學習方法。『真正有用的知識, 都不是那麼容易獲得的。』

ref:
寫自己的程式語言 (For Rubyist) 一文, 作者是文組學生, 卻開發出自己的程式語言, 資工本科系還不見得可以作到這件事情, 真是不簡單。參考其《自學歷程 (1)》

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 它, 要怎麼紀錄這樣的型別, 難倒我。

compiler [5] eval printf

以忍制己情，以恕制人情。

已經可以 eval 運算式了, 再來還得要有一個 output function, 在 c 上頭還有比 printf 更好的選擇嗎? 我決定要實作 printf。

ec.c

 1 
 2 int a;
 3 
 4 int f2(int i)
 5 {
 6   1+2;
 7   return 2+5+i;
 8 }
 9 
10 int main()
11 {
12   int x,y;
13   int a;
14   char *p;
15 
16   p="point strint";
17 
18   a=99;
19   printf("a: %d\n", a);
20 
21   y=2;
22   x = f2(y+1);
23 
24   printf("f2(): %d, %s, y=%d, p=%s\n", x, "test_string", y, p);
25 }

L24 可以正常 eval 的話, 就可以有輸出功能了, 這樣會讓這個 c interpreter 更好用, 可以把輸出結果印出來。

我一開始遇到的困難是不定個數參數怎麼傳給 printf?

ex.cpp

1 vector<string> args;
2 if (args.size() == 2)
3   printf(args[0].c_str(), args[1].c_str());
4 else if (args.size() == 3)
5        printf(args[0].c_str(), stoi(args[1]), args[2].c_str());

這樣我怎麼窮舉的完呢?

後來用了一個不太高明的方法解決了。呼叫 unix tool printf 來解決這問題。將 args 產生成 printf 的指令, 透過 system 執行。

p.cpp

 1 
 2 int main(int argc, char *argv[])
 3 {
 4   vector<string> args;
 5 
 6   string fmt = R"("test %d %s\n")";
 7   string p_str = tree_string(fmt);
 8 
 9   args.push_back(fmt);
10   args.push_back("123");
11   args.push_back("string_test");
12 
13   string cmd=R"(printf "My name is \"%s\".\nIt's a pleasure to meet you
14 %d.\n" "John" )";
15   string cmd_s{"printf "};
16   for (auto &i : args)
17   {
18     cmd_s += i;
19     cmd_s += " ";
20   }
21   cout << "cmd_s: " << cmd_s << endl;
22 
23   cmd+="25";
24   system(cmd.c_str());
25   system(cmd_s.c_str());
26   return 0;
27 }

可攜性如何呢? mac osX 沒問題, unix like 嘛! windows 呢? 別怕, printf 指令有 win32 版本, 所以還是有相當的可攜性。

這是很大的一個進步, 依靠語言本身自己印出結果, 不需要透過 interpreter 的程式印出運算結果。

再來是指標的問題, 我要怎麼印出指標呢? 在我實作出指標後 (雖然是 interpreter, 我還是想實作指標, 沒有指標, 就不能算是 c 了), 我想印出指標, printf 沒有支援 %p, 我耍了一點小心機, 將 %p 轉成 %x, 把指標的值順利印出。

雖然我在開始寫這個程式後, 陸續又買進不少編譯器的書, 但通過 lexer, parser, AST 的試鍊後, 幾乎都可以靠著自己的想法實作出目前的成果, 不在需要閱讀書籍中的知識。似乎只要建立起 AST 後, 再來的事情就沒有那麼難了。目前最新的成果 (20160909) 已經可以產生 gas 的組合語言, 雖然只有很小很小的一部份, 但已經沒有我開始寫的那種困難感了, 難度從一開始的 100 降低到 20 左右, 已經是可以靠著我自己的想法來實踐。自己土炮的作法也許和理論/專業的作法不同, 依然是玩具等級, 但最重要的是「這是我自己想出來的哦!」, 這比從書上獲得作法還更有意義。

interpreter 暫時告個段落, 我要向產生 machine code 邁進, 這是另外一個門檻, 我沒有做語意分析, 比起語意分析, 我更想先產生 machine code, 能把 c 程式碼轉成 machine code 的功能, 酷到讓我忍不住要先實作她。