手写一个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、亲缘性线程池等）
投递腾讯等公司8个岗位
查看10道真题和解析