LispE源码解析(二):词法分析、编译与字节码执行是如何工作的
LispE源码解析(二):词法分析、编译与字节码执行是如何工作的
LispE 是一个功能完整的 Lisp 解释器。本文带你完整走一遍它的执行管线:源码文本 → 词法分析(segmenting)→ 编译成语法树(Listincode)→ 指令分发表驱动的执行,帮助你快速理解这个 Lisp 解释器「词法分析、编译与字节码执行」三大核心机制的源码实现。
一、全局视角:一条代码的完整旅程
在 LispE 中,任何一段 Lisp 代码都会经过三个层次的处理:
| 阶段 | 核心入口 | 源码位置 |
|---|---|---|
| 词法分析 | LispE::segmenting |
src/lispe.cxx |
| 编译成语法树 | LispE::abstractSyntaxTree |
src/lispe.cxx |
| 求值执行 | List::eval_list_instruction |
src/functions.cxx |
最终入口函数是 include/lispe.h 中声明的 eval、execute、compile_lisp_code 等方法族。execute 的写法非常直白——「编译 + 求值」两连击:
return compile_lisp_code(code)->eval(this);
整个管线可以概括为一句话:先切成带类型的片段(tokens),再把片段递归组装成一棵 Listincode 语法树,最后按指令编码在分发表上查表执行。
二、词法分析:基于规则自动机的扫描器
LispE 的 lexer 不是手写 if-else 匹配,而是一个通用规则自动机 tokenizer_automaton,定义在 include/tokens.h。它把一套字符串规则(正则)编译成状态机,tokenize 一次扫描完成分词。
2.1 为 LispE 定制的词法规则
LispE 解释器使用的分词器是 lispe_tokenizer(include/tokens.h),它在 setrules() 中微调了通用规则:
rules[0] = U"%s+#"; // 把 %s 之类的符号归并处理
rules[i] = U";;?+;;=:67"; // 注释不再记录
rules[i+1] = U";?+#10=#";
而编辑器用的 segmenter_automaton(include/tokens.h)则支持 keepblanks(保留空白)和 setdecimalmode(小数分隔符模式),通过 flag_blocking_gate 标志位动态开关某些规则——规则可以运行时重编译,非常灵活。
2.2 每个 token 都得到一个「编码」
词法分析的结果不是裸字符串,而是 Tokenizer 结构(include/segmentation.h):其中 types 保存每个 token 的类型编码,strings 保存内容,positions/lines 保存位置与行号。
这些编码全部来自 include/elements.h 中的 lisp_code 枚举——这是理解后文「字节码执行」的钥匙:
typedef enum {
...
c_opening, c_closing, c_opening_bracket, ...,
e_error_brace, e_error_bracket, e_error_parenthesis, e_error_string,
e_no_error, t_comment, l_prefix, l_final
} lisp_code;
也就是说:圆括号、字符串、数字、关键字、错误码……统统映射成一个 int16_t 编码。segmenting 函数(src/lispe.cxx)在分词同时完成括号配平检查,发现 (、[、{ 不配平或字符串未闭合时,会返回 e_error_parenthesis、e_error_string 等错误码。
三、编译:递归构建 Listincode 语法树
3.1 编译入口:一个巧妙的「根包裹」技巧
LispE::compile_lisp_code(src/lispe.cxx)是编译的总入口,开头有一段很有意味的代码:
code = U"(__root__ " + code + U")"; // 把所有代码包进一个伪根节点
Tokenizer parse;
lisp_code retour = segmenting(code, parse); // 词法分析
abstractSyntaxTree(&courant, parse, index, false); // 构建语法树
用 (__root__ ...) 把整段代码包起来,编译结束后再判断「如果根节点只有两个元素,就直接取子元素求值」——这让任意代码片段都能被当作一棵完整的树处理。
3.2 abstractSyntaxTree:一次递归,token 流变成语法树
abstractSyntaxTree(src/lispe.cxx)是一个经典的递归下降结构。它按 token 类型驱动:
- 遇到
c_opening(():新建一个Listincode,递归调用自身处理列表内容; - 遇到
c_opening_brace({):构建字典; - 遇到
c_closing()):返回,结束当前列表; - 其余 token(数字、字符串、原子)直接挂到当前列表上。
每个新建的 Listincode 都会调用 set_idx_info(parse.lines[index]) 记录源码行号,所以运行期报错误时能精确指回代码行——这就是解释器里 delegation->i_current_line 的由来。
3.3 编译期优化:compileLocalStructure
裸列表还不够。abstractSyntaxTree 在处理完一个列表后会调用 compileLocalStructure(src/lispe.cxx),在编译期就识别并改写特殊结构:defun、lambda、block、while 以及 map/filter 等可组合结构会被转成更高效的形式(compose 合成栈)。换句话说,LispE 的「编译」不只是建树,还包含一轮模式匹配式的编译期变换——这也呼应了 Lispe 主打的 Pattern Programming 特色。
四、执行:指令编码 + 分发表的「字节码」模型
LispE 并没有传统意义上的 VM 字节码流,但它的设计本质上是「指令编码 → 查表 → 执行」的字节码思想:
4.1 指令表:编码即地址
Delegation(include/delegation.h)维护三张核心表,通过 set_instruction 注册每条内置指令:
inline void set_instruction(lisp_code instruction_code, string name,
unsigned long arity, methodEval m) {
straight_eval[instruction_code] = new Listincode(); // 编译期模板
instructions[instruction_code] = name; // 名称
arities[instruction_code] = arity; // 参数个数掩码
evals[instruction_code] = m; // 求值函数指针
}
lisp_code 编码在这里扮演「指令地址」的角色:evals 是指向 LispE 成员函数的指针表(类型见 include/lispe.h 的 checkEval),arities 用位掩码做参数个数校验(checkArity)。求值时 List::eval_list_instruction(src/functions.cxx)只需取列表头元素的编码,查表拿到函数指针直接调用——O(1) 分派,与解释器常见的「大 switch」相比开销更低。
4.2 求值:eval 的递归世界
每个 Element 子类都实现了 eval(LispE*),各类型的求值逻辑集中在 src/eval.cxx 与 src/straight_eval.cxx(超过 6900 行的直译执行实现)中。LispE::eval(u_ustring&)(src/eval.cxx)还顺带演示了垃圾回收:编译期新产生的对象进入 garbages 回收区,求值结果通过 protecting(true, this) 打上 s_protect 保护位,避免被误回收——对象生命周期状态位定义在 include/elements.h。
4.3 一个更直观的「字节码」示例:lisp mini
如果你想看一份最纯粹的「代码即字节码」实现,推荐读 editor/src/compiling.cxx 里的精简版解释器 lisp mini。它维护两个字典:
static std::map<u_ustring, uint16_t> code_dictionary; // 符号 → 16位编码
static std::map<uint16_t, lisp_element*> instructions_dictionary; // 编码 → 指令对象
任何符号(包括用户自定义原子)都通过 get_code() 映射成一个 uint16_t 编码;compile()(editor/src/compiling.cxx)把 token 流编译成由编码驱动的 lisp_list;执行就是 program->eval(this)。整个解释器不足 1000 行,是理解 Lispe 主实现「编码—查表—分派」模型的绝佳切片,配合 editor/lisp_mini.md 一起读效果更佳。
五、小结:LispE 执行管线的精华
- 词法分析:通用规则自动机
tokenizer_automaton+ 可运行时重编译的规则,每个 token 都得到lisp_code编码,同时完成括号配平与行号记录。 - 编译:
(__root__ ...)包裹 +abstractSyntaxTree递归下降,生成带行号信息的Listincode语法树,并在compileLocalStructure中做编译期结构优化。 - 执行:
lisp_code编码充当指令地址,Delegation的指令表(名称/参数掩码/函数指针)实现 O(1) 查表分派,配合保护位的轻量垃圾回收完成求值。
想动手验证的话,可以从 editor/README.md 开始,用 make mini 编译一个可交互的 lisp mini 演示环境,对照本文的三个阶段逐行阅读 editor/src/compiling.cxx 和 editor/src/eval.cxx,基本就能把这个执行管线吃透了。

