wei's Blog
0%

自幹編譯器心得

發表於 更新於 分類於 Disqus：

前言

最近突然發現忘記C語言的規則了，所以就把以前在PTT上發的廢文整理一下，改個排版，讓自己更好閱讀
當初這篇文章是我畢業專題那個很像論文的東東一直生不出來（抱歉，我真的不太會寫文章QQ），拖延症又發作，摻雜了當時已經完成的部份，才寫出來的
雖然現在畢業專題已經完成（我有整理放在這裡），但這篇文章還是有很多沒有寫進去的東西，作為筆記，讓我記得當時在做什麼還是很有價值的

正文

小弟私立科大學店生，誤信對岸知乎 程序員的三大浪漫

抄了jserv大大的MazuCC，然後到處抄，什麼都抄一點，然後再加上自己的劣化，最後生出了一陀不三不四的東西，然後我還拿去騙惹畢業專題

雖然我八成以後不會再寫編譯器惹，但還是整理一下抄編譯的流程八
首先實作編譯器很簡單，分三個部份，詞彙分析器、語法分析器、程式碼產生器

詞彙分析器

概念的部份可以看這個
10420陳煥宗教授計算機程式設計二_第6A講 編譯器概念

完全不懂的情況下「編譯器概念」這一節能大概知道什麼是編譯器
然後看完這個，詞彙分析器大概就完成了，反正我的程式最後開放四個函式

1
2
3
4
int is_punct(token *tok, int c); /*判斷tok是否是punct且符合c*/
void unget_token(token *tok);    /*將tok還回去*/
token *peek_token(void);         /*預先得知下個token，但不讀入*/
token *read_token(void);         /*讀入下個token*/

細節和功能邊做邊想就好了

語法分析器

然後語法分析器，可以跳著看和邊看邊睡對岸的開放式課程，作為參考
编译原理 — 中科大

然後語法當然不可能自己設計，所以繼續抄，有人已經整理好了C語言的BNF
既然是從The C programming language, 2nd整理出來的，那應該和C89差不遠
The syntax of C in Backus-Naur Form

再來就是看jserv大大的MazuCC
可以跪著看，如果膝蓋會痛，可以休息一下再繼續跪

真的毫不誇張！想學C、jserv有你所不知道的C語言可以學習；想學作業系統，jserv有mini-arm-os可以入門；想學編譯器，jserv就有MazuCC可以參考。
而且都有簡單到我這個學店生都能看懂的版本，根本是神！！！
當初在煩惱編譯器到底要怎麼寫的時候，jserv大大就剛好放出這個專案。感恩jserv，讚嘆jserv！

我自己寫的編譯器，list.h直接抄，typedef struct __Ast也直接抄
其他部份雖然名義上沒抄，但實際上大概就像寫數學想半天寫不出來，然後去看後面解答一樣

如果前面看開放式課程沒有睡的很死，那應該會知道，裡面實作解析運算子的方法是LR的運算子優先序解析器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static int priority(const Token tok)
{
    switch (get_punct(tok)) {
    case '[':
    case '.':
    case PUNCT_ARROW:
        return 1;
    case PUNCT_INC:
    case PUNCT_DEC:
        return 2;
    case '*':
    case '/':
        return 3;
    case '+':
    case '-':
        return 4;
    case PUNCT_LSHIFT:
    case PUNCT_RSHIFT:
        return 5;
    case '<':
    case '>':
        return 6;
    case '&':
        return 8;
    case '|':
        return 10;
    case PUNCT_EQ:
        return 7;
    case PUNCT_LOGAND:
        return 11;
    case PUNCT_LOGOR:
        return 12;
    case '?':
        return 13;
    case '=':
        return 14;
    default:
        return -1;
    }
}

因為LR解析器我從來都沒有看懂過，所以去瞄了一眼放在MazuCC簡介的8cc的原始碼
好的，是LL的遞迴下降解析器

基本上就是把BNF的C語法直接轉成程式碼，一層一層的遞迴下去
恩，看的懂，那就選這個八，所以全部改寫成遞迴下降的形式(原來連這個都是抄的)

像是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<conditional-expression> ::= <logical-or-expression>
                           | <logical-or-expression> ? <expression> :
<conditional-expression>

<logical-or-expression> ::= <logical-and-expression>
                          | <logical-or-expression> ||
