偃师 yanshi：一个可内嵌 C++ 动作、支持近似上下文无关文法的有限状态自动机生成器-平芜编程栈

偃师 yanshi：一个可内嵌 C++ 动作、支持近似上下文无关文法的有限状态自动机生成器

【免费下载链接】SafeLineSafeLine is a self-hosted WAF(Web Application Firewall) / reverse proxy to protect your web apps from attacks and exploits.项目地址: https://gitcode.com/GitHub_Trending/sa/SafeLine

yanshi 是 SafeLine 仓库中独立子项目yanshi/下实现的一个有限状态自动机（FSA）生成器，定位类似 Ragel，但通过@{}内联运算符把 C++ 代码嵌入到语言识别的每个关键节点，并额外提供了子串文法近似与递归自动机近似两种能力，以逼近上下文无关文法（CFG）的表达范围。读完本文，你将掌握 yanshi 的构建与命令行用法、yanshi 语言语法（正则式、动作、模块、子串文法）、EmbedExpr/CollapseExpr/CallExpr三种非终结符引用机制的差异与实现原理，以及其编译器内部结构与调试手段。

本文全部内容基于 yanshi/README.md 展开，并结合yanshi/src/、yanshi/unittest/、yanshi/contrib/等目录下的源码与测试进行佐证与深化。

概述与设计动机

定位

yanshi 是一个类似 Ragel 的有限状态自动机生成器，核心特性是：

使用内联运算符把 C++ 代码嵌入语言识别的过程之中；
提供近似子串文法（substring grammar）的能力；
提供递归自动机的近似能力，从而近似上下文无关文法（context-free grammar）。

为什么不用 Ragel

README 明确指出，创作 yanshi 的直接动机是：Ragel 没有提供序列化其有限状态自动机表示形式的机制，导致无法对生成后的自动机做后处理（post-process），也就难以从中得到子串文法识别器。

性能与内存问题的驱动

后续实践中作者发现，一个简化后的 SQL 文法可能包含超过 10000 个状态。此时：

自动机生成缓慢，难以进行快速的试错实验（trial-and-error）；
存储自动机浪费大量内存。

为此作者引入CollapseExpr，允许循环引用；CallExpr则更进一步，维护一个返回地址栈来模拟函数调用，可以视为CollapseExpr的增强版，消除了大量误报（false positive）情况。

名字的由来

名字"yanshi（偃师）"来自《列子》中关于古代中国自动机的一段记载（见 yanshi/README.md 的 Name 一节）：

中国古代关于自动机的奇闻见于公元前 3 世纪的《列子》，其中记载了周穆王（公元前 1023-957 年）与一位名叫偃师（Yan Shi）的机械工程师（"artificer"）更早的相遇。

构建

在yanshi/目录下执行：

调试构建：make
发布构建：make build=release

从 Makefile 可以看到两种构建的差异：

Debug 构建使用-g3 -std=c++1y -fsanitize=undefined,address -DDEBUG，链接-lasan -lubsan，产物在build/目录；
Release 构建使用-Os优化，产物在release/目录；
两者均链接 ICU（-licuuc，处理 Unicode 区间与字符）与 readline（-lreadline，交互式补全）；
lexer/parser 由 flex 与 bison 生成（src/lexer.l->src/lexer.cc，src/parser.y->src/parser.cc），源码树中只保留.l/.y原始文件，需要先安装 flex 与 bison 才能构建。

另外make unittest会编译并运行unittest/目录下的单元测试，例如 determinize_test.cc（NFA 确定化）、union_test.cc、intersection_test.cc、difference_test.cc、minimize_test.cc等，均通过unittest/目录下的测试辅助代码读取 NFA、执行相应自动机运算并校验状态数。

快速上手：生成并运行一个独立 C++ 程序

编写源文件

创建一个文件a.ys：

export foo = 'hello'

生成 C++ 代码

运行：

yanshi -S a.ys -o /tmp/a.cc

-S（--standalone）选项会生成一个独立可编译运行的 C++ 文件（包含头文件与main()）。生成的代码为foo提供三个核心函数：

