解析JSON这件事大多数时候就是调一个库返回一个对象完事。但你真的想过吗接口返回的字符串到你手里变成一个dict中间到底发生了什么如果从字节的角度看那只是一串没有任何结构的字符序列而程序要的却是一个能按键取值的哈希表。这个鸿沟就是由JSON解析器来填平的。它像极了一个数据翻译官把字节流翻译成程序能理解的结构。这篇文章就拿JSON解析器开刀用极简版的状态机实现把{age: 18}变成内存哈希表这整个过程拆开揉碎讲清楚。1. 解析器为什么必须存在字节流和内存结构之间的鸿沟1.1 一个JSON文本在计算机眼里到底是什么假设你有这么一行文本{age: 18}人眼一看这是明明白白的键值结构一个对象里面有个字段叫age值是18。但计算机看到的不是这些而是一串字符。我更愿意说“字节流”因为不管是存在文件里、走网络传输还是躺在内存缓冲区里它本质都是字节序列。如果把这几个字符换算成ASCII码大概是这样的123 34 97 103 101 34 58 32 49 56 125看到没有就是一堆数字。你没法直接在这串数字上问一句“年龄是多少”。没有字段名、没有边界、没有层级什么都看不出来。而程序真正想要的是一个能按键查值的结构。比如data parse_json(text) data[age] # 18在Python里这叫dict在Java里叫HashMap在C里叫unordered_map它们有一个共同的名字哈希表。哈希表的优势你应该很清楚能在平均O(1)的时间内根据一个键找到对应的值特别适合“按字段名取值”这种高频操作。从不可读的字节流到可操作的哈希表中间需要有人来完成转化。这个角色就是解析器。1.2 解析器在做的三件事词法、语法、语义很多人以为JSON解析器就是把字符串转成对象其实背后有三个层次词法层把连续的字符切成有意义的token。比如识别出{是左大括号age是一个字符串18是一个数字。词法分析处理的是“这是哪一类字符”的问题。语法层按照JSON语法规则判断token的组合是否合法。比如键后面必须是冒号值后面可以是逗号或右大括号。语法分析处理的是“这些token按这个顺序出现是否合理”的问题。语义层把合法的结构组装成真正的内存对象。遇到{新建一个哈希表遇到键值对就往哈希表里塞。语义层处理的是“这个结构在内存里应该长什么样”的问题。我之前见过有人用eval去解析JSON直接把字符串当代码执行。那本质上不是在写解析器而是把整个解释器的词法、语法、语义分析全借过来自己什么都没做。这种思路的问题有两个一是慢二是危险。JSON数据来自外部如果里面混进了恶意代码片段eval会把它当代码执行。真正的解析器必须自己掌握每个流程每个字符都能控制、能报错、能判断。1.3 一个极简解析器的整体视野拿{age: 18}这个JSON来说解析器的思考过程应该是这样的看到{知道要创建一个哈希表了。看到一个双引号字符串先不急着决定它是什么得看当前状态可能在键的位置也可能在值的位置。看到冒号知道刚读完的字符串应该是键。看到数字18知道当前键对应的值来了。最后看到}知道这个哈希表闭合了可以交出去了。如果JSON里还有嵌套比如对象套数组、数组套对象那就需要一个栈来记录“当前正在构造的容器”以及“下一次应该往哪里挂”。这个思路本质上就是状态机。2. 状态机为什么是解析器的天然搭档2.1 用红绿灯来理解状态机“状态机”这个词听起来很硬核其实并不难。它其实就是规定一堆状态和转移规则程序在某个状态下输入某个信号切换到下一个状态。你不需要记住之前经历了多少内容只需要知道当前状态和当前输入。生活里到处都是状态机。红绿灯就是一个典型例子红灯状态收到“倒计时结束”信号切到绿灯。绿灯状态收到“倒计时结束”信号切到黄灯。黄灯状态收到“倒计时结束”信号切回红灯。每个状态只关心当前灯色和当前信号不需要关心这个灯已经往返多少次。JSON解析器也是一回事每读一个字符不需要回顾前面全部字符的历史只需要知道当前解析到哪个阶段、这个字符是什么就能决定下一步怎么走。2.2 从JSON语法到一张状态转移表JSON的语法其实非常克制只有对象、数组、字符串、数字、布尔值、null这几种东西。一个极简解析器的状态集可以设计成六个核心状态状态含义合法输入BEGIN等待根容器开始{或[KEY_OR_END对象内部等待键名或结束或}AFTER_KEY键已读完等待冒号:VALUE等待一个值、{、[、数字、true、false、nullAFTER_VALUE值已读完等待后续,、}、]VALUE_OR_END数组内部等待元素或结束值、]这里最关键的一点是同一个字符在不同状态下含义完全不同。同样的双引号在KEY_OR_END状态下代表“键名的开始”在VALUE状态下代表“字符串值的开始”。同样的}在KEY_OR_END状态下代表“空对象结束”在AFTER_VALUE状态下代表“对象闭合”。如果不做状态区分代码会写得非常混乱到处都是难以维护的条件判断。我最早写解析器的时候喜欢把所有判断堆在一起结果一遇到嵌套就出事。后来老老实实把状态拆出来代码清爽了一个量级。状态机的价值不在于理论上的严谨表达而在于它把一个复杂问题变成了清晰的分支表。2.3 单遍扫描线性复杂度用状态机解析还有一个天然优势只需要从头到尾扫一遍字节流每个字符最多被处理一次。整体时间复杂度是O(n)和你输入的JSON大小成正比。这种特性非常适配网络流和文件流的场景读一点、解析一点、把已消费的字节丢弃内存占用可以保持得很低。相比之下有些解析器采用“先切成token数组再递归构建结构”的两阶段做法思路更直观但多了一次完整遍历也多了一份token存储的开销。这也是为什么很多高性能JSON库比如RapidJSON、simdjson、yyjson无论底层优化到什么程度骨架都还是逐字节推进的状态机。区别在于它们会用各种技巧减少进入状态机的字符数量而不是抛弃状态机。3. 手写一个极简版JSON解析器从零到能跑3.1 先明确状态集合下面这个极简版我打算严格用状态机的方式实现。状态集合就是上面表格里的六个状态。它不做太多花哨的事情核心目标是清楚表达状态转移和内存结构组装的过程。代码我用Python写因为可读性足够高你换成C、Go、Rust思路完全一样。3.2 完整代码一个能跑的极简状态机解析器def skip_ws(text, i): n len(text) while i n and text[i] in \t\n\r: i 1 return i def read_string(text, i): n len(text) parts [] while i n: ch text[i] if ch \\: i 1 if i n: break esc text[i] mapping { : , \\: \\, /: /, b: \b, f: \f, n: \n, r: \r, t: \t, } if esc u: if i 4 n: code int(text[i 1:i 5], 16) parts.append(chr(code)) i 4 else: parts.append(mapping.get(esc, esc)) i 1 elif ch : return .join(parts), i else: parts.append(ch) i 1 raise ValueError(未闭合的字符串) def read_number(text, i): start i n len(text) if i n and text[i] -: i 1 while i n and text[i].isdigit(): i 1 if i n and text[i] .: i 1 while i n and text[i].isdigit(): i 1 if i n and text[i] in eE: i 1 if i n and text[i] in -: i 1 while i n and text[i].isdigit(): i 1 raw text[start:i] if . in raw or e in raw or E in raw: return float(raw), i return int(raw), i def read_literal(text, i, word, value): if text.startswith(word, i): return value, i len(word) raise ValueError(f非法字面量期望 {word}) def attach(parent, key, value): if isinstance(parent, list): parent.append(value) else: parent[key] value def parse_json(text): i 0 n len(text) state BEGIN stack [] current_key None result None while True: i skip_ws(text, i) if i n: raise ValueError(JSON 数据不完整) ch text[i] if state BEGIN: if ch {: obj {} stack.append(obj) result obj state KEY_OR_END i 1 elif ch [: arr [] stack.append(arr) result arr state VALUE_OR_END i 1 else: raise ValueError(JSON 必须以 { 或 [ 开头) elif state KEY_OR_END: if ch }: if not isinstance(stack[-1], dict): raise ValueError(括号不匹配) stack.pop() if not stack: return result state AFTER_VALUE i 1 elif ch : i 1 key, end read_string(text, i) current_key key i end 1 state AFTER_KEY else: raise ValueError(对象中期望字符串键或 }) elif state AFTER_KEY: if ch ! :: raise ValueError(键后缺少冒号) state VALUE i 1 elif state VALUE: parent stack[-1] if ch : i 1 value, end read_string(text, i) attach(parent, current_key, value) i end 1 state AFTER_VALUE elif ch {: obj {} attach(parent, current_key, obj) stack.append(obj) state KEY_OR_END i 1 elif ch [: arr [] attach(parent, current_key, arr) stack.append(arr) state VALUE_OR_END i 1 elif ch - or ch.isdigit(): value, end read_number(text, i) attach(parent, current_key, value) i end state AFTER_VALUE elif ch t: value, end read_literal(text, i, true, True) attach(parent, current_key, value) i end state AFTER_VALUE elif ch f: value, end read_literal(text, i, false, False) attach(parent, current_key, value) i end state AFTER_VALUE elif ch n: value, end read_literal(text, i, null, None) attach(parent, current_key, value) i end state AFTER_VALUE else: raise ValueError(无法识别的值) elif state VALUE_OR_END: if ch ]: if not isinstance(stack[-1], list): raise ValueError(括号不匹配) stack.pop() if not stack: return result state AFTER_VALUE i 1 else: state VALUE elif state AFTER_VALUE: if ch ,: if isinstance(stack[-1], list): state VALUE_OR_END else: state KEY_OR_END i 1 elif ch } or ch ]: if ch }: if not isinstance(stack[-1], dict): raise ValueError(括号不匹配) else: if not isinstance(stack[-1], list): raise ValueError(括号不匹配) stack.pop() if not stack: return result i 1 else: raise ValueError(值后缺少逗号或右括号) else: raise ValueError(f未知状态: {state})你直接复制这段代码本地跑一下parse_json({age: 18})会得到{age: 18}这就是一个Python dict底层就是哈希表。3.3 几个容易被忽略的实现细节辅助函数返回值的约定read_string返回两个值解析出来的字符串以及结束引号所在的下标。read_number返回的是数字值以及数字结束后的下标。这个“返回结束位置”的设计很关键。主循环拿到结束位置后直接把指针移到下一个字符继续处理不用反复回退也不用额外记住“刚才停在哪了”。对于状态机来说当前位置指针就是状态的“输入来源”必须精确定位。attach函数为什么能统一对象和数组当解析出一个新值时它可能应该挂到对象上也可能应该挂到数组上。如果父容器是dict就parent[current_key] value如果是list就parent.append(value)。统一用一个attach函数处理主循环代码就不需要每遇到一个值都写一遍类型判断。current_key的覆盖机制current_key在极简版里是全局共享的。进入嵌套对象时挂载新对象用的还是外层当前键之后current_key会被内层重新赋值内层闭合、外层继续时下一个键会再次覆盖它。只要保证每一个键值对在attach时及时消费掉current_key就不会串数据。工业级实现会做得更稳妥把当前键也压进栈里但极简版已经足够说明问题。3.4 运行轨迹{age: 18}是如何变成哈希表的咱一步步看输入{age: 18}的解析过程步骤当前字符状态动作1{BEGIN新建空dict压入栈进入KEY_OR_END2KEY_OR_END读取键名age保存到current_key进入AFTER_KEY3:AFTER_KEY确认冒号进入VALUE41VALUE读取数字18挂到栈顶dict的age键进入AFTER_VALUE5}AFTER_VALUE栈顶dict闭合弹出栈空返回结果对照代码走一遍你会发现整个过程没有任何一步需要回头看已经消费的字符也没有任何一步需要预知后面还有多少内容。这就是状态机简单可靠的本源。4. 从age到18哈希表到底是怎么搭起来的4.1 attach背后发生的事当代码执行parent[current_key] 18时如果parent是Python的dict这一步实际在做两件事把字符串age作为键交给哈希函数计算哈希值。根据哈希值在底层的桶数组中找到对应位置把18写入。对外我们看到的只是一个赋值语句对内它完成了一次哈希计算和一次桶内操作。对用户来说完全透明。这也是哈希表在工程中如此普及的原因接口简单复杂度可控。有一点需要提醒JSON区分数字和字符串所以18和18完全是两个值。极简版里数字直接存成Python的int或float字符串存成str。以后你解析接口数据时遇到类型对不上往往是这里出了问题而不是JSON解析器出了问题。4.2 哈希表不是“字典”的唯一答案{age: 18}在Python里是dictJava里可能是HashMapC里可能是unordered_mapC项目里可能得自己维护一张哈希表。它们内部实现细节差别很大有的用开放寻址有的用链地址法有的扩容策略激进有的保守。但对JSON解析器来说它们只关心“能存能取”具体选择由宿主语言生态决定。在一些嵌入式或性能敏感环境中哈希表也不一定是优选。线性探测表、顺序存储的键值对列表都可能是更好的选择因为内存更紧凑、缓存更友好。哈希表是通用场景的默认答案不代表所有场景的唯一答案。极简版直接用dict是因为它忠实于“JSON对象天然对应哈希表”的直觉。4.3 一个完整的翻译闭环现在可以完整回答开头的提问了。输入是字节流左大括号、双引号、字母a、字母g、字母e、双引号、冒号、空格、数字1、数字8、右大括号。解析器用状态机逐字符推进把字节流拆成token识别出“这是一个对象里面有一个字符串键age一个数字值18”然后在堆上构造出一个哈希表填充键值对。当你拿到这个哈希表的引用时JSON文本已经被完全翻译成了内存结构。整个过程没有魔法就是状态机加数据结构组装。5. 极简版上线后的真实吐槽边界与错误处理5.1 字符串转义是个大坑极简版处理了基本的转义符\、\\、\n、\t、\uXXXX。但真实的JSON里有很多隐藏问题。比如emoji。很多emoji在JSON里是用两个\u转义字符表示的代理对像\uD83D\uDE00。规范上这两个码位要合并成一个Unicode字符。极简版没有做合并直接把两个单独的代理字符追加进字符串。在Python里字符串里可以容纳独立的代理项显示起来往往有问题但在别的语言里可能会直接产生乱码或报错。工业级解析器对这块有专门的处理逻辑。另一个隐蔽问题是控制字符。JSON规范不允许字符串里出现未转义的控制字符比如ASCII码0到31里的那些。极简版对它们很宽容直接放进结果。这在解析不规范第三方接口时会让你错过一次提前发现问题的机会。真实项目里我建议至少加一道校验字符串内如果出现小于0x20的字符且不是转义序列直接报错。5.2 数字格式你以为你写对了其实没有{age: 18}很简单但真实数据里经常出现各种奇怪写法。{v: 1e3}极简版会返回1000.0没问题。{v: 01}极简版也会返回1但这其实是非法JSON规范不允许前导0。{v: 1.2.3}极简版读数字到1.2为止然后在AFTER_VALUE状态发现下一个字符是.报错“缺少逗号或右括号”。这也算一种错误暴露但错误信息不够直观。{v: -}极简版在VALUE状态会进入数字分支但read_number读不到数字最终切片-会被int(-)抛出异常错误栈不太友好。更麻烦的是浮点精度。{id: 9007199254740993}这个数在支持任意精度整数的Python里能存准但如果目标语言是JavaScript或者你把它转成double它会变成9007199254740992精度丢了。这在涉及ID、金额、时间戳的JSON里是个经典大坑。如果你要解析超大数字最好确认目标解析器有没有任意精度模式或者干脆把数字先当字符串读再自己按需转换。5.3 报错要能定位到字符极简版的错误信息大致是“值后缺少逗号”“对象中期望字符串键或}”之类但没有行号、列号也没有上下文内容。调试一个几百行的JSON时这种错误信息约等于没有。真实解析器的错误定位非常讲究。要维护当前行号、列号遇到多字节字符时偏移量计算必须准确栈里还要保存每个括号的位置方便报“期望}但遇到]”时指出是哪个位置的问题。我自己调过一个大型集成配置报错只写了parse error at position xxx但全程没下标最后只能写脚本二分定位。工业级JSON解析器把错误信息做得很详细不是贴心是必需。5.4 重复键、深层嵌套和JSON Lines标准JSON没有禁止重复键。不同解析器处理方式也不一样有的保留最后一个有的保留第一个还有的直接报错。极简版本身是Python dict天然保留最后一个。但如果你在做一个配置系统重复键大概率说明配置文件写重了最好在解析之前做静态检查。深层嵌套也是个隐患。极简版用Python的list当栈能解析的深度受内存限制。但如果是递归下降实现还要受调用栈限制。真实世界里有些JSON的嵌套深到几千层甚至几万层比如某些自动生成的结构化数据。这时候解析器必须决定是限制深度直接报错还是冒着内存耗尽风险继续解析。simdjson有明确的深度控制安全要求高的解析器也会把深度上限作为配置项。极简版没有深度限制跑到很深很容易卡死你可以自己加一个depth计数。最后说一下JSON Lines。现在日志场景特别爱用NDJSON也就是每行一个JSON对象。它的解析器和普通JSON解析器最大的区别是必须支持流式增量切行不能假设一次就读完整段内容。极简版面向单段JSON如果你拿它去解析超大日志文件会非常吃力。6. 从能跑到能扛工业级解析器在卷什么6.1 内存分配一次分配和反复分配的区别极简版每遇到一个对象或数组就新建一个容器每读一个字符串就新建一个Python字符串对象。小JSON问题不大但几十MB的配置文件可能产生几百万个短字符串对象分配开销和内存碎片相当可观。RapidJSON提供了一个内存池分配器一次申请大块内存小对象从池里切用完统一释放。SIMD优化之外的另一个突破口就是减少内存分配次数。有的解析器还会做字符串去重、零拷贝引用避免把JSON文本里的子串反复复制成新字符串。这就是为什么同样的解析逻辑工业级实现能比玩具实现快几倍到几十倍。6.2 SIMD一次处理几十个字节逐字节解析是极简版的做法但现代CPU的SIMD指令可以一次处理16、32甚至64个字节。simdjson的绝活就是先用SIMD快速跳过大量无关字符定位到真正需要关注的符号——引号、冒号、括号、逗号——然后再把这一小段交给状态机细致处理。这其实并没有颠覆状态机而是减少了进入状态机的字符数量。所以你会看到性能测试里simdjson解析GB级JSON能比传统库快出一个数量级。明白这个原理对你选型也有帮助如果项目里有超大JSON或者高QPS接口别自己造轮子直接选有SIMD优化的解析器更靠谱。6.3 DOM还是SAX解析器不止一种形态极简版返回完整树结构对应的是DOM API。好处是随机访问方便任何字段都能随手查坏处是必须等全部解析完成而且整个结构都在内存里。另一种是流式API也叫SAX风格。解析器一边读一边回调“发现一个键”“发现一个值”“对象开始”“对象结束”客户端代码在回调里自己决定存什么、怎么存。这种模式非常适合超大JSON因为你不需要把完整结构放进内存解析到某个节点时已经可以直接开始处理并释放掉前面用过的内存。所以极简解析器只是让人理解原理的入门工具真正做项目选型时你得先回答一个问题我是要一次性完整结构还是要流水线式地处理大量JSON记录答案决定了你选哪个库、用哪种接口。我自己第一次手写JSON解析器的时候以为最难的是背JSON语法结果发现真正的坑全在边界转义、数字格式、括号匹配、深层嵌套、错误定位。极简版的好处就是把主干逻辑暴露得很干净你完全可以在它基础上继续加功能支持精确报错行号、支持深度限制、甚至扩展成流式回调接口。如果你真想彻底掌握解析器建议把这个代码抄一遍自己改一版能报错、能处理嵌套的完成版再拿几个真实接口的JSON数据去压一压。亲手把一个字节流变成哈希表的成就感真的和看一百篇原理文章不一样。
手写JSON解析器：用状态机把字节流变成哈希表
解析JSON这件事大多数时候就是调一个库返回一个对象完事。但你真的想过吗接口返回的字符串到你手里变成一个dict中间到底发生了什么如果从字节的角度看那只是一串没有任何结构的字符序列而程序要的却是一个能按键取值的哈希表。这个鸿沟就是由JSON解析器来填平的。它像极了一个数据翻译官把字节流翻译成程序能理解的结构。这篇文章就拿JSON解析器开刀用极简版的状态机实现把{age: 18}变成内存哈希表这整个过程拆开揉碎讲清楚。1. 解析器为什么必须存在字节流和内存结构之间的鸿沟1.1 一个JSON文本在计算机眼里到底是什么假设你有这么一行文本{age: 18}人眼一看这是明明白白的键值结构一个对象里面有个字段叫age值是18。但计算机看到的不是这些而是一串字符。我更愿意说“字节流”因为不管是存在文件里、走网络传输还是躺在内存缓冲区里它本质都是字节序列。如果把这几个字符换算成ASCII码大概是这样的123 34 97 103 101 34 58 32 49 56 125看到没有就是一堆数字。你没法直接在这串数字上问一句“年龄是多少”。没有字段名、没有边界、没有层级什么都看不出来。而程序真正想要的是一个能按键查值的结构。比如data parse_json(text) data[age] # 18在Python里这叫dict在Java里叫HashMap在C里叫unordered_map它们有一个共同的名字哈希表。哈希表的优势你应该很清楚能在平均O(1)的时间内根据一个键找到对应的值特别适合“按字段名取值”这种高频操作。从不可读的字节流到可操作的哈希表中间需要有人来完成转化。这个角色就是解析器。1.2 解析器在做的三件事词法、语法、语义很多人以为JSON解析器就是把字符串转成对象其实背后有三个层次词法层把连续的字符切成有意义的token。比如识别出{是左大括号age是一个字符串18是一个数字。词法分析处理的是“这是哪一类字符”的问题。语法层按照JSON语法规则判断token的组合是否合法。比如键后面必须是冒号值后面可以是逗号或右大括号。语法分析处理的是“这些token按这个顺序出现是否合理”的问题。语义层把合法的结构组装成真正的内存对象。遇到{新建一个哈希表遇到键值对就往哈希表里塞。语义层处理的是“这个结构在内存里应该长什么样”的问题。我之前见过有人用eval去解析JSON直接把字符串当代码执行。那本质上不是在写解析器而是把整个解释器的词法、语法、语义分析全借过来自己什么都没做。这种思路的问题有两个一是慢二是危险。JSON数据来自外部如果里面混进了恶意代码片段eval会把它当代码执行。真正的解析器必须自己掌握每个流程每个字符都能控制、能报错、能判断。1.3 一个极简解析器的整体视野拿{age: 18}这个JSON来说解析器的思考过程应该是这样的看到{知道要创建一个哈希表了。看到一个双引号字符串先不急着决定它是什么得看当前状态可能在键的位置也可能在值的位置。看到冒号知道刚读完的字符串应该是键。看到数字18知道当前键对应的值来了。最后看到}知道这个哈希表闭合了可以交出去了。如果JSON里还有嵌套比如对象套数组、数组套对象那就需要一个栈来记录“当前正在构造的容器”以及“下一次应该往哪里挂”。这个思路本质上就是状态机。2. 状态机为什么是解析器的天然搭档2.1 用红绿灯来理解状态机“状态机”这个词听起来很硬核其实并不难。它其实就是规定一堆状态和转移规则程序在某个状态下输入某个信号切换到下一个状态。你不需要记住之前经历了多少内容只需要知道当前状态和当前输入。生活里到处都是状态机。红绿灯就是一个典型例子红灯状态收到“倒计时结束”信号切到绿灯。绿灯状态收到“倒计时结束”信号切到黄灯。黄灯状态收到“倒计时结束”信号切回红灯。每个状态只关心当前灯色和当前信号不需要关心这个灯已经往返多少次。JSON解析器也是一回事每读一个字符不需要回顾前面全部字符的历史只需要知道当前解析到哪个阶段、这个字符是什么就能决定下一步怎么走。2.2 从JSON语法到一张状态转移表JSON的语法其实非常克制只有对象、数组、字符串、数字、布尔值、null这几种东西。一个极简解析器的状态集可以设计成六个核心状态状态含义合法输入BEGIN等待根容器开始{或[KEY_OR_END对象内部等待键名或结束或}AFTER_KEY键已读完等待冒号:VALUE等待一个值、{、[、数字、true、false、nullAFTER_VALUE值已读完等待后续,、}、]VALUE_OR_END数组内部等待元素或结束值、]这里最关键的一点是同一个字符在不同状态下含义完全不同。同样的双引号在KEY_OR_END状态下代表“键名的开始”在VALUE状态下代表“字符串值的开始”。同样的}在KEY_OR_END状态下代表“空对象结束”在AFTER_VALUE状态下代表“对象闭合”。如果不做状态区分代码会写得非常混乱到处都是难以维护的条件判断。我最早写解析器的时候喜欢把所有判断堆在一起结果一遇到嵌套就出事。后来老老实实把状态拆出来代码清爽了一个量级。状态机的价值不在于理论上的严谨表达而在于它把一个复杂问题变成了清晰的分支表。2.3 单遍扫描线性复杂度用状态机解析还有一个天然优势只需要从头到尾扫一遍字节流每个字符最多被处理一次。整体时间复杂度是O(n)和你输入的JSON大小成正比。这种特性非常适配网络流和文件流的场景读一点、解析一点、把已消费的字节丢弃内存占用可以保持得很低。相比之下有些解析器采用“先切成token数组再递归构建结构”的两阶段做法思路更直观但多了一次完整遍历也多了一份token存储的开销。这也是为什么很多高性能JSON库比如RapidJSON、simdjson、yyjson无论底层优化到什么程度骨架都还是逐字节推进的状态机。区别在于它们会用各种技巧减少进入状态机的字符数量而不是抛弃状态机。3. 手写一个极简版JSON解析器从零到能跑3.1 先明确状态集合下面这个极简版我打算严格用状态机的方式实现。状态集合就是上面表格里的六个状态。它不做太多花哨的事情核心目标是清楚表达状态转移和内存结构组装的过程。代码我用Python写因为可读性足够高你换成C、Go、Rust思路完全一样。3.2 完整代码一个能跑的极简状态机解析器def skip_ws(text, i): n len(text) while i n and text[i] in \t\n\r: i 1 return i def read_string(text, i): n len(text) parts [] while i n: ch text[i] if ch \\: i 1 if i n: break esc text[i] mapping { : , \\: \\, /: /, b: \b, f: \f, n: \n, r: \r, t: \t, } if esc u: if i 4 n: code int(text[i 1:i 5], 16) parts.append(chr(code)) i 4 else: parts.append(mapping.get(esc, esc)) i 1 elif ch : return .join(parts), i else: parts.append(ch) i 1 raise ValueError(未闭合的字符串) def read_number(text, i): start i n len(text) if i n and text[i] -: i 1 while i n and text[i].isdigit(): i 1 if i n and text[i] .: i 1 while i n and text[i].isdigit(): i 1 if i n and text[i] in eE: i 1 if i n and text[i] in -: i 1 while i n and text[i].isdigit(): i 1 raw text[start:i] if . in raw or e in raw or E in raw: return float(raw), i return int(raw), i def read_literal(text, i, word, value): if text.startswith(word, i): return value, i len(word) raise ValueError(f非法字面量期望 {word}) def attach(parent, key, value): if isinstance(parent, list): parent.append(value) else: parent[key] value def parse_json(text): i 0 n len(text) state BEGIN stack [] current_key None result None while True: i skip_ws(text, i) if i n: raise ValueError(JSON 数据不完整) ch text[i] if state BEGIN: if ch {: obj {} stack.append(obj) result obj state KEY_OR_END i 1 elif ch [: arr [] stack.append(arr) result arr state VALUE_OR_END i 1 else: raise ValueError(JSON 必须以 { 或 [ 开头) elif state KEY_OR_END: if ch }: if not isinstance(stack[-1], dict): raise ValueError(括号不匹配) stack.pop() if not stack: return result state AFTER_VALUE i 1 elif ch : i 1 key, end read_string(text, i) current_key key i end 1 state AFTER_KEY else: raise ValueError(对象中期望字符串键或 }) elif state AFTER_KEY: if ch ! :: raise ValueError(键后缺少冒号) state VALUE i 1 elif state VALUE: parent stack[-1] if ch : i 1 value, end read_string(text, i) attach(parent, current_key, value) i end 1 state AFTER_VALUE elif ch {: obj {} attach(parent, current_key, obj) stack.append(obj) state KEY_OR_END i 1 elif ch [: arr [] attach(parent, current_key, arr) stack.append(arr) state VALUE_OR_END i 1 elif ch - or ch.isdigit(): value, end read_number(text, i) attach(parent, current_key, value) i end state AFTER_VALUE elif ch t: value, end read_literal(text, i, true, True) attach(parent, current_key, value) i end state AFTER_VALUE elif ch f: value, end read_literal(text, i, false, False) attach(parent, current_key, value) i end state AFTER_VALUE elif ch n: value, end read_literal(text, i, null, None) attach(parent, current_key, value) i end state AFTER_VALUE else: raise ValueError(无法识别的值) elif state VALUE_OR_END: if ch ]: if not isinstance(stack[-1], list): raise ValueError(括号不匹配) stack.pop() if not stack: return result state AFTER_VALUE i 1 else: state VALUE elif state AFTER_VALUE: if ch ,: if isinstance(stack[-1], list): state VALUE_OR_END else: state KEY_OR_END i 1 elif ch } or ch ]: if ch }: if not isinstance(stack[-1], dict): raise ValueError(括号不匹配) else: if not isinstance(stack[-1], list): raise ValueError(括号不匹配) stack.pop() if not stack: return result i 1 else: raise ValueError(值后缺少逗号或右括号) else: raise ValueError(f未知状态: {state})你直接复制这段代码本地跑一下parse_json({age: 18})会得到{age: 18}这就是一个Python dict底层就是哈希表。3.3 几个容易被忽略的实现细节辅助函数返回值的约定read_string返回两个值解析出来的字符串以及结束引号所在的下标。read_number返回的是数字值以及数字结束后的下标。这个“返回结束位置”的设计很关键。主循环拿到结束位置后直接把指针移到下一个字符继续处理不用反复回退也不用额外记住“刚才停在哪了”。对于状态机来说当前位置指针就是状态的“输入来源”必须精确定位。attach函数为什么能统一对象和数组当解析出一个新值时它可能应该挂到对象上也可能应该挂到数组上。如果父容器是dict就parent[current_key] value如果是list就parent.append(value)。统一用一个attach函数处理主循环代码就不需要每遇到一个值都写一遍类型判断。current_key的覆盖机制current_key在极简版里是全局共享的。进入嵌套对象时挂载新对象用的还是外层当前键之后current_key会被内层重新赋值内层闭合、外层继续时下一个键会再次覆盖它。只要保证每一个键值对在attach时及时消费掉current_key就不会串数据。工业级实现会做得更稳妥把当前键也压进栈里但极简版已经足够说明问题。3.4 运行轨迹{age: 18}是如何变成哈希表的咱一步步看输入{age: 18}的解析过程步骤当前字符状态动作1{BEGIN新建空dict压入栈进入KEY_OR_END2KEY_OR_END读取键名age保存到current_key进入AFTER_KEY3:AFTER_KEY确认冒号进入VALUE41VALUE读取数字18挂到栈顶dict的age键进入AFTER_VALUE5}AFTER_VALUE栈顶dict闭合弹出栈空返回结果对照代码走一遍你会发现整个过程没有任何一步需要回头看已经消费的字符也没有任何一步需要预知后面还有多少内容。这就是状态机简单可靠的本源。4. 从age到18哈希表到底是怎么搭起来的4.1 attach背后发生的事当代码执行parent[current_key] 18时如果parent是Python的dict这一步实际在做两件事把字符串age作为键交给哈希函数计算哈希值。根据哈希值在底层的桶数组中找到对应位置把18写入。对外我们看到的只是一个赋值语句对内它完成了一次哈希计算和一次桶内操作。对用户来说完全透明。这也是哈希表在工程中如此普及的原因接口简单复杂度可控。有一点需要提醒JSON区分数字和字符串所以18和18完全是两个值。极简版里数字直接存成Python的int或float字符串存成str。以后你解析接口数据时遇到类型对不上往往是这里出了问题而不是JSON解析器出了问题。4.2 哈希表不是“字典”的唯一答案{age: 18}在Python里是dictJava里可能是HashMapC里可能是unordered_mapC项目里可能得自己维护一张哈希表。它们内部实现细节差别很大有的用开放寻址有的用链地址法有的扩容策略激进有的保守。但对JSON解析器来说它们只关心“能存能取”具体选择由宿主语言生态决定。在一些嵌入式或性能敏感环境中哈希表也不一定是优选。线性探测表、顺序存储的键值对列表都可能是更好的选择因为内存更紧凑、缓存更友好。哈希表是通用场景的默认答案不代表所有场景的唯一答案。极简版直接用dict是因为它忠实于“JSON对象天然对应哈希表”的直觉。4.3 一个完整的翻译闭环现在可以完整回答开头的提问了。输入是字节流左大括号、双引号、字母a、字母g、字母e、双引号、冒号、空格、数字1、数字8、右大括号。解析器用状态机逐字符推进把字节流拆成token识别出“这是一个对象里面有一个字符串键age一个数字值18”然后在堆上构造出一个哈希表填充键值对。当你拿到这个哈希表的引用时JSON文本已经被完全翻译成了内存结构。整个过程没有魔法就是状态机加数据结构组装。5. 极简版上线后的真实吐槽边界与错误处理5.1 字符串转义是个大坑极简版处理了基本的转义符\、\\、\n、\t、\uXXXX。但真实的JSON里有很多隐藏问题。比如emoji。很多emoji在JSON里是用两个\u转义字符表示的代理对像\uD83D\uDE00。规范上这两个码位要合并成一个Unicode字符。极简版没有做合并直接把两个单独的代理字符追加进字符串。在Python里字符串里可以容纳独立的代理项显示起来往往有问题但在别的语言里可能会直接产生乱码或报错。工业级解析器对这块有专门的处理逻辑。另一个隐蔽问题是控制字符。JSON规范不允许字符串里出现未转义的控制字符比如ASCII码0到31里的那些。极简版对它们很宽容直接放进结果。这在解析不规范第三方接口时会让你错过一次提前发现问题的机会。真实项目里我建议至少加一道校验字符串内如果出现小于0x20的字符且不是转义序列直接报错。5.2 数字格式你以为你写对了其实没有{age: 18}很简单但真实数据里经常出现各种奇怪写法。{v: 1e3}极简版会返回1000.0没问题。{v: 01}极简版也会返回1但这其实是非法JSON规范不允许前导0。{v: 1.2.3}极简版读数字到1.2为止然后在AFTER_VALUE状态发现下一个字符是.报错“缺少逗号或右括号”。这也算一种错误暴露但错误信息不够直观。{v: -}极简版在VALUE状态会进入数字分支但read_number读不到数字最终切片-会被int(-)抛出异常错误栈不太友好。更麻烦的是浮点精度。{id: 9007199254740993}这个数在支持任意精度整数的Python里能存准但如果目标语言是JavaScript或者你把它转成double它会变成9007199254740992精度丢了。这在涉及ID、金额、时间戳的JSON里是个经典大坑。如果你要解析超大数字最好确认目标解析器有没有任意精度模式或者干脆把数字先当字符串读再自己按需转换。5.3 报错要能定位到字符极简版的错误信息大致是“值后缺少逗号”“对象中期望字符串键或}”之类但没有行号、列号也没有上下文内容。调试一个几百行的JSON时这种错误信息约等于没有。真实解析器的错误定位非常讲究。要维护当前行号、列号遇到多字节字符时偏移量计算必须准确栈里还要保存每个括号的位置方便报“期望}但遇到]”时指出是哪个位置的问题。我自己调过一个大型集成配置报错只写了parse error at position xxx但全程没下标最后只能写脚本二分定位。工业级JSON解析器把错误信息做得很详细不是贴心是必需。5.4 重复键、深层嵌套和JSON Lines标准JSON没有禁止重复键。不同解析器处理方式也不一样有的保留最后一个有的保留第一个还有的直接报错。极简版本身是Python dict天然保留最后一个。但如果你在做一个配置系统重复键大概率说明配置文件写重了最好在解析之前做静态检查。深层嵌套也是个隐患。极简版用Python的list当栈能解析的深度受内存限制。但如果是递归下降实现还要受调用栈限制。真实世界里有些JSON的嵌套深到几千层甚至几万层比如某些自动生成的结构化数据。这时候解析器必须决定是限制深度直接报错还是冒着内存耗尽风险继续解析。simdjson有明确的深度控制安全要求高的解析器也会把深度上限作为配置项。极简版没有深度限制跑到很深很容易卡死你可以自己加一个depth计数。最后说一下JSON Lines。现在日志场景特别爱用NDJSON也就是每行一个JSON对象。它的解析器和普通JSON解析器最大的区别是必须支持流式增量切行不能假设一次就读完整段内容。极简版面向单段JSON如果你拿它去解析超大日志文件会非常吃力。6. 从能跑到能扛工业级解析器在卷什么6.1 内存分配一次分配和反复分配的区别极简版每遇到一个对象或数组就新建一个容器每读一个字符串就新建一个Python字符串对象。小JSON问题不大但几十MB的配置文件可能产生几百万个短字符串对象分配开销和内存碎片相当可观。RapidJSON提供了一个内存池分配器一次申请大块内存小对象从池里切用完统一释放。SIMD优化之外的另一个突破口就是减少内存分配次数。有的解析器还会做字符串去重、零拷贝引用避免把JSON文本里的子串反复复制成新字符串。这就是为什么同样的解析逻辑工业级实现能比玩具实现快几倍到几十倍。6.2 SIMD一次处理几十个字节逐字节解析是极简版的做法但现代CPU的SIMD指令可以一次处理16、32甚至64个字节。simdjson的绝活就是先用SIMD快速跳过大量无关字符定位到真正需要关注的符号——引号、冒号、括号、逗号——然后再把这一小段交给状态机细致处理。这其实并没有颠覆状态机而是减少了进入状态机的字符数量。所以你会看到性能测试里simdjson解析GB级JSON能比传统库快出一个数量级。明白这个原理对你选型也有帮助如果项目里有超大JSON或者高QPS接口别自己造轮子直接选有SIMD优化的解析器更靠谱。6.3 DOM还是SAX解析器不止一种形态极简版返回完整树结构对应的是DOM API。好处是随机访问方便任何字段都能随手查坏处是必须等全部解析完成而且整个结构都在内存里。另一种是流式API也叫SAX风格。解析器一边读一边回调“发现一个键”“发现一个值”“对象开始”“对象结束”客户端代码在回调里自己决定存什么、怎么存。这种模式非常适合超大JSON因为你不需要把完整结构放进内存解析到某个节点时已经可以直接开始处理并释放掉前面用过的内存。所以极简解析器只是让人理解原理的入门工具真正做项目选型时你得先回答一个问题我是要一次性完整结构还是要流水线式地处理大量JSON记录答案决定了你选哪个库、用哪种接口。我自己第一次手写JSON解析器的时候以为最难的是背JSON语法结果发现真正的坑全在边界转义、数字格式、括号匹配、深层嵌套、错误定位。极简版的好处就是把主干逻辑暴露得很干净你完全可以在它基础上继续加功能支持精确报错行号、支持深度限制、甚至扩展成流式回调接口。如果你真想彻底掌握解析器建议把这个代码抄一遍自己改一版能报错、能处理嵌套的完成版再拿几个真实接口的JSON数据去压一压。亲手把一个字节流变成哈希表的成就感真的和看一百篇原理文章不一样。
