Note: This page does not support English, using the default language version
栈虚拟机
思路和想法来源: 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库
```zigfn 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来判断往哪一个分支走.