企业官网建设流程全解析

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 ./tmp echo $? 247

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