从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| 降到 m，m 就是非空表项的个数。这就是 O(m) 的来源，它不是什么高深的算法技巧，本质上就是把遍历对象从稠密网格换成稀疏边集。

1.3 三种 SS 表存储形态的取舍对照

我选 CSR，理由不只是遍历快。更实际的一点是：GS 表最终也要用 CSR 存，如果 SS 表本身就是 CSR，那么从 SS 到 GS 的构造可以做到“零中间结构”，直接边扫边填目标数组，省掉一次全量拷贝。这一点在生成器每次启动都要跑一遍的场景里，收益是实打实的。

提示：如果你的 SS 表还在增量构造阶段（比如 LALR 的核合并没做完），别急着转 CSR。CSR 的优势在于“定型后读取快”，一旦需要在中途增删边，重建整张表的代价会吃掉所有收益。

2. 整体设计：从“逐格询问”改成“逐边搬运”

2.1 朴素实现为什么在真实文法上会慢得莫名其妙

我最早写的那版拆分逻辑，就是老老实实的两层循环，跑教学用的玩具文法毫无问题，一上真实文法就开始卡。当时的直觉是“不就是两万次查表吗，能有多慢”，后来用性能分析工具一看，热点确实就在这两层循环里，而且耗时分布极不均匀——某些状态的行非常空，查询几乎全是无效访问，还带来大量缓存未命中。

更麻烦的是稀疏行版本。如果 SS 表按行存成vector<pair<sym, 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赋值，也就没法确定每条边该写到哪个位置。

有两条路。一条是用vector<vector<>>先攒着，最后再压平，但这引入了一堆小分配，和 CSR 的初衷背道而驰。另一条就是老老实实扫两遍：第一遍只数度数，第二遍才真正填充。两遍扫描的总成本是 2m 次边访问加 2n 次数组操作，仍然是 O(m)，而且两遍都是纯顺序访问，缓存命中率极高。实测下来，两遍扫描比“一遍扫描 + 动态扩容”快将近一倍，因为后者在扩容时要反复搬数据。

2.4 必须在动手前想清楚的四个边界情况

第一个是ε 产生式。形如A → ε的规则在归约时不弹出任何状态，直接拿当前栈顶状态去查GS[栈顶][A]。这意味着凡是“能在此处归约出 A”的状态，GS 表里必须有 A 的出边。自动机构造阶段天然满足这一点，但如果中途做过状态合并，就必须重新校验，否则运行时会查空。

第二个是死状态。有些状态在任何符号上都没有出边（纯报错状态）。构造 GS 表时不要好心给它补一条默认边，补了之后分析器会把语法错误当成合法输入吞下去，最后在更远的地方炸掉，错误定位信息全丢。

第三个是表项冲突。同一个(状态, 非终结符)出现两个不同目标状态，在合法的 LR 类自动机里不该发生。一旦发生了，说明自动机构造有 bug，这时候必须断言失败而不是任选一个——静默覆盖会让你在几百行之后的调试里痛不欲生。

第四个是不可达非终结符。如果某个非终结符在 GS 表里一列都没有，说明它在自动机里没有任何入边。这通常意味着它推导不出终结符串，或者从开始符号根本走不到它。这种情况应该在文法预处理阶段就被剔除，如果漏到了构造阶段，就该作为文法警告报出来。

3. 核心数据结构与内存布局

3.1 CSR 的三个数组怎么摆

CSR 的全称是压缩稀疏行，本质上是三个平行数组：row_off长度 n+1，第 i 项到第 i+1 项之间的区间就是第 i 行的数据范围；col存列索引；val存值。这套结构对“按行遍历”极其友好，因为同一行的数据在内存里是连续的，一次顺序扫描就能走完，硬件预取器也能完美工作。

放到这个场景里，SS 表是输入侧 CSR，GS 表是输出侧 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::vector<uint32_t> row_off; // 长度 n+1，row_off[n] == 边数 std::vector<uint32_t> col; // 列索引，行内升序 std::vector<uint32_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::vector<uint32_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::vector<uint32_t> cursor(gs.row_off.begin(), gs.row_off.end() - 1);

前缀和本身是 O(n)。前面论证过 n ≤ m+1——自动机里除了初始状态，每个状态至少有一条入边，否则它就是不可达的。所以 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::vector<uint8_t>，再用一个模板参数控制类型，内存再降一档。

第二处是游标。有的人为了省一个数组，会在填充时直接复用gs.row_off当游标（填完再修回来），这招确实省了一点点内存，但极易出 bug——一旦填充过程中抛异常，row_off就永久损坏了，后面的代码拿到的是垃圾。我现在的写法是老老实实多开一个cursor数组，n 个uint32_t，几百字节到几 KB 的事，不值得为它冒风险。

4.5 复杂度逐行核算与实测数据

把整个过程拆开算：

在有效文法上，n ≤ m+1，|V| ≤ m，P 与 m 同阶（每条产生式的每个位置在自动机里至少对应一条路径边），所以整体收敛到O(m)。

下面这组数字来自我手上这套生成器某次完整的压测记录，机器是一台普通的开发机，绝对值不具备参考意义，看数量级关系就行：

差距一路从三倍拉到十八倍。原因不难理解：稠密扫描的成本和 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）之后反而更慢，因为二分时只需要col，val被白白加载进缓存，浪费了缓存行。最后的做法保持 SoA 不变，但把val的类型压到uint16_t，让整个val数组能整体驻留。另外把热路径上的“先二分再读值”改成“二分过程中顺手把值一起放进返回结构”，减少一次函数调用开销。

6. 这套做法的复用边界与我自己的体会

前面整套流程里真正有复用价值的部分，其实只有三件事：按边遍历而不是按格遍历、提前把类型判断降级成一次数值比较、用 CSR 让遍历变成纯顺序访问。这三招的组合不只出现在语法分析表构造里，任何“稀疏矩阵按特征拆分成两张表”的场景都适用——比如把无向图的邻接矩阵拆成两个方向各一张边表、把一棵语法树按终结符和非终结符拆成两个遍历序列、把一份配置的键值对按类型分流成不同的索引结构，内核都是同一套。

我个人的体会是，这类优化的收益极度依赖数据分布，别迷信理论复杂度就无脑上。如果你的表本身就非常稠密（每个状态都有一大堆非终结符出边），那 O(m) 相对 O(n·|V_N|) 的优势就没那么夸张，这时候反而要评估两遍扫描的固定开销值不值。我在一个极稠密的实验性文法上就遇到过这种情况，m 和 n·|V_N| 只差两倍多，两遍扫描相比一遍稠密扫描没有任何优势，最后还是保留了原来的稠密路径，加了个规模阈值做自动切换。

还有一个小心得：这套构造过程的正确性，八成靠的是输入侧的契约，也就是“符号编号重排后非终结符连续”和“SS 表行内有序”这两条。与其在输出侧写一堆防御性校验，不如在输入侧用类型或者构造函数把这两条钉死，让违反契约的代码根本编译不过或者构造失败。我现在的做法是把符号表封装成一个不可变对象，重排之后只能通过只读接口访问，行内有序性在 CSR 的构造接口里强制检查，一次检查的成本是 O(m)，换来的是后面几个小时甚至几天的排查时间，非常划算。