手写一门脚本语言 PlayScript：从词法到解释执行的编译器前端实战

编译原理实战系列 · 第 1 篇
对应宫文学《编译原理》极客时间课程：02 词法分析、03–05 语法分析与表达式优先级、09/13 面向对象与多态、10 闭包、11–12 语义分析与类型检查。

一、引言：为什么要亲手写一遍编译器前端？

很多人学编译原理时，停留在“龙书/虎书”的公式与自动机定理上，真要动手写一个能跑的语言组件，往往不知从何下笔。我自己的体会是：编译器唯一正确的学习方式，就是亲手实现。当你把一段文本，经过词法、语法、语义，最后真正“跑”出结果，那些抽象概念——DFA、递归下降、符号表、闭包、虚分派——才会从纸面落到指尖。

本篇我们参照课程主线，纯手写一门名为PlayScript的小型脚本语言解释器，覆盖编译器“前端”全部环节：

• 词法分析：手写 tokenizer，用正则/DFA 思想切分 Token；
• 语法分析：递归下降 parser，正确处理二元表达式的优先级与结合性，构建 AST；
• 语义分析：符号表 + 类型检查，捕获未声明变量、参数个数不匹配、类型不匹配；
• 解释执行：树遍历求值，实现词法作用域、闭包、面向对象（继承与多态）。

全部代码用纯 Python 3 实现（无需安装任何第三方库），真实运行在云主机（Ubuntu 24.04）上。本文所有输出，都是m1这台机器上真实采集的 stdout，没有任何编造。

二、核心概念：四个阶段，一条流水线

PlayScript 的编译流水线非常清晰，每一阶段只依赖上一阶段的产物：

源码字符串 │ lexer.tokenize （词法：字符流 → Token 流） ▼ Token 流 │ parser.Parser.parse （语法：Token 流 → AST） ▼ AST │ semantic.Analyzer （语义：作用域 + 类型检查） ▼ AST（已校验） │ interpreter.Interpreter（运行：树遍历求值） ▼ 运行结果 / 报错

回想课程里强调的“前端/后端”划分：前端负责理解程序（它是什么），后端负责优化与翻译（它怎么高效执行）。我们这一篇聚焦前端，执行方式选用最简单的“树遍历解释器”，好处是能最直接地体现语义与运行时模型，而不被寄存器分配等话题带偏。

PlayScript 支持的关键字：var function return if else while for class new this print，外加字面量true/false/null。运算符覆盖算术+ - * / %、关系< <= > >=、相等== !=、逻辑&& || !与赋值=。

三、分步代码讲解

3.1 词法分析：用“前瞻”区分单/双字符运算符

词法分析的本质，是按正则文法把字符流切成一个个词素（Token）。手写 tokenizer 的关键技巧是状态推进 + 前瞻一个字符。下面这段代码展示了最体现 DFA 思想的两处：双字符运算符的判定，以及数字/字符串状态的吸收。

# lexer.py（节选）TWO_CHAR_OPS={'==','!=','<=','>=','&&','||'}deftokenize(source):...# 双字符运算符：先看两个字符two=c+peek(1)iftwoinTWO_CHAR_OPS:tokens.append(Token('OP',two,line))i+=2continueifcin'+-*/%=<>!':# 单字符运算符tokens.append(Token('OP',c,line));i+=1;continue# 数字：持续吸收数字，遇 '.' 且后接数字则进入浮点ifc.isdigit():whilei<nandsource[i].isdigit():i+=1ifi<nandsource[i]=='.'andi+1<nandsource[i+1].isdigit():i+=1whilei<nandsource[i].isdigit():i+=1...# 字符串：遇到 '"' 进入，支持 \" \n \t \\ 转义ifc=='"':...

这里peek(1)就是 DFA 中“根据下一个输入决定状态转移”的工程化表达。==与=的处理顺序（先判双字符后判单字符）也至关重要，否则会把==误拆成两个=。

