本文介紹伴魚內部服務報警平臺中匹配器模塊的演進，及其利用 Lex 和 Yacc 同類工具構建 DSL 編譯器的過程。

背景

報警平臺是伴魚內部各端、應用、基礎設施等 服務異常狀態信息的集散中心 。整體流程如下圖所示：

信息源將信息投遞給報警平臺，後者將這些信息最終通過郵件、即時消息、電話呼叫的形式 路由 給理應關心它的人。總體而言，路由的需求可以分爲以下幾種：

• 路由給服務的負責人及其團隊
• 路由給服務依賴方人員及其團隊
• 路由給所有值班人員所在的即時消息羣

爲了滿足這樣的需求，報警平臺採用樹狀結構組織路由信息，如下圖所示：

每個節點是一個路由節點，節點上可以掛載不同的規則，如抑制規則、通知規則；也可以存放不同的配置信息，如觸發報警的閾值，以及相關負責人及其團隊的聯繫方式。

根路由是所有異常信息的必經之路，經過這裏的信息會路由給所有值班人員；一級子路由節點是所有的服務，經過這裏的信息會路由給該服務的負責人及其團隊；如果有其它團隊想要訂閱某服務的異常消息，如 Service A 團隊想要了解 Service B 的崩潰 (panic) 信息，則可以在 Service B 節點下創建子路由 Service B Panic ，並在上面配置 Service A 團隊的聯繫方式，從而達到訂閱目的。

那麼如何判斷一條報警信息將經過哪些路由節點，一條規則是否起作用？這就需要引入本文的主角： 匹配器 (matcher) ，每個路由、每條規則上都會掛載一個匹配器，當它成功匹配到報警信息時，路由和規則就會生效。一條典型的報警信息會有許多信息，我們不妨將它看作是任意數量的鍵值對，如：

 複製代碼

{
"title":"Web 服務 ServiceB 崩潰報警 ",
"source":"192.168.0.1",
"error_type":"panic",
"project_name":"ServiceB",
"project_source":"web",
"details":"(call stack)",
//...
}

我們可以試着寫出路由節點 ServiceB 及 Service B Panic 的匹配器：

• ServiceB ：project_source 爲 web 且 project_name 爲 ServiceB
• Service B Panic ：project_source 爲 web，且 project_name 爲 Service B，且 error_type 爲 panic

報警平臺的用戶需要親自配置部分路由和規則，能否定製一套簡單、易上手的 DSL？如：

 複製代碼

project_source="web"AND project_name ="ServiceB"

這樣即使用戶不是工程師，看過幾個例子後也能熟練地書寫匹配表達式。

匹配表達式定義

匹配器表達式由原始表達式和複合表達式構成。原始表達式是最小的匹配器，有 完全匹配 和 正則匹配 兩種：

 複製代碼

# 完全匹配
project_source="web"
# 正則匹配
details=~"duplicate key when insert"

原始表達式的左手邊是報警信息的標籤，不帶雙引號；原始表達式的右手邊是匹配文本，帶雙引號。不同的原始表達式可通過二元關係運算，AND (且) 和 OR (或) ，組合成複合表達式如：

 複製代碼

project_source="web"AND project_name ="ServiceB"OR"error_type"="panic"

類似於乘除之於加減，AND 的優先級大於 OR，如果要改變優先級，可通過增加括號來實現，如：

 複製代碼

project_source="web"AND (project_name ="ServiceB"OR"error_type"="panic")

編譯過程

一個完整的編譯過程大致分三階段：

1. 前端：驗證源碼的語法和語義，並解析成中間表述 (Immediate Representation, IR)
2. 中端：針對 IR 作一些與目標 CPU 架構無關的優化
3. 後端：針對目標 CPU 架構優化並生成可執行的機器指令

我們也可以將匹配器表達式理解成一門語言，但我們只需要將它轉化成合理的內存數據結構即可，因此這裏只涉及到完整編譯過程的前端：

