JSON 解析器

本章导读

递归下降是最直观的解析技术：为语法规则中的每个产生式写一个函数，函数之间互相递归调用。JSON 的语法规则只有 6 条（value → object | array | string | number | true/false | null），因此解析器结构清晰、代码量小（约 150 行），却完整展示了编译前端的工作原理。

52.1 JSON 语法规范

JSON 的完整语法（RFC 8259 简化）：

// BNF 产生式
value   = object | array | string | number | "true" | "false" | "null"
object  = "{" [ pair *( "," pair ) ] "}"
pair    = string ":" value
array   = "[" [ value *( "," value ) ] "]"
string  = '"' *char '"'
number  = [ "-" ] int [ "." digits ] [ ("e"|"E") ["+"|"-"] digits ]
int     = "0" | digit1-9 *digit

每条产生式对应解析器中的一个函数。函数之间通过递归调用处理嵌套结构（对象中包含数组，数组中包含对象...）。

52.2 值的类型表示

JSON 值有 6 种类型，用 xlang 的 class 表示：

// JSON 值类型枚举
final int JNULL = 0
final int JBOOL = 1
final int JNUMBER = 2
final int JSTRING = 3
final int JARRAY = 4
final int JOBJECT = 5

class JsonValue
    int type
    bool boolVal
    double numVal
    string strVal
    list<JsonValue> arrVal
    list<string> objKeys
    list<JsonValue> objVals

    func makeNull() as JsonValue
        JsonValue v = JsonValue()
        v.type = JNULL
        return v
    end

    func makeBool(bool b) as JsonValue
        JsonValue v = JsonValue()
        v.type = JBOOL
        v.boolVal = b
        return v
    end

    func makeNumber(double n) as JsonValue
        JsonValue v = JsonValue()
        v.type = JNUMBER
        v.numVal = n
        return v
    end

    func makeString(string s) as JsonValue
        JsonValue v = JsonValue()
        v.type = JSTRING
        v.strVal = s
        return v
    end

    func makeArray() as JsonValue
        JsonValue v = JsonValue()
        v.type = JARRAY
        v.arrVal = list<JsonValue>()
        return v
    end

    func makeObject() as JsonValue
        JsonValue v = JsonValue()
        v.type = JOBJECT
        v.objKeys = list<string>()
        v.objVals = list<JsonValue>()
        return v
    end
end

52.3 词法分析

解析器维护一个位置指针，逐字符扫描：

class Parser
    string src
    int pos

    func init(string text)
        src = text
        pos = 0
    end

    // 查看当前字符（不移动）
    func peek() as int
        if pos >= src.len() then return 0 end
        return src[pos]
    end

    // 消费当前字符（移动）
    func next() as int
        int ch = peek()
        pos += 1
        return ch
    end

    // 跳过空白（空格、制表符、换行、回车）
    func skipWhitespace()
        while pos < src.len()
            int ch = src[pos]
            if ch == 32 or ch == 9 or ch == 10 or ch == 13 then
                pos += 1
            else
                break
            end
        end
    end

    // 期望某个字符，不匹配则报错
    func expect(int ch)
        skipWhitespace()
        int got = next()
        if got != ch then
            error("期望 '" + string.char(ch) + "' 但得到 '" + string.char(got) + "'")
        end
    end
end

52.4 字符串解析与转义

JSON 字符串支持转义序列：

func parseString() as string
    expect(34)   // 消费开头的 "
    string result = ""

    while true
        int ch = next()
        if ch == 0 then
            error("字符串未闭合")
        end
        if ch == 34 then   // 结尾的 "
            break
        end
        if ch == 92 then   // 反斜杠 \
            int esc = next()
            if esc == 34 then result += "\""        // \"
            elif esc == 92 then result += "\\"      // \\
            elif esc == 47 then result += "/"       // \/
            elif esc == 98 then result += "\b"      // \b
            elif esc == 102 then result += "\f"     // \f
            elif esc == 110 then result += "\n"     // \n
            elif esc == 114 then result += "\r"     // \r
            elif esc == 116 then result += "\t"     // \t
            elif esc == 117 then                    // \uXXXX
                string hex = ""
                int i = 0
                while i < 4
                    hex += string.char(next())
                    i += 1
                end
                int code = int.parse(hex, 16)
                result += string.char(code)
            else
                error("无效转义: \\" + string.char(esc))
            end
        else
            result += string.char(ch)
        end
    end

    return result
end

52.5 数字解析

func parseNumber() as double
    skipWhitespace()
    int start = pos

    // 可选负号
    if peek() == 45 then next() end   // '-'

    // 整数部分
    if peek() == 48 then              // '0'
        next()
    else
        while peek() >= 48 and peek() <= 57   // '0'-'9'
            next()
        end
    end

    // 小数部分
    if peek() == 46 then              // '.'
        next()
        while peek() >= 48 and peek() <= 57
            next()
        end
    end

    // 指数部分
    if peek() == 101 or peek() == 69 then   // 'e' or 'E'
        next()
        if peek() == 43 or peek() == 45 then next() end  // '+' or '-'
        while peek() >= 48 and peek() <= 57
            next()
        end
    end

    string numStr = src.substring(start, pos)
    return double.parse(numStr)
end

52.6 数组解析

