JSON 解析器是学习编译原理基础概念的绝佳练手项目——规范小、边界明确、不需要代码生成。本文用 Python 从零实现一个完整的 JSON 解析器，覆盖词法分析（Lexer）和语法分析（Parser）两个阶段。
整体思路
JSON 解析分为两步：
JSON 字符串 → Lexer(词法分析) → Token 流 → Parser(语法分析) → Python 对象
Lexer 把原始字符串切分为 Token（标记），比如 {、"name"、:、42、true。
Parser 根据 JSON 语法规则，把 Token 流组装成对应的数据结构。
Token 定义
from enum import Enum, auto
from dataclasses import dataclass
from typing import Any
class TokenType(Enum):
LEFT_BRACE = auto() # {
RIGHT_BRACE = auto() # }
LEFT_BRACKET = auto() # [
RIGHT_BRACKET = auto() # ]
COLON = auto() # :
COMMA = auto() # ,
STRING = auto() # "..."
NUMBER = auto() # 42, 3.14, -1, 1e10
TRUE = auto() # true
FALSE = auto() # false
NULL = auto() # null
EOF = auto() # 输入结束
@dataclass
class Token:
type: TokenType
value: Any
pos: int # 在原始字符串中的位置，用于错误提示
Lexer（词法分析）
Lexer 逐字符扫描，跳过空白，识别出 Token：
class JSONLexError(Exception):
def __init__(self, msg: str, pos: int):
super().__init__(f"Lex error at position {pos}: {msg}")
self.pos = pos
class Lexer:
def __init__(self, text: str):
self.text = text
self.pos = 0
def _current(self) -> str | None:
if self.pos < len(self.text):
return self.text[self.pos]
return None
def _advance(self) -> str:
ch = self.text[self.pos]
self.pos += 1
return ch
def _skip_whitespace(self):
while self.pos < len(self.text) and self.text[self.pos] in ' \t\n\r':
self.pos += 1
def _read_string(self) -> str:
'''读取 JSON 字符串（处理转义）'''
start = self.pos
self._advance() # 跳过开头的 "
chars = []
while True:
ch = self._current()
if ch is None:
raise JSONLexError("Unterminated string", start)
if ch == '"':
self._advance()
return ''.join(chars)
if ch == '\\':
self._advance()
esc = self._advance()
escape_map = {
'"': '"', '\\': '\\', '/': '/',
'b': '\b', 'f': '\f', 'n': '\n',
'r': '\r', 't': '\t',
}
if esc in escape_map:
chars.append(escape_map[esc])
elif esc == 'u':
# Unicode 转义: \uXXXX
hex_str = self.text[self.pos:self.pos + 4]
if len(hex_str) < 4:
raise JSONLexError("Invalid unicode escape", self.pos)
self.pos += 4
chars.append(chr(int(hex_str, 16)))
else:
raise JSONLexError(f"Invalid escape: \\{esc}", self.pos)
else:
chars.append(self._advance())
def _read_number(self) -> float | int:
'''读取 JSON 数字'''
start = self.pos
# 可选负号
if self._current() == '-':
self._advance()
# 整数部分
if self._current() == '0':
self._advance()
elif self._current() and self._current().isdigit():
while self._current() and self._current().isdigit():
self._advance()
else:
raise JSONLexError("Invalid number", start)
# 小数部分
is_float = False
if self._current() == '.':
is_float = True
self._advance()
if not (self._current() and self._current().isdigit()):
raise JSONLexError("Invalid number: digit expected after '.'", self.pos)
while self._current() and self._current().isdigit():
self._advance()
# 指数部分
if self._current() and self._current() in 'eE':
is_float = True
self._advance()
if self._current() and self._current() in '+-':
self._advance()
if not (self._current() and self._current().isdigit()):
raise JSONLexError("Invalid number: digit expected in exponent", self.pos)
while self._current() and self._current().isdigit():
self._advance()
num_str = self.text[start:self.pos]
return float(num_str) if is_float else int(num_str)
def _read_keyword(self, keyword: str, token_type: TokenType) -> Token:
'''读取关键字 (true/false/null)'''
start = self.pos
for ch in keyword:
if self._current() != ch:
raise JSONLexError(f"Expected '{keyword}'", start)
self._advance()
return Token(token_type, keyword, start)
def tokenize(self) -> list[Token]:
'''将输入字符串转换为 Token 列表'''
tokens = []
while True:
self._skip_whitespace()
if self.pos >= len(self.text):
tokens.append(Token(TokenType.EOF, None, self.pos))
break
ch = self._current()
pos = self.pos
simple_tokens = {
'{': TokenType.LEFT_BRACE,
'}': TokenType.RIGHT_BRACE,
'[': TokenType.LEFT_BRACKET,
']': TokenType.RIGHT_BRACKET,
':': TokenType.COLON,
',': TokenType.COMMA,
}
if ch in simple_tokens:
tokens.append(Token(simple_tokens[ch], ch, pos))
self._advance()
elif ch == '"':
s = self._read_string()
tokens.append(Token(TokenType.STRING, s, pos))
elif ch == '-' or ch.isdigit():
num = self._read_number()
tokens.append(Token(TokenType.NUMBER, num, pos))
elif ch == 't':
tokens.append(self._read_keyword("true", TokenType.TRUE))
elif ch == 'f':
tokens.append(self._read_keyword("false", TokenType.FALSE))
elif ch == 'n':
tokens.append(self._read_keyword("null", TokenType.NULL))
else:
raise JSONLexError(f"Unexpected character: '{ch}'", pos)
return tokens
Parser（语法分析）
递归下降解析器，每个 JSON 类型对应一个解析方法：
class JSONParseError(Exception):
def __init__(self, msg: str, pos: int):
super().__init__(f"Parse error at position {pos}: {msg}")
self.pos = pos
class Parser:
def __init__(self, tokens: list[Token]):
self.tokens = tokens
self.pos = 0
def _current(self) -> Token:
return self.tokens[self.pos]
def _eat(self, expected: TokenType) -> Token:
'''消费一个期望类型的 Token'''
token = self._current()
if token.type != expected:
raise JSONParseError(
f"Expected {expected.name}, got {token.type.name}",
token.pos
)
self.pos += 1
return token
def parse(self) -> Any:
'''解析入口'''
result = self._parse_value()
self._eat(TokenType.EOF)
return result
def _parse_value(self) -> Any:
'''解析一个 JSON 值'''
token = self._current()
if token.type == TokenType.LEFT_BRACE:
return self._parse_object()
elif token.type == TokenType.LEFT_BRACKET:
return self._parse_array()
elif token.type == TokenType.STRING:
self.pos += 1
return token.value
elif token.type == TokenType.NUMBER:
self.pos += 1
return token.value
elif token.type == TokenType.TRUE:
self.pos += 1
return True
elif token.type == TokenType.FALSE:
self.pos += 1
return False
elif token.type == TokenType.NULL:
self.pos += 1
return None
else:
raise JSONParseError(
f"Unexpected token: {token.type.name}", token.pos
)
def _parse_object(self) -> dict:
'''解析 JSON 对象: { key: value, ... }'''
self._eat(TokenType.LEFT_BRACE)
obj = {}
if self._current().type == TokenType.RIGHT_BRACE:
self._eat(TokenType.RIGHT_BRACE)
return obj
# 解析第一个 key-value
key_token = self._eat(TokenType.STRING)
self._eat(TokenType.COLON)
obj[key_token.value] = self._parse_value()
# 后续 key-value
while self._current().type == TokenType.COMMA:
self._eat(TokenType.COMMA)
key_token = self._eat(TokenType.STRING)
self._eat(TokenType.COLON)
obj[key_token.value] = self._parse_value()
self._eat(TokenType.RIGHT_BRACE)
return obj
def _parse_array(self) -> list:
'''解析 JSON 数组: [ value, ... ]'''
self._eat(TokenType.LEFT_BRACKET)
arr = []
if self._current().type == TokenType.RIGHT_BRACKET:
self._eat(TokenType.RIGHT_BRACKET)
return arr
arr.append(self._parse_value())
while self._current().type == TokenType.COMMA:
self._eat(TokenType.COMMA)
arr.append(self._parse_value())
self._eat(TokenType.RIGHT_BRACKET)
return arr
整合与测试
def json_parse(text: str) -> Any:
'''解析 JSON 字符串，返回 Python 对象'''
lexer = Lexer(text)
tokens = lexer.tokenize()
parser = Parser(tokens)
return parser.parse()
# ---- 测试 ----
if __name__ == "__main__":
# 基本类型
assert json_parse("42") == 42
assert json_parse("-3.14") == -3.14
assert json_parse("1e10") == 1e10
assert json_parse('"hello"') == "hello"
assert json_parse("true") is True
assert json_parse("false") is False
assert json_parse("null") is None
# 字符串转义
assert json_parse(r'"hello\nworld"') == "hello\nworld"
assert json_parse(r'"tab\there"') == "tab\there"
assert json_parse(r'"\u0041"') == "A"
# 数组
assert json_parse("[]") == []
assert json_parse("[1, 2, 3]") == [1, 2, 3]
assert json_parse('[1, "two", true, null]') == [1, "two", True, None]
# 对象
assert json_parse("{}") == {}
assert json_parse('{"a": 1, "b": "hello"}') == {"a": 1, "b": "hello"}
# 嵌套结构
nested = '{"users": [{"name": "Alice", "age": 30}, {"name": "Bob", "age": 25}]}'
result = json_parse(nested)
assert result["users"][0]["name"] == "Alice"
assert result["users"][1]["age"] == 25
# 错误处理
try:
json_parse('{"key": }')
except JSONParseError:
pass # 期望抛出错误
try:
json_parse('"unterminated string')
except JSONLexError:
pass
print("All tests passed!")
解析流程图解
以 {"name": "Alice", "age": 30} 为例：
Lexer 输出的 Token 流:
{ → STRING("name") → : → STRING("Alice") → , → STRING("age") → : → NUMBER(30) → }
Parser 递归调用:
parse()
└─ _parse_value()
└─ _parse_object()
├─ eat({)
├─ eat(STRING "name") → eat(:) → _parse_value() → "Alice"
├─ eat(,)
├─ eat(STRING "age") → eat(:) → _parse_value() → 30
└─ eat(})
最终结果: {"name": "Alice", "age": 30} (Python dict)
递归下降解析器的特点
递归下降是最直观的解析方法——每个语法规则对应一个函数，函数之间互相调用形成递归。JSON 的语法规则：
value → object | array | string | number | "true" | "false" | "null"
object → "{" (pair ("," pair)*)? "}"
pair → string ":" value
array → "[" (value ("," value)*)? "]"
每个规则直接对应 Parser 中的一个方法。这种一一对应的关系使得代码非常容易理解和维护。
局限性：递归下降要求语法是 LL(1) 的——即看一个 Token 就能决定走哪个分支。JSON 天然满足这个条件（看到 { 就知道是对象，看到 [ 就知道是数组），所以非常适合用递归下降来解析。
总结
完整代码大约 200 行。这个实现覆盖了 JSON 规范的所有数据类型，包括字符串转义和 Unicode 转义。如果要做到生产级别，还需要处理：数字精度问题（大整数）、重复 key 策略、最大嵌套深度限制、更友好的错误信息等。但作为理解词法分析和语法分析的入门练习，JSON 解析器是一个复杂度恰到好处的项目。