1. 詞法分析 (Lexical Analysis)：將完整的語句拆成詞語和標點符號
2. 語法分析 (Syntax Analysis)：根據語法規範，將詞語和標點符合組合成抽象語法樹 (AST)
3. 語義分析 (Semantic Analysis)：向語法樹中添加語義信息，完成校驗變量類型等各種語義檢查
4. 生成中間表述 (IR Generation)：轉化成合理的內存數據結構

以下就是匹配表達式的 IR：

 複製代碼

typePrimitiveMatcherstruct{
Labelstring
Textstring
IsRegexpbool
re *regexp.Regexp
}

typeMatcherstruct{
PrimitiveMatcher *PrimitiveMatcher
IsCompoundbool
Operator MatcherOperator
Operands []*Matcher
}

其中 Matcher 既可以是原始匹配器 (表達式) 也可以是複合匹配器 (表達式)。

下面分別介紹報警平臺匹配器編譯器的兩個版本實現，Matcher Compiler V1 (MCV1) 和 Matcher Compiler V2 (MCV2)。

Matcher Compiler V1

在實現 MCV1 時我們並未從編譯的角度看待這個模塊，而只是單純地想實現從表達式到 IR 的轉化。憑藉工程師的本能，MCV1 將編譯的前端處理過程分成 3 步：

 複製代碼

err = m.parseToken()
iferr !=nil{
return
}

err = m.toElements()
iferr !=nil{
return
}

returnm.buildMatcher()

parseToken

parseToken 將原始表達式轉化成一個詞語數組，是詞法分析的雛形，其整體過程如下：

 複製代碼

fori, c := m.expr {
hasLeftDoubleQuote :=false
switchc {
case'(':
//...
case')':
//...
case'=':
//...
case'~'
//...
default:
//...
}
}

parseToken 需要許多狀態，如：

• 是否在括號內
• 是否在引號內
• 遇到 ~ 要考慮是否會和上一個字符共同組成 =~

由於狀態較多，要同時考慮各種狀態及其之間的轉化過程，使得 parseToken 足夠健壯，過程燒腦且容易出錯。

toElements

toElements 遍歷詞語數組，構建其中的原始表達式，可以看作理解成是語法分析和語義分析的一部分，其整體過程如下：

 複製代碼

