从SS表到GS表：O(m)构造、CSR布局与两遍扫描

“由 SS 表构造 GS 表”这个标题我第一次看到的时候是愣了一下的。不是因为难而是因为这两个缩写在不同教材里的指代差异太大——有人拿 SS 指简单优先关系矩阵有人拿它指分析自动机的状态-符号转移表GS 也一样有的语境里指 GOTO 转移表有的指状态分组表。口径不统一写出来的代码和脑子里的模型就对不上这是做表驱动解析这类活儿最容易吃的暗亏。这篇文章我采用的约定是SS 表指语法分析自动机的“状态 × 文法符号”总转移表终结符列和非终结符列混在同一张表里GS 表指从它当中切出来的、只保留非终结符转移的那部分也就是分析器在完成一次归约之后去查的那张 GOTO 表。标题里的O(m)m 数的是 SS 表里非空表项的数量也就是自动机的转移边数不是状态数乘符号数那个乘积。这个区别是整个优化能不能成立的关键后面会花不少篇幅把它掰开。这篇内容适合三类人正在自己撸语法分析器生成器、需要把内部中间表示转成运行时表的在做表驱动解析器性能调优、想搞清楚查表热路径到底慢在哪的以及单纯被“O(m)”这个标注吸引过来、想弄明白为什么它比直觉上的 O(n·|V|) 低一个数量级的。我会把数据结构、编号方案、两遍扫描的实现、以及实际踩过的坑都摊开讲代码给的是可直接编译验证的片段不是伪代码糊弄。1. 术语对齐SS 表、GS 表与那个容易被误解的 O(m)1.1 分析器运行时到底在查哪几张表任何一个表驱动的自底向上分析器运行时手里就两样东西一个状态栈和一张或两张查找表。循环逻辑极其简单——看栈顶状态、看当前输入符号、查表、根据查到的动作决定移进还是归约。真正复杂的部分全部被前置到“生成这张表”的阶段去了。问题在于生成阶段和运行阶段对“表”的期望是不一样的。生成阶段希望信息集中方便做闭包计算、冲突检测、状态合并运行阶段希望信息分片因为终结符和非终结符的处理路径根本不同。遇到终结符查到的可能是“移进某个状态”“按某条产生式归约”“接受”“报错”四种动作之一遇到非终结符只有一种可能——转移到某个状态而且这个查询只在归约之后才发生不在主循环的每一步。所以运行时要的是两张表一张终结符侧的动作表一张非终结符侧的转移表也就是 GS 表。而生成器内部为了构造方便往往先把它们揉成一张 SS 表等自动机定型了再拆开。拆这个动作看起来平淡无奇但它是每次生成分析器都要跑一遍的固定开销文法一大拆分耗时会变得很显眼。1.2 m 到底数的是什么按格子算还是按边算这是全篇最核心的一个认知转换。假设自动机有 n 个状态文法有 |V| 个符号其中非终结符 |V_N| 个。如果按“格子”的思路去做这件事你会自然而然地写出两层循环外层遍历 n 个状态内层遍历 |V_N| 个非终结符逐个去 SS 表里查SS[i][A]有没有值。复杂度就是 O(n·|V_N|)。可真实文法的数据分布完全不是这样。一个状态在非终结符上通常只有零到两条出边绝大多数格子是空的。也就是说你花了 n·|V_N| 次查询其中有九成以上查了个寂寞。举个量级感受一下一个中等规模的语言文法状态数两三百符号数八九十格子数是两万多而实际的非终结符转移边数常常只有一百多到两百条。差了整整两个数量级。按“边”的思路则完全不同我不去问“每个格子有没有值”我只遍历那些确实有值的表项边走边判断这条边的目标符号是不是非终结符是就搬到 GS 表里不是就跳过。遍历次数从 n·|V_N| 降到 mm 就是非空表项的个数。这就是 O(m) 的来源它不是什么高深的算法技巧本质上就是把遍历对象从稠密网格换成稀疏边集。1.3 三种 SS 表存储形态的取舍对照存储形态随机访问内存占用线性遍历效率构造难度适用场景稠密二维数组T[n][|V|]O(1)n×|V|×4 字节一般空项也扫最低状态少、符号少的教学文法稀疏行vectorvectorpairO(d) 或 O(log d)只存非空项但每行有 vector 头开销差指针跳转多低增量构造、频繁修改三元组(row, col, val)数组O(m)3×m×4 字节好但要先排序中中间过渡形态CSR 两段式row_off col valO(log d) 行内二分(n1 2m)×4 字节最好连续内存中构造完即定型的最终形态我选 CSR理由不只是遍历快。更实际的一点是GS 表最终也要用 CSR 存如果 SS 表本身就是 CSR那么从 SS 到 GS 的构造可以做到“零中间结构”直接边扫边填目标数组省掉一次全量拷贝。这一点在生成器每次启动都要跑一遍的场景里收益是实打实的。提示如果你的 SS 表还在增量构造阶段比如 LALR 的核合并没做完别急着转 CSR。CSR 的优势在于“定型后读取快”一旦需要在中途增删边重建整张表的代价会吃掉所有收益。2. 整体设计从“逐格询问”改成“逐边搬运”2.1 朴素实现为什么在真实文法上会慢得莫名其妙我最早写的那版拆分逻辑就是老老实实的两层循环跑教学用的玩具文法毫无问题一上真实文法就开始卡。当时的直觉是“不就是两万次查表吗能有多慢”后来用性能分析工具一看热点确实就在这两层循环里而且耗时分布极不均匀——某些状态的行非常空查询几乎全是无效访问还带来大量缓存未命中。更麻烦的是稀疏行版本。如果 SS 表按行存成vectorpairsym, state那么SS[i][A]这个查询在每行里都要做一次线性查找或二分。总成本变成 O(n·|V_N|·log d)比稠密数组还糟糕。这也是很多人写生成器时踩过的坑为了省内存用了稀疏结构结果在拆分阶段被反噬。2.2 符号编号重排把类型判断降级成一次整数比较逐边遍历之后每条边都要回答一个问题这条边的目标符号是终结符还是非终结符最直白的做法是查一张类型表is_nonterm[sym]。但这样一来每条边都多一次内存访问而这张类型表本身也可能不在缓存里。真正省事的做法是在文法读入完成后做一次符号编号重排把所有终结符排在前面所有非终结符排在后面记下分界点nonterm_base。重排之后判断就变成了一句sym nonterm_base编译器会把它编译成一次寄存器比较零内存访问。这个改动看起来微不足道但在 m 达到几十万条的规模时省下的就是几十万次潜在的缓存缺失。重排本身的成本是 O(|V|)——遍历符号表、生成新旧编号的映射数组、再把所有产生式右部、First/Follow 集合、项目集里的符号编号替换一遍。有人会担心这一步破坏了 O(m) 的承诺其实不会在剔除无用符号之后的文法里每个有效符号必然至少在某条转移边上出现过要么作为出边的标签要么作为某条路径上的符号所以 |V_有效| ≤ m重排成本被 m 吸收掉了。注意重排之后所有已经算好的哈希表、位图、索引数组全部失效必须同步重建。我见过有人重排了符号编号却忘了更新 Follow 集的位图结果生成出来的分析器在一半输入上行为诡异排查了大半天。2.3 为什么两遍扫描比一遍扫描更划算第一反应肯定是想一遍扫描搞定边遍历 SS 表边往 GS 表里塞。问题是 GS 表用 CSR 存而 CSR 的行偏移数组必须在填充之前就知道每一行有多少个元素。你不知道每个状态有几个非终结符出边就没法给row_off赋值也就没法确定每条边该写到哪个位置。有两条路。一条是用vectorvector先攒着最后再压平但这引入了一堆小分配和 CSR 的初衷背道而驰。另一条就是老老实实扫两遍第一遍只数度数第二遍才真正填充。两遍扫描的总成本是 2m 次边访问加 2n 次数组操作仍然是 O(m)而且两遍都是纯顺序访问缓存命中率极高。实测下来两遍扫描比“一遍扫描 动态扩容”快将近一倍因为后者在扩容时要反复搬数据。2.4 必须在动手前想清楚的四个边界情况第一个是ε 产生式。形如A → ε的规则在归约时不弹出任何状态直接拿当前栈顶状态去查GS[栈顶][A]。这意味着凡是“能在此处归约出 A”的状态GS 表里必须有 A 的出边。自动机构造阶段天然满足这一点但如果中途做过状态合并就必须重新校验否则运行时会查空。第二个是死状态。有些状态在任何符号上都没有出边纯报错状态。构造 GS 表时不要好心给它补一条默认边补了之后分析器会把语法错误当成合法输入吞下去最后在更远的地方炸掉错误定位信息全丢。第三个是表项冲突。同一个(状态, 非终结符)出现两个不同目标状态在合法的 LR 类自动机里不该发生。一旦发生了说明自动机构造有 bug这时候必须断言失败而不是任选一个——静默覆盖会让你在几百行之后的调试里痛不欲生。第四个是不可达非终结符。如果某个非终结符在 GS 表里一列都没有说明它在自动机里没有任何入边。这通常意味着它推导不出终结符串或者从开始符号根本走不到它。这种情况应该在文法预处理阶段就被剔除如果漏到了构造阶段就该作为文法警告报出来。3. 核心数据结构与内存布局3.1 CSR 的三个数组怎么摆CSR 的全称是压缩稀疏行本质上是三个平行数组row_off长度 n1第 i 项到第 i1 项之间的区间就是第 i 行的数据范围col存列索引val存值。这套结构对“按行遍历”极其友好因为同一行的数据在内存里是连续的一次顺序扫描就能走完硬件预取器也能完美工作。放到这个场景里SS 表是输入侧 CSRGS 表是输出侧 CSR两者结构完全一致。这种一致性带来一个额外好处调试的时候可以用同一套打印函数把两张表都 dump 出来肉眼比对非常方便。我在项目里就写了一个dump_csr工具接受任意 CSR 结构和一张符号名表输出成人能读的矩阵样式定位问题时省了大量时间。3.2 列索引压缩全局符号号还是局部列号GS 表的列逻辑上对应非终结符。存的时候有两种选择存全局符号编号比如A的全局号是 37或者存局部列号A - nonterm_base比如 3。前者查表时不需要做减法后者占用的数值范围小得多。我选局部列号理由很实际局部列号的上界是 |V_N|一个中等文法通常几十到两百多个非终结符用uint8_t就装得下|V_N| ≤ 256 时最多也就uint16_t。而全局符号号可能上千必须用uint32_t。这一下就把col数组的体积压掉了四分之三。GS 表在分析器热路径上被反复读取体积小意味着更容易整体驻留在 L1 缓存里。代价是查表时要多做一次减法。但这个减法完全可以提前做掉在生成阶段把每条产生式左部对应的局部列号预先算好存进产生式结构里归约时直接拿这个数去查热路径上一次减法都省了。这是那种“看起来只有一点点收益但乘以每秒几百万次归约就很可观”的优化。3.3 数据类型选型uint16 还是 uint32状态编号的类型选择取决于状态数。状态数小于 65536 时uint16_t够用超过就必须上uint32_t。这个决定最好做成编译期常量或者构建时参数而不是拍脑袋写死。我吃过一次亏早期为了省内存全用了uint16_t后来某个大型配置语言的文法状态数突破了这个界限整数溢出导致状态号回绕分析器在处理特定输入时进入死循环症状极其隐蔽。一个折中做法是用uint32_t存状态号用uint16_t或uint8_t存列索引因为列索引的上界是非终结符数量比状态数小得多。这样内存占用和安全性都能兼顾。至于row_off它必须能表示到 m所以跟状态号和边数中较大的那个对齐一般用uint32_t。4. 完整实现从 SS 表到 GS 表的两遍扫描4.1 结构定义与前置约定先把结构体和全局约定摆出来。约定有三条状态编号从 0 连续排到 n-1符号编号重排后终结符占[0, nonterm_base)非终结符占[nonterm_base, num_symbols)SS 表用 CSR 存且每一行内的列索引按升序排好。第三条很关键它让 GS 表继承有序性后续行内二分才有意义。#include cstdint #include vector #include cassert struct CSR { std::vectoruint32_t row_off; // 长度 n1row_off[n] 边数 std::vectoruint32_t col; // 列索引行内升序 std::vectoruint32_t val; // 目标状态 }; struct Automaton { uint32_t num_states 0; uint32_t num_symbols 0; uint32_t nonterm_base 0; // 非终结符起始的全局符号号 CSR ss; // 状态 x 符号 的总转移表 };SS 表在自动机构造阶段生成时只要保证每次往某一行插边都按列索引有序插入或者整行构造完再排一次序就能满足约定。实测两种方式都行增量有序插入在边少的时候更省整行排序在边多的时候更快交叉点大概在一行超过八条边左右。4.2 第一遍统计每个状态的非终结符出度第一遍只做一件事——数出每个状态在非终结符上有多少条出边。除了数数什么都不干这样循环体极小编译器能把它优化得很好实测这一遍的耗时通常只有第二遍的三到四成。// 第一遍统计每个状态的 GS 出度 std::vectoruint32_t gs_deg(num_states, 0); for (uint32_t s 0; s num_states; s) { for (uint32_t k ss.row_off[s]; k ss.row_off[s 1]; k) { if (ss.col[k] nonterm_base) { // 一次比较零访存 gs_deg[s]; } } }这里就能看出编号重排的价值了。如果把ss.col[k] nonterm_base换成查类型表is_nonterm[ss.col[k]]循环体里就多了一次随机内存访问在 m 达到几十万的规模下这一句的差异能到几十微秒。别小看这几十微秒如果生成器在开发过程中被反复调用比如每次改文法都重新生成累计起来就是可感知的等待。顺带说一句这个循环的访存模式是纯顺序的ss.col从row_off[0]一路扫到row_off[n]中间不跳。gs_deg虽然是被随机下标访问但它是个小数组通常整个驻留在 L1 里。这种访存模式是 CSR 相对稀疏行的最大优势。4.3 前缀和与游标初始化拿到度数之后做一次前缀和就得到row_off。这一步是标准的 CSR 构造套路没什么花活但有个细节值得提游标数组应该直接从row_off的拷贝初始化而不是从零重新累加。这样即使后面有人改了逻辑顺序写入位置也不会错位属于防御性写法。CSR gs; gs.row_off.resize(num_states 1); gs.row_off[0] 0; for (uint32_t s 0; s num_states; s) { gs.row_off[s 1] gs.row_off[s] gs_deg[s]; } const uint32_t gs_edges gs.row_off[num_states]; gs.col.resize(gs_edges); gs.val.resize(gs_edges); // 游标第 s 行下一个空位的写入位置 std::vectoruint32_t cursor(gs.row_off.begin(), gs.row_off.end() - 1);前缀和本身是 O(n)。前面论证过 n ≤ m1——自动机里除了初始状态每个状态至少有一条入边否则它就是不可达的。所以 O(n) 也被 O(m) 吸收总的复杂度记作 O(m) 是站得住的。4.4 第二遍填充 GS 表第二遍重新扫一遍 SS 表这次是真正把非终结符边搬过去。写入位置由游标维护每条边写完后游标自增天然保证同一行内按 SS 表的原始顺序排列也就继承了行内升序的性质。// 第二遍填充 GS 表 for (uint32_t s 0; s num_states; s) { for (uint32_t k ss.row_off[s]; k ss.row_off[s 1]; k) { const uint32_t sym ss.col[k]; if (sym nonterm_base) { const uint32_t p cursor[s]; gs.col[p] sym - nonterm_base; // 压成局部列号 gs.val[p] ss.val[k]; } } }这段代码里有两处值得展开。第一处是sym - nonterm_base把全局符号号压成局部列号前面讲过它能省内存这里补充一点压缩之后gs.col的取值范围是[0, |V_N|)如果 |V_N| 不超过 256可以直接把gs.col声明成std::vectoruint8_t再用一个模板参数控制类型内存再降一档。第二处是游标。有的人为了省一个数组会在填充时直接复用gs.row_off当游标填完再修回来这招确实省了一点点内存但极易出 bug——一旦填充过程中抛异常row_off就永久损坏了后面的代码拿到的是垃圾。我现在的写法是老老实实多开一个cursor数组n 个uint32_t几百字节到几 KB 的事不值得为它冒风险。4.5 复杂度逐行核算与实测数据把整个过程拆开算阶段操作次数复杂度符号编号重排约 |V| PP 为产生式总长度O(|V| P)第一遍统计度数m 次边访问 n 次自增O(m n)前缀和n 次加法O(n)游标初始化n 次拷贝O(n)第二遍填充m 次边访问 至多 m 次三连写O(m)合计O(m n |V| P)在有效文法上n ≤ m1|V| ≤ mP 与 m 同阶每条产生式的每个位置在自动机里至少对应一条路径边所以整体收敛到O(m)。下面这组数字来自我手上这套生成器某次完整的压测记录机器是一台普通的开发机绝对值不具备参考意义看数量级关系就行文法规模状态数 n符号数 |V|转移边数 mGS 边数稠密扫描耗时按边扫描耗时教学用玩具文法322178243 μs1 μs某内部配置语言2148763117841 μs6 μs某脚本语言子集10241563487902380 μs27 μs大型表达式文法2871203964223111.4 ms78 μs差距一路从三倍拉到十八倍。原因不难理解稠密扫描的成本和 n×|V_N| 成正比而每行的出度基本稳定在个位数所以文法越大浪费的比例越高。这也解释了为什么很多人在小文法上测不出问题一上真实项目就发现生成器启动要等好几秒。4.6 三条构造后断言构造完必须校验不然错了要等到分析器跑崩溃才发现那就太晚了。我固定加三条断言全部是 O(m) 或 O(n) 的几乎不增加开销。第一条校验边数一致统计出来的非终结符边总数必须等于gs.row_off[num_states]。如果不等说明两遍扫描之间有数据被改动了。第二条校验行内严格递增对每个状态检查gs.col在其区间内严格单调。这条能抓出 SS 表本身无序的问题——如果 SS 表行内是乱序的GS 表继承下来也是乱序的二分查找会静默返回错误结果比崩溃更难查。for (uint32_t s 0; s num_states; s) { for (uint32_t k gs.row_off[s] 1; k gs.row_off[s 1]; k) { assert(gs.col[k] gs.col[k - 1] GS row not sorted); } }第三条是运行期交叉校验拿一组测试输入跑完整分析流程每一次归约之后查 GS 得到的新状态都要和“直接用项目集族重新算一遍”的结果比对。这条成本高只在调试构建里开但它是唯一能真正证明 GS 表语义正确的手段。5. 排查实录五个真实踩过的坑5.1 归约时 GOTO 查空症状是分析器在某个特定输入上直接崩断言信息显示“在状态 X 上查非终结符 A 没有出边”。第一反应是 GS 表构造漏了但把 SS 表的对应行打出来一看明明有这条边。根因在别处归约时的弹栈长度算错了。对于A → X1 X2 ... Xk弹出的是 k 个状态而当时的实现里把 k 算成了“产生式右部的字符串长度”遇到多字符非终结符就多弹了。栈顶错位之后查到的自然是另一个状态那个状态当然没有 A 的出边。这类问题的特征是“错误位置和分析表本身无关”排查时第一件事应该是把手算的弹栈长度和代码里的打出来对照。5.2 两遍扫描度数对不上第一遍数出 GS 边数是 178第二遍填完只有 174断言直接炸了。查了很久才发现SS 表在冲突消解阶段被增量修改过——某个状态的一条边目标被改了符号类别但那次修改没有重新排序该行导致第一遍按无序状态扫、第二遍按另一种顺序扫两边看到的边集不一致。解决办法很土但有效构造 GS 表之前先给 SS 表拍个快照或者加只读约束两遍扫描都基于同一份不可变数据。如果实在要在增量过程中构造那就得在每次修改 SS 表时同步维护度数数组代价更大不划算。5.3 ε 产生式让栈顶状态错位这条前面提过但实际踩的时候表现形式很迷惑。某个单元测试的输入里明明语法合法分析器却报错。打了栈的完整历史才看出来归约A → ε时按“弹出 0 个状态”处理是对的但代码里是先弹栈再查表弹完之后忘了把栈顶指针更新于是查的还是弹出前的那个状态。这个 bug 的阴险之处在于绝大多数产生式右部长度非零走的是另一条分支所以常规测试全绿只有 ε 相关的用例才暴露。我的建议是给“空产生式归约”单独写一条路径别和常规归约共用同一段弹栈逻辑路径分开之后这类错位问题就基本绝迹了。5.4 行内列索引无序导致二分失效GS 表填完之后跑测试偶尔算错偶尔又对症状飘忽。定位到二分查找上发现某些行的col不是升序的。根源在 SS 表本身构造自动机时为了快采用的是“先追加后补排序”的策略但补排序只对超过某个阈值的行做了小行就漏了。给 SS 表加一条全局后置排序或者逐行排序就解决了。顺带说一句这提醒了一个通用原则CSR 的行内有序性是个必须显式维护的契约不能靠构造过程“顺手”保证。要么在构造结束时统一排一遍要么在类型层面用不变量把它钉死。5.5 表很小但 cache miss 很高最后一坑比较隐蔽。GS 表总共才几千字节理论上整个都能塞进 L1但性能分析工具显示查表处的缓存缺失率远高于预期。查了半天问题是col和val交错访问每次二分要读col命中之后要读val两个数组虽然都是连续存放的但它们是分开的数组访问模式依然是两次不同的内存区域。改成结构体数组AoS之后反而更慢因为二分时只需要colval被白白加载进缓存浪费了缓存行。最后的做法保持 SoA 不变但把val的类型压到uint16_t让整个val数组能整体驻留。另外把热路径上的“先二分再读值”改成“二分过程中顺手把值一起放进返回结构”减少一次函数调用开销。6. 这套做法的复用边界与我自己的体会前面整套流程里真正有复用价值的部分其实只有三件事按边遍历而不是按格遍历、提前把类型判断降级成一次数值比较、用 CSR 让遍历变成纯顺序访问。这三招的组合不只出现在语法分析表构造里任何“稀疏矩阵按特征拆分成两张表”的场景都适用——比如把无向图的邻接矩阵拆成两个方向各一张边表、把一棵语法树按终结符和非终结符拆成两个遍历序列、把一份配置的键值对按类型分流成不同的索引结构内核都是同一套。我个人的体会是这类优化的收益极度依赖数据分布别迷信理论复杂度就无脑上。如果你的表本身就非常稠密每个状态都有一大堆非终结符出边那 O(m) 相对 O(n·|V_N|) 的优势就没那么夸张这时候反而要评估两遍扫描的固定开销值不值。我在一个极稠密的实验性文法上就遇到过这种情况m 和 n·|V_N| 只差两倍多两遍扫描相比一遍稠密扫描没有任何优势最后还是保留了原来的稠密路径加了个规模阈值做自动切换。还有一个小心得这套构造过程的正确性八成靠的是输入侧的契约也就是“符号编号重排后非终结符连续”和“SS 表行内有序”这两条。与其在输出侧写一堆防御性校验不如在输入侧用类型或者构造函数把这两条钉死让违反契约的代码根本编译不过或者构造失败。我现在的做法是把符号表封装成一个不可变对象重排之后只能通过只读接口访问行内有序性在 CSR 的构造接口里强制检查一次检查的成本是 O(m)换来的是后面几个小时甚至几天的排查时间非常划算。