<logical-and-expression>

<logical-and-expression> ::= <inclusive-or-expression>
                           | <logical-and-expression> &&
<inclusive-or-expression>

<inclusive-or-expression> ::= <exclusive-or-expression>
                            | <inclusive-or-expression> |
<exclusive-or-expression>

<exclusive-or-expression> ::= <and-expression>
                            | <exclusive-or-expression> ^ <and-expression>

<and-expression> ::= <equality-expression>
                   | <and-expression> & <equality-expression>

<equality-expression> ::= <relational-expression>
                        | <equality-expression> == <relational-expression>
                        | <equality-expression> != <relational-expression>

給個圖

20210516032823683_30358

就能寫成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
static Ast *conditional_expr()
{
    Ast *ast = logical_or_expr();
    token *tok = read_token();

    if(is_punct(tok, '?')) {
        Ast *r = expr();
        token *rtok = read_token();
        if(!is_punct(rtok, ':'))
            error("next is ':' ");
        Ast *l = conditional_expr();
        r = ast_binop(rtok->punct, r, l);

        return ast_binop(tok->punct, ast, r);
    }
    unget_token(tok);

    return ast;
}

static Ast *logical_or_expr()
{
    Ast *ast = logical_and_expr();
    token *tok = read_token();

    while(is_punct(tok, PUNCT_LOGOR)) {
        ast = ast_binop(tok->punct, ast, logical_and_expr());
        tok = read_token();
    }
    unget_token(tok);
    return ast;
}

static Ast *logical_and_expr()
{
    Ast *ast = inclusive_or_expr();
    token *tok = read_token();

    while(is_punct(tok, PUNCT_LOGAND)) {
        ast = ast_binop(tok->punct, ast, inclusive_or_expr());
        tok = read_token();
    }

    unget_token(tok);
    return ast;
}

static Ast *inclusive_or_expr()
{
    Ast *ast = exclusive_or_expr();
    token *tok = read_token();

    while(is_punct(tok, '|')) {
        ast = ast_binop(tok->punct, ast, exclusive_or_expr());
        tok = read_token();
    }

    unget_token(tok);
    return ast;
}

static Ast *exclusive_or_expr()
{
    Ast *ast = and_expr();
    token *tok = read_token();

    while(is_punct(tok, '^')) {
        ast = ast_binop(tok->punct, ast, and_expr());
        tok = read_token();
    }

    unget_token(tok);
    return ast;
}

static Ast *and_expr()
{
    Ast *ast = equality_expr();
    token *tok = read_token();

    while(is_punct(tok, '&')) {
        ast = ast_binop(tok->punct, ast, equality_expr());
        tok = read_token();
    }

    unget_token(tok);
    return ast;
}

static Ast *equality_expr()
{
    Ast *ast = relational_expr();
    token *tok = read_token();

    while(is_punct(tok, PUNCT_EQ) || is_punct(tok, PUNCT_NE)) {
        ast = ast_binop(tok->punct, ast, relational_expr());
        tok = read_token();
    }

    unget_token(tok);
    return ast;
}

484簡單很多

然後寫到這裡大概會發現，恩，全部都能用Lex和yacc完成呢～，原理一樣，成果一樣，不一樣的只是他是自動的，你是手動的（笑
這讓我陷入了某種無力感，隔了幾天接受了這個事實，然後繼續寫八
再來就是C語言的精隨指標和陣列拉

因為是精隨，所以你要懂一點點C語言才能寫出來
建議去看jserv大大的你所不知道的C語言系列講座
通常我是聽不懂，但只要開著直播，就能感受到經驗值往上漲

再來是《C專家編程》（Expert C Programming: Deep C Secrets）
因為英文很爛，所以我就看簡中版，可以當故事書看，輕鬆有趣
其中的一些故事可以對C的指標有更深入的理解（我有不少關於C語言的細節是參考這本書的，在我自幹編譯器時幫助很大）
看完之後有總結出一些規律拉，大概是這樣
dXluSNc

指標解析方向由中間開始，然後是右邊、左邊
不知道對不對拉，不過目前都還能當人肉cdecl還蠻爽的

然後你會發現一件事，就是關於type的問題
陣列在運算式中會強制表示為指標+偏移的形式，但偏移的單位是「指標指向type的大小」

例如：

