数据解析 解析数据结构和算法，源码

class JsonParser:
    def __init__(self, s):
        self.index = 0
        self.str = s

    def parse_value(self):
        if self.current_char() == '{':
            return self.parse_object()
        # 处理数组、字符串等其他类型...

    def parse_object(self):
        obj = {}
        self.eat('{')
        while self.current_char() != '}':
            key = self.parse_string()
            self.eat(':')
            value = self.parse_value()
            obj[key] = value
            if self.current_char() == ',':
                self.eat(',')
        self.eat('}')
        return obj

这个状态机像吃豆人游戏，逐个字符吞噬输入流。currentchar()相当于探照灯，eat()方法像传送带把字符喂给解析器。注意parseobject里的循环结构，像极了现实中的装配流水线——遇到冒号就切换零件组装模式。

递归下降法在真实项目中很常见，比如Python的json模块底层就有类似结构。它的优势在于调试方便，遇到语法错误时调用栈就是天然的错误定位器。但手写解析器有个坑：处理unicode转义时容易漏掉四字节编码的情况。看看Go语言标准库的实现：

func (p *parser) parseString() (string, error) {
    var buf bytes.Buffer
    for {
        c := p.getc()
        if c == '"' {
            break
        }
        if c == '\\' {
            // 处理转义字符的分支
            switch p.getc() {
            case 'u':
                // 读取四字节unicode
                r := p.parseUnicode()
                buf.WriteRune(r)
            // 其他转义情况...
            }
        } else {
            buf.WriteRune(c)
        }
    }
    return buf.String(), nil
}

这个实现用状态变量代替递归，更适合处理长字符串。注意getc()方法暗藏玄机——它维护的读取位置索引，就像侦探破案时在卷宗上的标记，必须精确到每个字节的位置。

当遇到嵌套结构时，解析器需要栈结构辅助。比如XML解析器遇到时压栈，遇到时弹栈校验。这种场景下，用双向链表实现栈比数组更高效，因为节点删除操作时间复杂度能降到O(1)。Java的LinkedList源码就深谙此道：

public class LinkedList<E> extends AbstractSequentialList<E> {
    private transient Entry<E> header = new Entry<E>(null, null, null);
    
    public void push(E item) {
        addBefore(item, header.next);
    }
    
    public E pop() {
        return removeFirst();
    }
}

这个实现里header节点充当哨兵，addBefore操作就像在火车车厢间插入新车厢，无需移动其他元素。这种设计在解析深度嵌套的JSON或XML时，能有效避免频繁的对象创建开销。

解析算法最刺激的部分当属错误恢复。V8引擎的JSON.parse在遇到错误时会执行如下操作：

1. 记录错误位置
2. 跳过非法字符直到遇到结构边界
3. 尝试继续解析

这就像外科医生处理创伤，既要切除坏死组织，又要尽量保留健康器官。这种启发式处理让很多"不完美"的JSON数据也能被解析，代价是可能隐藏潜在的数据错误。

最后说个冷知识：Protocol Buffers的解析器比JSON快5-8倍，秘诀在于它用查表法替代条件判断。当字段标识号连续时，直接通过偏移量访问处理函数，这种空间换时间的策略在Kafka等高性能系统中随处可见。