手写一个brain***编译器

前言:自从7月份开始投递简历,就两个面试,心态直接炸裂了.... 然后不想在继续投递了,个人兴趣加上在宿舍因为大四也没课,所以就鼓捣一下开源和学一下rust...
因此这个是rust实现的..当然学习了rust后才发现以前的程序员的牛批之处,因为现在的语言,gc全部给你封装好了,还有很多地方error给放到运行时,导致我们开发时不用考虑很多东西,也就是现在转码选手为啥这么多的缘故,假如目前主流是rust,应该就没有这么多转码选手了吧...当然我也是转码选手哈哈
比如rust的gc:基于所有权的回收、如何解决悬空指针(NLL),match、RC计数等等,都挺有意思的,当然,rust给人劝退的地方就在于,新手基本写两行代码就是build一下,因为rust是一门静态强类型语言,在编译期对类进行检查,所以很多错误运行时是报不出来的,可能发现报错了告诉你哪儿错了你都束手无策,第二就是rust规则很多,但是如果熟悉了真的可以得心应手,很方便,而且很强大,第三就是网上资料太少了,java报个错一搜一堆,rust估计只有github的issue或者stackoverflow上面去找demo看了....

首先,整体代码量不大,也就300行左右,但是却完全实现了一个brain***编译器,其中有程序计数器、寄存器等概念,还有IR优化等等,估计科班入门可能就是看这玩意吧,可惜转码选手很难接触到这些,以下就是我的学习历程了~

大佬划走~

Brain***是一种简单且最小的图灵完备编程语言这种语言由八种运算符构成。

就像一条无限长的纸带,然后在上面打印brain***语法。

Brain*** 语法定义

