*, /, ()を言語に追加するには演算子の優位順位を決めなければならない
– パーサの実装
入力はフラットなトークンの列で出力は入れ子構造を表す木にする
単純な生成規則
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()); } |