語法樹

2021-03-22
#algorithm
筆記

前言

最近在玩編譯器的實作，裡面有提到語法樹，正好是我國中時看到但是無法實作的東西，就來填自己以前的坑囉。

開頭問題

實作出可以四則運算的計算機。

分析

四則運算必須考慮到$+$, $-$, $\times$, $\div$的運算優先度，還有()的使用。
乍看之下很複雜，但是可以感覺的某種遞迴的關係，例如:$5+9 \times 7$，可以看成$(5)+(9 \times 7)$，而右邊的括號又可以看成一個獨立的算式。
根據上面的規則可以將算式寫成樹，每個節點都是不同的運算子或數字。
Imgur
將左子樹跟右子樹算好後，再根據此節點的符號運算，就可以得到答案。

實作

實作上可以先將運算式拆成一個個token後，利用list串起來。
例如: $5 + 9 \times 7$，”5”是數字類型的token、”+”是符號類型，token的好處是可以以避免不必要的麻煩，例如空白、非法字元等。

token

首先定義token的種類:

1
2
3
4
5
6
typedef enum
{
    TK_sign, // 符號
    TK_num,  // 數字
    TK_EOL,  // end of line
} TokenKind;

token本體:

1
2
3
4
5
6
7
8
9
typedef struct Token Token;

struct Token
{
    TokenKind kind;
    Token* nex;
    int64_t num;
    char* str;
};

new一個token，並設定種類

1
2
3
4
5
6
7
8
Token* new_Token(TokenKind TKK, char* str)
{
    Token* tmp = (Token *)calloc(1, sizeof(Token));
    tmp->kind = TKK;
    tmp->str = str;
    tmp->nex = nullptr;
    return tmp;
}

將算式處理成token。

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
Token* tokenize(char* s)
{
    Token head; // head is a EMPTY token, and shouldn't be returned
    head.nex = nullptr;
    Token* tail = &head;

    while (*s)
    {
		// 跳過空白
        if (isspace(*s))
        {
            ++s;
            continue;
        }

		// 判斷是否是合法的符號，是自定義的函式
        if (isSign(*s))
        {
            tail->nex = new_Token(TK_sign, s++);
            tail = tail->nex;
            continue;
        }
		
		// 判斷是否是數字
        if (isdigit(*s))
        {
            tail->nex = new_Token(TK_num, s);
            tail = tail->nex;
            tail->num = strtol(s, &s, 10);
            continue;
        }

        printf("tokenize ERROR");
        exit(1);
    }

    tail->nex = new_Token(TK_EOL, s);
    tail = tail->nex;

    return head.nex;
}

語法樹

接著必須剖析一個「算式」的組成。
假設目前的算式已經處理好比$+$,$-$優先度高的運算，只剩下$+$,$-$，可以利用正規表達式定義:
expr = mul(+mul | -mul)*

而$\times$,$\div$的運算式，可以定義為:
mul = term(*term | \/term)*

最後()裡的算式定義為:
term = (num | (expr))

將上述的定義套用至語法樹的「生成」上(看code可能比較好理解)。

節點種類:

1
2
3
4
5
6
7
8
typedef enum
{
    NK_add, // 加法
    NK_sub, // 減法
    NK_mul, // 乘法
    NK_div, // 除法
    NK_num  // 數字
}NodeKind;

節點本體:

1
2
3
4
5
6
7
8
typedef struct node node;

struct node
{
    NodeKind kind;
    node *l, *r;
    int64_t val;
};

new Node，分成符號與數字類型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
node* new_node(NodeKind NKK, node* l, node* r)
{
    node* p = (node *)calloc(1, sizeof(node));
    p->kind = NKK;
    p->l = l;
    p->r = r;
    return p;
}

// 數字類型沒有左右子樹
node* new_node(NodeKind NKK, int64_t n)
{
    node* p = (node*)calloc(1, sizeof(node));
    p->kind = NKK;
    p->val = n;
    return p;
}

expr()生成函式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
node* expr()
{
    node* Node = mul(); // 遞迴判斷是否有乘除法運算

    while (true)
    {
        if (TK_isSign('+')) // 判斷目前的token是否是'+'
        {
            now_token = now_token->nex;
            Node = new_node(NK_add, Node, mul()); // 生成節點，將目前的node變為父節點，一路建構上去
        }
        else if (TK_isSign('-')) // // 判斷目前的token是否是'-'
        {
            now_token = now_token->nex;
            Node = new_node(NK_sub, Node, mul());
        }
        else 
            return Node;

    }
}

mul()生成函式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
node* mul()
{
    node* Node = term(); // 遞迴判斷是否是另一個expr或num

    while (true)
    {
        if (TK_isSign('*')) // 判斷目前的token是否是'*'
        {
            now_token = now_token->nex;
            Node = new_node(NK_mul, Node, term());
        }
        else if (TK_isSign('/')) // 判斷目前的token是否是'/'
        {
            now_token = now_token->nex;
            Node = new_node(NK_div, Node, term());
        }
        else
            return Node;
    }
}

term生成函式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
node* term()
{
    node* Node = nullptr;
    if (TK_isSign('('))
    {
        now_token = now_token->nex;
        Node = expr();
        if (!TK_isSign(')'))
        {
            printf("term ERROR");
            exit(1);
        }
        now_token = now_token->nex;
        return Node;
    }

    Node = new_node(NK_num, TK_takeInt()); // 不是另一個expr，直接生成數字節點
    now_token = now_token->nex;
    return Node;
}

計算語法樹的最終答案，每個運算結果都會放在stack裡，回傳後再進行運算，最終答案就是stack的頂端數字:

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
stack<int64_t> st;
void cal(node* p) // 呼叫時，應代語法樹的根
{
    if (p->kind == NK_num)
    {
        st.push(p->val);
        return;
    }

    cal(p->l); cal(p->r); // 計算左右子樹

    long b = st.top(); st.pop(); // 因為stack的性質，後面的運算元應該先pop出來
    long a = st.top(); st.pop();

    switch (p->kind)
    {
    case NK_add:
        st.push(a + b);
        return;

    case NK_sub:
        st.push(a - b);
        return;

    case NK_mul:
        st.push(a * b);
        return;

    case NK_div:
        st.push(a / b);
        return;

    default:
        break;
    }

    return;
}

(完整程式碼: https://github.com/OEmiliatanO/Project/tree/main/Syntax%20tree)

結語

語法樹比起中序轉後序還要複雜一點，但是寫起來很有規則；且如果要增加其他的運算子，例如開根號等，只需要多加幾行code就可以實現。
不只是四則運算，語法樹對於許多語法分析來說都很有用，例如編譯器。

我的這顆語法樹也是參考編譯器實作裡學來的。

Reference

https://koshizuow.gitbook.io/compilerbook/