偃师——finite automaton生成工具

我一只上海的喵怎么到北京来了呢?……“苟利长亭生死以,岂因祸福避趋之”那么所以我就到了北京。到了北京我干了这二十几天我也没有什么别的,大概三件事:

一个,开发了一个安全产品(秘); 第二个,做了一个自动机生成工具; 第三个,就是见了一些同学,从学长那里听到了一点人生的经验。

如果说还有一点什么成绩就是收了Code Jam、百度之星、2016 Topcoder Open Regional Beijing三件T恤,但这些都是次要的。

偃师

这个自动机生成工具叫做偃师,名字取自《列子·汤问》中记载的一位工匠,善于制造能歌善舞的人偶。

示例

编辑a.ys

1
2
3
4
5
6
7
8
9
10
11
import 'c.ys' as C

export main = goodnight C::world

action good {
puts("good");
}

goodnight = good night
good = [Gg] 'o'{2} 'd' @ good
night = ("ni" [Gg] "ht" - 'niGht') @ C::night

c.ys

1
2
3
4
5
action night {
puts("night");
}

world = ('\u0076' .. '\u0077' & '\u0077' .. '\u0078') 'orld' > {puts("world");}

根据该文法生成表示main的DFA,{}里的是action。

1
2
3
make
build/yanshi -S /tmp/a.ys -o /tmp/a.cc && make -C /tmp/a
/tmp/a 'Goodnightworld'

输出:

1
2
3
4
5
6
good
night
world
len: 14
state: 14
final: true

流程

  • lexer.l,parser.y。解析命令行指定的.ys文件,构建abstract syntax tree
  • loader.cc。每个文件视为一个模块,
    • 记录nonterminal定义
    • 若有import "filename.ys"则递归载入
    • 把每个nonterminal定义中引用的标识符(可以用模块名限定)与其定义关联。每个nonterminal代表一个顶点,依赖关系为边,建图。
    • 对依赖图用post-order DFS进行拓扑排序。若有循环依赖则报错。
    • 按拓扑序编译各nonterminal,每个nonterminal编译成一个automaton,若A依赖B,则B先编译。
    • 对于每个标记为export的nonterminal,为其生成C++代码。

词法分析

使用flex进行词法分析。下面描述用到的技巧。

词法元素添加位置信息

使用%option bison-bridge生成与bison协作的代码,lexer.l中可以访问yylval并设置其各个域,以向bison返回词法元素信息。

%option extra-type="long"记录一个额外信息,表示文件偏移。使用%option bison-locations以访问yylloc,定义#define YY_USER_ACTION即可给bison提供词法元素的位置,并更新文件偏移。

1
2
3
4
5
6
#define YY_USER_ACTION                      \
do { \
yylloc->start = yyget_extra(yyscanner); \
yylloc->end = yylloc->start + yyleng; \
yyset_extra(yylloc->end, yyscanner); \
} while (0);

Off-side rule

.ys文件中可以用semicolonnosemicolon指定用分号或换行符标记Stmt结束。

1
2
3
4
5
6
7
semicolon;
c++ {
};
foo = !meow;

nosemicolon
meow = !foo
1
2
3
4
5
6
7
8
{%
static bool semicolon;
%}

"semicolon" semicolon = true;
"nosemicolon" semicolon = false;
";" if (semicolon) return '\n';
"\n" if (YY_START == INITIAL && ! semicolon) return '\n';

偃师当前没有用到缩进。若要支持缩进文法,注意到各行缩进数形成了树,可以用栈维护当前行所有祖先顶点的缩进数,用flex规则记录换行符前空格数。

Start conditions切换词法分析模式

就像lex、yacc,偃师.ys文件中c++ {}大括号内可以引入任意C++代码。词法分析时要能判断是否在代码块内部,若是,那么大部分顶层规则失效,遇到配对的}则退出代码模式。

1
2
3
4
5
6
c++ {
// arbitrary C++ code
"\a{";
{if(0){foo();}}
'a';
}