3.2 语法分析：用“分层函数”编码运算符优先级

二元表达式的优先级与结合性，是递归下降 parser 的经典难点（对应课程 03–05）。我们的做法是：把表达式按优先级从紧到松拆成多个函数，高层函数只调用更紧的底层函数——优先级就这样“自然涌现”。

# parser.py（节选）defadditive(self):# + - （最低优先级之一）left=self.multiplicative()whileself.check('OP','+')orself.check('OP','-'):op=self.advance().lexeme right=self.multiplicative()# 右侧只解析更紧的层left=A.Binary(op,left,right,self.ln())returnleftdefmultiplicative(self):# * / %left=self.unary()whileself.check('OP','*')orself.check('OP','/')orself.check('OP','%'):op=self.advance().lexeme right=self.unary()left=A.Binary(op,left,right,self.ln())returnleft

因为additive在需要右操作数时调用multiplicative，所以1 + 2 * 3会被解析成1 + (2 * 3)——优先级正确。同一层用while循环“吸干”连续的同优先级运算符，于是a - b - c变成(a - b) - c，即左结合。

赋值则要右结合，我们用递归自身实现：

defassignment(self):expr=self.logical_or()ifself.check('OP','='):self.advance()value=self.assignment()# 递归 → 右结合ifisinstance(expr,A.Var):returnA.Assign(expr.name,value)ifisinstance(expr,A.Member):returnA.Set(expr.obj,expr.name,value)raiseParseError(...)returnexpr