字符 含义
> 指针加一
< 指针减一
+ 指针指向的字节的值加一
- 指针指向的字节的值减一
. 输出指针指向的单元内容(ASCII码)
, 输入内容到指针指向的单元(ASCII码)
[ 如果指针指向的单元值为零,向后跳转到对应的]指令的次一指令处
] 如果指针指向的单元值不为零,向前跳转到对应的[指令的次一指令处

比如,用brain***写一个hello world,是这样的:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

只能说以前的骨灰级程序员是真牛逼....

话不多说,直接实现一个brain***的编译器吧,里面会有简单的程序计数器和寄存器这些基本概念。

Brain*** OpenCode

由于brain***语言只有八种符号,所以就用一个enum来代替它的所有可能,格式:操作 = ASCII码

#[derive(Debug, PartialEq)]
pub enum OpenCode {
    SHR = 0x3E,     //shift the right >
    SHL = 0x3C,     //shift the left <
    ADD = 0x2B,     // +
    SUB = 0x2D,     // -
    PUTCHAR = 0x2E,     // ,
    GETCHAR = 0x2C,     // .
    LB = 0x5B,      // [
    RB = 0x5D,      // ]
}

然后接下来就需要将我们输入的brain***语法,解析成我们代码自定义的语法

impl From<u8> for OpenCode {
    fn from(u: u8) -> Self {
        match u {
            0x3E => OpenCode::SHR,
            0x3C => OpenCode::SHL,
            0x2B => OpenCode::ADD,
            0x2D => OpenCode::SUB,
            0x2E => OpenCode::PUTCHAR,
            0x2C => OpenCode::GETCHAR,
            0x5B => OpenCode::LB,
            0x5D => OpenCode::RB,
            /*
                Ascii code ranges from 0 to 255, and if it doesn't belong to these 8 characters,
                the rest of the program will simply exit without parsing
             */
            _ => unreachable!(),
        }
    }
}

pub struct Brain***Code {
    pub instrs: Vec<OpenCode>,          //指令  instruction
    pub jtable: std::collections::HashMap<usize, usize>,  // 加速代码执行 ,将语言的位置写在jtable中
}

impl Brain***Code {
    pub fn from(data: Vec<u8>) -> Result<Self, Box<dyn std::error::Error>> {
        let dict: Vec<u8> = vec![
            OpenCode::SHR as u8,
            OpenCode::SHL as u8,
            OpenCode::ADD as u8,
            OpenCode::SUB as u8,
            OpenCode::PUTCHAR as u8,
            OpenCode::GETCHAR as u8,
            OpenCode::LB as u8,
            OpenCode::RB as u8,
        ];
        let instrs: Vec<OpenCode> =  data
            .iter()
            .filter(|x| dict.contains(x))
            .map(|x| OpenCode::from(*x))
            .collect();

        let mut jstack: Vec<usize> = Vec::new();
        let mut jtable: std::collections::HashMap<usize, usize> = std::collections::HashMap::new();
        for (i, e) in instrs.iter().enumerate() {
            if OpenCode::LB == *e {
                jstack.push(i);
            }
            if OpenCode::RB == *e {
                let js = jstack.pop().ok_or("pop from empty list")?;
                jtable.insert(js, i);
                jtable.insert(i, js);
            }
        }
        Ok(Brain***Code {instrs, jtable})
    }
}

如上述代码所示,我们实现了一个instrs 和一个jtable,从

  • instrs:存储指令具体的值
  • jtable:当前指令和他在纸袋上处于的位置,由brain***语法可以看到,[]是成对出现的,所以需要一个kv存储临时记录[]的位置,提高解析速度,否则就要线性向前或者向后扫描,如果代码量较多的情况下速度就很慢。

以上就简单实现了一个brain***的语法解析器。

这是我项目的目录结构,其中准备了一些brain***的文件,打印hello world等例子

--brain***_jit_opcode
    -- src
        brain***_opcode.rs
        main.rs
    -- test
        hello_world.bf    // brain***文件

然后读取hello_world文件,打印出我们解析的opencode。

main.rs

fn main() -> Result<(), Box<dyn std::error::Error>> {

    let args: Vec<String> = std::env::args().collect();
    let data = std::fs::read(&args[1])?;
    let code = OpenCode::from(data)?;
    // let mut interpreter = Interpreter::new();
    // interpreter.run(data);

    println!("{:?}", code.instrs);

    Ok(())
}

执行 cargo build,然后 ./target/debug/main test/hello_world.bf,可以看到结果:

[ADD, ADD, ADD, ADD, 
 ADD, ADD, ADD, ADD, 
 LB, SHR, ADD, ADD, 
 ADD, ADD, LB, SHR, 
 ADD, ADD, SHR, ADD, 
 ADD, ADD, SHR, ADD, 
 ADD, ADD, SHR, ADD, 
 SHL, SHL, SHL, SHL, 
 SUB, RB, SHR, ADD, 
 SHR, ADD, SHR, SUB, 
 SHR, SHR, ADD, LB, 
 SHL, RB, SHL, SUB, 
 RB, SHR, SHR, PUTCHAR, 
 SHR, SUB, SUB, SUB, 
 PUTCHAR, ADD, ADD, ADD, 
 ADD, ADD, ADD, ADD, 
 PUTCHAR, PUTCHAR, ADD, 
 ADD, ADD, PUTCHAR, SHR, 
 SHR, PUTCHAR, SHL, SUB, 
 PUTCHAR, SHL, PUTCHAR, ADD, 
 ADD, ADD, PUTCHAR, SUB, SUB, 
 SUB, SUB, SUB, SUB, PUTCHAR, 
 SUB, SUB, SUB, SUB, 
 SUB, SUB, SUB, SUB, 
 PUTCHAR, SHR, SHR, ADD, 
 PUTCHAR, SHR, ADD, ADD, PUTCHAR]

然后我们发现一个问题,有些指令完全就是连着的,比如发现有ADD操作有些至少有三个连着,但是我们都得打出来,这完全就是一个冗余的操作,所以我们可以将它优化一下。

使用中间表示优化运行速度,IR

一个 ADD 操作符执行的是加 1 操作,那么如果相邻着十个连续的 ADD,便可以 ADD(10) 来表示。为此定义如下的中间语言表示。

中间语言(英语:Intermediate Language,IR),在计算机科学中,是指一种应用于抽象机器(abstract machine)的编程语言,它设计的目的,是用来帮助我们分析计算机程序。这个术语源自于编译器,在编译器将源代码编译为目的码的过程中,会先将源代码转换为一个或多个的中间表述,以方便编译器进行最佳化,并产生出目的机器的机器语言。

我们用一个枚举代表brain***中的几种中间表达形式

#[derive(Debug, PartialEq)]
pub enum IR {
    SHR(u32),
    SHL(u32),
    ADD(u8),
    SUB(u8),
    PUTCHAR,
    GETCHAR,
    JIZ(u32),   // jump if zero , 代替 [
    JNZ(u32),   // jump if not zero 代替 ]
}

然后需要将之前的opencode转换成我们所需要的中间表达式

impl Brain***Code {
    pub fn from(data: Vec<brain***_opcode::OpenCode>) -> Result<Self, Box<dyn std::error::Error>> {
        let mut instrs: Vec<IR> = Vec::new();
        let mut jstack: Vec<u32> = Vec::new();

        // 判断是否是连续相同的指令
        for e in data {
            match e {
                OpenCode::SHR => {
                    match instrs.last_mut() {
                        Some(IR::SHR(x)) => {
                            *x += 1;
                        }
                        _ => {
                            instrs.push(IR::SHR(1));
                        }
                    }
                }
                OpenCode::SHL => {
                    match instrs.last_mut() {
                        Some(IR::SHL(x)) => {
                            *x += 1;
                        }
                        _ => {
                            instrs.push(IR::SHL(1));
                        }
                    }
                }

                OpenCode::ADD => {
                    match instrs.last_mut() {
                        Some(IR::ADD(x)) => {
                            let (b, _) = x.overflowing_add(1);
                            *x = b;
                        }
                        _ => {
                            instrs.push(IR::ADD(1));
                        }
                    }
                }
                OpenCode::SUB => {
                    match instrs.last_mut() {
                        Some(IR::SUB(x)) => {
                            let (b, _) = x.overflowing_sub(1);
                            *x = b;
                        }
                        _ => {
                            instrs.push(IR::SUB(1));
                        }
                    }
                }
                OpenCode::PUTCHAR => {
                    instrs.push(IR::PUTCHAR);
                }
                OpenCode::GETCHAR => {
                    instrs.push(IR::GETCHAR);
                }
                OpenCode::LB => {
                    instrs.push(IR::JIZ(0));
                    jstack.push((instrs.len() - 1) as u32);
                }
                OpenCode::RB => {
                    let js = jstack.pop().ok_or("pop from empty list")?;
                    instrs.push(IR::JNZ(js));
                    let instrs_len = instrs.len();
                    match &mut instrs[js as usize] {
                        IR::JIZ(x) => {
                            *x = (instrs_len - 1) as u32;
                        }
                        _ => unreachable!()
                    }

                }
            }
        }


        Ok(Brain***Code {instrs})
    }
}

在重新编写main方法

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let args: Vec<String> = std::env::args().collect();
    let data = std::fs::read(&args[1])?;

        // 获取opencode码
    let code = brain***_opcode::Brain***Code::from(data)?;
    // 通过ir优化获取ir_code码
    let ir_code = Brain***Code::from(code.instrs)?;

        // 打印ir_code码
    println!("istrs; {:?}", ir_code.instrs);


    // let mut interpreter = Interpreter::default();
    // interpreter.run(data);

    Ok(())
}

