栈虚拟机

思路和想法来源: bilibili-帆影

一些具体的实现可能有不同, 比如解释器方面我可能受<<用Go自制解释器>>这本书的影响多一些. 但是毕竟是学习Up的写法和思路, 大部分是相似的

词法分析

功能: 解析一些运算相关的表达式, 例如加法.

主体设计

Tokenizer的设计基本上参考了上面的那本书, 这个结构体如下

• input —用于接受输入的源文件
• atPosition —记录当前消费到的位置
• readPosition —记录atPosition的前一个位置
• char — atPosition所代表的字符

    const Tokenizer = struct {
    const State = enum { start, interger };

    source:        []const u8, 
    atPosition:    usize,       
    readPosition:  usize,       
    char:          ?u8,       
};

其中的各种与词法分析相关的方法都可以通过调用Tokenizer的实例对象来进行使用 但是看up的实现发现zig实现这个自动机的方法很特别, 还有一个Satae参数. 这样的话可以通过状态的改变来驱动

const State = enum { start, interger };
state: switch (State.start) {
    .start => { ... continue :state .start; },
    .interger => { ... continue :state .start; },
}

辅助函数

与那本书中类似, 一个readChar来消费字符, 一个peekChar来不消费的看一个字符以决定状态的转移, 像是skipWithSpace和 isDigit用zig库

```zig
fn peekChar(self: *Tokenizer) ?u8 {
    if (self.readPosition >= self.source.len) return null;
    return self.source[self.readPosition];
}

不移动指针，仅查看下一个字符。这在处理 - 号时用于区分减号与负号：

'-' => minus: {
    if (self.peekChar()) |peek| {
        if (std.ascii.isDigit(peek)) {
            continue :state .interger;
        }
    }
    break :minus .minus;                 
},

状态机流程

自己写这个流程图有点难受, 让ai画了

                    ┌─────────────────┐
         开始       │     .start      │
           │        └───┬───┬───┬─────┘
           ▼            │   │   │
        char==null? ────┘   │   │  → break :state (生成 EOF)
           │                │   │
        空白字符? ──────────┘   │  → readChar(), continue :state .start
           │                    │
        数字? ─────────────────┘  → continue :state .interger
           │
        符号 ( ) + - ────────────→ 生成对应 Token,
                                   readChar(),
                                   continue :state .start

                    ┌──────────────────────┐
                    │     .interger        │
                    │                      │
                    │ 跳过前导 '-' (如有)   │
                    │ while isDigit: 读数字 │
                    │ 切片 + parseInt      │
                    │ 生成 interger Token  │
                    │ → continue .start    │
                    └──────────────────────┘

整数的解析

.interger => {
    const position = self.atPosition;          // 记录起始位置
    if (self.char.? == '-') self.readChar();   // 处瑾负号
    while (std.ascii.isDigit(self.char.?)) {
        self.readChar();                       // 读取数字
    }
    const str = self.source[position..self.atPosition];
    const num = try std.fmt.parseInt(i32, str, 10);  
    try token_list.append(gpa, .{ .interger = num });
    continue :state .start;
},

这里又去学习了一下zig的std.fmt

语法分析

这个好像只解释表达式, 那就没必要写完全部的节点了

对于表达式的定义:

const Expr = union(enum) {
    const BinOp = enum { add, sub };

    binary: struct {
        op:    BinOp,
        left:  *Expr,
        right: *Expr, //用指针,zig中无法递归自身
    },
    number: i32,
};

一个表达式抽象为一棵树, 这里我的理解是可以产生值的就是表达式, 对于具体的值, 使用number字段

普拉特解析法

怎通构造AST呢?通过不断读取Token, 并且用合适的状态转移来处理.

fn parse(self: *Lexer, arena: std.mem.Allocator) !*Expr {
    switch (self.token) {
        .lparen => {
            self.readToken();                          // 处理 '('
            switch (self.token) {
                .plus, .minus => {
                    const op: Expr.BinOp = switch (self.token) {
                        .plus  => .add,
                        .minus => .sub,
                        else => unreachable,
                    };
                    self.readToken();                  // 处理运算符
                    const left  = try self.parse(arena);  // 递归解析左操作数
                    const right = try self.parse(arena);  // 递归解析右操作数

                    const bin_expr = self.arena.create(Expr) catch unreachable;
                    bin_expr.* = .{ .binary = .{ .op = op, .left = left, .right = right } };
                    std.debug.assert(self.token == .rparen);
                    return bin_expr;
                },
                else => unreachable,
            }
        },
        .interger => {
            const exper = self.arena.create(Expr) catch unreachable;
            exper.* = .{ .number = self.token.interger };
            self.readToken();
            return exper;
        },
        else => unreachable,
    }
}

学习了一个arean的管理, 这个还是相当常用的

虚拟机

指令集设计

const Inst = enum(u8) {
    start,     // 0
    constant,  // 1
    add,       // 2
    minus,     // 3
};

辅助函函数

fn from(inst: u8) Inst {
    return @enumFromInt(inst);
}
fn toU8(inst: Inst) u8 {
    return @intFromEnum(inst);
}

• 写入字节码时：Inst.constant.toU8() 将枚举转为 u8 写入 ArrayList(u8)
• 执行字节码时：@enumFromInt(bytes[pos]) 将读出的 u8 还原为 Inst 枚举

解释一下这个opcode的语义

指令	opcode	操作数	栈效应	语义
start	0	无	—	取指/分发状态
constant	1	4 字节 i32	push value	将立即数压栈
add	2	无	pop b, pop a, push a+b	栈顶两数相加
minus	3	无	pop b, pop a, push a-b	栈顶两数相减

VM执行

const Value = i32;

const VM = struct {
    stack: [128]Value,
    stack_top: usize, //stack_top 永远指向栈顶的第一个空闲位置
    fn init()
    fn push()
    fn pop()
};

push/pop

fn push(self: *VM, val: Value) void {
    self.stack[self.stack_top] = val;
    self.stack_top += 1;
}

fn pop(self: *VM) Value {
    self.stack_top -= 1;
    return self.stack[self.stack_top];
}

栈的结构说明

constant 指令 (5 字节):
+---------+-----------------------------+
| opcode  |        operand (i32)        |
| 1 byte  |          4 bytes            |
+---------+-----------------------------+

处理字节序列的方法

const a: i32 = 1;
const a_slice: [4]u8 = @bitCast(a);

将内存中的四个字节解释为[4]u8 来解释, 这里是小端序.

var bytes_list: std.ArrayList(u8) = .empty;
try bytes_list.appendSlice(init.gpa, &a_slice);  // 写入 4 字节操作数
try bytes_list.append(init.gpa, Inst.constant.toU8());  // 写入 1 字节 opcode

状态机的实现

zig中的标签是很有意思啊. 类似于goto

var pos: usize = 0;
state: switch (Inst.start) {
    .start => {
        if (pos >= bytes.len) break :state; 
        const inst: Inst = @enumFromInt(bytes[pos]); //取指译码
        pos += 1; //pc ++
        continue :state inst; //分发
    },
    .constant => {
        const item = std.mem.readVarInt(i32, bytes[pos .. pos + 4], .little);
        pos += 4;
        vm.push(item);
        continue :state .start;
    },
    .add, .minus => |inst| {
        const op = inst;
        const bval = vm.pop();
        const aval = vm.pop();
        const res = switch (op) { .add => aval + bval, .minus => aval - bval, else => unreachable };
        vm.push(res);
        continue :state .start;
    },
}

这里是要严格按照顺序来的, 要不然会栈溢出的

.start其实是一个分发器,通过opcode来判断往哪一个分支走.