偃师——finite automaton生成工具

11th Jun 2016
15 min read
Tags:
automaton,
parser generator,
regular expression,
yanshi

偃师

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

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

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

偃师

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

示例

编辑a.ys：

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：

action night {
  puts("night");
}

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

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

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

输出：

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提供词法元素的位置，并更新文件偏移。

#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文件中可以用semicolon或nosemicolon指定用分号或换行符标记Stmt结束。

semicolon;
c++ {
};
foo = !meow;

nosemicolon
meow = !foo

{%
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++代码。词法分析时要能判断是否在代码块内部，若是，那么大部分顶层规则失效，遇到配对的}则退出代码模式。

c++ {
  // arbitrary C++ code
  "\a{";
  {if(0){foo();}}
  'a';
}

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

%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的节点中。

%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-B、UnionExpr表示并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。

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));
  }
};

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_dev和st_ino是否之前出现过。

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

循环依赖的检测

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

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

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

比如如下.ys文件

earth = venus
venus = mars arch
mars = earth

arch = felix
felix = cat
cat = arch

会生成如下错误：

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状态。

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：

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简化中识别CallExpr或CollapseExpr

`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，结束遍历时队列中所有插入过的顶点即为结果。一个小技巧是结束后擦除顶点的访问标记，可以避免完整初始化访问标记。

  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，添加新边：

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

src成为新的start，A、B顶点的final标记保留。这样得到的是standardized automaton。

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

差

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

如果左侧含有CallExpr或CollapseExpr，结果可能不正确。

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

Kleene star

引入两个新顶点src和sink，添加新边：

(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

引入两个新顶点src和sink，建立新边：

(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提出一个方法，对于

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

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

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

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

A、B两个产生式对应的automata构造好之后，在A的automaton上添加新边：

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

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

void A()
{
  B();
  B();
}

void C()
{
  B();
}

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

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

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

TODO 考虑

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。

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文件语法

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

import 'a.ys'

action定义

定义一个带名字的action：

action foo {
  puts("foo");
}

之后可以用> foo等引用：

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

C++定义

Contrib

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

代码还比较乱……

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

~~听说这个东西有望开源？~~开源了，https://github.com/MaskRay/yanshi。