1
int a[2][3];

在運算式中a[1][1]會表示成

1
*(*(a + 1) + 2)_

a就會加上sizeof(int) * 3 * 1個單位再加上sizeof(int) * 1 * 2個單位

也就是說在AST中表示成這樣

1
2
3
4
5
6
7
8
9
    *
    |
    +
   / \
  *   2
  |
  +
 / \
a   1

但是a和1相加的時候，可以明確知道a的type，但*和2相加的時候，就不知道a的type了

所以需要將type往上傳讓其他節點也擁有type的資訊，這樣在*與2相加的時候，就能知道
要偏移sizeof(int) * 1 * 2
那要如何將變數往上傳？喔，首先你要在運算的時候得知他當初宣告時的type，這需要一個symbol table，然後其他的我直接抄MazuCC了

這邊我後來看了程式碼，並不是當時寫的這樣，我的作法是每個節點都有type這個屬性，所以在做運算的時候，遵循C語言的轉型規則，以這裡舉例a的type是int，1的type是int，所以+節點的type就是int+int = int，不需要symbol table

程式碼產生器

然後就是程式碼產生器，我的程式碼產生器產生兩種目標語言
一種是Mano machine的組合語言，另一種是S-expression
Mano machine是一個教學用的計算機結構

為什麼選這個？因為我在舊書店買到了這本書阿

emCYranl

然後自己學了好幾章
我一直覺得組合語言不是人寫的，所以一直想要一個編譯器，難得有機會當然要做做看

然後是S-expression，這是我又聽信知乎
跑去買了SICP的中譯本，然後看了幾節SICP的影片，雖然最後還是沒學會，只學會了

BBHdDlNl

不過還是有所啟發，所以寫了S表達式的程式碼產生器
例如：

1
2
3
4
5
6
7
8
9
int main()
{
    int sum = 0;

    for(int i = 0; i < 10; i++)
        sum = sum + i;

    return sum;
}

可以產生出這樣的形式

1
2
3
4
5
6
7
(AST_FUNC (main (int))
          (AST_DECL (= ((int) sum) 0))
          (AST_FOR (INIT (AST_DECL (= ((int) i) 0)))
                   (COND (< ((int) i) 10))
                   (STEP (++ ((int) i)))
                   (BODY (= ((int) sum) (+ ((int) sum) ((int) i)))))
          (AST_RETURN ((int) sum)))

當然輸出的都是沒排版的，這時可以寫一個簡單的排版程式，會用到編譯器的相關知識

然後組合語言產生器嗎…就組合語言產生器阿
選的組合語言不要太簡單，像是我選的就太簡單的，很多指令要另外寫副程式

像是PUSH和POP要自己寫，還因為沒辦法把PC的值抓出來（只有呼叫副程式的只能碰到PC），所以要用很迂迴的手法才能抓到PC

然後也要有symbol table，因為你前面宣告，後面要用，除了要判斷變數是否存在，還要
知道區域變數與BP的偏移位置

再來要對lvalue有概念，第一次寫的時候以為我有概念，但寫出來的扣說我沒概念

重寫的時候我以為我有概念了，但寫到後來發現我好像搞錯了什麼？因為扣比第一次簡單
很多，而且快到deadline了，所以我現在還在想我搞錯什麼？

心得？

大概是這樣

這版的大大的程度應該都高我很多，我的學習歷程應該沒什麼參考性
如果有錯或冒犯到大大，請多見諒
會寫出來只是報告還沒做完+深夜情緒

做這個花了我七、八個月，前面幾個月常常陷入「我是誰？我要做什麼？」的狀態

然後中間遇到問題沒人可以問，只能自己找資料，也不知道找到的資料有沒有用（當然也是我個性的問題拉，不擅長社交，只在討論區問問題，強者我朋友遇到同樣的問題可能會直接私訊大大八:P）

還有沒人監督+沒明確截止日+糟糕的時間管理的隨意浪費時間

雖然對未來找工作沒什麼幫助，沒有強到不看學歷那就只看學歷，以我私立科大的學歷，第一份工作八成不到30K

業界最多工作還是web，對我這種能拿出來現的只有一點計算機冷知識和C語言，還是去學
比較實用的技術八:P

最後人還是要腳踏實地，不要被浪漫衝昏頭，雖然真的很浪漫就是了