Linux C编译器从零开发三

AST语法树

BNF抽象

expr       = equality
equality   = relational ("==" relational | "!=" relational)*
relational = add ("<" add | "<=" add | ">" add | ">=" add)*
add        = mul ("+" mul | "-" mul)*
mul        = unary ("*" unary | "/" unary)*
unary      = ("+" | "-")? primary
primary    = num | "(" expr ")"

AST构建

#include "chibicc.h"static Node *expr(Token **rest, Token *tok);
static Node *equality(Token **rest, Token *tok);
static Node *relational(Token **rest, Token *tok);
static Node *add(Token **rest, Token *tok);
static Node *mul(Token **rest, Token *tok);
static Node *unary(Token **rest, Token *tok);
static Node *primary(Token **rest, Token *tok);static Node *new_node(NodeKind kind) {Node *node = calloc(1, sizeof(Node));node->kind = kind;return node;
}static Node *new_binary(NodeKind kind, Node *lhs, Node *rhs) {Node *node = new_node(kind);node->lhs = lhs;node->rhs = rhs;return node;
}static Node *new_unary(NodeKind kind, Node *expr) {Node *node = new_node(kind);node->lhs = expr;return node;
}static Node *new_num(int val) {Node *node = new_node(ND_NUM);node->val = val;return node;
}// expr = equality
static Node *expr(Token **rest, Token *tok) {return equality(rest, tok);
}// equality = relational ("==" relational | "!=" relational)*
static Node *equality(Token **rest, Token *tok) {Node *node = relational(&tok, tok);for (;;) {if (equal(tok, "==")) {node = new_binary(ND_EQ, node, relational(&tok, tok->next));continue;}if (equal(tok, "!=")) {node = new_binary(ND_NE, node, relational(&tok, tok->next));continue;}*rest = tok;return node;}
}// relational = add ("<" add | "<=" add | ">" add | ">=" add)*
static Node *relational(Token **rest, Token *tok) {Node *node = add(&tok, tok);for (;;) {if (equal(tok, "<")) {node = new_binary(ND_LT, node, add(&tok, tok->next));continue;}if (equal(tok, "<=")) {node = new_binary(ND_LE, node, add(&tok, tok->next));continue;}if (equal(tok, ">")) {node = new_binary(ND_LT, add(&tok, tok->next), node);continue;}if (equal(tok, ">=")) {node = new_binary(ND_LE, add(&tok, tok->next), node);continue;}*rest = tok;return node;}
}// add = mul ("+" mul | "-" mul)*
static Node *add(Token **rest, Token *tok) {Node *node = mul(&tok, tok);for (;;) {if (equal(tok, "+")) {node = new_binary(ND_ADD, node, mul(&tok, tok->next));continue;}if (equal(tok, "-")) {node = new_binary(ND_SUB, node, mul(&tok, tok->next));continue;}*rest = tok;return node;}
}// mul = unary ("*" unary | "/" unary)*
static Node *mul(Token **rest, Token *tok) {Node *node = unary(&tok, tok);for (;;) {if (equal(tok, "*")) {node = new_binary(ND_MUL, node, unary(&tok, tok->next));continue;}if (equal(tok, "/")) {node = new_binary(ND_DIV, node, unary(&tok, tok->next));continue;}*rest = tok;return node;}
}// unary = ("+" | "-") unary
//       | primary
static Node *unary(Token **rest, Token *tok) {if (equal(tok, "+"))return unary(rest, tok->next);if (equal(tok, "-"))return new_unary(ND_NEG, unary(rest, tok->next));return primary(rest, tok);
}// primary = "(" expr ")" | num
static Node *primary(Token **rest, Token *tok) {if (equal(tok, "(")) {Node *node = expr(&tok, tok->next);*rest = skip(tok, ")");return node;}if (tok->kind == TK_NUM) {Node *node = new_num(tok->val);*rest = tok->next;return node;}error_tok(tok, "expected an expression");
}Node *parse(Token *tok) {Node *node = expr(&tok, tok);if (tok->kind != TK_EOF)error_tok(tok, "extra token");return node;
}

代码生成 

#include "chibicc.h"static int depth;static void push(void) {printf("  push %%rax\n");depth++;
}static void pop(char *arg) {printf("  pop %s\n", arg);depth--;
}static void gen_expr(Node *node) {switch (node->kind) {case ND_NUM:printf("  mov $%d, %%rax\n", node->val);return;case ND_NEG:gen_expr(node->lhs);printf("  neg %%rax\n");return;}gen_expr(node->rhs);push();gen_expr(node->lhs);pop("%rdi");switch (node->kind) {case ND_ADD:printf("  add %%rdi, %%rax\n");return;case ND_SUB:printf("  sub %%rdi, %%rax\n");return;case ND_MUL:printf("  imul %%rdi, %%rax\n");return;case ND_DIV:printf("  cqo\n");printf("  idiv %%rdi\n");return;case ND_EQ:case ND_NE:case ND_LT:case ND_LE:printf("  cmp %%rdi, %%rax\n");if (node->kind == ND_EQ)printf("  sete %%al\n");else if (node->kind == ND_NE)printf("  setne %%al\n");else if (node->kind == ND_LT)printf("  setl %%al\n");else if (node->kind == ND_LE)printf("  setle %%al\n");printf("  movzb %%al, %%rax\n");return;}error("invalid expression");
}void codegen(Node *node) {printf("  .globl main\n");printf("main:\n");gen_expr(node);printf("  ret\n");assert(depth == 0);
}

#include "chibicc.h"int main(int argc, char **argv) {if (argc != 2)error("%s: invalid number of arguments", argv[0]);Token *tok = tokenize(argv[1]);Node *node = parse(tok);codegen(node);return 0;
}

 ./chibicc "1 + -2* 3 -(4+5/6) > tmp.s
cc -o tmp tmp.s./tmpecho $?247

---

创作不易，小小的支持一下吧！