本身分为以下四个部分：
- 如何写一个 JSON parser
- 剖析 Go 官方 JSON parser 的源码（encoding/json）
- 从 JSON 引申出的一个题目：Markdown 标题解析
- JSON 作者的一些趣闻
- 参考资料
其中参考资料里面有项目配套的源码仓库。
如何写一个 JSON Parser
前置知识
除了熟练掌握一门编程语言和对递归比较舒适外，本文不需要任何前置知识，甚至不需要读者了解 JSON。力求从第一性原理出发，让刚刚入门编程的读者也可以写出 JSON Parser。
文章中的 Parser 实现与剖析的源码都是基于 Go，Go 本身是一门非常简洁甚至过去很长时间内匮乏的语言，本文会对涉及的 Go 语法做一些讲解，不必恐慌。
什么是 JSON 以及为什么要写 Parser
JSON 是一种不同程序间交换数据（Data Interchange）的格式，最初多用于浏览器与服务器之间，现在的应用范围延伸到了程序的配置文件、服务器之间通信、RPC 通信等等（比如 VsCode 的 LSP 协议）。
比如：浏览器的程序是 JavaScript 写的，服务器的程序是 Python 写的。两方需要基于 HTTP 协议进行通信，那么通信的数据就需要一个通用的格式，该格式可以在 JavaScript、Python 之间自由转换。
换句话说，JSON 本质上是一种建模。用来描述现实世界，比如一个用户可以用 JSON 描述为：
{ "name" : "hq",
"age" : 27,
"height" : 174
}
这段 JSON 描述了一个用户的名字、年龄和身高。
这里是 JSON 的完整定义。如果不了解 JSON 可以先浏览一遍。
为什么要写 JSON Parser？
首先 JSON 本身涉及一个元问题：如何设计和解析跨语言的通信格式？这个问题非常有趣，而且渗透到计算机软件的方方面面；其次 JSON 本身就是一种编程语言，虽然简洁但是却很完备，可以充分描述现实中的各种存在，这正是本文真正的野心：以 JSON 为切入点探讨编程语言的实现。如果你想要入门编译器而不得，写完 JSON Parser 后你会发现之后即使解析复杂的语言，基本原理都是一致的。
具体实现我们需要探讨以下几部分：API 设计、核心架构、Debug、测试。
我用 cloc 统计了 Parser 实现，结果如下：
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
Go 1 31 11 254
-------------------------------------------------------------------------------
用了单文件254行。
API 设计
API 设计我们遵循 Go 官方库的 API：
func Unmarshal(data []byte, v any) error
其中 data 是把 JSON 字符串转成字节数组，而 v 是一个空接口，error 是一种错误类型。调用完 Unmarshal 之后，通过函数返回值得到是否出错的信息，该函数会修改 v 的值，将解析后的数据放入 v 之中。
Go 中的 any 指的是一种通用类型，也就是说任何类型都可以转成 any。在之后如要做处理、运算时，再将其转化为具体的类型。非常像 C 语言的空指针（*void）。
JSON 这个格式的类型有以下三种：
- 基本类型 （primitive）：Number、String、Boolean、null。其中 null 指的是空，就像 Python 中的 None 或者 C 的 null。
- Array。数据里面有多个的元素，每个元素可能是任何一种类型，用 “,” 分隔。
- Object。对象就是一个键值对，里面的 key 必须是字符串类型，而 value 可以是任何类型。
从 RFC 文档的描述中可以看出来，JSON 是一种递归的数据结构，可以无限嵌套下去。官方库对于 JSON 字符串映射的 Go 类型提供了非常多的选择，这里根据官方文档JSON and Go，我们采用最简单的格式：any。也就是说
- 基本类型中 Number 转为 float64，String 转为 string， Boolean 转为 bool， null 转为 nil，最后全部放入 any 中。
- Array 转成元素为 any 的 slice：[]any。
- Object 转成 map：map[string]any
其中 slice 是 Go 的变长数组，map 是 Go 的哈希表。
接下来在测试上，可以看到 api 的具体例子。
测试
测试的策略是从最简单的类型开始，然后是无嵌套的 Array、Object，最后是嵌套的 Array、Object。
第一个测试用例是布尔值：
data := `
true`
var result any
var expected any = true
if err := Unmarshal([]byte(data), &result); err != nil {
t.Fatalf("bool err %v", err)
}
if !reflect.DeepEqual(result, expected) {
t.Fatalf("Unmarshal result %v, expected: %v", result, expected)
}
其中 data 是 JSON 字符串，result 是通用类型，传入它的指针到 Unmarshal，expected 里面放了正确的结果。因为后文中要对 slice 和 map 进行比对，所以我一律使用了反射包中的 DeepEqual 来比对两个值是否相等。这里也可以直接比对。
然后是字符串：
data = ` "Hello world! 你好，世界！" `
expected = "Hello world! 你好，世界！"
然后是数字：
data = ` 42 `
expected = float64(42)
然后是数组：
data = ` [116, 943, 234, 38793]`
expected = []any{float64(116), float64(943), float64(234), float64(38793)}
然后是 object：
data = `
[
{
"keya":123,
"keyb":234
},
{
"keya":123,
"keyb":234
}
]
`
expected = []any{
map[string]any{
"keya": float64(123),
"keyb": float64(234),
},
map[string]any{
"keya": float64(123),
"keyb": float64(234),
},
}
文中省略了大量的 edge case，比如负数、嵌套的结构，详情可以参考配套的程序。
核心结构
核心结构包括两部分：状态机和算法。
状态机包括状态值和状态值的流转。
最核心的状态值就是 index，即指向当前需要处理的字符的游标。我们会将 index 不断增加，从而遍历 JSON 字符串，在这个过程中把扫描出来的字符串转为 Go 的数据类型保存下来。
index 的状态流转分为两种情况：
- 略过非数据，自增1（index += 1）。比如需要空格、换行符等等没有信息的符号，直接让 index 自增，调整到下一个字符。这种情况下这些字符串被当做无用信息略过，它们唯一的作用就是可能作为背景信息（上文），比如 “,” 就说明数组还有元素，并没有结束。
- 扫描数据，自增多个（index += n）。比如解析 true，刚开始遇到 t 这个字符时，直接使 index 增加4，指向 true 之后的字符。其他字符串等等也是一样。此时要将扫描出来的字符串转成 Go 的数据类型，然后保存在结果中。
举两个例子，第一个是略过非字符
func (t *parser) pass(input ...rune) {
for {
if t.curChar() == ']' || t.curChar() == '}' {
return
}
for _, v := range input {
if t.curChar() == v {
t.next()
return
}
}
}
}
任何略过字符的函数都会调用 pass 这个基础工具函数，它会判断当前字符是否是函数参数中的目标字符，如果是就调用 t.next() 将 index 增加 1 。
第二个是解析布尔值：
func (t *parser) tryBool() (any, bool) {
switch t.curChar() {
case 't':
t.index += 4
return true, true
case 'f':
t.index += 5
return false, true
default:
return nil, false
}
}
这时会根据布尔值改变 index 的值，自增多个值直到指向布尔值之后的字符。同时把扫描出来的布尔值转成 Go 的布尔值，以 any 类型返回到调用方，调用方会将其保存。
算法方面JSON 这个语言有两个核心特征：
- 需要上文来进行解析。编程语言的上下文指我们在扫描程序字符串的过程中，需要根据之前扫描出来的信息和之后扫描出来的信息，确定当前扫描出来的数据要如何解析。比如 JSON 中扫描出一个 “,"，可能是 Object 的 value 的分隔符，也可能是 array 的元素分隔符，还可能是一个字符串中间的 “,”，到底是哪种情况需要看上文，当前究竟是在一个 object 还是在一个 array 或者字符串之中。而 JSON 的语法解析不涉及下文，这种情形多见于一些比较复杂的编程语言中，
- 因为可以嵌套，所以需要用递归的架构。分析递归需要将其拆解为基本情况和复杂情况。 以下是我的程序的入口的实现：
if item, ok = t.tryPrimitive(); ok {
return item
} else if item, ok = t.tryArray(); ok {
return item
} else if item, ok = t.tryObject(); ok {
return item
} else {
panic("invalid")
}
其中
func (t *parser) tryPrimitive() (any, bool)
是基本类型，里面没有任何递归调用。
而数据和对象的解析：
func (t *parser) tryArray() (any, bool)
func (t *parser) tryObject() (any, bool)
是递归的情况，它们会在内部调用以上的三个函数，这三个函数都会尝试讲接下来的 JSON 数据当做自认为的数据类型解析，直到成功或者确认不是这种数据类型，后者会返回一个 true，外部的调用方就可以尝试下一种情况。
比如在 tryArray 中解析数据元素时就会把这个元素分为三种情况去解析：
if item, ok = t.tryPrimitive(); ok {
} else if item, ok = t.tryArray(); ok {
} else if item, ok = t.tryObject(); ok {
} else {
panic("array invalid")
}
在之后阅读 Go JSON 源码时，会发现官方的源码也是采用这种递归结构实现的。
Debug
这个程序核心就是遍历一个数组，不涉及并发场景或者特别难以阅读的数据格式，所以 debug 的方式只需要找到每次循环的开始和结束，把关键的状态值打印出来即可。这样每次运行程序整个数据流和状态机的流转都能一目了然。
GO JSON Parser 剖析
我们解读的源码版本是
go version go1.18.2 darwin/amd64
我把 encoding/json 目录下的文件拷贝出来放到了博文配套的程序里。这个库包括的内容很多，其中和解析 JSON 相关的主要是在 decode.go 和 scanner.go 之中。
用 cloc 先统计:
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
Go 2 158 379 1397
-------------------------------------------------------------------------------
值得注意的有两点
- 评论比程序达到了惊人的三分之一，一方面是因为 Go 会用评论来生成文档，另一方面是官方实现的文档确实很多，包括函数的作用还有状态值的含义。
- 整个实现行数是我的实现行数的将近五倍，具体原因我会在下文道来。
go JSON 库的作者是 Russ Cox，听到这个名字可能有些陌生，但是说起 MIT 操作系统课程采用的教学 OS xv6，估计喜欢 CS 公开课的读者就无人不晓了，他就是 xv6 的作者。后来在贝尔实验室开发了 Plan 9 操作系统，目前参与 Go 的开发。可见顶尖的工程圈其实是很小的，就比如 memcached 作者后来也去了 Go 团队。
API
官方实现的 API 比起前文的实现非常全面，这也是程序量暴涨的主要原因；其次出于一些设计上的考量，比如需要检查 JSON 的格式以及提供非常详细的报错信息，该实现采用了更为复杂的状态机，里面有更多的状态值和状态流转。
查看文档我们可以看到源码的 API 大概可以分为三种：
- 提供了如下的接口：
type Unmarshaler interface {
UnmarshalJSON([]byte) error
}
type TextUnmarshaler interface {
UnmarshalText(text []byte) error
}
比如 Go 标准库中的时间类型就提供了这个接口，这样就绕过了 Go 的 JSON 解析实现，转而使用调用方自己的实现。
- 转成 Go 的基本类型。比如 “123” 可以转成 int、int8、int16、int32、uint8 等等。这里映射到的 Go 类型远比上文实现的要多，比如 JSON array 可以映射成 Go 的 array 或者 slice，JSON object 可以映射成 Go 的 map 或者结构体，结构体这里又设计到反射。
- 转成 Go 的通用类型（any），这里也就是上文所实现的部分。
API 中很重要的一个部分就是容错。容错包括检查错误、提供详细的错误信息以及后续的错误处理。源码里错误检查分为两种：静态检查和动态检查，很像 Go 、Rust 这样的编程语言。其中静态检查严格，动态检查松散。
它会先做静态检查，把整个字符串扫描一遍但是不做解析，这一步对于错误是非常严格的，只要遇到一个就会中止整个流程，直接返回给调用方错误信息；如果通过了静态检查接下来就是动态检查，这一步和 JSON 的解析混合在一起，比较松散，比如解析整数时溢出了，Parser 会记录这个错误信息然后继续往下走，还是会把接下来的 JSON 结构解析出来返回给调用方。
状态机
整个 JSON Parse 的核心状态机都在 decodeState 里面
// decodeState represents the state while decoding a JSON value.
type decodeState struct {
data []byte
off int // next read offset in data
opcode int // last read result
scan scanner
errorContext *errorContext
savedError error
useNumber bool
disallowUnknownFields bool
}
其中 data 存放了输入的 JSON 字符串，off 对应上文的 index，指向接下来要处理的字符，errContext 和 savedError 保存错误信息，useNumber 指是否使用了 源码里定义的 Number 而不是映射到 Go 的整数或者浮点数，disallowUnknownFields 是 JSON parser 的另一个解析的 API 用到的，Unmarshal API 没有涉及，主要指 JSON 字符串和提前定义好的 Go 结构体如果字段对不上要如何处理。
以上状态值都是比较常规的，比较特殊的是 opCode 和 scanner 这两个状态值，也是整个 JSON Parser 设计精致、让我惊讶的部分。
要想理解这两个状态值，必须要理解库中的“事件”概念，事件指的就是我所写的 Parser 中提到的上文（context）。比如遇到 “,”，根据当前事件就可以判断它是 array 分隔符、object 分隔符或者字符串中的字符。程序里定义的事件有以下几种：
const (
// Continue.
scanContinue = iota // uninteresting byte
scanBeginLiteral // end implied by next result != scanContinue
scanBeginObject // begin object
scanObjectKey // just finished object key (string)
scanObjectValue // just finished non-last object value
scanEndObject // end object (implies scanObjectValue if possible)
scanBeginArray // begin array
scanArrayValue // just finished array value
scanEndArray // end array (implies scanArrayValue if possible)
scanSkipSpace // space byte; can skip; known to be last "continue" result
// Stop.
scanEnd // top-level value ended *before* this byte; known to be first "stop" result
scanError // hit an error, scanner.err.
)
其中的每一个 opCode 就对应了一个事件。
可以看到这些事件涵盖了解析 JSON 的方方面面，比如和 object 解析有关的就有开始扫描 object、扫描 key、扫描 value、扫描 object 结束。那么为什么需要添加这个抽象层？而我所实现的 Parser 却不需要这个状态值？
这样做的好处是清晰，之前写的 Parser 是没有具体的事件概念的，我们会在函数里根据调用的上文判断如何解析，这样需要读具体的程序细节才能知道当前的事件，而库源码可以直接利用 opCode 的值来判断。它把一个用程序细节模糊概括的概念用状态值直接清晰地表达，而且予以强调。
比如扫描完空白字符后，根据第一个字符得到的结果写入相应的 opCode 值，“[” 对应 scanBeginArray， “{”对应 scanBeginObject。下面流程的函数就可以直接使用 opCode 来判断。比如：
func (d *decodeState) value(v reflect.Value) error {
switch d.opcode {
default:
panic(phasePanicMsg)
case scanBeginArray:
// 详细逻辑略过
case scanBeginObject:
case scanBeginLiteral:
return nil
}
在源码入口处函数 value 里，根据 opCode 直接把程序导向解析基本类型、object、array 三种 case。
那么 opCode 具体的流转逻辑又是如何的？这就要讲到 scanner 了。它是一个专注于扫描字符然后得出 opCode的状态机，也就是说输入当前的字符串，然后输出 opCode。它里面又会封装一些上文状态来判断当前要得到哪个 opCode。
定义如下：
// A scanner is a JSON scanning state machine.
// Callers call scan.reset and then pass bytes in one at a time
// by calling scan.step(&scan, c) for each byte.
// The return value, referred to as an opcode, tells the
// caller about significant parsing events like beginning
// and ending literals, objects, and arrays, so that the
// caller can follow along if it wishes.
// The return value scanEnd indicates that a single top-level
// JSON value has been completed, *before* the byte that
// just got passed in. (The indication must be delayed in order
// to recognize the end of numbers: is 123 a whole value or
// the beginning of 12345e+6?).
type scanner struct {
// The step is a func to be called to execute the next transition.
// Also tried using an integer constant and a single func
// with a switch, but using the func directly was 10% faster
// on a 64-bit Mac Mini, and it's nicer to read.
step func(*scanner, byte) int
// Reached end of top-level value.
endTop bool
// Stack of what we're in the middle of - array values, object keys, object values.
parseState []int
// Error that happened, if any.
err error
// total bytes consumed, updated by decoder.Decode (and deliberately
// not set to zero by scan.reset)
bytes int64
}
其中值得注意的就是 step 和 parseState。
parseState 保存了一个栈，来记录当前解析到了 JSON 数据结构哪一层，以及上面的 parent 节点。 之所以用栈，就像函数的调用栈一样，JSON 解析层级结构是一个先进后出的状态。除此之外利用栈还可以判断目前嵌套的层数，源码做了限制，嵌套层数不能超过10000层，这个动态检查就是利用 parseState 来做判断的。
比如下面的 JSON 结构，是 array 嵌套 object，然后里面又嵌套 array，将它们命名为 array1、object1、array2。解析顺序是 array1、object1、array2，那么解析完离开这些结构的顺序就是 array2、object1、array1：
[
{
"key": [1, 2, 3]
}
]
为什么我自己的实现不需要这个状态？因为官方源码做了更细致的抽象封装。比如处理 “,” 我会在解析 array、解析 object 的函数里分别直接提取出字符来判断，这样调用方直接提供了上文（事件），但与此同时对于 “,” 的处理细节也就暴露在了调用方之中。而官方实现处理“,”时是利用封装的函数的，只能根据 parseState 判断当前所处的事件。
parseState 有以下枚举值：
// These values are stored in the parseState stack.
// They give the current state of a composite value
// being scanned. If the parser is inside a nested value
// the parseState describes the nested state, outermost at entry 0.
const (
parseObjectKey = iota // parsing object key (before colon)
parseObjectValue // parsing object value (after colon)
parseArrayValue // parsing array value
)
因为是要保存解析栈，所以只保存嵌套的数据结构的上文。
接下来说到 step 函数签名，它的作用就是输入一个当前字符，利用 parseState 作为上文状态，输出一个 opCode 指导 decodeState 接下来应该做什么。另一方面，它也会更新 scanner 里面的 step 方法。
是的，step 函数本身就是一个状态值！函数被作为数据变量，每个具体实现就是一个状态值，step 的实现会随着字符和上文而修改 step 这个值。
它有很多种枚举值（都是函数），列举几种：
// 刚开始解析一个 value 时的 step，也是状态机初始化的状态
func stateBeginValue(s *scanner, c byte) int
// 解析完一个 value 之后，根据下一个 char 返回相应的 opCode
func stateEndValue(s *scanner, c byte) int
// stateInString is the state after reading `"`.
func stateInString(s *scanner, c byte) int
让我们总结一下，decodeState 做的事情有两点：
- 根据 opCode 来决定接下来要怎么解析数据
- 数据解析完保存到结果中，这时要把结果转化成 Go 的类型
那么 opCode 的状态流转就被封装到了 scanner，decodeState 只关心接下来的 opCode 是什么样的，不关心它的流转细节具体是什么，也就是说这一步如果直接修改了 opCode 的状态值就破坏了程序的层级关系。scanner 做的事情包括：
- 维护 parseState 记录解析栈，同时维护 step 使它指向正确的 step 函数实现。
- 根据 parseState 、step、输入的字符来得出当前的 opCode。
其中 decodeState 是 high level 的，scanner 是相对 low level 的。
整体结构
看函数的入口：
func Unmarshal(data []byte, v any) error {
// Check for well-formedness.
// Avoids filling out half a data structure
// before discovering a JSON syntax error.
var d decodeState
err := checkValid(data, &d.scan)
if err != nil {
return err
}
d.init(data)
return d.unmarshal(v)
}
入口分为两步：
- 其中 checkValid 做了 JSON 字符串的静态检查，有报错就直接返回。
- 初始化 decodeState，然后调用它的 unmarshal 方法。
接下来看它的 unmarshal 方法：
func (d *decodeState) unmarshal(v any) error {
rv := reflect.ValueOf(v)
if rv.Kind() != reflect.Pointer || rv.IsNil() {
return &InvalidUnmarshalError{reflect.TypeOf(v)}
}
d.scan.reset()
d.scanWhile(scanSkipSpace)
// We decode rv not rv.Elem because the Unmarshaler interface
// test must be applied at the top level of the value.
err := d.value(rv)
if err != nil {
return d.addErrorContext(err)
}
return d.savedError
}
它的工作分为四步：
- 对函数输入的 v 值做检查，比如确保它是指针，而且不为空。
- 初始化 decodeState 里面的 scanner 的值，这一步会把 step 赋值为 stateBeginValue ，也就是整个状态机的初始状态；然后调用 scanWhile 开始扫描字符串，略过空白字符串，直到遇到一个有意义的字符串，此时修改 opCode 的状态值，告知接下来的函数要做什么处理。
- 调用 value 方法，整个 Parser 的核心逻辑就在这里。
- 解析完成后查看动态检查的结果，如果有错误就返回给调用方。
再看 value 的实现：
func (d *decodeState) value(v reflect.Value) error {
// fmt.Printf("value opCode: [%d]\n", d.opcode)
switch d.opcode {
default:
panic(phasePanicMsg)
case scanBeginArray:
// fmt.Printf("value IsValid: [%v]\n", v.IsValid())
if v.IsValid() {
if err := d.array(v); err != nil {
return err
}
} else {
d.skip()
}
// fmt.Printf("value after array: [%+v]\n", v.Elem())
d.scanNext()
case scanBeginObject:
if v.IsValid() {
if err := d.object(v); err != nil {
return err
}
} else {
d.skip()
}
d.scanNext()
case scanBeginLiteral:
// All bytes inside literal return scanContinue op code.
start := d.readIndex()
d.rescanLiteral()
// fmt.Printf("literal value after scan: #%c#\n", d.data[start:d.readIndex()])
if v.IsValid() {
if err := d.literalStore(d.data[start:d.readIndex()], v, false); err != nil {
return err
}
}
}
return nil
}
里面分为三种情况：基本类型、array、object，其中 array 和 object 都会进行递归调用，再次调用 value，和我的实现的递归思路是完全相同的。
注意这里可能会报 panic，具体信息如下：
const phasePanicMsg = "JSON decoder out of sync - data changing underfoot?"
是因为作者考虑到 checkValid 之后调用方可能会有后台线程修改输入的 JSON 字符串，这时动态检查已经默认 JSON 通过了静态检查，所以报错信息可能会非常奇怪。所以作者又在这里加上了部分静态检查的逻辑，而且提供了相应的逻辑。
之前提到过官方实现有三种 API，那么这三种 API 要如何优雅分层呢？ 我们来用 array 函数做例子，它的函数体开头是这样的：
u, ut, pv := indirect(v, false)
if u != nil {
start := d.readIndex()
d.skip()
return u.UnmarshalJSON(d.data[start:d.off])
}
if ut != nil {
d.saveError(&UnmarshalTypeError{Value: "array", Type: v.Type(), Offset: int64(d.off)})
d.skip()
return nil
}
v = pv
//...
可以看到作者使用了一个 indirect 函数进行分流，里面利用反射查看 v 实现了哪些接口，然后传出三个指针，三个指针是否为空分别代表是否实现了UnmarshalJSON、UnmarshalText，或者是 Go 的基本类型、空接口（any）。
这个函数会在 object、array、literalStore（解析出 JSON 基本类型后转化成 Go 类型）中调用，三个函数是平层的。
其中 step 状态机有一些看似琐碎的实现，比如针对布尔值就有三种情况：
// stateT is the state after reading `t`.
func stateT(s *scanner, c byte) int
// stateTr is the state after reading `tr`.
func stateTr(s *scanner, c byte) int
// stateTru is the state after reading `tru`.
func stateTru(s *scanner, c byte) int
上面分别对应解析 true 的 r、u、e，为什么这么繁琐？需要看 checkValid 的实现：
func checkValid(data []byte, scan *scanner) error {
scan.reset()
for _, c := range data {
scan.bytes++
if scan.step(scan, c) == scanError {
return scan.err
}
}
if scan.eof() == scanError {
return scan.err
}
return nil
}
可以看到 checkValid 内部实现是非常干净整齐的，简单说就是扫描每一个字符串，然后调用 step 函数。
因为不会跳过字符串，所以自然需要实现如此琐碎的状态机。在动态检查这里为了干净的结构，把琐碎细节藏到了 step 状态机里。否则的话就要在这里也实现一套接近 d.unmarshal(v) 动态解析的逻辑，但是又有很多不同，无法完全复用。
case study
前文说过 checkValid 不会跳过字符串，那么 d.unmarshal(v) 里面自然解析时会跳过，这里我们尝试使用一个小小的例子来观察调用链和状态流转：
[123, 456]
一叶知秋，如果把各种基本的、组合的 case 都跑一遍，熟悉调用链和状态机，对这个库就很熟了，可以达到修改的水平了。
这里只关注最重要的函数。先会调用
d.scanWhile(scanSkipSpace)
它会把例子中的换行符、空格全部略过，直到遇到 “[”，然后调用 stateBeginValue，这个函数里面有这样的逻辑：
case '[':
s.step = stateBeginValueOrEmpty
return s.pushParseState(c, parseArrayValue, scanBeginArray)
它会把 opCode 置为 scanBeginArray，在 parseState 栈里面放入 parseArrayValue，标记现在的扫描进入了 array 之中，同时把 step 指向 stateBeginValueOrEmpty，它的作用是进入 array 之后的状态流转。
然后跳出来，可以看到 value 里面根据 opCode 走向了 array 的处理分支，调用 d.array(v)：
case scanBeginArray:
if v.IsValid() {
if err := d.array(v); err != nil {
return err
}
} else {
d.skip()
}
// fmt.Printf("value after array: [%+v]\n", v.Elem())
d.scanNext()
假设我们把 JSON 解析成 Go 的 any，则又会调用 d.arrayInterface()。它又会调用 d.scanWhile(scanSkipSpace)，略过空白字符。因为 JSON 在空白字符上是非常松散的，所以处处都要考虑空白字符。如前文所说，这个函数会设置 opCode，接下来：
func (d *decodeState) valueInterface() (val any) {
switch d.opcode {
default:
panic(phasePanicMsg)
case scanBeginArray:
val = d.arrayInterface()
d.scanNext()
case scanBeginObject:
val = d.objectInterface()
d.scanNext()
case scanBeginLiteral:
val = d.literalInterface()
}
return
}
其中 d.literalInterface() 是基本 case，解析 JSON 中的 number、boolean、string、null，也是这里解析 123 的分支：
func (d *decodeState) literalInterface() any {
// All bytes inside literal return scanContinue op code.
start := d.readIndex()
d.rescanLiteral()
item := d.data[start:d.readIndex()]
switch c := item[0]; c {
case 'n': // null
return nil
case 't', 'f': // true, false
return c == 't'
case '"': // string
s, ok := unquote(item)
if !ok {
panic(phasePanicMsg)
}
return s
default: // number
if c != '-' && (c < '0' || c > '9') {
panic(phasePanicMsg)
}
n, err := d.convertNumber(string(item))
if err != nil {
d.saveError(err)
}
return n
}
}
可以看到经过了重重状态流转和递归，终于到了最实在的逻辑，这里的实现与前文我的实现基本类似，记录当前 off 指向的字符（”1“），然后调用 d.rescanLiteral() 将 off 指向 123 之后的字符（”,“）。根据这两个游标，解析出 123 来然后调用 d.convertNumber(string(item)) 转成 Go 的 float64 类型。
可以看到这里是略过了三个字符的，而不是像 checkValid 那样老老实实一个一个字符去解析。
之后解析 456 大同小异，然后在遇到 ”]“ 时把 parseState 栈里面的 parseArrayValue pop 出来。
测试方法论
源码的测试分为两部分，第一部分是比较琐碎、不成系统的测试，主要是后来的 contributer 根据出现的 bug 或者新增的 feature 添加的，第二部分是比较系统的测试。其中定义了测试数据的结构体，里面有输入、期望输出、期望的报错，然后全部放到了一个 slice 里面。只要遍历这个 slice 加上很少的程序就可以完成测试。
这一点给我的启发很大，要尽量利用声明式的方式来写程序，这样可以提升抽象度。最起码在测试上是非常高效的，这样写出的测试程序很短，而且之后想要新增 case 只要在 slice 里面添加一组数据即可，而不用复制粘贴程序。
一道面试题： Markdown 标题解析
一般我是比较讨厌面试做题的，有种浓浓的应试教育的味道，因为这些题目非常脱离实际，比如判断链表是否有环这种题目，本身的思路甚至需要专业数学家来提出和证明，如果之前没有做过现场很难做出来。
但是读官方 JSON Parser 让我想起一道面试题，那是我18年刚入行时被问到的，非常贴近实际，当时的我也没有做出。题目如下：
Markdown Parser
实现一个函数，根据 Markdown 的标题序列生成相应的标题序号。
比如输入：{"# a", "## b", "## c", "### d", "# e"}
输出：
{
{level: "1", name: "a"},
{level: "1.1", name: "b"},
{level: "1.2", name: "c"},
{level: "1.2.1", name: "d"},
{level: "2", name: "e"},
}
现在读完源码，尤其是里面用栈来存储嵌套的上文状态（parseState），给了我很大的启发。我的思路是这样：
- 扫描整个标题数组。
- 扫描的过程中将之后需要的上文保存到一个栈中。
- 每次扫描到一个元素，就利用存储上文的栈来生成它的标题序号。
- 生成序号时分为以下三种情况：和当前栈里的标题是平级、下级、上级，针对这三种情况生成相应的标题序号。
具体的实现在 markdown.go 中，大概花了不到一小时就完成了。
我的感受就是”诸法相同“，当时完全不懂编译原理，自然也无从下手。
JSON 作者趣闻
JSON 作者叫 Douglas Crockford ，之前恰好读过他的访谈，非常有趣。也让我意识到”提供一碗水需要自己有一桶“。JSON 格式看似简单，但是 Crockford 的编程底蕴是很深厚的。
以下摘录一些关于他的趣闻：
- Crockford 本科读的是电视广播专业，因为大学时没有机会去演播室实习，转而学习了学校开的 Fortran 课程，得以入门编程。
感想：其实很多编程大师都不是通过严格规划的方式进入该领域的，如果想要探索自己的兴趣一定要进入一个非常宽松的环境，比如如果他没机会选修 Fortran 就很难进入 CS 领域。
- 他曾经写过一个程序来反汇编 Fortran，这让他深刻理解了 Fortran。
感想：如果想要成为技术专家，个人项目一定要由浅入深，不能长期停留在一个难度上。
- 他早起写的很多程序都是游戏。
感想：读厉害创作者的传记，感觉就是他们很早就会跨过消费者到创作者的这道门槛。而我大学时身边的一些同学一直沉迷消费游戏，与其说是因为智力悬殊，我觉得更有可能是一种人格的倾向和自我意识。
他提到提升能力很重要的一点就是组织团队做程序阅读，挑出一个人写的程序，大家用投影一起细致阅读。这种方法可以极大提升程序的可读性。他也提到这样做的前提是团队之间有足够的默契。
采访者问及年龄增加带来的编程能力下降，他的回答是：随着年龄变大，更加注意程序的可读性和文档编写，感觉自己的编程能力反而提升了。
感想：随着年龄变大，我们每个人都要无可避免走向某些维度的下滑，比如精力、流体智力，照顾老人和小孩也要消耗我们的精力。面对这种现实，灌鸡汤和当鸵鸟是两种极端。比较实际的方法是寻找可以随着年龄提升的维度，比如知识、经验，用它们来弥补其他维度的下降。其实很多顶尖的运行员这方面都是很早熟的，比如乔丹就早早从突破转向了背身单打，把自己的黄金期延长到了令人咂舌的长度。
在实现 JSON Parser 的过程中，我收获的是信心：原来一个真实世界中完备的数据交换格式竟然这么容易实现；而在阅读官方源码的过程中，我收获的是对编程和 Go 更深更广的理解，比如：
- 把核心状态机单独抽象出来，给出清晰的定义和注释。
- 函数也是可以作为状态值的。
- 错误可以分为静态检查和动态检查，动态检查的错误可以用结构体的一个 field 来传递，这样就不用在期间每个函数的返回值都定义一个 error 了。错误在传递过程还可以添加相应的背景信息。
- 语法解析的关键是上下文，利用上下文来消除歧义和判断要做什么操作（这是我之前模糊懂得，但是在写作此文过程中才获得深刻理解的）。包括写编译器的后端时，也需要利用上下文来做汇编的生成。
- 测试最好写成数据驱动的风格，把测试用例放到数组之中，直接遍历就可以用很少的程序完成测试。
在这个过程中也锻炼了自己的薄弱项：源码阅读能力。可谓受益匪浅。
参考资料
- 我的配套源码
- JSON RFC 文档
- Go 官方的 JSON 库使用教程
- 其中 Crockford 采访来自 《编程人生》，Peter Seibel 著，人民邮电出版社。