func parseArray() as JsonValue
    expect(91)   // '['
    JsonValue arr = JsonValue.makeArray()

    skipWhitespace()
    if peek() == 93 then   // 空数组 ']'
        next()
        return arr
    end

    while true
        JsonValue elem = parseValue()
        arr.arrVal.push(elem)

        skipWhitespace()
        if peek() == 44 then       // ','
            next()
        elif peek() == 93 then     // ']'
            next()
            break
        else
            error("数组中期望 ',' 或 ']'")
        end
    end

    return arr
end

52.7 对象解析

func parseObject() as JsonValue
    expect(123)   // '{'
    JsonValue obj = JsonValue.makeObject()

    skipWhitespace()
    if peek() == 125 then   // 空对象 '}'
        next()
        return obj
    end

    while true
        // 键必须是字符串
        skipWhitespace()
        string key = parseString()

        // 冒号
        expect(58)   // ':'

        // 值
        JsonValue val = parseValue()
        obj.objKeys.push(key)
        obj.objVals.push(val)

        skipWhitespace()
        if peek() == 44 then       // ','
            next()
        elif peek() == 125 then    // '}'
            next()
            break
        else
            error("对象中期望 ',' 或 '}'")
        end
    end

    return obj
end

52.8 完整解析器

parseValue 是入口，根据首字符分发：

func parseValue() as JsonValue
    skipWhitespace()
    int ch = peek()

    if ch == 123 then return parseObject() end    // '{'
    if ch == 91 then return parseArray() end      // '['
    if ch == 34 then                              // '"'
        return JsonValue.makeString(parseString())
    end
    if ch == 116 then                             // 't' → true
        expectLiteral("true")
        return JsonValue.makeBool(true)
    end
    if ch == 102 then                             // 'f' → false
        expectLiteral("false")
        return JsonValue.makeBool(false)
    end
    if ch == 110 then                             // 'n' → null
        expectLiteral("null")
        return JsonValue.makeNull()
    end
    if ch == 45 or (ch >= 48 and ch <= 57) then   // '-' 或数字
        return JsonValue.makeNumber(parseNumber())
    end

    error("意外的字符: '" + string.char(ch) + "'")
    return JsonValue.makeNull()   // 不可达
end

func expectLiteral(string lit)
    int i = 0
    while i < lit.len()
        if next() != lit[i] then
            error("期望 '" + lit + "'")
        end
        i += 1
    end
end

// 顶层入口
func parse(string text) as JsonValue
    Parser p = Parser()
    p.init(text)
    JsonValue result = p.parseValue()
    p.skipWhitespace()
    if p.pos < p.src.len() then
        p.error("尾部有多余字符")
    end
    return result
end

52.9 序列化输出

将 JsonValue 重新输出为 JSON 文本：

func stringify(JsonValue v, int indent) as string
    if v.type == JNULL then return "null" end
    if v.type == JBOOL then
        if v.boolVal then return "true" else return "false" end
    end
    if v.type == JNUMBER then return v.numVal.toString() end
    if v.type == JSTRING then return escapeString(v.strVal) end
    if v.type == JARRAY then
        if v.arrVal.len() == 0 then return "[]" end
        string s = "["
        int i = 0
        while i < v.arrVal.len()
            if i > 0 then s += "," end
            s += stringify(v.arrVal[i], indent)
            i += 1
        end
        return s + "]"
    end
    // JOBJECT
    if v.objKeys.len() == 0 then return "{}" end
    string s = "{"
    int i = 0
    while i < v.objKeys.len()
        if i > 0 then s += "," end
        s += escapeString(v.objKeys[i]) + ":" + stringify(v.objVals[i], indent)
        i += 1
    end
    return s + "}"
end

func escapeString(string s) as string
    string result = "\""
    int i = 0
    while i < s.len()
        int ch = s[i]
        if ch == 34 then result += "\\\""
        elif ch == 92 then result += "\\\\"
        elif ch == 10 then result += "\\n"
        elif ch == 13 then result += "\\r"
        elif ch == 9 then result += "\\t"
        else result += string.char(ch)
        end
        i += 1
    end
    return result + "\""
end

52.10 错误报告

好的解析器需要精确的错误定位：

func error(string msg)
    // 计算行号和列号
    int line = 1
    int col = 1
    int i = 0
    while i < pos and i < src.len()
        if src[i] == 10 then
            line += 1
            col = 1
        else
            col += 1
        end
        i += 1
    end
    println("JSON 解析错误 [行 " + line.toString() + ", 列 " + col.toString() + "]: " + msg)
    assert false, msg
end

测试错误报告：

// 缺少引号
// parse("{name: 1}")  → 错误 [行 1, 列 2]: 期望 '"' 但得到 'n'

// 尾部多余字符
// parse("[1,2] extra")  → 错误 [行 1, 列 7]: 尾部有多余字符

// 未闭合字符串
// parse("\"hello")  → 错误 [行 1, 列 7]: 字符串未闭合

深入细节

⚠️ 常见错误

本章小结

复习题

1. 递归下降解析器的核心思想是什么？BNF 中的 | 和 * 分别对应什么代码结构？
2. JSON 字符串有哪些合法转义序列？\u0041 表示什么字符？
3. 为什么 JSON 不需要运算符优先级处理？
4. [1, 2, ] 为什么是非法 JSON？解析器如何检测？
5. parseValue 如何判断下一个值是数组还是对象还是字符串？
6. 为什么对象的键必须是字符串而不能是数字？
7. skipWhitespace 跳过哪些字符？为什么 JSON 允许任意空白？
8. 手写解析器相比标准库 json.parse 的优势是什么？

编程练习