lib-bnf:把文法编译成一条正则的实现细节

> 上一篇《Fun - BNF/FD 的双层自举》(fun-self.htm)用图示讲清了 Fun 为什么能"用自己解析自己":lib-bnf 自举 BNF 元语法,lib-fd 自举 FD 格式。这篇拆实现——那台"把文法编译成一条正则"的机器到底是怎么在 114 行里跑起来的,正则只负责匹配,语法树又是凭什么拼回来的。两篇合起来:一篇给地图,一篇给机芯。

## 一、真正在编译的是什么:一次展开把文法变成一条正则

FD/BNF 自举只是结果,地基是 `lib-bnf` 里一个朴素的念头:**把整门文法递归展开成一条 PCRE 正则,交给内建正则引擎去跑**。

核心是 `CBNF` 类的 `expand()`。对文法里每个非终结符引用,它做的是自顶向下的原地替换——遇到递归引用,就用 PCRE 的子程序调用语法 `(?&n)` 原地展开,而不是去写一个带调用栈的递归下降:

```fun
result = '(?<$nn>%s)'.eval().format(
           count[n]>1 and '(?&$n)'.eval() or expand(n));
```

一条文法规则可以引自己(BNF 最常见的递归),也可以被多处引用。`expand()` 用一个计数器追踪每个非终结符被展开的次数,凡是被引用两次以上的,就落成 `(?&n)` 子程序调用,让 PCRE 引擎去管那份递归;只出现一次的,则直接内联展开它的定义。最终产物是一条拖着几十个命名分组的巨型正则,交给 Fun 内建的正则引擎执行。文法的描述形式、自举的叙事,都在这一行之外——这里的全部功夫,就是"展开"。

## 二、两个旋钮:歧义与空白

把文法压成单条正则,最怕两件事:歧义,和手写空白规则。`CBNF` 用两个选项各化解一个。

`dup` 控制歧义处理。PCRE 的子程序调用在一个递归分支里复用同一份命名分组,文法一旦有歧义,分支上下文会互相踩踏。开启 `dup` 时,同一非终结符的多次出现被展开成带编号的副本(`Key_1`、`Key_2`),各自保留一份命名空间,歧义分支从此不再共享状态。

`ws` 则顺手消灭"填空白的仪式感"。多数文法不需要 `ws 空格 ws` 这种啰嗦的手写空白规则,`ws` 模式会在每个 token 之间自动缝上 `\s*+`(占有量词,防止回溯失控),文法作者只管写骨架,token 间的空白由生成器代劳。

## 三、正则只给"匹配",语法树靠偏移归约拼回来

这是整条链最巧的一环。正则引擎是纯文本匹配器,它只回答"匹配上了没有",永远不会直接吐一棵树。`group()` 怎么补上这段距离?

思路是把**匹配到的位置当中间码**。文法里每条规则成功匹配后,它的起点和终点偏移被打包进一个名为 `*` 的隐藏分组——每段 8 字节,`str2int` 的 `packed: 2` 模式直接按二进制读出(而不是转成字符串再解析)。于是正则一趟跑完,拿到的是一串扁平、按规则排序的偏移对,不是树。

要把它还原成树,`group()` 里是一个栈式归约 `reduce`:先把所有命中按**终点位置**排序,再一路 `peek` 栈顶——终点更早的节点先入栈当候选父节点,后到的节点看自己落在谁的区间里,据此决定是成为它的子节点还是兄弟:

```fun
loop
  var p = result.peek();
  exit when p = nil or not p.@a or o <> nil and o.e <= p.e;
  result.pop();
end loop;
```

树建好之后,`group()` 按节点名分派调用者提供的 `actions` 动作表——每个动作就是一个闭包,拿到的参数自带父指针 `p` 和结果槽 `r`。没有 Visitor 基类,没有回调注册中心,一张 map 就是全部接口。匹配、树重建、动作分派三层各司其职,整个解析器生成器于是只剩 114 行。

## 四、自举:文法自己也是这么来的(看代码版)

fun-self 那篇把两层自举画成了图示,这里只看代码是怎么咬合的。

`bnf.fd` 是"BNF 的 BNF"——11 行文法定义 BNF 自身的词法(非终结符 `Ref`、转义 `Escape`、字符类 `Class`……)。文件里同时存着源文法和编译产物:末尾的 `@regex` 字段就是 `expand()` 输出的成品正则,文法与目标码并排放着,像一份自带汇编清单的教科书。

`fd.bnf.fd` 则是 FD 格式自己的文法(21 行),定义缩进(`Ind/Indx`)、键(`Key`)、值(`Val`)、十六进制长度串(`Length`)。`lib-fd` 加载它的方式最能说明"数据即模块":

```fun
use ':fd.bnf.fd' as rules;      // use 直接把 FD 文件当数据载入
rules = rules.getJson(fd: true);
var cbcb = CBNF(rules, dup: 0); // 文法喂给生成器,得到 FD 的解析器
```

`use ':文件名'` 让任何 FD 文件都能像代码一样被导入。FD 用 lib-bnf 生成的解析器解析自己,lib-bnf 的文法又是 FD 写的——一个不需要 yacc、不需要独立生成步骤、运行时随手组装的鸡生蛋闭环。想一览整体闭环的,回看 fun-self 那篇的概念图即可,这里不再重复。

## 五、真有人用它:26789 行的那张表

自举不是炫技,因为有真实消费者。最大的藏在 `lib-asm-pro` 里:上一篇文章《lib-asm/jit:三条路到机器码》读过的 `asm-list.fd` 是一张 **26789 行的 x86 指令编码数据库**,每行一条规则如 `adc al,%2=14%2`(助记符+操作数=机器码模板),文件头 `#!kvd:=` 声明以 `=` 为键值分隔的方言变体。汇编器每翻译一条指令,就是在这张表里做一次字典查询。换句话说,fun-self 讲的那套自举、本文讲的那台正则生成器,最终服务的是一张让"助记符→机器码"能查得动的表。

性能上这套方案自然比不过表驱动的 yacc——每次解析都要真的跑一遍巨型正则,深递归文法还受 PCRE 回溯深度约束。但它的定位从来不是替代编译器后端,而是给 DSL 作者一个"5 分钟内造出解析器"的日常工具:写 20 行 BNF,喂给 `CBNF`,挂上动作闭包,一门小语言就活了。

## 六、结语:元编程的轻量级答案

把 lib-bnf、lib-fd、fd.fd 放回 Fun 的全景看,它们回答了上一篇留下的问题:一门自托管脚本语言,如何在不引入外部工具链的前提下支撑起自己的基础设施?答案是压扁层级——格式规范用数据格式自身书写,解析器生成器用 114 行闭包组装,工具链的每一环既是数据又是代码。比起工业级编译器基础设施,它更像一套精密的瑞士军刀:单件都不重,合起来能削出整个语言的自举闭环。概念地图见 fun-self 那篇;想看"文法怎么变成一条正则、又怎么拆回一棵树"的,本文这几节就是答案。