这样a = b = c会被解析为a = (b = c)，符合多数语言的语义。此外，调用与成员访问被做成后缀（call()里循环处理(与.），因此f().g(1).h也能正确解析。

3.3 语义分析：符号表 + 类型检查

语义分析在 AST 上做静态检查（课程 11–12）。我们用一个作用域栈记录每个名字的类型，并在进入函数/类/块时压栈、离开时弹栈。类型用字符串表示：int/float/number/string/bool/object/any。对于“两端类型都已知且明显冲突”的运算，我们直接报错；含any（未知/动态）的运算则保守放行，避免误报。

# semantic.py（节选）def_check_binary(self,op,lt,rt,line):ifop=='+':ifltinNUM_TYPESandrtinNUM_TYPES:return'number'iflt=='string'andrt=='string':return'string'iflt=='string'andrtinNUM_TYPES:raiseSemanticError(f"第{line}行：类型错误，字符串不能与数字相加（+）")...

第一遍先收集全局函数与类的签名（参数个数、方法名），从而支持“先调用后定义”以及方法分派检查；第二遍再逐个语句做声明检查。未声明变量、函数参数个数不匹配都在此被拦截。

3.4 解释执行：闭包、this 与多态虚分派

解释器对 AST 做深度优先遍历求值。最值得讲的是三个运行时模型：

词法作用域与闭包（课程 10）：Environment是一条链，查找变量沿链向上。函数对象捕获定义时的环境closure，所以内部函数能访问外部局部变量——这正是闭包的本质。

# interpreter.py（节选）classFunction:def__init__(self,decl,closure,name):self.decl=decl;self.closure=closure# 捕获定义环境defcall(self,interpreter,args):env=Environment(self.closure)# 新环境挂在闭包之下forp,ainzip(self.decl.params,args):env.define(p,a)...

面向对象与 this（课程 09）：BoundMethod在“方法被访问”时，把this注入方法的环境。调用obj.foo()时，实际是BoundMethod(method, obj).call(...)，于是方法体内this指向obj。

继承与多态（课程 13）：ClassDef.find_method沿继承链向上查找方法，调用方只看“对象实际属于哪个类”——这就是虚分派（动态分派），多态由此自然产生。

classClassDef:deffind_method(self,name):ifnameinself.methods:returnself.methods[name]ifself.superclassisnotNone:returnself.superclass.find_method(name)# 沿父类链查找returnNone

四、真实运行效果（m1 云主机采集）

我把 7 个示例放进examples/，用run_all.sh在m1上一键运行，下面是真实的 stdout（含语义报错）：

$cd/root/compiler/front&&bashrun_all.sh====examples/01_fib.ps====--- 运行 examples/01_fib.ps ---55====examples/02_closure.ps====--- 运行 examples/02_closure.ps ---12314====examples/03_oop.ps====--- 运行 examples/03_oop.ps ---28.262028.26203====examples/04_undeclared.ps====--- 运行 examples/04_undeclared.ps --- 错误：第2行：未声明的变量'x'====examples/05_arity.ps====--- 运行 examples/05_arity.ps --- 错误：第5行：函数'add'需要2个参数，实参给了1个====examples/06_logic.ps====--- 运行 examples/06_logic.ps ---4501234====examples/07_type_error.ps====--- 运行 examples/07_type_error.ps --- 错误：第3行：类型错误，字符串不能与数字相加（+）

逐一解读：

• 斐波那契：fib(10) == 55，验证了递归与表达式优先级（fib(n-1)+fib(n-2)中-比+更紧）。
• 闭包计数器：连续调用c()得到1 2 3，再新建c2()得到1，最后c()给出4——证明两个计数器持有互相独立的环境，闭包捕获生效。
• 继承与多态：Circle(3).area() == 28.26、Rectangle(4,5).area() == 20；随后用基类变量s先指向圆、再指向矩形，s.area()分别动态分派出28.26与20，多态成立；c.r == 3表明字段访问正常。
• 三类语义错误：未声明变量、参数个数不匹配、字符串+数字类型不匹配，全部在运行前被静态分析拦截并给出精确行号。

另外，解释器也提供交互式 REPL（持久环境，前面行定义的变量/函数在后续行仍可用）：

$ python3 repl.py PlayScript REPL（输入exit退出，ctrl-D 结束） ps>var x=1+2*3;..print(x);7..var f=function(n){returnn * n;};..print(f(5));25

五、难点解析

1) 二元表达式的优先级与结合性。这是手写 parser 最容易翻车的地方。口诀是“高层调低层 = 优先级，同层 while 循环 = 左结合，递归自身 = 右结合”。把*/%放在比+-更“里层”的函数里，优先级就解决了；赋值=用value = self.assignment()递归得到右结合。

2) 闭包。关键一句话：函数是“代码 + 定义时环境”的打包。很多初学者误以为闭包需要特殊的“捕获列表”，其实只要函数对象持有对外部Environment的引用，查找变量时沿链而上，闭包就自然成立。解释器里Function.closure就是那个被打包的环境。

3) 多态虚分派。面向对象语言的多态，并不靠“记住类型”实现，而是靠“调用时按对象实际类型查方法表”。find_method从实例的真实类出发向上查找，因此s.area()在s指向不同子类时自动走到不同实现——这就是虚分派，也是多态的运行期心脏。

六、小结与下一步

我们纯手写实现了 PlayScript 的解释器前端：词法分析用前瞻区分运算符、语法分析用分层函数编码优先级、语义分析用作用域栈做类型检查、解释执行用环境链实现闭包、用方法表查找实现多态。所有代码在云主机m1上真实跑通，输出如上，无任何虚构。

源码结构（/root/compiler/front/）：

下一步，可以沿两条线深入：一是把“树遍历解释”升级为“字节码虚拟机”（课程后端），体会指令式执行与栈式机器的差异；二是为语义分析引入更完整的类型推导（如 Hindley–Milner 的简化版），让any的地方也能给出更精准的检查。这正是《编译原理》后段“中端/后端”要解决的问题——我们下一篇继续。

完整源码已同步到本地D:/D/compiler-work/code/front/，可在云主机m1的/root/compiler/front/上复现全部运行结果。