手写一门脚本语言 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):...# 双字符运算符先看两个字符twocpeek(1)iftwoinTWO_CHAR_OPS:tokens.append(Token(OP,two,line))i2continueifcin-*/%!:# 单字符运算符tokens.append(Token(OP,c,line));i1;continue# 数字持续吸收数字遇 . 且后接数字则进入浮点ifc.isdigit():whileinandsource[i].isdigit():i1ifinandsource[i].andi1nandsource[i1].isdigit():i1whileinandsource[i].isdigit():i1...# 字符串遇到 进入支持 \ \n \t \\ 转义ifc:...这里peek(1)就是 DFA 中“根据下一个输入决定状态转移”的工程化表达。与的处理顺序先判双字符后判单字符也至关重要否则会把误拆成两个。3.2 语法分析用“分层函数”编码运算符优先级二元表达式的优先级与结合性是递归下降 parser 的经典难点对应课程 03–05。我们的做法是把表达式按优先级从紧到松拆成多个函数高层函数只调用更紧的底层函数——优先级就这样“自然涌现”。# parser.py节选defadditive(self):# - 最低优先级之一leftself.multiplicative()whileself.check(OP,)orself.check(OP,-):opself.advance().lexeme rightself.multiplicative()# 右侧只解析更紧的层leftA.Binary(op,left,right,self.ln())returnleftdefmultiplicative(self):# * / %leftself.unary()whileself.check(OP,*)orself.check(OP,/)orself.check(OP,%):opself.advance().lexeme rightself.unary()leftA.Binary(op,left,right,self.ln())returnleft因为additive在需要右操作数时调用multiplicative所以1 2 * 3会被解析成1 (2 * 3)——优先级正确。同一层用while循环“吸干”连续的同优先级运算符于是a - b - c变成(a - b) - c即左结合。赋值则要右结合我们用递归自身实现defassignment(self):exprself.logical_or()ifself.check(OP,):self.advance()valueself.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:returnnumberifltstringandrtstring:returnstringifltstringandrtinNUM_TYPES:raiseSemanticError(f第{line}行类型错误字符串不能与数字相加)...第一遍先收集全局函数与类的签名参数个数、方法名从而支持“先调用后定义”以及方法分派检查第二遍再逐个语句做声明检查。未声明变量、函数参数个数不匹配都在此被拦截。3.4 解释执行闭包、this 与多态虚分派解释器对 AST 做深度优先遍历求值。最值得讲的是三个运行时模型词法作用域与闭包课程 10Environment是一条链查找变量沿链向上。函数对象捕获定义时的环境closure所以内部函数能访问外部局部变量——这正是闭包的本质。# interpreter.py节选classFunction:def__init__(self,decl,closure,name):self.decldecl;self.closureclosure# 捕获定义环境defcall(self,interpreter,args):envEnvironment(self.closure)# 新环境挂在闭包之下forp,ainzip(self.decl.params,args):env.define(p,a)...面向对象与 this课程 09BoundMethod在“方法被访问”时把this注入方法的环境。调用obj.foo()时实际是BoundMethod(method, obj).call(...)于是方法体内this指向obj。继承与多态课程 13ClassDef.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/frontbashrun_all.shexamples/01_fib.ps--- 运行 examples/01_fib.ps ---55examples/02_closure.ps--- 运行 examples/02_closure.ps ---12314examples/03_oop.ps--- 运行 examples/03_oop.ps ---28.262028.26203examples/04_undeclared.ps--- 运行 examples/04_undeclared.ps --- 错误第2行未声明的变量xexamples/05_arity.ps--- 运行 examples/05_arity.ps --- 错误第5行函数add需要2个参数实参给了1个examples/06_logic.ps--- 运行 examples/06_logic.ps ---4501234examples/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 结束 psvar x12*3;..print(x);7..var ffunction(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/文件职责lexer.py词法分析tokenizerparser.py递归下降语法分析 AST 构建ast.pyAST 节点定义semantic.py符号表 类型检查interpreter.py树遍历解释执行闭包 / OOPrepl.py运行入口 交互式 REPLexamples/*.ps7 个示例程序run_all.sh一键运行全部示例下一步可以沿两条线深入一是把“树遍历解释”升级为“字节码虚拟机”课程后端体会指令式执行与栈式机器的差异二是为语义分析引入更完整的类型推导如 Hindley–Milner 的简化版让any的地方也能给出更精准的检查。这正是《编译原理》后段“中端/后端”要解决的问题——我们下一篇继续。完整源码已同步到本地D:/D/compiler-work/code/front/可在云主机m1的/root/compiler/front/上复现全部运行结果。