可以看到结果是这样

[ADD(8), JIZ(29), SHR(1), ADD(4), 
JIZ(15), SHR(1), ADD(2), SHR(1), 
ADD(3), SHR(1), ADD(3), SHR(1), 
ADD(1), SHL(4), SUB(1), JNZ(4), 
SHR(1), ADD(1), SHR(1), ADD(1), 
SHR(1), SUB(1), SHR(2), ADD(1), 
JIZ(26), SHL(1), JNZ(24), SHL(1), 
SUB(1), JNZ(1), SHR(2), PUTCHAR, 
SHR(1), SUB(255), PUTCHAR, ADD(7), 
PUTCHAR, PUTCHAR, ADD(3), PUTCHAR, 
SHR(2), PUTCHAR, SHL(1), SUB(1), 
PUTCHAR, SHL(1), PUTCHAR, ADD(3), 
PUTCHAR, SUB(252), PUTCHAR, SUB(250),
PUTCHAR, SHR(2), ADD(1), PUTCHAR, 
SHR(1), ADD(2), PUTCHAR]

这样就会降低很多开销。

brain***解释器

我们之前只不过将其用我们自己的opencode把brain***语法表示出来,接下来就是让计算机去识别这些assci码。

所以需要编写我们的解释器

1.定义一条无限长的纸带,用来打印brain***语句

struct Interpreter {
    stack: Vec<u8>,
}

2.实现解释器具体逻辑

impl Interpreter {
    fn run(&mut self, data: Vec<u8>) -> Result<(), Box<dyn std::error::Error>> {
        let opcode_code = brain***_opcode::Brain***Code::from(data)?;
        let ir_code = Brain***Code::from(opcode_code.instrs)?;
        let ir_code_len = ir_code.instrs.len();
        let mut pc = 0;
        let mut sp = 0;

        loop {
            if pc >= ir_code_len {
                break;
            }
            match ir_code.instrs[pc] {
                IR::SHR(x) => {
                    sp += x as usize;
                    if sp >= self.stack.len() {
                        let expand = sp - self.stack.len() + 1;
                        for _ in 0..expand {
                            self.stack.push(0);
                        }
                    }
                }
                IR::SHL(x) => {
                    loop {
                        for i in 0..x {
                            if sp != 0 {
                                sp -= 1;
                            } else {
                                break;
                            }
                        }
                    }
                }
                IR::ADD(x) => {
                    // 防止溢出
                    self.stack[sp] = self.stack[sp].overflowing_add(x).0;
                }
                IR::SUB(x) => {
                    self.stack[sp] = self.stack[sp].overflowing_sub(1).0;
                }
                IR::PUTCHAR => {
                    std::io::stdout().write_all(&[self.stack[sp]])?;
                }
                IR::GETCHAR => {
                    let mut buf: Vec<u8> = vec![0; 1];
                    std::io::stdin().read_exact(&mut buf)?;
                    self.stack[sp] = buf[0];
                }
                IR::JIZ(x) => {
                    if self.stack[sp] == 0x00 {
                        pc = x as usize;
                    }
                }
                IR::JNZ(x) => {
                    if self.stack[sp] != 0x00 {
                        pc = x as usize;
                    }
                }
            }
            pc += 1;
        }


        Ok(())
    }
}