解决方案是使用flex的start conditions,{"'(等均会改变start condition,改变对字符的处理方式。为了正确处理这些特殊字符的嵌套,需要把之前的状态保存在栈中。flex提供了%option stack以使用yy_push_stateyy_pop_state,不过需要注意的是实际生效的状态是当前start condition YY_START而不是yy_top_state()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
%x EXPECT_CODE
%x IN_CODE
%s IN_PAREN
%x IN_Q_STRING
%x IN_QQ_STRING

<EXPECT_CODE>{
"{" BEGIN IN_CODE; tmp_bracket.clear();
/* ...... */
}

<IN_CODE>{
"'" { tmp_bracket += '\''; yy_push_state(IN_Q_STRING, yyscanner); }
"\"" { tmp_bracket += '"'; yy_push_state(IN_QQ_STRING, yyscanner); }
"{" { tmp_bracket += '{'; yy_push_state(IN_CODE, yyscanner); }
"}" {
yy_pop_state(yyscanner);
if (YY_START == INITIAL || YY_START == IN_PAREN) {
yylval->str = new string(tmp_bracket);
return BRACED_CODE;
} else
tmp_bracket += '}';
}
.|"\n" tmp_bracket += yytext[0];
<<EOF>> yy_pop_state(yyscanner); unexpected_eof(yylval, "}");
}

' tmp_str.clear(); yy_push_state(IN_Q_STRING, yyscanner);
"\"" tmp_str.clear(); yy_push_state(IN_QQ_STRING, yyscanner);
<IN_Q_STRING>{
' {
yy_pop_state(yyscanner);
if (YY_START == INITIAL || YY_START == IN_PAREN) {
yylval->str = new string(tmp_str);
return STRING_LITERAL;
}
tmp_bracket += yytext;
}
<<EOF>> yy_pop_state(yyscanner); unexpected_eof(yylval, "'");
}
<IN_QQ_STRING>{
"\"" {
yy_pop_state(yyscanner);
if (YY_START == INITIAL || YY_START == IN_PAREN) {
yylval->str = new string(tmp_str);
return STRING_LITERAL;
}
tmp_bracket += yytext;
}
<<EOF>> yy_pop_state(yyscanner); unexpected_eof(yylval, "\"");
}

<IN_Q_STRING,IN_QQ_STRING>{
\\[0-7]{1,3} /* ...... */
\\x[0-9a-fA-F]+ /* ...... */
.|\n tmp_str += yytext[0]; tmp_bracket += yytext[0];
/* ...... */
}

语法分析

位置信息

定义#define YYLTYPE Location指定用struct Location { long start, end; };表示位置信息。定义#define YYLLOC_DEFAULT(Loc, Rhs, N),在规则匹配成功后设定yyloc,把该信息复制到abstract syntax tree的节点中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
%code requires {
/* struct Location { long start, end; ...... }; */
#define YYLTYPE Location
#define YYLLOC_DEFAULT(Loc, Rhs, N) \
do { \
if (N) { \
(Loc).start = YYRHSLOC(Rhs, 1).start; \
(Loc).end = YYRHSLOC(Rhs, N).end; \
} else { \
(Loc).start = YYRHSLOC(Rhs, 0).end; \
(Loc).end = YYRHSLOC(Rhs, 0).end; \
} \
} while (0)
}

%locations

%%

stmt:
define_stmt { $$ = $1; }
| IMPORT STRING_LITERAL AS IDENT { $$ = new ImportStmt(*$2, *$4); delete $2; delete $4; $$->loc = yyloc; }
| IMPORT STRING_LITERAL { string t; $$ = new ImportStmt(*$2, t); delete $2; $$->loc = yyloc; }
| ACTION IDENT BRACED_CODE { $$ = new ActionStmt(*$2, *$3); delete $2; delete $3; $$->loc = yyloc; }
| CPP BRACED_CODE { $$ = new CppStmt(*$2); delete $2; $$->loc = yyloc; }

Abstract syntax tree表示

分成三类:Stmt、Expr、Action。

为构成Expr的每种语法都创建一个Expr子类,如BracketExpr表示[0-9a-z]DifferenceExpr表示差A-BUnionExpr表示并A|B等。

分析模块定义的nonterminal、关联标识符引用与定义、根据nonterminal定义生成automaton均需遍历AST,每一种遍历方式对不同Expr子类的处理方式不同,可以应用double dispatch的visitor pattern。

以Action为例。

Action继承自VisitableBase,声明virtual void accept(Visitor<T>& visitor) = 0;,各子类实现accept:调用visitor中以子类具体类型为参数的重载方法。

实现了Expr遍历的visitor继承自Visitor<Expr>,递归访问子树时应调用visit(Expr&),以便在pre-order和post-order时执行各个hooks。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T>
struct Visitor;

template<class T>
struct VisitableBase {
virtual void accept(Visitor<T>& visitor) = 0;
};

