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

KGT铁路图美化算法解析8个Pretty Pass如何让图形输出更简洁【免费下载链接】kgtBNF wrangling and railroad diagrams项目地址: https://gitcode.com/gh_mirrors/kg/kgtKGTKates 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 容器2skippable给带空分支的 alt 打上 skippable 标记3redundant删掉循环外多余的选项框、循环内套循环4 collapse再清一次单元素容器5roll把与循环体首尾相同的节点卷进循环6 collapse清理7nested把嵌套的 alt/seq 压平合并8ci拆出大小写字母对生成a-z样式省略号9 collapse清理10affixes循环前后的重复片段并入循环计数11 collapse清理12bottom把底重顶轻的循环翻过来加跳过分支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.calt 里出现空分支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.calt 里套 alt、seq 里套 seq在铁路图上就是框中画框、线条绕圈。这个 Pass 把内层列表直接摊平合并进外层列表一层变多层视觉复杂度大幅下降。6️⃣ ci大小写字母对 → 省略号文件src/rrd/pretty_ci.cBNF 里常写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改写循环后可能产生新的单元素容器所以后面紧跟collapsebottom放在最后等结构基本定型再决定翻转方向。每步的 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/目录。小结8 个 Pretty Pass 高频清道夫collapse组成一条 13 步的铁路图美化流水线每个 Pass 只负责一种结构简化剥壳、标记、去冗余、卷循环、压平、字母合并、计数并入、翻转不动点迭代 顺序编排是输入任意 BNF输出都能又简洁又稳定的关键全部源码位于src/rrd/pretty_*.c入口src/rrd/pretty.c非常适合逐文件阅读源码。【免费下载链接】kgtBNF wrangling and railroad diagrams项目地址: https://gitcode.com/gh_mirrors/kg/kgt创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考