impl std::default::Default for Interpreter {
    fn default() -> Self {
        // 初始化,提供默认值
        Self { stack: vec![0; 1] }
    }
}

核心在于代码中实现的两个变量:pcsp

pc 程序计数器,代表当前的代码执行到哪儿了,执行到哪个指令了

sp 寄存器,代表当前代码在纸带上面的索引,也就是stack上面的指针

其他的具体代码,其实就是rust语法,按照brain***语义执行对应的逻辑

然后编写我们的main方法,如何对brain***代码执行编译执行。

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let args: Vec<String> = std::env::args().collect();
    let data = std::fs::read(&args[1])?;

    let mut interpreter = Interpreter::default();
    interpreter.run(data);

    Ok(())
}

build后执行./target/debug/main test/hello_world.bf 就可以看到输出的hello world了~

#后端开发#
技术面经+架构+八股 文章被收录于专栏

1. 关于当前公司所用技术架构(目前在某个短视频公司营销部门) 2. 关于个人之前接触的项目(存储、分布式、缓存) 3. 个人面经和之前的一块儿面试时的面经(核心部门 or ssp) 4. 个人简历模板 5. 手写的一些框架(时序数据库、编译器、hotring、亲缘性线程池等)

全部评论
航哥以前:rust有啥用吗? 航哥现在:手写编译器。
1 回复 分享
发布于 2022-09-05 18:14 吉林
大佬情况如何,有offer了吗😭
点赞 回复 分享
发布于 2022-08-30 16:08 广东

相关推荐

1、底层通信组件方案通信模式封装支持兼容多种通信模式普通消息模式:PUB/SUB(发布订阅)、PUSH/PULL(点对点通信)RPC&nbsp;模式:通过ZMQ_REP、ZMQ_REQ&nbsp;封装&nbsp;RPC&nbsp;功能RPC功能支持&nbsp;RPC&nbsp;方法的动态注册提供默认的&nbsp;RPC&nbsp;方法列表查询支持&nbsp;RPC&nbsp;调用2、Master模块(实现思路:类似ROS1&nbsp;Master功能,&nbsp;更轻量化)背景:分布式大模型系统中,多个节点(如llm/vlm,&nbsp;asr,tts,&nbsp;camera,yolo)需要动态发现彼此并高效通信,外部用户可以动态管理节点内任务调度​​节点注册与发现​实现轻量化内存kv缓存数据库:存储节点元信息;并提高sql查询接口,供节点动态通信节点启动时向Master模块注册,上报自身元信息;节点通信时自动匹配动态任务调度分配设计用户请求-任务匹配机制:外部用户仅封装简易数据包请求,可实现动态控制各个模块(启停/llm推理等)3、Channel模块封装上层发布-订阅(PUB/SUB)和点对点通信(PUSH/PULL)混合通信模式设计闭包,通过闭包将​​网络层​​(ZeroMQ)与​​业务层​​(用户回调)解耦,同时隐式维护了通信上下文状态。4、Infra基础架构模块rpc分布式控制指令下发+异步​事件驱动架构​​注册rpc_setup/rpc_pause等分布式控制接口-&gt;注册eventpp事件监听-&gt;上层触发rpc调用&nbsp;-&gt;&nbsp;添加eventpp事件队列中-&gt;&nbsp;异步事件驱动-&gt;各子类Setup/Pause等功能接口标准化控制协议​​基于抽象接口(Setup/Pause等)实现跨模块统一管控,支持LLM/ASR/TTS等异构节点无缝集成5、TASK模块与Infra模块关系:类似与进程和线程之间关系,Infra模块负责资源分配和流程管控,TASK模块是真正干活的,干的活如下:各模块中模型生命周期管理(加载/卸载)infra推理包装回调输出等等
点赞 评论 收藏
分享
06-10 19:06
门头沟学院 C++
某公司一颗钉子:推荐几个项目 web多人聊天(进阶版webserver):https://www.bilibili.com/video/BV1iYtrezEkA/ 云存储:https://www.bilibili.com/video/BV1XPfTY8EGD/ 多线程任务队列系统:https://www.bilibili.com/video/BV1XS9dYsE9d/ RPC项目:https://www.bilibili.com/video/BV15ff4YsEPy/
点赞 评论 收藏
分享
评论
5
8
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务