template<class Base, class Derived>
struct Visitable : Base {
void accept(Visitor<Base>& visitor) override {
visitor.visit(static_cast<Derived&>(*this));
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct Action;
struct InlineAction;
struct RefAction;
template<>
struct Visitor<Action> {
virtual void visit(Action& action) = 0;
virtual void visit(InlineAction&) = 0;
virtual void visit(RefAction&) = 0;
};

struct Action : VisitableBase<Action> {
Location loc;
virtual ~Action() = default;
};

struct InlineAction : Visitable<Action, InlineAction> {
string code;
InlineAction(string& code) : code(move(code)) {}
};

struct Module;
struct RefAction : Visitable<Action, RefAction> {
string qualified, ident;
Module* define_module; // set by ModuleUse
RefAction(string& qualified, string& ident) : qualified(move(qualified)), ident(move(ident)) {}
};

struct PrePostStmtVisitor : Visitor<Stmt> {
void visit(Stmt& stmt) override {
// pre-order
stmt.accept(*this);
// post-order
}
void visit(ActionStmt& stmt) override {}
void visit(CppStmt& stmt) override {}
void visit(DefineStmt& stmt) override {}
void visit(EmptyStmt& stmt) override {}
void visit(ImportStmt& stmt) override {}
};

import "filename.ys"的处理与多文件支持

ImportStmt import "filename.ys"可以导入其他文件定义的nonterminal,或者用import "filename.ys" as B带限定地导入。

解析完一个文件后,访问各个Stmt,若有nonterminal定义(DefineStmt)则记录下来;若有ImportStmt则递归载入其他文件。为了支持循环导入,一个文件只会被导入一次,打开文件后,判断fstat(2)获取的st_devst_ino是否之前出现过。

记录完所有模块的定义后再把产生式右边的标识符引用和定义关联。

循环依赖的检测

对依赖图用post-order DFS进行拓扑排序。每个顶点可能处于四种状态之一:

  1. 未访问
  2. 遍历中,当前顶点是它的后裔,所有状态1顶点在栈中
  3. 所有后裔均已访问过,不在环中
  4. 所有后裔均已访问过,在环中

枚举各个顶点,若状态为0则DFS,若遇到状态为1的顶点则找到了一个环,从而输出循环依赖错误。

比如如下.ys文件

1
2
3
4
5
6
7
earth = venus
venus = mars arch
mars = earth

arch = felix
felix = cat
cat = arch
会生成如下错误:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
b.ys 2:1-17 'venus': circular embedding
venus = mars arch
b.ys 1:1-13 required by earth
earth = venus
b.ys 3:1-12 required by mars
mars = earth
b.ys 2:1-17 required by venus
venus = mars arch

b.ys 7:1-10 'cat': circular embedding
cat = arch
b.ys 6:1-11 required by felix
felix = cat
b.ys 5:1-12 required by arch
arch = felix
b.ys 2:1-17 required by venus
venus = mars arch
b.ys 7:1-10 required by cat
cat = arch

Finite state automaton

src/fsa.{cc,hh}定义了finite state automaton的表示方式以及一些基本操作。用自然数表示状态,邻接表存储边,一条边表示为pair<pair<long, long>, long>即(标号区间,目标顶点),\(\epsilon\)转移表示为标号区间\([-1,0)\)。有序表存储final状态。

1
2
3
4
5
6
7
8
9
typedef pair<long, long> Label;
typedef pair<Label, long> Edge;

struct Fsa {
long start;
vector<long> finals; // sorted
vector<vector<Edge>> adj; // sorted
/* ...... */
};

src/fsa_anno.{cc,hh}定义了FsaAnno

1
2
3
4
5
6
struct FsaAnno {
bool deterministic;
Fsa fsa;
vector<vector<pair<Expr*, ExprTag>>> assoc;
/* ...... */
};

deterministic标注是否为DFA。编译时,AST的每个节点都会对应一个automaton,AST对应了一棵automaton tree。Automaton tree中内部节点automaton的顶点有两种来源:来自某个孩子automaton、新引入的。assoc[i]记录了根automaton的顶点\(i\)之前从属的所有automata以及所处的位置(start、final、inner)。

assoc信息有三个作用:

  • 判断哪些边会触发Action
  • 在substring grammar中判断一个顶点是否为内部顶点
  • 在recursive automaton简化中识别CallExprCollapseExpr

DotExpr: .

两个顶点,start为0,final为1,边\((0, (0, AB), 1)\)代表任意codepoint都会从0转移至1。

assoc[0]包含一个元素{DotExpr*, ExprTag::start},表示DotExpr对应的automaton包含顶点0且0是start。 assoc[1]包含一个元素{DotExpr*, ExprTag::final},表示DotExpr对应的automaton包含顶点1且1是final。

LiteralExpr: 'literal'

单双引号的字串在AST中表示为LiteralExpr。对于长为\(l\)的字串,创建\(l+1\)个顶点。 assoc[0]包含一个元素{LiteralExpr*, ExprTag::start},表示LiteralExpr对应的automaton包含顶点0且0是start。 assoc[l]包含一个元素{LiteralExpr*, ExprTag::final},表示LiteralExpr对应的automaton包含顶点\(l\)\(l\)是start。 其他assoc[i]包含一个元素{LiteralExpr*, ExprTag::inner},表示LiteralExpr对应的automaton包含顶点\(i\)\(l\)为内部顶点,ExprTag::inner在substring grammar中用到,可以避免连边时指向它。

\(\epsilon\)-closure

输入NFA顶点集,输出其\(\epsilon\)-closure,以有序NFA顶点集表示。

使用breadth-first search,结束遍历时队列中所有插入过的顶点即为结果。一个小技巧是结束后擦除顶点的访问标记,可以避免完整初始化访问标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (long i: src)
vis[i] = true;
REP(i, src.size()) {
long u = src[i];
for (auto& e: adj[u]) {
if (-1 < e.first) break;
if (! vis[e.second]) {
vis[e.second] = true;
src.push_back(e.second);
}
}
}
for (long i: src)
vis[i] = false;

运算

Thompson's construction algorithm描述了几种运算的构造方法,它产生的是normalized automaton,start和final均只有一个,且不存在指向start或从final出发的边。并、Kleene star等运算均引入两个顶点。这样做的好处是每个顶点入度、出度不超过2,各运算时间复杂度为常数。

为了减少顶点数,我尽量让结果为standardized automaton:有多个final,不存在指向start的边。

构造两个automata的product automaton,求NFA的product automaton会有大量\(\epsilon\)-closure计算操作,因此先把NFA转成DFA再进行交运算。

修改assoc以标识每个顶点都在IntersectExpr标识的automaton中。

引入新顶点src,添加新边:

1
2
(src, -1, A.start)
(src, -1, B.start)

src成为新的startAB顶点的final标记保留。这样得到的是standardized automaton。

修改assoc以标识每个顶点都在UnionExpr标识的automaton中。

与交类似,先转成DFA再运算。

如果左侧含有CallExprCollapseExpr,结果可能不正确。

修改assoc以标识每个顶点都在DifferenceExpr标识的automaton中。

Kleene star

引入两个新顶点srcsink,添加新边:

1
2
3
4
5
(src, -1, sink)
(src, -1, start)
for each final
(final, -1, sink)
(final, -1, start)

src成为新的start,sink成为唯一的final。这样得到的是normalized automaton。若不存在从final出发的边可以省掉sink,若不存在指向start的边可以省掉src

修改assoc以标识每个顶点都在StarExpr标识的automaton中。

Kleene plus

各final向start连\(\epsilon\)边。

修改assoc以标识每个顶点都在PlusExpr标识的automaton中。

Question

引入两个新顶点srcsink,建立新边:

1
2
(src, -1, sink)
(src, -1, start)

src成为新的start,给sink设置final标记。

修改assoc以标识每个顶点都在QuestionExpr标识的automaton中。

编译

类似于reverse Polish calculator,每个Expr会编译成一个automaton。

每个automaton都要转成一个最小化的DFA,有三个步骤:

  • Subset construction转成DFA
  • Hopcroft minimization合并Nerode equivalent states
  • 去除co-inaccessible states即无法达到final的状态

实践中发现最小化每个部件比只最小化最终automaton要快很多。

含递归的产生式和简化的recursive automaton

产生式中可能含有递归,比如直接递归A = A b或间接的A = B b; B = A a,如何用automaton描述呢?

之前fqj1994提出一个方法,对于

1
2
A = a B a | c
B = b A b | d

把产生式中递归引用的nonterminal用一个字符集外的terminal表示:

1
2
A = a "B" a | c
B = b "A" b | d

这里假设"B"为字符集外的terminal,表示为含两个顶点start和final的automaton,start向final连标号为"B"的边。"A"同理。

AB两个产生式对应的automata构造好之后,在A的automaton上添加新边:

1
2
("B".start, -1, B.start)  # 对B产生式的调用
(B.final, -1, "B".final) # B匹配完后返回到B被调用的地方

"B"在多个产生式中出现或者一个产生式中出现多次时,就可能发生调用处和返回处不匹配,比如下面的C程序:

1
2
3
4
5
6
7
8
9
10
void A()
{
B();
B();
}

void C()
{
B();
}

执行A函数中第一个B(),返回时应该到第一个B()调用的下一条指令处。但是按照前文描述的连边规则,返回地址可能是三个B()中任意一个的下一条指令。

偃师支持两种调用,EmbedExpr A = BCollapseExprA = !BEmbedExprB的automaton嵌入到A的automaton中,会产生依赖关系以防止A被嵌入到B中。CollapseExpr允许递归,按照前文的连边规则构造automaton。

对于原始文法,找出循环依赖形成的强联通分量,用CollapseExpr把环破开即得到了一种regular approximation。

TODO 考虑

1
S = !A !A

这种方式引入的顶点数很少。

我另外查阅了其他方案,比如Regular Approximation of CFLs: A Grammatical View,\(k\)个顶点、\(l\)条边的强联通分量会变成\(4kl\)条边,不可接受。

Substring grammar

我们的另一个需求是匹配SQL子串,即SQL的substring grammar。取suffix grammar的prefix grammar即得到substring grammar,根据对称性,知道如何求suffix grammar后即可求prefix grammar。Suffix grammar构造方法大致是这样:根据每个nonterminal \(A\)生成相应的\(A'\)\(A'\)的产生式为A的产生式去除proper prefix。

1
2
S = A B C
S' = A' B C | B' C | C'

不过很多suffix grammar都有歧义,无法用LR(1),得诉诸Cocke-Younger-Kasami、Backtracking LR、Generalized LR、Earley parser等通用的parser。CYK、GLR Tomita、Binary Right Nulled GLR、Earley等都是\(O(n^3)\)的,\(n\)为输入长度,在我们的应用场景下不可接受。

另一方面,根据regular grammar求substring grammar很容易,构造原始文法的finite automaton,对每个顶点添加start和final标记即可。

Action

给状态转移添加action。具体地,每个顶点有四类hook:

每个顶点所属于若干互相嵌套的Expr,由assoc记录。每个Expr可以有四类hook:entering、finishing、leaving、transiting。从顶点\(u\)转移到顶点\(v\)时,若对于某个Expr \(e\)

  • \(u\notin e, v\in e\),触发\(e\)的entering hook
  • \(u\in e, v\notin e\),触发\(e\)的leaving hook
  • \(u\in e, v\in finals(e)\),即\(v\)\(e\)表示的automaton中是final顶点,触发\(e\)的finishing hook
  • \(u\in e, v\in e\),触发\(e\)的transiting hook

这部分代码在src/fsa_anno.{cc,hh}实现。

.ys文件语法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
toplevel:
stmt_list

stmt_list:
%empty
| '\n' stmt_list
| stmt '\n' stmt_list

stmt:
define_stmt
| 'import' STRING_LITERAL 'as' IDENT
| 'import' STRING_LITERAL
| 'action' IDENT BRACED_CODE
| 'c++' BRACED_CODE

define_stmt:
IDENT '=' union_expr
| IDENT ':' union_expr
| IDENT ':' '|' union_expr
| 'export' define_stmt
| 'intact' define_stmt

union_expr:
intersect_expr
| union_expr '|' intersect_expr

intersect_expr:
difference_expr
| intersect_expr '&' difference_expr

difference_expr:
concat_expr
| difference_expr '-' concat_expr

concat_expr:
unop_expr
| concat_expr unop_expr

unop_expr:
factor
| '~' unop_expr

factor:
'epsilon'
| IDENT
| IDENT '::' IDENT
| '!' IDENT
| '!' IDENT '::' IDENT
| STRING_LITERAL
| '.'
| bracket
| STRING_LITERAL '..' STRING_LITERAL
| '(' union_expr ')'
| repeat
| factor '>' action
| factor '@' action
| factor '%' action
| factor '$' action
| factor '+'
| factor '?'
| factor '*'

repeat:
factor '{' INTEGER ',' INTEGER '}'
| factor '{' INTEGER ',' '}'
| factor '{' INTEGER '}'
| factor '{' ',' INTEGER '}'

action:
IDENT
| IDENT '::' IDENT
| BRACED_CODE

bracket:
'[' bracket_items ']'
| '[' '^' bracket_items ']'

bracket_items:
bracket_items CHAR '-' CHAR
| bracket_items CHAR
| %empty

顶层

源文件每行是一个定义、import、action定义、或C++代码块。

import

1
import 'a.ys'

action定义

定义一个带名字的action:

1
2
3
action foo {
puts("foo");
}

之后可以用> foo等引用:

1
bar = 'a' > foo @ foo $ foo % foo > {puts("unnamed");}

C++定义

Contrib

contrib/下有Vim插件和Zsh配置文件。

代码还比较乱……

此处似乎得有广告,长亭科技https://chaitin.cn

听说这个东西有望开源?

开源了,https://github.com/MaskRay/yanshi