手写JSON解析器：从词法分析到语法树的编译原理实战-北京尧图网络

1. 从一段JSON文本到内存对象解析器到底在做什么很多人第一次接触编译原理都是从写一个JSON解析器开始的。这个选择很聪明——JSON的语法足够简单简单到一页纸就能写完文法但它又足够完整完整到能覆盖词法分析、语法分析、语义动作、错误处理这一整条链路。换句话说JSON解析器是编译原理的最小可用样本麻雀虽小五脏俱全。我在带新人做这个项目时最常听到的疑问是JSON解析器不就是调个库吗JSON.parse()一行代码的事为什么要自己写这个问题问得好因为它恰恰点出了这个项目的真正价值。调库你学到的是API自己写你学到的是文本如何变成结构化数据这套通用方法论。这套方法论往上可以延伸到编程语言的编译器、SQL引擎、配置文件解析器、模板引擎往下可以帮你理解为什么有些JSON库快得飞起有些却慢得让人抓狂。所以这篇内容我打算把整个流程从头到尾拆一遍从字符流开始经过词法分析切成Token再经过语法分析构建语法树最后通过语义动作把语法树转成真正的内存对象。中间我会重点讲清楚每一步为什么这么设计以及实际写代码时那些文档里不会告诉你的坑。适合已经会写代码、想真正搞懂解析器原理的读者也适合正在做编译原理课程设计、需要一份可落地参考的同学。先给一个全局的流程图景方便你建立心理模型。假设输入是这段JSON{name: parser, version: 2, tags: [json, compiler]}它在我们程序里的旅程是这样的字符流一长串字符程序眼里没有结构只有一个个char。词法分析Lexer/Tokenizer把字符流切成有意义的Token比如{、name、:、parser、,……每个Token带上类型和值。语法分析Parser按照JSON文法把Token序列组织成一棵语法树AST确认这个括号配对了这个逗号位置对了。语义动作/求值遍历AST把节点转换成目标语言的数据结构比如Python的dict、list或者Java的Map、List。这四步里前两步是识别后两步是构造。很多教程只讲前两步就收尾了结果读者拿到一棵AST不知道怎么用。我会把第四步也讲透因为那才是解析器真正交付价值的地方。提示本文所有代码示例以Python为主因为它的可读性最好方便你把注意力放在原理上。换成Java、Go、C思路完全一致只是类型声明和内存管理的细节不同。2. 词法分析把字符流切成有意义的Token2.1 为什么不能跳过词法分析直接做语法分析有人会想我直接在语法分析里一个字符一个字符地读边读边判断不行吗技术上可行但你会把两种完全不同性质的逻辑搅在一起。词法分析关心的是这个词长什么样——是数字、字符串、还是标点语法分析关心的是这些词的排列是否符合规则。把它们分开每一层的代码都会简单很多出错时也更容易定位是Token切错了还是Token组合错了一眼就能分辨。这就像读英文句子你先要能认出一个个单词词法才能分析句子结构语法。如果连单词边界都分不清谈何分析主谓宾。2.2 JSON的Token类型清单JSON的Token种类不多我整理成一张表写代码时照着实现就行Token类型说明示例LBRACE左花括号{RBRACE右花括号}LBRACKET左方括号[RBRACKET右方括号]COLON冒号:COMMA逗号,STRING字符串字面量helloNUMBER数字字面量42、3.14、-1e10TRUE / FALSE布尔字面量true、falseNULL空值nullEOF输入结束无注意这里有个设计选择true、false、null我建议单独作为Token类型而不是当成标识符再在语法阶段判断。原因是JSON里根本没有标识符这个概念把这三个关键字单独拎出来语法分析时直接匹配就行省去一层判断。2.3 手写词法分析器的核心循环词法分析器本质上是一个带位置指针的循环。核心逻辑是看当前字符是什么决定进入哪个分支消费掉相应的字符产出一个Token。class Token: def __init__(self, type_, value, pos): self.type type_ self.value value self.pos pos # 记录位置报错时能指出在哪 class Lexer: def __init__(self, text): self.text text self.pos 0 self.length len(text) def peek(self): if self.pos self.length: return self.text[self.pos] return None def advance(self): ch self.text[self.pos] self.pos 1 return ch def tokenize(self): tokens [] while self.pos self.length: ch self.peek() if ch in \t\n\r: self.advance() continue if ch {: tokens.append(Token(LBRACE, {, self.pos)); self.advance() elif ch }: tokens.append(Token(RBRACE, }, self.pos)); self.advance() # ... 其他单字符Token类似处理 elif ch : tokens.append(self.read_string()) elif ch - or ch.isdigit(): tokens.append(self.read_number()) elif ch t or ch f or ch n: tokens.append(self.read_keyword()) else: raise SyntaxError(fUnexpected character {ch} at {self.pos}) tokens.append(Token(EOF, None, self.pos)) return tokens这段代码看起来平平无奇但里面藏着几个关键决策我逐个说。2.4 字符串解析转义字符是第一个大坑read_string是词法分析里最容易写错的部分。JSON字符串支持转义\、\\、\n、\t、\uXXXX都要处理。新手最常见的错误是遇到\就以为字符串结束了结果把a\b这种输入切错。正确的做法是进入字符串后逐字符扫描遇到反斜杠就进入转义模式把下一个字符特殊处理。def read_string(self): start self.pos self.advance() # 跳过开头的引号 buf [] while True: ch self.peek() if ch is None: raise SyntaxError(fUnterminated string starting at {start}) if ch : self.advance() break if ch \\: self.advance() esc self.advance() mapping {: , \\: \\, /: /, n: \n, t: \t, r: \r, b: \b, f: \f} if esc u: hex_str self.text[self.pos:self.pos4] buf.append(chr(int(hex_str, 16))) self.pos 4 elif esc in mapping: buf.append(mapping[esc]) else: raise SyntaxError(fInvalid escape \\{esc} at {self.pos}) else: buf.append(self.advance()) return Token(STRING, .join(buf), start)这里有个细节值得强调Token里存的应该是解码后的字符串值而不是原始文本。比如输入是a\nbToken的value应该是真正含换行符的a换行b而不是字面的反斜杠加n。这样后续语法分析和求值阶段就不用再关心转义了。这个在词法阶段完成解码的原则能帮你省掉后面很多重复劳动。2.5 数字解析别用正则偷懒数字看起来简单其实JSON对数字的格式有严格规定不能有前导零01非法、小数点后必须有数字1.非法、指数部分要合法1e非法。很多人图省事直接上一个正则-?\d(\.\d)?([eE][-]?\d)?能跑但错误提示会很差——用户输入01你只能告诉他数字格式错误说不出具体哪里错。我建议手写状态机虽然代码长一点但每一步都能给出精确的错误位置。核心是分三段读整数部分、小数部分、指数部分每段都校验合法性。def read_number(self): start self.pos buf [] if self.peek() -: buf.append(self.advance()) # 整数部分 if self.peek() 0: buf.append(self.advance()) elif self.peek() and self.peek().isdigit(): while self.peek() and self.peek().isdigit(): buf.append(self.advance()) else: raise SyntaxError(fInvalid number at {start}) # 小数部分 if self.peek() .: buf.append(self.advance()) if not (self.peek() and self.peek().isdigit()): raise SyntaxError(fExpected digit after . at {self.pos}) while self.peek() and self.peek().isdigit(): buf.append(self.advance()) # 指数部分 if self.peek() in (e, E): buf.append(self.advance()) if self.peek() in (, -): buf.append(self.advance()) if not (self.peek() and self.peek().isdigit()): raise SyntaxError(fExpected digit in exponent at {self.pos}) while self.peek() and self.peek().isdigit(): buf.append(self.advance()) return Token(NUMBER, float(.join(buf)), start)注意这里我把所有数字都转成了float。实际生产环境要区分整数和浮点因为大整数用float会丢精度。JSON规范本身不区分但你的目标语言可能区分这个取舍要在设计阶段就想清楚。2.6 词法分析的经验之谈做了几个解析器之后我总结出几条词法阶段的通用经验分享给你位置信息一定要记。每个Token都带上起始偏移量报错时能直接告诉用户第15个字符处出错。没有位置信息的解析器调试起来是噩梦。空白字符的处理要统一。JSON的空白只有空格、制表符、换行、回车四种别用str.isspace()一把梭那个会匹配更多Unicode空白可能引入意外行为。不要边解析边求值。词法阶段就老老实实产出Token别想着读到数字就顺便存起来职责分离是解析器可维护性的基石。3. 语法分析递归下降如何把Token组织成树3.1 为什么选递归下降而不是自动生成工具语法分析有两大流派一是用工具如Yacc、ANTLR根据文法自动生成解析器二是手写递归下降。对于JSON这种规模我强烈建议手写递归下降理由有三第一JSON的文法是LL(1)的意味着只需要向前看一个Token就能决定走哪个分支递归下降写起来极其自然。第二手写代码可调试、可断点、可加日志出问题一眼能看出在哪一层。第三自动生成工具会引入额外的构建依赖和学习成本为了一个JSON解析器不值得。递归下降的核心思想是为文法里的每个非终结符写一个函数。JSON的文法大致是这样value → object | array | string | number | true | false | null object → { (pair (, pair)*)? } pair → string : value array → [ (value (, value)*)? ]对应地我们就写parse_value、parse_object、parse_array这几个函数每个函数负责识别自己那部分遇到子结构就调用对应的函数。3.2 语法树的节点设计在写解析函数之前先定义AST节点。JSON的节点类型和它的值类型一一对应class ASTNode: pass class ObjectNode(ASTNode): def __init__(self, pairs): self.pairs pairs # list of (key, value_node) class ArrayNode(ASTNode): def __init__(self, elements): self.elements elements class StringNode(ASTNode): def __init__(self, value): self.value value class NumberNode(ASTNode): def __init__(self, value): self.value value class BoolNode(ASTNode): def __init__(self, value): self.value value class NullNode(ASTNode): pass你可能会问既然最后要求值成Python的dict和list为什么不直接在解析阶段就构造dict还要多此一举搞个AST这是个好问题。答案是分层带来的灵活性。有了AST这层中间表示你可以做很多事静态检查比如检测重复key、格式转换转成YAML、XML、代码生成、甚至做AST的变换和优化。如果解析阶段直接产出dict这些能力就都失去了。多一层抽象换来的是可扩展性。3.3 递归下降解析器的骨架解析器持有一个Token列表和一个当前位置指针核心操作是peek()看当前Token、advance()消费当前Token、expect(type)断言当前Token类型并消费。class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def advance(self): tok self.tokens[self.pos] self.pos 1 return tok def expect(self, type_): tok self.peek() if tok.type ! type_: raise SyntaxError( fExpected {type_} but got {tok.type} at {tok.pos}) return self.advance() def parse(self): node self.parse_value() self.expect(EOF) return node def parse_value(self): tok self.peek() if tok.type LBRACE: return self.parse_object() elif tok.type LBRACKET: return self.parse_array() elif tok.type STRING: self.advance() return StringNode(tok.value) elif tok.type NUMBER: self.advance() return NumberNode(tok.value) elif tok.type TRUE: self.advance() return BoolNode(True) elif tok.type FALSE: self.advance() return BoolNode(False) elif tok.type NULL: self.advance() return NullNode() else: raise SyntaxError(fUnexpected token {tok.type} at {tok.pos})这段代码是整个解析器的中枢。parse_value根据当前Token的类型分派到具体的解析函数这就是递归下降里下降的含义——从高层结构一层层下降到基本值。3.4 对象和数组的解析处理逗号和空集合对象和数组的解析是递归下降里稍微绕一点的地方因为要处理空集合和元素间逗号两种情况。以对象为例def parse_object(self): self.expect(LBRACE) pairs [] if self.peek().type RBRACE: self.advance() return ObjectNode(pairs) while True: key_tok self.expect(STRING) self.expect(COLON) value_node self.parse_value() pairs.append((key_tok.value, value_node)) tok self.peek() if tok.type COMMA: self.advance() continue elif tok.type RBRACE: self.advance() break else: raise SyntaxError(fExpected , or }} at {tok.pos}) return ObjectNode(pairs)这里有个容易写错的地方循环的退出条件。很多新手写成先读一个pair然后while看是不是逗号结果遇到空对象{}就崩了因为第一个pair根本不存在。正确做法是先判断是不是右括号是就直接返回空对象否则进入循环。数组同理。还有一个细节逗号后面必须跟下一个元素不能直接跟右括号。也就是说[1,2,]是非法JSON。上面代码里遇到逗号后continue回到循环开头会再次调用parse_value如果此时是]parse_value会抛Unexpected token正好把这种错误拦下来。这个行为是符合JSON规范的别好心去容忍尾随逗号。3.5 错误恢复与报错质量一个能跑的解析器和一个好用的解析器差距往往在报错上。递归下降的报错天然有优势因为你知道自己期望什么。上面expect函数里那句Expected {type_} but got {tok.type} at {tok.pos}就是最基本的报错。但实际用起来光有Token类型还不够。用户看到Expected RBRACE but got COMMA at 42可能还是懵。我的经验是在报错信息里带上出错位置附近的原文片段。比如def error_context(self, pos, radius10): start max(0, pos - radius) end min(len(self.text), pos radius) return self.text[start:end]报错时输出... name: parser, ...并标出出错字符用户一眼就能定位。这个技巧在任何解析器里都适用成本极低体验提升巨大。3.6 递归深度与栈溢出递归下降有个天然隐患深层嵌套会导致栈溢出。JSON里[[[[[...]]]]]这种结构每嵌套一层就多一层函数调用。默认的递归深度Python约1000在解析恶意构造的深层JSON时会直接崩溃。解决方案有两个一是设置最大嵌套深度超过就报错这是最简单也最推荐的做法二是把递归改成显式的栈循环但代码复杂度会大幅上升对JSON这种场景不划算。我一般会在解析器里加一个depth计数器超过比如200层就抛Maximum nesting depth exceeded。这个数字不是随便定的要结合你的实际业务——正常JSON很少超过20层200层已经非常宽松了。4. 从语法树到内存对象求值阶段的设计4.1 求值器为什么值得单独写拿到AST之后最后一步是把它变成目标语言的数据结构。这一步看起来简单——遍历树遇到ObjectNode就建dict遇到ArrayNode就建list——但里面有几个设计点值得琢磨。首先是求值策略。你可以写一个递归的evaluate(node)函数也可以给每个节点类加一个eval()方法。前者把逻辑集中在一处后者更面向对象。我倾向于前者因为求值逻辑和节点结构是两回事分开更清晰将来想加一个转成YAML的求值器只要再写一个函数就行不用动节点类。def evaluate(node): if isinstance(node, ObjectNode): result {} for key, value_node in node.pairs: result[key] evaluate(value_node) return result elif isinstance(node, ArrayNode): return [evaluate(e) for e in node.elements] elif isinstance(node, StringNode): return node.value elif isinstance(node, NumberNode): return node.value elif isinstance(node, BoolNode): return node.value elif isinstance(node, NullNode): return None else: raise TypeError(fUnknown node type: {type(node)})就这么十几行但它完成了整个解析器的最终交付。4.2 重复key的处理一个被忽视的规范细节JSON规范里对重复key的行为是未定义的——{a: 1, a: 2}到底该得到什么规范没说。不同语言的库行为不一有的保留最后一个有的保留第一个有的报错。我的建议是明确报错。因为重复key几乎总是bug静默地取某一个值会让问题藏得很深。在求值阶段检测if key in result: raise ValueError(fDuplicate key {key}) result[key] evaluate(value_node)这个决策看起来小但在实际项目里能帮你省下大量排查时间。我见过因为重复key导致配置被覆盖、排查了半天的案例加上这个检查就再也不会发生了。4.3 大数字的精度陷阱前面词法阶段我提到把所有数字转成float这里要展开说说为什么这是个需要慎重对待的决策。JSON规范不区分整数和浮点但很多实际数据里整数可能非常大比如ID、时间戳毫秒级、雪花算法生成的ID。这些数字动辄18、19位超过了float能精确表示的53位尾数范围。一旦转成float末尾几位就丢了而且丢得悄无声息。 float(1234567890123456789) 1.2345678901234568e18看到没最后几位变了。如果你的JSON里存的是订单号这一丢就是灾难。解决方案是在词法阶段保留数字的原始字符串在求值阶段根据是否有小数点/指数来决定转int还是float。有小数点或指数就转float纯整数就转intPython的int是任意精度的不会丢。这个改动很小但能避免一类隐蔽的生产事故。4.4 性能优化什么时候该在意一个朴素的递归下降JSON解析器性能大概是标准库的几分之一到十几分之一。对于大多数场景够用了但如果你要解析几十MB的大JSON就得考虑优化。我按性价比排序几个优化点优化手段收益实现成本用字符索引代替切片中低预编译字符分类表中低避免中间Token列表流式解析高中用C扩展或Cython重写热点极高高前两个是顺手就能做的。比如判断字符是不是数字与其每次调isdigit()不如预先建一个256长度的布尔数组is_digit[ord(ch)]一次查表搞定。第三个流式解析是指词法分析和语法分析不分成两趟而是语法分析需要Token时现从字符流里取省掉整个Token列表的内存和构建时间。这个改动对架构有影响但收益明显。不过我要泼盆冷水在你确认解析器是性能瓶颈之前不要优化。绝大多数应用的瓶颈在IO和网络不在JSON解析。过早优化只会让代码变复杂、变难维护。5. 实测中那些文档不会告诉你的坑5.1 Unicode转义与代理对JSON的\uXXXX转义有个深坑代理对surrogate pair。Unicode里超过UFFFF的字符比如很多emoji在UTF-16里用两个16位码元表示JSON的\u转义沿用了这个机制。所以\uD83D\uDE00表示的是一个字符笑脸而不是两个。如果你在词法阶段遇到\u就简单地chr(int(hex, 16))会把代理对拆成两个无效字符。正确做法是读到高位代理0xD800-0xDBFF时检查后面是否紧跟一个低位代理0xDC00-0xDFFF是的话合并成一个码点。def read_unicode_escape(self): code int(self.text[self.pos:self.pos4], 16) self.pos 4 if 0xD800 code 0xDBFF: # 高位代理期待低位代理 if self.text[self.pos:self.pos2] \\u: self.pos 2 low int(self.text[self.pos:self.pos4], 16) self.pos 4 if 0xDC00 low 0xDFFF: combined 0x10000 ((code - 0xD800) 10) (low - 0xDC00) return chr(combined) raise SyntaxError(Invalid low surrogate) raise SyntaxError(Unpaired high surrogate) return chr(code)这个坑不常遇到但一旦遇到就是字符显示成乱码这种让人抓狂的问题。测试时记得加几个emoji的用例。5.2 空输入和纯空白输入和这种输入很多解析器会直接崩在parse_value里因为第一个Token就是EOF没有匹配任何分支。正确的行为是报一个清晰的错Empty input或Unexpected end of input。这个case在单元测试里一定要覆盖因为配置文件为空是很常见的场景。5.3 数字溢出的边界1e400这种数字转成float会变成inf。JSON规范没规定怎么办但静默变成无穷大通常不是用户想要的。我的做法是检测到inf就报错明确告诉用户数字超出范围。同理-1e400会变成-inf。5.4 深度嵌套的防御前面提过递归深度的问题这里补充一个实测数据Python默认递归限制1000但每层JSON嵌套实际消耗的栈帧不止一个parse_value调parse_array调parse_value……所以实际能承受的嵌套深度大概在300-400层。设置200层的上限是安全的。如果你用其他语言这个数字要重新测。5.5 一个完整的测试用例集写完解析器我建议至少覆盖这些用例它们能帮你发现90%的bug空对象{}、空数组[]单元素对象、单元素数组嵌套对象、嵌套数组、混合嵌套各种转义\、\\、\n、\u0041、代理对各种数字整数、负数、小数、指数、大整数三个字面量true、false、null错误用例未闭合字符串、尾随逗号、重复key、非法转义、空输入把这些用例写成表格驱动的测试每加一个功能就跑一遍回归成本极低。6. 把解析器用起来几个真实的扩展方向6.1 带位置信息的错误报告如果你的解析器要给终端用户用比如一个配置文件校验工具错误报告的质量直接决定用户体验。我建议在AST节点上也保留位置信息这样不仅能报语法错误还能报语义错误在第几行第几列。实现方式是在Token里记位置构造AST节点时把位置传进去。6.2 流式解析大文件标准做法是把整个文件读进内存再解析。但如果文件有几百MB内存扛不住。这时可以改成流式词法分析器从一个字符流而不是字符串读取语法分析器按需拉取Token。这样内存占用只和嵌套深度相关和文件大小无关。代价是代码复杂度上升且不能做需要全局信息的检查。6.3 从JSON扩展到JSON5或JSONCJSON5支持注释、尾随逗号、单引号字符串、无引号key等扩展语法。如果你理解了本文的解析器结构扩展起来并不难词法阶段加注释和单引号的识别语法阶段放宽逗号规则。这也是检验你是否真正掌握解析器原理的好练习——如果你能轻松扩展说明你理解了如果处处掣肘说明有些地方是死记硬背的。6.4 反向操作序列化器解析器是文本到对象序列化器是对象到文本。两者是对偶的写序列化器能加深你对格式规范的理解。比如字符串序列化时哪些字符必须转义控制字符、引号、反斜杠必须转义其他字符可以直接输出。这个必须转义的最小集合是很多人写序列化器时会搞错的点。我在实际项目里踩过最深的坑是早期版本没处理代理对结果用户存的昵称里带emoji解析出来变成两个乱码字符排查了半天才定位到\u转义。从那以后我写任何解析器都会先把Unicode相关的测试用例补齐。这个教训分享给你希望你能少走这段弯路。解析器这东西原理不难难的全在边界情况的处理上而边界情况恰恰是区分能跑和可靠的分水岭。

手写JSON解析器：从词法分析到语法树的编译原理实战

相关推荐

Java俄罗斯方块源码解析：游戏主循环、碰撞检测与消行实现

NLP与无人船：从自然语言指令到自主靠泊的完整技术链路

施耐德平台API设备列表获取与同步实战指南

更多资讯

MTT AIBOOK深度实测：专为AI Agent与多Agent协作打造的生产级运行平台

快恢复二极管FRD选型指南：从反向恢复时间到产线布局的行业调研拆解

机械原理试讲课件拆解：19页PPT讲透自由度计算与运动副分类

lingbot-map：移动机器人地图管理模块的设计与工程实践

自建知识工作插件集：从采集到检索的本地自动化方案

拆解“2000万只鹅已就位”：爆品预热背后的预期管理与营销逻辑

今日更新

微信云开发旅游小程序实战：LBS打卡+UGC社交全栈方案

金融AI代理平台核心拆解：从多代理协作到财报分析实战

基于大数据的智慧旅游推荐与可视化平台架构实践

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？