当前位置:网站首页>自己动手写RISC-V的C编译器-02语法描述方法和递归下降解析
自己动手写RISC-V的C编译器-02语法描述方法和递归下降解析
2022-08-11 05:29:00 【YOUNIKOJIAO】
自己动手写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;
}
}
边栏推荐
- C语言实现猜数字(附带源码,可直接运行)
- mk file introduction
- 127.0.0.1 已拒绝连接
- Building a data ecology for feature engineering - Embrace the open source ecology, OpenMLDB fully opens up the MLOps ecological tool chain
- vscode插件开发——懒人专用markdown插件开发
- Tinker接入全流程---配置篇
- Day 73
- mk文件介绍
- Interpretation of the paper: GAN and detection network multi-task/SOD-MTGAN: Small Object Detection via Multi-Task Generative Adversarial Network
- mount命令--挂载出现只读,解决方案
猜你喜欢
随机推荐
构建面向特征工程的数据生态 ——拥抱开源生态,OpenMLDB全面打通MLOps生态工具链
Promise 中状态改变和回调执行先后顺序 和promise多次回调
The official website of OpenMLDB is upgraded, and the mysterious contributor map will take you to advance quickly
父子节点数据格式不一致的树状列表实现
Typescript学习日记,typescript从基础到进阶(第一章)
品优购项目实战笔记
127.0.0.1 connection refused
OpenMLDB + Jupyter Notebook:快速搭建机器学习应用
openlayer中实现截图框截图的功能
STM32-库函数-SetSysClock(void)函数解析-正点原子探索者
mk file introduction
Manufacturer Push Platform-Huawei Access
Use c language to implement tic-tac-toe chess (with source code, you can run it directly)
127.0.0.1 已拒绝连接
Day 79
mount命令--挂载出现只读,解决方案
Building a data ecology for feature engineering - Embrace the open source ecology, OpenMLDB fully opens up the MLOps ecological tool chain
mongoose连接mongodb不错,显示encoding没有定义
SearchGuard configuration
vscode插件开发——懒人专用markdown插件开发