[コンパイラ]文法記述方法と再帰下降構文解析

*, /, ()を言語に追加するには演算子の優位順位を決めなければならない

– パーサの実装
入力はフラットなトークンの列で出力は入れ子構造を表す木にする

単純な生成規則
expr = num(“+” num | “-” num)*
mul = num(“*” num | “/” num)*
具象構文木(concrete syntax tree)

再帰を含む生成規則
expr = mul(“+” mul | “-” mul)*
mul = primary(“*” primary | “/” primary)
primary = num | “(” epr “)”

再帰下降構文解析
expr = mul(“+” mul | “-” mul)*
mul = primary(“*” primary | “/” primary)*
primary = num | “(” epr “)”

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
typedef enum {
    ND_ADD,
    ND_SUB,
    ND_MUL,
    ND_DIV
    ND_NUM,
} NodeKind;
 
typedef struct Node Node;
 
struct Node {
    NodeKind kind;
    Node *lhs;
    Node *rhs;
    int val;
};
 
Node *new_node(NodeKind kind, Node *lhs, Node *rhs){
    Node *node = calloc(1, sizeof(Node));
    node->kind = kind;
    node->lhs = lhs;
    node->rhs = rhs;
    return node;
}
 
Node *new_node_num(int val) {
    Node *node = calloc(1, sizeof(Node));
    node->kind = ND_NUM;
    node->val = val;
    return node;
}
 
Node *expr(){
    Node *node = mul();
 
    for(;;){
        if(consume('+'))
            node = new_node(ND_ADD, node, mul());
        else if(consume('-'))
            node = new_node(ND_SUB, node, mul());
        else
            return node;
    }
}
 
Node *mul(){
    Node *node = primary();
 
    for(;;){
        if(consume('*'))
            node = new_node(ND_MUL, node, mul());
        else if(consume('/'))
            node = new_node(ND_DIV, node, mul());
        else
            return node;
    }
}
 
Node *primary(){
    if(consume('(')){
        Node *node = expr();
        expect(')');
        return node;
    }
 
    return new_node_num(expect_number());
}