kbnf

本库提供了一种约束解码引擎，确保语言模型输出严格遵循 KBNF（Koishi 的 BNF）定义的格式，KBNF 是 EBNF 的增强变体。KBNF 包含增强可用性的功能，特别是可嵌入的正则表达式和更灵活的异常处理。

如果您对这个库的设计和实现感兴趣，可以查看我的博客。

功能

• 支持完整的上下文无关语法，时间复杂度为 O(m*n^3)，其中 n 是生成的文本长度，m 是词汇表大小。
• 对于上下文无关语法的子类，渐近速度最快。
  • 对于每个 LR(k) 语法（包括几乎所有实用语法），保证最坏情况下的时间复杂度为 O(m*n)
  • 当 n 具有固定上限或语法为正则时，通过缓存最终实现 O(n) 时间复杂度
• 与词汇无关。
  • 支持 BPE、BBPE 等所有类型的词汇表。
• 支持语法中的 UTF-8 字符。
• 支持可嵌入的正则表达式。
• 更灵活的异常处理，可以排除字符串的并集。

文档

文档和示例.

添加到您的项目中

只需将其添加到您的 Cargo.toml 或在命令行中运行 cargo add kbnf

性能

本库的目标之一是使约束解码引擎“快速”。这可以从理论和实践两个方面来理解。

理论上，这个库旨在为上下文无关文法的每个子类提供渐近最快的算法。通过实现带有Leo优化的Earley识别器，该库已成功实现了每个LR(k)文法的线性时间复杂度以及每个无歧义文法的二次时间复杂度。对于一般的上下文无关文法，情况更为复杂（这里有意为之）：虽然存在子立方算法（尽管常数较大），但所有其他通用解析算法（如Earley、GLR、GLL等）的确是立方时间复杂度，就像我们的算法一样。