yanshi_foo_start：起始状态为 0（状态用自然数表示）；
yanshi_foo_is_final：忽略ret_stack后，检查状态u是否是终结状态；
yanshi_foo_transit：忽略ret_stack后，u是当前状态，c是下一个输入码点（codepoint）或标签（label）。

编译并运行

% make -C /tmp a make: Entering directory '/tmp' g++ a.cc -o a make: Leaving directory '/tmp' % /tmp/a hello 0 h 1 e 2 l 3 l 4 o 5 len: 5 pref: 5 state: 5 final: true % /tmp/a hello<press C-d>0 h 1 e 2 l 3 l 4 o 5 len: 5 pref: 5 state: 5 final: true

输出解读：状态用黄色打印并与转移标签交错，终结状态为粗体黄色。四行输出分别表示：

len：输入码点或标签的长度；
pref：不进入死状态的最长前缀长度；
state：消费输入后进入的状态；
final：该状态是否为终结状态。

当不提供命令行参数时，程序从标准输入读取（示例中hello<press C-d>表示输入hello后按 Ctrl-D 结束输入）。

交互式模式

-i（--interactive）选项启用交互模式，适合快速试错与检查自动机内部结构：

% yanshi -i a.ys Testing foo foo :: DefineStmt .integer mode Commands available from the prompt: .automaton dump automaton .assoc dump associated AST Expr for each state .help display this help .integer input is a list of non-negative integers, macros(#define) or '' quoted strings .macro display defined macros .string input is a string .stmt <ident> change target DefineStmt to <ident> .quit exit interactive mode λ 104 101 108 108 111 0 104 1 101 2 108 3 108 4 111 5 export foo = 'hello': λ .string .string mode λ hello 0 h 1 e 2 l 3 l 4 o 5 export foo = 'hello': λ

交互模式的实现位于 repl.cc，其命令表与 README 完全对应。从源码看，交互模式下支持两种输入模式：

.string：输入按字符串处理；
.integer：输入是一系列非负整数（即码点），也可以使用#define宏或''引号字符串。

交互模式还通过 readline 提供命令补全（command_completer）、宏补全（macro_completer）与语句补全（stmt_completer），.stmt <ident>命令在源码中通过resolve()解析标识符并切换到对应的DefineStmt后，将anno指针更新为对应自动机，后续输入均针对该自动机执行。

yanshi 语言：正则式风格语法与运算符

括号表达式与重复

export hello = [gh] 'e' l{2} 'o' l = 'l'

[gh]是括号表达式（bracket expression），匹配一个字符；
l{2}表示匹配l至少两次。

该文法匹配hello、gello、helllo，等等。

组合运算符

运算符	含义	示例
`\\|`	并（Union）	`c = a \\| b`
`&&`	交（Intersection）	`c = a && b`
`-`	差（Difference）	`c = a - b`
空格	连接（Concatenation）	`c = a b`
`~`	补（Complement）	`c = ~ a`

这些运算符对应源码 syntax.hh 中的UnionExpr、IntersectExpr、DifferenceExpr、ConcatExpr、ComplementExpr等 AST 节点，而 fsa.hh 提供了对应的自动机运算：intersect、difference、determinize（用于将 NFA 确定化为 DFA）、distinguish（DFA 最小化）、accessible/co_accessible（可达/共可达状态裁剪）等。单元测试 union_test.cc、intersection_test.cc、difference_test.cc、determinize_test.cc 分别对上述运算进行了验证。

动作（内嵌 C++ 代码）

c++ { #include <stdio.h> } export hello = '喵' @ { puts("meow"); } {2}

c++ { ... }把 C/C++ 代码原样嵌入到生成的 C++ 文件中（对应源码中的CppStmt）；
@ { ... }在某个识别节点执行内联动作（对应InlineAction）。

注意：README 明确说明动作的执行点（executing point）可能反直觉，其实现尚未完全想清楚，使用时建议先做实验验证执行时机。

模块与导入

# a.ys import 'b.ys' as B # B::bar import 'b.ys' # qux export foo = B::bar | qux bar = '4' # b.ys bar = '3' qux = '5'

import 'b.ys' as B：带限定名的导入，引用其中的定义需写作B::bar；
import 'b.ys'：不带限定名的导入，其中的定义（如qux）可以直接使用；
导入搜索路径可通过-I, --import <dir>命令行选项添加（见 main.cc 中opt_include_paths）。

模块相关数据结构定义在 loader.hh 的Module结构中：defined保存本模块定义，unqualified_import/qualified_import分别保存无限定名与带限定名的导入模块，macro保存#define宏。

子串文法

--substring-grammar选项生成子串文法的代码，即生成的代码匹配该文法的每一个子串。实现方式是：创建一个新的起始状态和新的终结状态，把新起始状态连到旧起始状态，把旧终结状态连到新终结状态。README 同时提到，子串文法的实现需要查找"内部状态"（既非起始也非终结的状态），这依赖assoc信息（见下文 Internals 一节）。

三种非终结符引用机制

yanshi 提供三种引用非终结符的方式，是理解其表达能力（从正则语言逼近上下文无关文法）的核心。

`EmbedExpr`：直接引用

foo = bar bar = [0-9]

不带任何修饰符引用非终结符时，bar的完整自动机会在每一个引用点被复制。如果被引用的自动机很大，EmbedExpr会显著增加状态数。EmbedExpr在状态间建立依赖关系，不允许循环依赖。

`CollapseExpr`：`!`修饰符

export foo = 'pre' !bar 'post' bar = [\u0300-\u034E] quz = 'meow' !bar 'meow'

'pre'的终结状态与'post'的起始状态之间会用一条特殊有向弧连接；
导出时，从该弧的尾部到bar的起始状态增加一条 epsilon 转移，从bar的各个终结状态到该弧的头部各增加一条 epsilon 转移。

CollapseExpr的行为像函数调用，但不保存返回地址（因此命名为 collapse），状态在穿过bar后可能走到其他调用点。上例中，穿过bar后状态可能走向foo或quz，从而产生误报。

`CallExpr`：`&`修饰符

export foo = 'pre' &bar 'post' bar = '4'

这是CollapseExpr的改良。假设状态&B位于A的定义中（即A调用B），&B会被表示成一条伪弧u -> v，其中u是&B之前的状态，v是&B之后的状态：

如果u的弧与B的弧不发生冲突，那么当当前状态集合包含u且没有其他转移时，转移函数会把v压入返回栈；
注意B与A是断开的，这与CollapseExpr不同。机器会在自动机B上贪心转移；
如果没有转移，则弹出返回地址（此处即v）并跳转到它。

从 syntax.hh 可以看到三种引用分别对应EmbedExpr、CollapseExpr、CallExpr三个 AST 节点，它们都记录qualified（限定名）与ident（标识符），并由编译器在解析引用后回填define_stmt指针。返回栈的长度由命令行选项--max-return-stack控制（默认 100，见 main.cc）。

在交互模式与独立代码生成之外，-G, --graph <dir>选项还可以输出 Graphviz dot 文件（对应 option.hh 中的Mode::graphviz），方便可视化查看自动机拓扑。

完整的命令行选项

根据 main.cc 的print_help与参数解析逻辑，yanshi 支持以下选项：

短选项	长选项	含义
`-b`	`--bytes`	标签取值范围为`[0,256)`，Unicode 字面量按 UTF-8 字节处理（同时将字母表大小`AB`设为 256）
`-C`	生成 C 源码（默认生成 C++）
`-c`	`--check`	只检查语法与 use/def
`-d`	`--debug`	调试级别
`-l`	`--debug-output`	调试输出文件名（默认 stderr）
`--dump-action`	输出每条边关联的动作
`--dump-assoc`	输出每个状态关联的 AST Expr
`--dump-automaton`	输出自动机
`--dump-embed`	输出 EmbedExpr 统计信息
`--dump-module`	输出模块的 use/def 等
`--dump-tree`	输出 AST
`--extern-c`	生成`extern "C"`说明符
`-G`	`--graph <dir>`	输出 Graphviz dot 文件
`-I`	`--import <dir>`	添加`import`搜索路径
`-i`	`--interactive`	交互模式
`--max-return-stack`	C 生成器中返回栈最大长度（默认 100）
`-k`	`--keep-inaccessible`	不做 accessible/co-accessible 裁剪
`-S`	`--standalone`	生成头文件与`main()`
`-s`	`--substring-grammar`	构造子串文法的正则近似；标有`intact`的非终结符内部状态不连接到 start/final
`-o`	`--output <file>`	`.cc`输出文件名
`-O`	`--output-header <file>`	`.hh`输出文件名
`-h`	`--help`	显示帮助并退出

编辑器与 Shell 集成

Vim

yanshi/contrib/vim/提供语法高亮与语法检查插件（面向 Syntastic），安装方式（符号链接到~/.vim对应子目录）：

ln -sr contrib/vim/compiler/yanshi.vim ~/.vim/compiler/ ln -sr contrib/vim/ftdetect/yanshi.vim ~/.vim/ftdetect/ ln -sr contrib/vim/ftplugin/yanshi.vim ~/.vim/ftplugin/ ln -sr contrib/vim/syntax/yanshi.vim ~/.vim/syntax/ ln -sr contrib/vim/syntax_checker/yanshi ~/.vim/syntax_checker/

Zsh

yanshi/contrib/zsh/_yanshi提供命令行补全，安装方式：

# ~/.zshrc fpath=(~/.zsh $fpath) # ln -sr contrib/zsh/_yanshi ~/.zsh/

注意：syntax_checker目录在 README 中写作syntax_checkers，实际源码树中的目录名为yanshi/contrib/vim/syntax_checkers/yanshi/，安装时应以实际目录名为准。

内部实现（Internals）

源码结构

src common.{cc,hh} main.{cc,hh} syntax.{cc,hh} loader.{cc,hh} fsa.{cc,hh} fsa_anno.{cc,hh} compiler.{cc,hh} parser.y lexer.l location.cc

编译流水线

lexer.l：词法分析；
parser.y：语法分析并生成语法树；
loader.cc依次完成：
1. 获取定义列表；
2. 为每个import递归加载模块；
3. 解析引用并把使用关联到定义（used_as_call/used_as_collapse/used_as_embed三类引用分别记录，见 loader.hh）；
4. 从EmbedExpr构建依赖图；
5. 按拓扑序为每个非终结符编译自动机，其中CollapseExpr与CallExpr用特殊有向弧表示；
6. 为export的非终结符生成代码，解析CollapseExpr与CallExpr。

有限状态自动机的构建

语法树的每个节点都对应一个自动机。父节点根据子节点的语义由子节点构造自己的自动机——父节点的自动机可能包含某个子节点的自动机中的状态，也可能是父节点自己引入的新状态。

assoc[i]记录了自动机树中的关联节点（语法树中哪些部分与该状态有关联）以及状态i的位置（起始状态、终结状态或内部状态），其用途有三：

检查应该触发哪个动作；
在子串文法的实现中查找内部状态（既非起始也非终结）；
检查该状态是否关联到CallExpr或CollapseExpr。

该结构对应 fsa_anno.hh 中的FsaAnno（由compile()填充到 compiler.hh 的compiled映射中），--dump-assoc与交互模式的.assoc命令都会输出它。

循环引用与近似 CFG 的动机回顾

回到 README 开头的问题：简化 SQL 文法超过 10000 个状态。引入CollapseExpr后允许循环引用，不再需要把被引用的自动机整体展开复制（这是EmbedExpr的做法）；CallExpr进一步通过返回地址栈消除误报。这三者的递进关系（Embed -> Collapse -> Call）正是 yanshi"以正则自动机近似上下文无关文法"这一设计路线的核心。

总结

yanshi 是一个"类 Ragel、但可后处理自动机"的 FSA 生成器，通过@{}内联 C++ 动作、--substring-grammar子串文法近似、CollapseExpr/CallExpr递归近似来逼近 CFG 的表达能力；
三种非终结符引用中，EmbedExpr直接复制自动机（允许重复引用、不允许循环），CollapseExpr用 epsilon 弧连接调用点但不保存返回地址（可能误报），CallExpr用返回地址栈模拟真实函数调用（误报最少）；
调试与试错可以通过-i交互模式、-GGraphviz 输出以及--dump-*系列选项完成，单元测试位于yanshi/unittest/，实现细节可继续阅读 yanshi/src/ 下的源码。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

偃师 yanshi：一个可内嵌 C++ 动作、支持近似上下文无关文法的有限状态自动机生成器