从零设计编程语言：词法分析、语法分析与解释器实现指南

设计一门编程语言这个话题乍一听像是只在论文和编译器教科书里才会出现的事但说实话它离我们并不远。你每天写的SQL、正则表达式、甚至配置文件里的DSL本质上都是“门小型编程语言”。我自己从零折腾过解释器也维护过公司内部的一套规则引擎语法今天就把这条路从头到尾捋一遍设计语言到底在做什么、需要哪些工具、每一步怎么落地以及最容易卡住你的那些坑。这篇文章适合几类人想搞懂编译器/解释器原理但被龙书劝退的初学者需要在业务里设计DSL的工程师还有纯粹好奇“一门语言是怎么从0长出来的”的人。我会尽量用大白话把词法分析、语法分析、代码生成这些东西讲清楚并且给出真正能跑起来的工具链配置而不是只贴术语。1. 设计语言之前先想清楚这四件事1.1 设计目标决定了你接下来80%的技术选型很多人一上来就急着写代码结果写到Parser就崩了因为根本没想清楚“这门语言到底给谁用、解决什么问题”。我见过最典型的失败案例是想做一门“比Python更优雅”的语言结果功能越加越多两年了连个稳定版都出不来。你在动手前必须回答四个问题应用场景是通用编程语言像Python、Go还是嵌入式脚本像Lua还是某个领域的专用语言像SQL、正则通用语言要考虑的东西太多类型系统、模块机制、并发模型、生态工具链每一项都是无底洞。如果你只是想解决某个特定问题强烈建议先做DSL把范围缩小到“只做一件事”。运行方式解释执行逐行跑源码、编译执行生成机器码/字节码、还是两者结合先编译成字节码再虚拟机执行解释器实现快但性能弱编译器性能强但工作量成倍增加。JVM系的Groovy、Kotlin走的就是“先编译成字节码再解释”的路子这也是很多脚本语言的主流方案。执行环境跑在什么平台上如果只需要一个平台直接依赖系统的ABI就行如果需要跨平台就要考虑字节码虚拟机或者像Go那样直接静态编译成各平台原生代码。这里有一个很实际的选择如果你要跑在浏览器里就得考虑编译成WebAssembly那前面的工具链就完全不同了。使用人群使用者的水平决定了你语法设计的复杂度。给程序员用的语言可以上类型推导、函数式特性给业务人员用的DSL就必须让语法尽量贴近自然语言并且错误提示要极其友好。记住一个原则语言设计的第一原则是克制。每加一个语法特性你要付出的不光是实现成本还有文档、调试、兼容性的长期维护成本。CoffeeScript曾红极一时就是因为“少”后来死于“多”——特性越堆越多JavaScript本身又追了上来。1.2 语法风格选型C风格、函数式、还是DSL范式确定了目标之后接下来要决定语法风格。这不是审美问题而是直接影响你Parser写法的技术决策。如果你选择C系语法花括号分号好处是程序员零学习成本解析起来也简单——{}天然标识了代码块边界;让语句结束位置一目了然。坏处是这类语言多如牛毛除非你有真正的杀手锏特性否则根本没有存在感。我自己做过一个小工具语言一开始用了C风格后来发现根本没必要——花括号和分号对DSL用户来说就是噪音。如果你选择Python风格缩进敏感就要在Tokenizer阶段处理缩进级别把INDENT和DEDENT当作隐式Token塞进Token流。这会让词法分析器复杂一截但换来的是源码更简洁。Python官方文档里有一整节专门讲“缩进是怎么被解析的”建议动手前先读一遍。如果你选择Lisp风格一切皆表达式、括号嵌套Parser反而是最简单的——因为语法树和源码结构几乎是直接映射的你甚至不需要手写AST节点类型直接用嵌套列表就行。这也是为什么很多教学语言选Lisp变体因为可以把有限精力全放在语义和求值上。我的建议是除非你有明确理由否则第一门语言选C风格或者极简表达式风格。把复杂度留给后面真正重要的部分——语义和运行时。2. 开发工具全景从手写Parser到自动生成器2.1 词法分析工具Flex、Regex还是手写先说词法分析Tokenizer/Lexer阶段这是把源码字符串切成一串有意义的Token。比如let x 42要切成LET、IDENT(x)、EQ、INT(42)这几个Token。选工具有三条路手动实现几百行代码遍历字符遇到空白就跳过遇到字母就继续读直到非字母然后查关键字表决定是IDENT还是关键字。这条路我强烈推荐你至少做一次——它能帮你彻底理解Token的本质。而且对大多数DSL来说手写词法器其实足够用了因为你的规则很少。正则表达式驱动用re库或者Lua的lpeg把每种Token定义成正则按优先级依次尝试匹配。速度快、代码短但调试起来有点麻烦——正则写错了很难肉眼发现。适合Token类型不超过20种的场景。词法生成器像FlexC/C、JFlexJava、Ragel多种语言。你写规则文件它生成完整的词法分析器代码。优点是规则清晰、可以处理复杂的上下文缺点是生成的代码不可读而且有学习成本。如果选了ANTLR它其实自带强大的词法规则语法能覆盖绝大多数场景就不需要额外单独引一个词法工具了。有个经验之谈Token一定要带上位置信息行列号。哪怕你现在的错误提示只是“语法错误”将来想升级成“第25行第8列这里少了一个右括号”没有位置信息就得全盘重写。2.2 语法分析工具ANTLR、Bison/Yacc、还是手写递归下降词法分析把文本切成Token语法分析负责把这些Token按语法规则组装成一棵“抽象语法树”AST。这是整个流程里最容易劝退人的环节也是工具选择最关键的地方。三大流派ANTLRJava写的解析器生成器支持Java、Python、C#、JavaScript等语言。它的语法文件.g4非常直观像expr: term ( term)*这种写法。它的王牌功能是ANTLR能自动生成遍历器Visitor/Listener配合可视化工具ANTLRWorks调试对初学者极其友好。我平时做DSL原型如果时间紧直接上ANTLRPython target下午三点开会讨论语法六点就能跑通一个最小解释器。Bison/YaccUnix老牌组合C语言的标杆工具。性能极好生成的Parser是LALRLook-Ahead LR算法能处理非常复杂的文法。但缺点也很明显——写规则用类似expr: expr term { $$ $1 $3; }这种嵌入式动作代码调试难度大而且Yacc对左递归有天然限制虽然有办法解决但很绕。除非你要写C/C的编译器或者对性能有极端要求否则不推荐入门用。手写递归下降Parser这是我最推荐初学、也最推荐小型语言用的方案。原理就是用一到几个函数每个函数负责解析一种语法规则A调用B、B调用C互相递归。比如parseExpr()里调parseTerm()parseTerm()里根据Token的类型决定是返回数字还是再调parseExpr()。它需要你手动处理运算符优先级但整个逻辑是透明的、可断点调试的。对Tokenizer的输出要求也低出错能精确到具体函数。我的结论很简单做原型用ANTLR做真正的产品语言用手写递归下降。理由后面实操部分展开说。2.3 代码生成与优化工具LLVM、C作为后端、还是自研字节码虚拟机如果你做的是编译型语言语法分析之后不是直接输出机器码——中间还有语义分析类型检查、变量绑定、作用域解析、中间表示IR生成、优化、目标代码生成这几个阶段。这里的选择会直接影响你整个编译器的架构。最常见的三条路线LLVMLow Level Virtual Machine现在是工业界事实标准的编译器后端基础设施。你负责把语言翻译成LLVM IR中间表示剩下的寄存器分配、指令调度、平台适配、各种优化全交给LLVM。Rust、Swift、ClangC/C、甚至Julia的编译器都跑在LLVM上。缺点是LLVM的API极其庞大且迭代激进学习曲线陡峭而且版本升级经常弄坏老代码。我自己在macOS上折腾LLVM 15到16的迁移就花了一整天都是被API改名坑的。如果你走这条路建议直接用llvm-sysRust或者llvmlitePython这类高层绑定别直接碰C API。把C语言当作“可移植汇编器”你先把源码翻译成C代码然后丢给GCC/Clang编译。这是最省力的方案——你不需要关心寄存器分配、ABI、平台差异C编译器全部包圆了。早期很多语言这么干比如最早的C编译器cfront就是把C翻译成C再编译。我自己做过一个小语言的编译器选择翻译成C一天就通了性能只比手写C慢10%左右——对你自研语言来说这个性能损失完全无所谓。这个方案的缺点是生成的C代码里到处是struct和各种函数指针调试起来不太直观。自研字节码虚拟机VM先把源码编译成一串字节码类似Java的class文件再写一个C/Rust/Go程序来“解释执行”这些字节码。Lua、Python、Java早期走的都是这条路。优点是跨平台、可加运行时特性GC、协程、动态类型、实现难度适中缺点是性能上限不如直接编译到原生码而且虚拟机本身的性能调优是个新坑。如果让我给一个普遍的推荐业余项目或DSL直接走“翻译成C”或者“字节码VM”两条路想做商业级通用语言再认真研读LLVM教程。2.4 运行时与生态配套工具GC、调试器、包管理器很多人设计语言时只盯着编译前端词法、语法、代码生成结果到后期才发现运行时相关的东西一件都没准备。这里有几样最容易被忽略内存管理如果走“翻译成C”路线最简单的是直接用引用计数每个对象记一个“被引用次数”归零就释放——这比写精确的GC简单一个量级。Lua和Python早期都用引用计数可见这条路走得通。真要实现分代GC像Java那样你面对的就是“对象什么时候能回收”“要不要stop-the-world”“怎么处理循环引用”每一项都够写一篇论文。标准库与内置函数语言本身只提供语法真正让用户愿意用的是print、len、str()这些内置函数。这些函数的实现看起来简单但每加一个都要考虑与运行时交互的边界。要有心理准备这是被低估的工作量黑洞。调试器这是最痛苦的部分。如果没有调试器支持用户排错就靠print和运气。要给自己的语言加断点、单步、变量查看意味着你必须在编译产物里保留源码映射source map并在运行时暴露足够的执行状态接口。我建议你第一版先不做但一定要在Token和AST阶段就保留位置信息——这是将来做调试器的地基。包管理器/模块系统除非语言定位为“一次性脚本”否则迟早要做模块导入机制。而模块系统一旦引入就要面对循环依赖、初始化顺序、多版本冲突这些老朋友。建议参考Go的“模块路径版本化”思路别自己重新发明。3. 实操过程从零实现一门Toy语言的完整链路3.1 定义语言一个极简配置DSL的语法规范纸上谈兵没意思我直接带你在30分钟内跑通一门极小型配置语言的完整实现。为了不让篇幅失控我不做通用语言做一个极简的“账单计算DSL”功能只有三样定义数值变量let x 10加减乘除表达式x 2 * 3输出print x 1语法用伪BNF一种描述语法的写法表示program : statement* statement : let_stmt | print_stmt let_stmt : let IDENT expr print_stmt : print expr expr : term (( | -) term)* term : factor ((* | /) factor)* factor : NUMBER | IDENT | ( expr )注意我把表达式分成了expr/term/factor三层这是手工处理运算符优先级最常见的手法层级越深优先级越高。3.2 词法分析器的手写实践与边界case处理我选择手写词法器因为对这种小语言引入Flex反而是杀鸡用牛刀。核心代码我用Python演示逻辑清晰方便你跑起来import re TOKEN_SPEC [ (NUMBER, r\d), (IDENT, r[a-zA-Z_][a-zA-Z0-9_]*), (OP, r[\-*/]), (EQ, r), (LPAREN, r\(), (RPAREN, r\)), (SKIP, r[ \t\n]), ] KEYWORDS {let, print} def tokenize(code): tokens [] pos 0 line 1 col 1 while pos len(code): for tok_type, pattern in TOKEN_SPEC: regex re.compile(pattern) match regex.match(code, pos) if not match: continue text match.group(0) # 计算新的行列号 newline_count text.count(\n) if tok_type ! SKIP: if tok_type IDENT and text in KEYWORDS: tokens.append((text.upper(), text, line, col)) else: tokens.append((tok_type, text, line, col)) pos match.end() line newline_count col len(text) - text.rfind(\n) - 1 if newline_count else col len(text) break else: raise SyntaxError(f无法识别的字符: {code[pos]} 在第{line}行第{col}列) tokens.append((EOF, , line, col)) return tokens这里有几个边界case值得你注意行号列号计算我专门统计了\n的个数并且重新算列号。你可能会觉得“先留着以后再补”但真的到报错信息需要坐标时你不可能回头再改一遍——那时候所有数据都流过了。关键字优先于标识符正则里IDENT已经能匹配let所以必须在Token化时做一次关键字表检查把let从IDENT降级成KW_LET。顺序不能反过来——先查关键字表再识别普通标识符是错的因为letter这个合法变量名会被误伤。最长匹配原则正则列表按“特殊优先”排列看起来很自然但实际应该按“最长优先”工作。这里因为模式互斥顺序关系不大但如果你加了像和这样的运算符必须把放在前面。词法器是“一把尺子量到底”只要有一个Token定错后面全乱。运行tokenize(let x 10)你会得到[(KW_LET, let, 1, 1), (IDENT, x, 1, 5), (EQ, , 1, 7), (NUMBER, 10, 1, 9), (EOF, , 1, 11)]3.3 递归下降Parser实现与运算符优先级处理Token流拿到之后接下来是Parser。我直接手写递归下降核心代码如下class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def consume(self, expected_type): token self.tokens[self.pos] if token[0] ! expected_type: raise SyntaxError(f期望 {expected_type}实际得到 {token[0]} 在 {token[2]}:{token[3]}) self.pos 1 return token def parse_program(self): statements [] while self.peek()[0] ! EOF: statements.append(self.parse_statement()) return statements def parse_statement(self): token self.peek() if token[0] KW_LET: return self.parse_let_statement() elif token[0] KW_PRINT: return self.parse_print_statement() else: raise SyntaxError(f未知语句开头: {token}) def parse_let_statement(self): self.consume(KW_LET) ident self.consume(IDENT) self.consume(EQ) expr self.parse_expr() return (let, ident[1], expr) def parse_print_statement(self): self.consume(KW_PRINT) expr self.parse_expr() return (print, expr) # 加法/减法 —— 最外层优先级最低 def parse_expr(self): node self.parse_term() while self.peek()[0] OP and self.peek()[1] in (, -): op self.consume(OP) right self.parse_term() node (binop, op[1], node, right) return node # 乘法/除法 —— 中间层 def parse_term(self): node self.parse_factor() while self.peek()[0] OP and self.peek()[1] in (*, /): op self.consume(OP) right self.parse_factor() node (binop, op[1], node, right) return node # 数字/变量/括号 —— 最内层优先级最高 def parse_factor(self): token self.peek() if token[0] NUMBER: self.consume(NUMBER) return (number, int(token[1])) elif token[0] IDENT: self.consume(IDENT) return (var, token[1]) elif token[0] LPAREN: self.consume(LPAREN) expr self.parse_expr() self.consume(RPAREN) return expr else: raise SyntaxError(f无法识别的表达式开头: {token})这里最关键的细节是“等级化解析”。注意parse_expr只处理、-然后调用parse_term处理*、/再调用parse_factor处理数字、变量、括号。为什么要有层级因为表达式1 2 * 3如果都放在一个函数里平级处理会产生(1 2) * 3的错误AST。层级天然保证了“乘除法先做”的优先级规则。我在工程里踩过一个坑运算符优先级不只是算术优先还涉及结合性。比如10 - 5 - 2应该从左到右等价于(10 - 5) - 2我的while循环天然实现了左结合但如果想做右结合的赋值运算符就得把解析循环改成递归调用自身如parse_assign里先解析右侧再递归左侧。这个差别要提前想明白。3.4 解释器实现与闭包、作用域处理的取舍Parser产出的是AST用元组嵌套表示接下来写一个树遍历解释器就是边遍历边算结果class Interpreter: def __init__(self): self.env {} def eval(self, node): if node[0] number: return node[1] elif node[0] var: name node[1] if name not in self.env: raise NameError(f未定义变量: {name}) return self.env[name] elif node[0] binop: op, left_node, right_node node[1], node[2], node[3] left_val self.eval(left_node) right_val self.eval(right_node) if op : return left_val right_val if op -: return left_val - right_val if op *: return left_val * right_val if op /: return left_val / right_val elif node[0] let: _, name, expr node self.env[name] self.eval(expr) return None elif node[0] print: _, expr node print(self.eval(expr)) return None else: raise ValueError(f未知节点: {node})这个东西跑起来已经很有成就感了输入let x 10再输入print x 2 * 3输出16。但如果你要做的是真实语言必须提前想清楚作用域Scope问题。上面的代码用的是单一全局env字典这在只有全局变量的语言里没问题。可一旦引入函数或者块级作用域就必须把env改成“作用域链”——每进入一个函数/代码块就新建一个外层作用域的引用变量查找从内向外逐层查找。我最开始做自己的迷你Lisp时就是忽略了作用域导致嵌套函数里访问全局变量时数据全乱了。如果你用的是“翻译成C”的编译路线作用域问题更微妙你必须在编译期把变量名解析成“某个结构体里的第几个字段”这相当于在语义分析阶段做一次“变量落地resolve”。这一步非法后面生成代码必然出错。3.5 把解释器升级为编译器生成LLVM IR的关键步骤如果想让这个语言跑得更快可以把解释器替换成“编译器”。给你看一个用LLVM做后端的最简思路——不展开全部代码只讲链条先写codegen函数对每个AST节点生成对应的LLVM IR文本def codegen_expr(node): if node[0] number: return f %{tmp} add i32 0, {node[1]}\n # LLVM里常量要用指令加载 elif node[0] binop: left_ir codegen_expr(node[2]) right_ir codegen_expr(node[3]) op_map {: add, -: sub, *: mul, /: sdiv} return f %{tmp} {op_map[node[1]]} i32 {left_reg}, {right_reg}\n然后用LLVM的库把IR文本编译成目标文件链接执行。关键步骤有几步定义模块module llvm.core.Module.new(test)声明main函数LLVM里程序入口必须叫main返回i32把print内置函数链接到C标准库的printf对AST节点逐个生成IR指令用llvmlite的jit或llvm命令行工具生成可执行文件这一步最大的坑是LLVM API版本。llvmlite只绑定特定版本的LLVM你换一个Python环境就可能绑不上。在工程里我学到的教训是版本锁死并且在CI里跑一次“能否import”的冒烟测试。如果你嫌LLVM太重回到“翻译成C”的路线就轻松多了直接ast_to_c(node)把AST拼成字符串再用subprocess调gcc编译。两条路线的核心区别是翻译成C你只要处理“字符串拼接”生成LLVM IR则要处理“寄存器编号管理”——一个表达式的中间结果放哪个寄存器、生命周期到哪结束这些都是真实编译器寄存器分配器要解决的问题只不过LLVM帮你把最后的分配工作全包了。4. 常见问题与排查技巧实录4.1 左递归引发的无限循环与消除方法写递归下降Parser时最容易碰到的崩溃是“左递归”问题。如果你把表达式定义写成expr : expr term那么parse_expr()会先调用自己永远无法前进。解决办法是改写为循环形式也就是我上面写的while循环版本。更通用的改写套路叫“消除左递归”适合在BNF层面做转换如果用了ANTLR或Yacc这类生成器它们内部通常已经处理了这个问题但你手工写递归下降时千万别把产生式的左递归直接翻译成函数递归。4.2 运算符优先级与结合性出错的经典症状优先级错误的典型现象是输入print 1 2 * 3输出9而不是7。我排查这个问题时最有效的方法是先打印AST结构比如(binop, , (binop, *, 2, 3), 1)一眼就能看出乘法的层级没被抬高。另一个症状是在同一优先级下连续出现同级别操作符——比如10 - 5 - 2算成7而不是3这通常是你把右结合写成左结合了。你可以在代码里临时加一个AST打印函数方便可视化排查。我在自己的工具语言里专门留下了--ast命令行参数输出树形结构这比一步步打Log快十倍。4.3 Token流追踪报错信息永远指示在错误位置新手最多的问题不是代码逻辑错而是“报错行号永远差一截”。比如源码第10行报错但实际错误在第9行甚至第8行。我见过最常见的元凶是Token化时没有正确处理换行符和注释里的\n错误是前一Token的“延迟效应”导致的例如在parse_factor里要RPAREN但实际是EOF报错时用了self.pos而不是“当前Token的位置信息”我自己的铁律是所有报错必须带Token的行列号。如果你在Parser里统一用peek()获取当前Token把行列号打印出来绝大多数定位问题立刻解决。4.4 工具链版本与环境的“隐形杀手”最后一条是我摔得最惨的地方工具链版本不一致比代码bug还难查。用ANTLR时注意4.x和3.x的语法文件不兼容网上抄的旧教程经常直接叫你配3.x。更坑的是ANTLR运行时版本必须与生成代码的版本严格一致差一个小版本都会跑出“NoSuchMethodError”。用LLVM时Rust绑定llvm-sys编译时间极长而且一旦你本机装了多个版本LLVMCMake会随机选一个编出来的代码在另一个机器上跑不了。建议直接docker固定环境镜像。我自己的经验是把一个“能跑的完整环境”用脚本固化下来要求所有同事都用同一个镜像或同一个脚本安装依赖。如果你只是个人项目写一个setup.sh也比口头约定强。4.5 从Toy语言到生产级语言的路线扩展如果你真想把这个Toy语言推向真实场景我建议按这个顺序扩展先做标准库字符串、数组、文件IO再做错误处理和堆栈跟踪然后才是类型系统、垃圾回收、并发。类型系统是个无底洞从动态类型到静态类型不是一个增量而是一次架构重写。Lua和JavaScript最初都是动态类型后来加类型标注都费了多年功夫。如果你一开始就带着类型系统设计建议直接参考TS或者Python的渐进类型方案不要闭门造车。还有一处容易被忽略社区与文档。语言设计90%的功夫在设计本身但10%的文档和示例代码决定了有没有人愿意用。我自己写语言时最深的体会是——给用户写一份像我上面这种“从0到1跑通”的教程效果比任何漂亮的语言特性都好。5. 写在最后的几个小建议整篇聊下来你会发现设计语言真的不是一件“必须懂编译原理所有章节”的玄学。它是由多个工程环节串联起来的想清楚目标选好工具链我建议手写Tokenizer递归下降ParserC后端把基础链路跑通再按需扩展。我见过太多人被“编译原理”四个字吓退但其实人人都可以造一门极小的语言。给你几个最实际的建议用Python做原型最快因为字符串处理和数据结构都方便做产品时再考虑换Rust或Go重写性能敏感部分。语法设计从极小集开始每加一个特性都要问自己“少了它用户真会分分钟放弃吗”。所有自研工具都做好版本锁定和环境脚本不然半年后你回来看自己的代码可能当场崩溃。最后再分享一个亲身经历的小技巧留着Tokenizer和Parser的接口稳定版本。哪怕你后来把整个后端重写只要前端的Token类型和AST节点不翻天覆地你积累的测试用例就能一直复用。我自己维护的脚本语言迭代到第二版时90%的测试用例原封不动跑通全靠当初接口设计时没贪图省事。这个习惯希望你也早点养成。