fori, word :=rangem.words {
switchstrings.ToLower(word) {
case"=":
leftWord, rightWord, _ := m.tryFetchBothSideWord(i)
m.addElement(m.buildPrimitiveMatcher(leftWord, rightWord,false))
case"=~":
leftWord, rightWord, _ := m.tryFetchBothSideWord(i)
m.addElement(m.buildPrimitiveMatcher(leftWord, rightWord,true))
// deal with more cases
default:
// ...
}

這部分邏輯比較簡單，遇到 = 或者 =~ 時看一下前後的詞語，看是否能構成原始表達式。

buildMatcher

buildMatcher 遍歷 elements 數組，構建最終的樹狀複合表達式，其實就是中綴表達式的計算過程，是棧的典型 應用場景 ，利用操作符棧和操作數棧即可實現，其整體過程如下：

 複製代碼

var(
valueStack Stack
opStack Stack
)

fori, element :=rangem.elements {
switche := element; {
casee =="(":
opStack.Push("(")
casee ==")":
forop := opStack.Pop(); op !="("{
rhs, lhs := valueStack.Pop(), valueStack.Pop()
// apply
}
// operators
caseisOp(e):
currOp = e
forprevOp := opStack.Peek(); precedence[currOp] <= precedence[prevOp] {
opStack.Pop()
rhs, lhs := valueStack.Pop(), valueStack.Pop()
// apply prevOp
}
opStack.Push(currOp)
default:
valueStack.Push(e)
}
}

// deal with the rest valueStack and opStack

MCV1 小結

MCV1 是憑藉工程師本能構建的一個模塊，優勢就在於可以迅速地搭建原型，驗證想法。從代碼健壯性角度看， parseToken 的狀態管理比較脆弱；從可讀性角度看，無法從邏輯中直接看出其所支持的語法，爲後期維護造成障礙；從可擴展性角度看， buildMatcher 目前只支持中綴表達式，如果有語法變化將整體邏輯產生較大影響；從效率角度看，編譯一次表達式需要 3 次遍歷，如果將 toElements 與 buildMatcher 邏輯合併可以優化到 2 次。

Matcher Compiler V2

爲了解決上述問題，我們想到了 Lex 和 Yacc。Lex 是 lexical analyzer generator，能夠幫助我們生成詞法分析器 (lexical analyzer)；Yacc 是 parser generator，能夠幫助我們生成解析器 (parser)，完成語法分析。Lex 和 Yacc 是 Unix 系統的原生工具，Linux 與 MacOS 平臺也都自帶這兩個工具。既然已經有前人爲我們栽樹，我們爲什麼不趁機乘涼？

Lex & Yacc

Lex 和 Yacc 的協作過程如下圖所示：

開發者將構詞規則和一些定製化邏輯 (C Code) 定義到 lex.l 文件中，利用 lex 命令生成詞法分析器；將語法規則和一些定製化邏輯定義到 parser.y 文件中，利用 yacc 命令生成解析器。詞法分析器的 yylex 方法將輸入文本轉化成 token，投餵給 yyparse ，後者根據語法和定製化邏輯將 token 流轉化成最終的目標數據結構，即 IR。

Example：Calculator

以一個支持加減運算的計算機爲例，先定義語法規則：

 複製代碼

// parser.y
%token NUMBER
%%

// 括號中的 $$ 表示語法左手邊 (LHS) 的值
// 括號中的 $1、$2、$3 表示語法右手邊 (RHS) 的值
statement: expression {printf("= %d\n", $1); }
;

expression: NUMBER'+'NUMBER { $$ = $1+ $3; }
| NUMBER'-'NUMBER { $$ = $1- $3; }
| NUMBER { $$ = $1; }
;

第一行的 token 定義語法中的數據類型，由於單個字符本身沒有歧義，在 Lex 和 Yacc 無需特別定義單字符 token，如 + 和 - ，因此在這裏我們只需要數字 NUMBER 。在第一個 %% 之後，定義了計算器的語法，含義非常直白，可讀性強。

然後再定義構詞規則：

 複製代碼

// lex.l
%{
#include"y.tab.h"
externintyylval;
%}

%%
[0-9]+ { yylval = atoi(yytext);returnNUMBER; }
[ \t] ;
\nreturn0;
.returnyytext[0];
%%

在兩個 %% 中間的就是構詞規則：

• 符合正則表達式 [0-9]+ 就是數字類型的詞語，其對應的值爲 atoi(yytext)
• 符合正則表達式 [ \t] 的不處理，即忽略空格和製表符
• 符合正則表達式 \n 的返回 0，即用換行符標識文本結束位置
• 符合正則表達式 . 的返回文本本身，即所有非數字的字符直接返回，這裏實際上指的就是 + 和 - 。

接下來只需要用 lex 和 yacc 命令生成詞法分析器和解析器，然後運行即可：

 複製代碼

#MacOS
$lex lex.l
$yacc -d parser.y
$gcc y.tab.c lex.yy.c -ly -ll -o calculator
$./calculator
>128 + 128
>= 256

對比分析

從代碼健壯性角度上看， lex 生成的詞法分析器已經經受時間的檢驗，開發者大可相信其代碼的健壯性；從可讀性角度看，構詞規則和語法規則定義簡短，通俗易懂；從可擴展性角度看，任何可以通過上下文無關文法 (context-free grammar) 表達的語法都能支持；從效率角度看， yylex 與 yyparse 可以流式地處理文本， yyparse 從 yylex 獲取詞語，即時地根據語法規則組合成 IR，這種做法使得編譯前端的工作只需要 1 次遍歷便可完成。但 lex 和 yacc 爲了支持更復雜的場景，其生成的代碼也會更復雜，這也是效率與通用性權衡的表現。

Nex & Goyacc

報警平臺使用 Go 語言編碼，直接使用 lex 和 yacc 需要引入 cgo ，這也使得二者的使用門檻變高。好在 Go 官方提供了 goyacc ，方便我們在 parser.y 中引入用 Go 語言編寫的定製化邏輯；斯坦福的一位博士 Ben Lynn 開源了它的 nex 項目，作爲用 Go 語言原生開發的詞法分析器生成器，能與 goyacc 兼容，形成類似 lex 和 yacc 一般的搭檔。接下來我們將利用 nex 和 goyacc 來實現匹配器編譯器。

與計算器的例子類似，我們先看語法規則中定義的數據類型：

 複製代碼

%union{
strstring
expr *MatchExpr
pexpr *PrimitiveExpr
}

%token LABEL VALUE
%token REG_EQ AND OR

%type<expr> expr
%type<pexpr> pexpr
%type<str> LABEL VALUE
%type<str> REG_EQ AND OR

其中，語法中的數據類型包括：

• LABEL ：原子表達式的 LHS
• VALUE ：原子表達式的 RHS
• REG_EQ 、 AND 、 OR 分別爲正則匹配，且和或

此外我們還定義了原始表達式 pexpr 和複合表達式 expr 供定義語法規則時引用。由於語法中有多種關係運算符，它們的優先級不同，因此我們還需要定義運算符的優先級：

 複製代碼

%left OR
%left AND
%left'('')'

left 表示先從運算符的 LHS 開始計算，三者的優先級關係是 OR < AND < '(' == ')' ，非常直觀。最後進入我們的語法規則：

 複製代碼

// 匹配器表達式可以是空字符串，也可以是一個合法的表達式
matcher:
{ setResult(yylex, &Matcher{}) }
| expr
{ setResult(yylex, $1) }

// 表達式可能以下之一：
// 複合表達式：expr AND expr
// 複合表達式：expr OR expr
// 原始表達式：pexpr
// 括號表達式：(expr)
expr: expr AND expr
{ $$ = &Matcher{IsCompound:true, Operator:$2, Operands:[]*Matcher{$1,$3}} }
| expr OR expr
{ $$ = &Matcher{IsCompound:true, Operator:$2, Operands:[]*Matcher{$1,$3}} }
| pexpr
{ $$ = &Matcher{IsCompound:false, PrimitiveMatcher:$1} }
|'('expr')'
{ $$ = $2}
// 原始表達式要麼是 LABEL = VALUE, 要麼是 LABEL =~ VALUE
pexpr: LABEL'='VALUE
{ $$ = &PrimitiveMatcher{Label:$1, Text:$3, IsRegex:false} }
| LABEL REG_EQ VALUE
{ $$ = &PrimitiveMatcher{Label:$1, Text:$3, IsRegex:true} }

每條語法規則的含義已經標明在註釋中，在每條語法規則之後，是 Go 語言編碼的簡單邏輯，告訴解析器在不同情況下如何拼裝 IR。搞定語法後，我們就可以定義構詞規則：

 複製代碼

/[aA][nN][dD]/ { lval.str ="AND";returnAND }
/[oO][rR]/ { lval.str ="OR";returnOR }
/=~/ {returnREG_EQ }
/=/ {returnint(yylex.Text()[0]) }
/\(/ {returnint(yylex.Text()[0]) }
/\)/ {returnint(yylex.Text()[0]) }
/[A-Za-z][A-Za-z0-9_]*/ { lval.str = yylex.Text();returnLABEL }
/".*"/ { lval.str = yylex.Text()[1:len(yylex.Text())-1];returnVALUE }
/[ \t\r\n]+/ {/* white spaces ignored */}
//
packagec

• 大小寫無關的字符串 “AND” 返回類型 AND ；“OR” 返回類型 OR
• “=~”、"="、"("、")" 直接返回相應的數據類型
• 正則表達式 /[A-Za-z][A-Za-z0-9_]*/ 匹配的是原始表達式中的 LABEL
• 正則表達式 /".*"/ 匹配的是原始表達式中的 VALUE
• 正則表達式 /[ \t\r\n]+/ 匹配的是空格字符，即忽略所有類型的空格

最後使用 nex 和 goyacc 就可以生成詞法分析器和解析器：

 複製代碼

$nex nex.l
$goyacc -o parser.go parser.y

然後再把二者串起來即可：

 複製代碼

// 忽略細節處理
funcCompile(ctx context.Context, in io.Reader)(m *Matcher, err error){
lr := NewLexer(in)
yyParse(lr)

iflr.parseResult ==nil{
err = SyntaxError
return
}

m = lr.parseResult.(*Matcher)
return
}

Rob Pike Style Lexer

完成上面的工作，本可以告一段落，但有一個問題還困擾着我們：”爲什麼 Go 只推出了 yacc 的移植版本，而不順便推出 lex 的移植版本？“ 幾經周折找到了 Rob Pike 2011 年的一次演講： “Lexical Scanning in Go”。在演講中他認爲 ” lex 生成的代碼太多，過於複雜，用 Go 語言實現一個並非難事，且 Go 的 channel 能方便地實現 lex 和 yacc 的流水線協作。“ 儘管這種觀點也是在爲 Go 站臺，我們還是決定試一試他提出的 lexical scanning 方案。

詞法分析的過程，就是從輸入字符流起點掃描至終點的線性過程，在掃描期間，詞法分析器需要正確地判斷自己所處的狀態，以起點爲例，剛開始掃描，可能進入 LABEL 狀態，也可能進入 ( 狀態：

 複製代碼

labela="a"AND (labelb="b"ORlabelc="c")
↑
在 LABEL 中

(labela="a") ORlabelb="b"
↑
在'('中

掃描完 VALUE 後，可能進入 結束 狀態，也可能進入 ) 狀態或 關係運算符 狀態：

 複製代碼

labela="a"AND (labelb="b"ORlabelc="c")
↑
進入 [關係運算符] 狀態
(labela="a")
↑
進入 ')' 狀態
labela="a"
↑
進入 [結束] 狀態

不難看出，這實際上就是一個狀態機，詳細的狀態轉移過程如下圖所示：

 複製代碼

# start: [開始]; leftParen: '('; label: [標籤]; eq: [匹配符]; value: [文本];
# rightParen: ')'; binaryOp: [關係運算符]; end: [結束]
+------------+
|rightParen|-------------+
+------------+|
^ ||
|||
+----------------------+ |----------------+|
|v|v|
|+-----------+ +-------+ +----+ +------------+ +-----+|
||start|-->|label|-->|eq|-->|value|-->|end||
|+-----------+ +-------+ +----+ +------------+ +-----+|
||^||
|||||
|v|v|
|+-----------+|+------------+|
+- |leftParen|+---------------------|binaryOp|<------------+
+-----------+ +------------+
^|
+------------------------------------------+

接下來就需要讓這個狀態機動起來：

 複製代碼

typelexerstruct{
namestring// used only for error reports.
inputstring// the string being scanned.
startint// start position of this item.
posint// current position in the input.
widthint// width of last rune read from input.
itemschanitem// channel of scanned items.
}

// stateFn represents the state of the scanner
// as a function that returns the next state.
typestateFnfunc(*lexer)stateFn

func(l *lexer)run(){
forstate := lexStart; state !=nil; {
state = state(l)
}
close(l.items)
}

其中 stateFn 就是狀態轉移方程，約定當 stateFn == nil 時，狀態機停止，即 nil 就是結束狀態的轉移方程。接下來只需要定義各個狀態轉移方程即可：

 複製代碼

funclexStart(l *lexer)stateFn{}
funclexLabel(l *lexer)stateFn{}
funclexLeftParen(l *lexer)stateFn{}
funclexRightParen(l *lexer)stateFn{}
funclexEq(l *lexer)stateFn{}
funclexValue(l *lexer)stateFn{}
funclexBinaryOp(l *lexer)stateFn{}

每當狀態即將轉移時， stateFn 內部就會將在本狀態中掃描到的詞語傳給 item channel ，這個 channel 就是 lexer 與 parser 之間通信的媒介。

值得一提的是，Go 的模板引擎 template，就是按照上述方式構建的，感興趣可以閱讀 源碼 。

參考文獻

• Compilers: Principles, Techniques, and Tools, the dragon book
• GeeksforGeeks: Expression Evaluation Problem
• Lex & Yacc, website , book
• Lexical Scanning in Go by Rob Pike , video , slides , go blog
• Go Template, source code