KGT铁路图美化算法解析：8个Pretty Pass如何让图形输出更简洁-开发者社区

KGT铁路图美化算法解析：8个Pretty Pass如何让图形输出更简洁

【免费下载链接】kgtBNF wrangling and railroad diagrams项目地址: https://gitcode.com/gh_mirrors/kg/kgt

KGT（Kate's Grammar Tool）是一款用于 BNF 语法 wrangling 的命令行工具：输入各种 BNF 方言（WSN、ISO EBNF、ABNF、RBNF 等），输出转换后的 BNF 以及美观的铁路图（Railroad Diagram）。其中铁路图之所以看起来清爽，靠的是一组藏在src/rrd/下的美化算法（Pretty Pass）——本文带你快速看懂这 8 个 Pass 各干了什么。

美化在 KGT 流水线中的位置

KGT 的转换流程是：解析 BNF → 构建语法树 → 转成铁路图节点（RRD）→ 运行 Pretty Pass → 渲染输出。渲染器（SVG、UTF-8 文本等）在输出前统一调用一次rrd_pretty()入口函数，例如 svg/output.c 与 rrtext/output.c 都是如此。

驱动逻辑集中在src/rrd/pretty.c（第 63-86 行）：按固定顺序执行 Pass，每个 Pass 反复扫描整棵树，直到一次完整扫描没有产生任何改动（不动点迭代），且单 Pass 最多重试 20 次防止死循环。

美化流水线：一次运行的完整顺序

rrd_pretty()实际排了 13 步棋，collapse作为"清道夫"穿插在其余 8 个 Pass 之间：

步骤	Pass	作用一句话
1	🧹 collapse	移除只含 1 个元素的 alt/seq 容器
2	skippable	给带空分支的 alt 打上 skippable 标记
3	redundant	删掉循环外多余的选项框、循环内套循环
4	🧹 collapse	再清一次单元素容器
5	roll	把与循环体首尾相同的节点"卷"进循环
6	🧹 collapse	清理
7	nested	把嵌套的 alt/seq 压平合并
8	ci	拆出大小写字母对，生成`a-z`样式省略号
9	🧹 collapse	清理
10	affixes	循环前后的重复片段并入循环计数
11	🧹 collapse	清理
12	bottom	把"底重顶轻"的循环翻过来加跳过分支
13	🧹 collapse	收尾清理

逐个拆解：8 个 Pretty Pass 各做什么

以下源码都在src/rrd/目录，每个 Pass 都是对整棵 RRD 树的一次改写函数。

1️⃣ collapse：删空壳容器

文件：src/rrd/pretty_collapse.c

铁路图里"选择框（alt）"和"顺序框（seq）"如果只剩 1 个子节点，纯属浪费。这个 Pass 把壳剥掉，直接换成里面的子节点。它最频繁运行（13 步里出现 6 次），保证其他 Pass 每次改写后结构立即归整。

2️⃣ skippable：识别"可跳过"分支

文件：src/rrd/pretty_skippable.c

alt 里出现空分支（NULL，语义上是"什么都不写"）时，说明整个 alt 是可跳过的——Pass 会把NODE_ALT改写为NODE_ALT_SKIPPABLE，并顺手删掉 seq / skippable-alt 里无意义的空节点。渲染器借此画出一条干净的跳过直线，而不是一截悬空的空框。

3️⃣ redundant：消灭冗余包装

文件：src/rrd/pretty_redundant.c

处理两类冗余：

选项框包循环：ALT_SKIPPABLE只有两个分支，其中一个正好是可选循环（带跳过分支的 loop），那么这个 alt 是多余的，直接换成循环本身；
循环套循环：外层循环体内只有一层内循环且半边为空时，剥掉外层，只留内层。

4️⃣ roll：把重复片段卷进循环

文件：src/rrd/pretty_roll.c

源码注释里的 ASCII 示意最直观：当循环出口路径上的片段A B C与循环回边上的C B A等价时，把其中一个搬进循环的.forward列表，让重复部分整体进入循环结构，而不是画在循环外面。roll_prefix/roll_suffix分别处理循环前缀和后缀两种形态，图面立刻短了一截。

5️⃣ nested：压平嵌套结构

文件：src/rrd/pretty_nested.c

alt 里套 alt、seq 里套 seq，在铁路图上就是框中画框、线条绕圈。这个 Pass 把内层列表直接"摊平"合并进外层列表，一层变多层，视觉复杂度大幅下降。

6️⃣ ci：大小写字母对 → 省略号

文件：src/rrd/pretty_ci.c

BNF 里常写"26 个小写字母各写一遍"的冗长选择列表。这个 Pass 发现 alt 的每个文本分支都是单字符、且大小写各一份时，把它们转成成对的大小写敏感字面量，后续 tnode 重写阶段就能合并渲染成a-z/A-Z的省略号区间——几十个分支变成一个椭圆。

7️⃣ affixes：首尾匹配片段并入循环计数

文件：src/rrd/pretty_affix.c

若循环后面紧跟的片段恰好等于一次完整循环体（前缀/后缀匹配），就删掉这段 affix，把循环的 min/max 计数 +1。例如"至少出现 2 次"的X X，不再画成循环 → X，而是直接把循环记为X两次。

8️⃣ bottom：翻转"底重顶轻"的循环

文件：src/rrd/pretty_bottom.c

有些循环顶部为空、底部（回边）却是一大串复杂结构。直接渲染会让主路径变成一条反着走的线。这个 Pass 把循环上下翻转，并外包一个可跳过的 alt，用稍宽的图换取内容正序阅读——注释里明确写道："图会更宽，但避免了反转序列内容"。

为什么这个顺序不能乱

顺序本身就是算法的一部分：

先skippable标记可跳过性，redundant才能安全识别"可跳过的选项框"；
roll/affixes改写循环后可能产生新的单元素容器，所以后面紧跟collapse；
bottom放在最后，等结构基本定型再决定翻转方向。

每步的 20 次不动点迭代上限（见src/rrd/pretty.c第 78-84 行的limit = 20）则保证任何语法都能终止收敛。

上手看看效果

仓库的examples/目录提供了各方言的示例语法（如examples/expr.bnf、examples/expr.iso-ebnf），用 KGT 把任一 BNF 转成rrutf8或svg输出，美化前后的差别一眼可见。完整文档见 man/kgt.1/kgt.1.xml，教程图见doc/tutorial/目录。