手写一个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] } } }
核心在于代码中实现的两个变量:pc
和sp
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、亲缘性线程池等)