自己动手写RISC-V的C编译器-02语法描述方法和递归下降解析

自己动手写RISC-V的C编译器-02语法描述方法和递归下降解析

本节增加对*、/、+、-、()运算的支持

使用生成规则表示运算符优先级

expr = mul("+" mul | "-" mul)*
mul  = num("*" num | "/" num)*

上面的表达式可以很容易的推导出对于对于运算1*2+3的语法树

由expr开始推导乘除法一定会在加减法的更下一层，所以很自然的得出乘法优先级大于加减法优先级。接下来我们对表达式进行拓展，使编译器能解析()、*、/

expr    = mul("+" mul | "-"mul)*
mul     = primary("*" primary | "/" primary)*
primary = num | "(" expr ")"

运算1*(2+3)的语法树如下：

数据结构设计

​ 通过上面的解释，我们发现将一串暂时无意义的字符串变成一个有规则的树形结构可以更好的表示算式的优先级，上面的树形结构就是所谓AST（抽象语法树） 所以解析算式我们采用AST

节点数据结构设计

和上一篇类似，我们依然采用enum类型来自动生成每个节点的类型编号。

typedef enum {
    
    nd_num,
    nd_add,
    nd_sub,
    nd_mul,
    nd_div,
} node_kind;

AST的节点就是一个二叉树的子节点，所以他应该包括三部分节点类型、左子树、右子树、如果是数字节点那还应该包括数字的值。

typedef struct node node;
struct node {
    
    node_kind kind;
    node *lch;
    node *rch;
    int val;
};

使用三个函数来构建二叉树的基本结构

node *new_node(node_kind kind) {
      // 用于构建一个子节点并返回该节点的指针
    node *nd = calloc(1, sizeof(node));
    nd->kind = kind;
    return nd;
}

node *new_binary(node_kind kind, node *lch, node *rch) {
      // 用域构建一个二叉树
    node *nd = new_node(kind);
    nd->lch = lch;
    nd->rch = rch;
    return nd;
}

node *new_num(int val) {
      // 构建一个数字子节点
    node *nd = new_node(nd_num);
    nd->val = val;
    return nd;
}

递归下降解析

构建AST

有了上面的运算规则就可以着手编写程序对算式进行解析了，首先先构建语法树。构建语法树需要用到三个函数expr、mul、primary分别用于解析算式、乘法算式、数字或括号表达式

node *expr(token **rest, token *tok);
node *mul(token **rest, token *tok);
node *primary(token **rest, token *tok);

下面通过代码具体看看如何构建出一颗AST

// expr = mul("+" mul | "-"mul)*
// mul = primary("*" primary | "/" primary)*
// primary = num | "(" expr ")"

node *expr(token **rest, token *tok){
    
    node *nd = mul(&tok, tok);
    
    while (true) {
    
        if (equal(tok, "+")) {
    
            nd = new_binary(nd_add, nd, mul(&tok, tok->next));
            continue;
        }
        
        if (equal(tok, "-")) {
    
            nd = new_binary(nd_sub, nd, mul(&tok, tok->next));
            continue;
        }
        
        *rest = tok;
        return nd;
    }
}

node *mul(token **rest, token *tok) {
    
    node *nd = primary(&tok, tok);
    
    while (true) {
    
        if (equal(tok, "*")) {
    
            nd = new_binary(nd_mul, nd, primary(&tok, tok->next));
            continue;
        }
        
        if (equal(tok, "/")) {
    
            nd = new_binary(nd_div, nd, primary(&tok, tok->next));
            continue;
        }
        
        *rest = tok;
        return nd;
    }
}

node *primary(token **rest, token *tok) {
    
    if (tok->kind == num) {
    
        node *nd = new_num(tok->val);
        *rest = tok->next;
        return nd;
    }
    
    if (equal(tok, "(")) {
    
        node *nd = expr(&tok, tok->next);
        *rest = skip(tok, ")");
        return nd;
    }
    
    error_at(tok->loc, "expexted an expression");
    return NULL;
}

通过遍历AST生成汇编代码

以以下AST为例

​ 先遍历到最右子节点，将3压入栈。之后遍历到节点2，并放入a0中，将3从栈中弹出并放入a1中。根据2和3的父节点类型选择相应的汇编代码，最后完成汇编代码的生成。

int depth;

void push() {
    
    printf(" addi sp, sp, -8\n");
    printf(" sd a0, 0(sp)\n");
    depth ++;
}

void pop(char *reg) {
    
    printf(" ld %s, 0(sp)\n", reg);
    printf(" addi sp, sp, 8\n");
    depth --;
}

void gen_expr(node *nd) {
    
    if (nd->kind == nd_num) {
    
        printf(" li a0, %d\n", nd->val);
        return;
    }

    gen_expr(nd->rch);
    push();
    gen_expr(nd->lch);
    pop("a1");

    switch (nd->kind)
    {
    
    case nd_add:
        printf(" add a0, a0, a1\n");
        return;
    case nd_sub:
        printf(" sub a0, a0, a1\n");
        return;
    case nd_mul:
        printf(" mul a0, a0, a1\n");
        return;
    case nd_div:
        printf(" div a0, a0, a1\n");
        return;
    default:
        break;
    }

}