本文介紹伴魚內(nèi)部服務報警平臺中匹配器模塊的演進，及其利用 Lex 和 Yacc 同類工具構(gòu)建 DSL 編譯器的過程。
背景
報警平臺是伴魚內(nèi)部各端、應用、基礎設施等服務異常狀態(tài)信息的集散中心。整體流程如下圖所示：
信息源將信息投遞給報警平臺，后者將這些信息最終通過郵件、即時消息、電話呼叫的形式路由給理應關心它的人。總體而言，路由的需求可以分為以下幾種：
- 路由給服務的負責人及其團隊
- 路由給服務依賴方人員及其團隊
- 路由給所有值班人員所在的即時消息群
為了滿足這樣的需求，報警平臺采用樹狀結(jié)構(gòu)組織路由信息，如下圖所示：
每個節(jié)點是一個路由節(jié)點，節(jié)點上可以掛載不同的規(guī)則，如抑制規(guī)則、通知規(guī)則；也可以存放不同的配置信息，如觸發(fā)報警的閾值，以及相關負責人及其團隊的聯(lián)系方式。
根路由是所有異常信息的必經(jīng)之路，經(jīng)過這里的信息會路由給所有值班人員；一級子路由節(jié)點是所有的服務，經(jīng)過這里的信息會路由給該服務的負責人及其團隊；如果有其它團隊想要訂閱某服務的異常消息，如 Service A 團隊想要了解 Service B 的崩潰 (panic) 信息，則可以在 Service B 節(jié)點下創(chuàng)建子路由 Service B Panic，并在上面配置 Service A 團隊的聯(lián)系方式，從而達到訂閱目的。
那么如何判斷一條報警信息將經(jīng)過哪些路由節(jié)點，一條規(guī)則是否起作用？這就需要引入本文的主角：匹配器 (matcher)，每個路由、每條規(guī)則上都會掛載一個匹配器，當它成功匹配到報警信息時，路由和規(guī)則就會生效。一條典型的報警信息會有許多信息，我們不妨將它看作是任意數(shù)量的鍵值對，如：
復制代碼
{ "title": "Web 服務 ServiceB 崩潰報警 ", "source": "192.168.0.1", "error_type": "panic", "project_name": "ServiceB", "project_source": "web", "details": "(call stack)", //...}
我們可以試著寫出路由節(jié)點 ServiceB 及 Service B Panic 的匹配器：
- ServiceB：project_source 為 web 且 project_name 為 ServiceB
- Service B Panic：project_source 為 web，且 project_name 為 Service B，且 error_type 為 panic
報警平臺的用戶需要親自配置部分路由和規(guī)則，能否定制一套簡單、易上手的 DSL？如：
復制代碼
project_source = "web" AND project_name = "ServiceB"
這樣即使用戶不是工程師，看過幾個例子后也能熟練地書寫匹配表達式。
匹配表達式定義
匹配器表達式由原始表達式和復合表達式構(gòu)成。原始表達式是最小的匹配器，有完全匹配和正則匹配兩種：
復制代碼
# 完全匹配project_source = "web"# 正則匹配details =~ "duplicate key when insert"
原始表達式的左手邊是報警信息的標簽，不帶雙引號；原始表達式的右手邊是匹配文本，帶雙引號。不同的原始表達式可通過二元關系運算，AND (且) 和 OR (或) ，組合成復合表達式如：
復制代碼
project_source = "web" AND project_name = "ServiceB" OR "error_type" = "panic"
類似于乘除之于加減，AND 的優(yōu)先級大于 OR，如果要改變優(yōu)先級，可通過增加括號來實現(xiàn)，如：
復制代碼
project_source = "web" AND (project_name = "ServiceB" OR "error_type" = "panic")
編譯過程
一個完整的編譯過程大致分三階段：
- 前端：驗證源碼的語法和語義，并解析成中間表述 (Immediate Representation, IR)
- 中端：針對 IR 作一些與目標 CPU 架構(gòu)無關的優(yōu)化
- 后端：針對目標 CPU 架構(gòu)優(yōu)化并生成可執(zhí)行的機器指令
我們也可以將匹配器表達式理解成一門語言，但我們只需要將它轉(zhuǎn)化成合理的內(nèi)存數(shù)據(jù)結(jié)構(gòu)即可，因此這里只涉及到完整編譯過程的前端：
- 詞法分析 (Lexical Analysis)：將完整的語句拆成詞語和標點符號
- 語法分析 (Syntax Analysis)：根據(jù)語法規(guī)范，將詞語和標點符合組合成抽象語法樹 (AST)
- 語義分析 (Semantic Analysis)：向語法樹中添加語義信息，完成校驗變量類型等各種語義檢查
- 生成中間表述 (IR Generation)：轉(zhuǎn)化成合理的內(nèi)存數(shù)據(jù)結(jié)構(gòu)
以下就是匹配表達式的 IR：
復制代碼
type PrimitiveMatcher struct { Label string Text string IsRegexp bool re *regexp.Regexp} type Matcher struct { PrimitiveMatcher *PrimitiveMatcher IsCompound bool Operator MatcherOperator Operands []*Matcher}
其中 Matcher 既可以是原始匹配器 (表達式) 也可以是復合匹配器 (表達式)。
下面分別介紹報警平臺匹配器編譯器的兩個版本實現(xiàn)，Matcher Compiler V1 (MCV1) 和 Matcher Compiler V2 (MCV2)。
Matcher Compiler V1
在實現(xiàn) MCV1 時我們并未從編譯的角度看待這個模塊，而只是單純地想實現(xiàn)從表達式到 IR 的轉(zhuǎn)化。憑借工程師的本能，MCV1 將編譯的前端處理過程分成 3 步：
復制代碼
err = m.parseToken()if err != nil { return} err = m.toElements()if err != nil { return} return m.buildMatcher()
parseToken
parseToken 將原始表達式轉(zhuǎn)化成一個詞語數(shù)組，是詞法分析的雛形，其整體過程如下：
復制代碼
for i, c := m.expr { hasLeftDoubleQuote := false switch c { case '(': //... case ')': //... case '=': //... case '~' //... default: //... }}
parseToken 需要許多狀態(tài)，如：
- 是否在括號內(nèi)
- 是否在引號內(nèi)
- 遇到 ~ 要考慮是否會和上一個字符共同組成 =~
- …
由于狀態(tài)較多，要同時考慮各種狀態(tài)及其之間的轉(zhuǎn)化過程，使得 parseToken 足夠健壯，過程燒腦且容易出錯。
toElements
toElements 遍歷詞語數(shù)組，構(gòu)建其中的原始表達式，可以看作理解成是語法分析和語義分析的一部分，其整體過程如下：
復制代碼
for i, word := range m.words { switch strings.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: // ...}
這部分邏輯比較簡單，遇到 = 或者 =~ 時看一下前后的詞語，看是否能構(gòu)成原始表達式。
buildMatcher
buildMatcher 遍歷 elements 數(shù)組，構(gòu)建最終的樹狀復合表達式，其實就是中綴表達式的計算過程，是棧的典型應用場景，利用操作符棧和操作數(shù)棧即可實現(xiàn)，其整體過程如下：
復制代碼
var ( valueStack Stack opStack Stack) for i, element := range m.elements { switch e := element; { case e == "(": opStack.Push("(") case e == ")": for op := opStack.Pop(); op != "(" { rhs, lhs := valueStack.Pop(), valueStack.Pop() // Apply } // operators case isOp(e): currOp = e for prevOp := 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 小結(jié)
MCV1 是憑借工程師本能構(gòu)建的一個模塊，優(yōu)勢就在于可以迅速地搭建原型，驗證想法。從代碼健壯性角度看， parseToken 的狀態(tài)管理比較脆弱；從可讀性角度看，無法從邏輯中直接看出其所支持的語法，為后期維護造成障礙；從可擴展性角度看，buildMatcher 目前只支持中綴表達式，如果有語法變化將整體邏輯產(chǎn)生較大影響；從效率角度看，編譯一次表達式需要 3 次遍歷，如果將 toElements 與 buildMatcher 邏輯合并可以優(yōu)化到 2 次。
Matcher Compiler V2
為了解決上述問題，我們想到了 Lex 和 Yacc。Lex 是 lexical analyzer generator，能夠幫助我們生成詞法分析器 (lexical analyzer)；Yacc 是 parser generator，能夠幫助我們生成解析器 (parser)，完成語法分析。Lex 和 Yacc 是 Unix 系統(tǒng)的原生工具，linux 與 macOS 平臺也都自帶這兩個工具。既然已經(jīng)有前人為我們栽樹，我們?yōu)槭裁床怀脵C乘涼？
Lex & Yacc
Lex 和 Yacc 的協(xié)作過程如下圖所示：
開發(fā)者將構(gòu)詞規(guī)則和一些定制化邏輯 (C Code) 定義到 lex.l 文件中，利用 lex 命令生成詞法分析器；將語法規(guī)則和一些定制化邏輯定義到 parser.y 文件中，利用 yacc 命令生成解析器。詞法分析器的 yylex 方法將輸入文本轉(zhuǎn)化成 token，投喂給 yyparse，后者根據(jù)語法和定制化邏輯將 token 流轉(zhuǎn)化成最終的目標數(shù)據(jù)結(jié)構(gòu)，即 IR。
Example：Calculator
以一個支持加減運算的計算機為例，先定義語法規(guī)則：
復制代碼
// parser.y%token NUMBER%% // 括號中的 $$ 表示語法左手邊 (LHS) 的值// 括號中的 $1、$2、$3 表示語法右手邊 (RHS) 的值statement: expression { printf("= %dn", $1); } ; expression: NUMBER '+' NUMBER { $$ = $1 + $3; } | NUMBER '-' NUMBER { $$ = $1 - $3; } | NUMBER { $$ = $1; } ;
第一行的 token 定義語法中的數(shù)據(jù)類型，由于單個字符本身沒有歧義，在 Lex 和 Yacc 無需特別定義單字符 token，如 + 和 -，因此在這里我們只需要數(shù)字 NUMBER。在第一個 %% 之后，定義了計算器的語法，含義非常直白，可讀性強。
然后再定義構(gòu)詞規(guī)則：
復制代碼
// lex.l%{#include "y.tab.h"extern int yylval;%} %%[0-9]+ { yylval = atoi(yytext); return NUMBER; }[ t] ;n return 0;. return yytext[0];%%
在兩個 %% 中間的就是構(gòu)詞規(guī)則：
- 符合正則表達式 [0-9]+ 就是數(shù)字類型的詞語，其對應的值為 atoi(yytext)
- 符合正則表達式 [ t] 的不處理，即忽略空格和制表符
- 符合正則表達式 n 的返回 0，即用換行符標識文本結(jié)束位置
- 符合正則表達式 . 的返回文本本身，即所有非數(shù)字的字符直接返回，這里實際上指的就是 + 和 -。
接下來只需要用 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 生成的詞法分析器已經(jīng)經(jīng)受時間的檢驗，開發(fā)者大可相信其代碼的健壯性；從可讀性角度看，構(gòu)詞規(guī)則和語法規(guī)則定義簡短，通俗易懂；從可擴展性角度看，任何可以通過上下文無關文法 (context-free grammar) 表達的語法都能支持；從效率角度看，yylex 與 yyparse 可以流式地處理文本，yyparse 從 yylex 獲取詞語，即時地根據(jù)語法規(guī)則組合成 IR，這種做法使得編譯前端的工作只需要 1 次遍歷便可完成。但 lex 和 yacc 為了支持更復雜的場景，其生成的代碼也會更復雜，這也是效率與通用性權(quán)衡的表現(xiàn)。
Nex & Goyacc
報警平臺使用 Go 語言編碼，直接使用 lex 和 yacc 需要引入 cgo，這也使得二者的使用門檻變高。好在 Go 官方提供了 goyacc，方便我們在 parser.y 中引入用 Go 語言編寫的定制化邏輯；斯坦福的一位博士 Ben Lynn 開源了它的 nex 項目，作為用 Go 語言原生開發(fā)的詞法分析器生成器，能與 goyacc 兼容，形成類似 lex 和 yacc 一般的搭檔。接下來我們將利用 nex 和 goyacc 來實現(xiàn)匹配器編譯器。
與計算器的例子類似，我們先看語法規(guī)則中定義的數(shù)據(jù)類型：
復制代碼
%union{ str string 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
其中，語法中的數(shù)據(jù)類型包括：
- LABEL：原子表達式的 LHS
- VALUE：原子表達式的 RHS
- REG_EQ、AND、OR 分別為正則匹配，且和或
此外我們還定義了原始表達式 pexpr 和復合表達式 expr 供定義語法規(guī)則時引用。由于語法中有多種關系運算符，它們的優(yōu)先級不同，因此我們還需要定義運算符的優(yōu)先級：
復制代碼
%left OR%left AND%left '(' ')'
left 表示先從運算符的 LHS 開始計算，三者的優(yōu)先級關系是 OR < AND < '(' == ')'，非常直觀。最后進入我們的語法規(guī)則：
復制代碼
// 匹配器表達式可以是空字符串，也可以是一個合法的表達式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 =~ VALUEpexpr: LABEL '=' VALUE { $$ = &PrimitiveMatcher{Label:$1, Text:$3, IsRegex: false} }| LABEL REG_EQ VALUE { $$ = &PrimitiveMatcher{Label:$1, Text:$3, IsRegex: true} }
每條語法規(guī)則的含義已經(jīng)標明在注釋中，在每條語法規(guī)則之后，是 Go 語言編碼的簡單邏輯，告訴解析器在不同情況下如何拼裝 IR。搞定語法后，我們就可以定義構(gòu)詞規(guī)則：
復制代碼
/[aA][nN][dD]/ { lval.str = "AND"; return AND }/[oO][rR]/ { lval.str = "OR"; return OR }/=~/ { return REG_EQ }/=/ { return int(yylex.Text()[0]) }/(/ { return int(yylex.Text()[0]) }/)/ { return int(yylex.Text()[0]) }/[A-Za-z][A-Za-z0-9_]*/ { lval.str = yylex.Text(); return LABEL }/".*"/ { lval.str = yylex.Text()[1:len(yylex.Text())-1]; return VALUE }/[ trn]+/ { /* white spaces ignored */ }//package c
- 大小寫無關的字符串 “AND” 返回類型 AND；“OR” 返回類型 OR
- “=~”、"="、"("、")" 直接返回相應的數(shù)據(jù)類型
- 正則表達式 /[A-Za-z][A-Za-z0-9_]*/ 匹配的是原始表達式中的 LABEL
- 正則表達式 /".*"/ 匹配的是原始表達式中的 VALUE
- 正則表達式 /[ trn]+/ 匹配的是空格字符，即忽略所有類型的空格
最后使用 nex 和 goyacc 就可以生成詞法分析器和解析器：
復制代碼
$ nex nex.l$ goyacc -o parser.go parser.y
然后再把二者串起來即可：
復制代碼
// 忽略細節(jié)處理func Compile(ctx context.Context, in io.Reader) (m *Matcher, err error) { lr := NewLexer(in) yyParse(lr) if lr.parseResult == nil { err = SyntaxError return } m = lr.parseResult.(*Matcher) return}
Rob Pike Style Lexer
完成上面的工作，本可以告一段落，但有一個問題還困擾著我們：”為什么 Go 只推出了 yacc 的移植版本，而不順便推出 lex 的移植版本？“ 幾經(jīng)周折找到了 Rob Pike 2011 年的一次演講： “Lexical Scanning in Go”。在演講中他認為 ” lex 生成的代碼太多，過于復雜，用 Go 語言實現(xiàn)一個并非難事，且 Go 的 channel 能方便地實現(xiàn) lex 和 yacc 的流水線協(xié)作。“ 盡管這種觀點也是在為 Go 站臺，我們還是決定試一試他提出的 lexical scanning 方案。
詞法分析的過程，就是從輸入字符流起點掃描至終點的線性過程，在掃描期間，詞法分析器需要正確地判斷自己所處的狀態(tài)，以起點為例，剛開始掃描，可能進入 LABEL 狀態(tài)，也可能進入 ( 狀態(tài)：
復制代碼
labela = "a" AND (labelb = "b" OR labelc = "c")↑ 在 LABEL 中 (labela = "a") OR labelb = "b"↑在'('中
掃描完 VALUE 后，可能進入結(jié)束狀態(tài)，也可能進入 ) 狀態(tài)或 關系運算符 狀態(tài)：
復制代碼
labela = "a" AND (labelb = "b" OR labelc = "c") ↑ 進入 [關系運算符] 狀態(tài)(labela = "a") ↑ 進入 ')' 狀態(tài)labela = "a" ↑ 進入 [結(jié)束] 狀態(tài)
不難看出，這實際上就是一個狀態(tài)機，詳細的狀態(tài)轉(zhuǎn)移過程如下圖所示：
復制代碼
# start: [開始]; leftParen: '('; label: [標簽]; eq: [匹配符]; value: [文本];# rightParen: ')'; binaryOp: [關系運算符]; end: [結(jié)束] +------------+ | rightParen | -------------+ +------------+ | ^ | | | | | +----------------------+ | ----------------+ | | v | v | | +-----------+ +-------+ +----+ +------------+ +-----+ | | | start | --> | label | --> | eq | --> | value | --> | end | | | +-----------+ +-------+ +----+ +------------+ +-----+ | | | ^ | | | | | | | | v | v | | +-----------+ | +------------+ | +- | leftParen | +--------------------- | binaryOp | <------------+ +-----------+ +------------+ ^ | +------------------------------------------+
接下來就需要讓這個狀態(tài)機動起來：
復制代碼
type lexer struct { name string // used only for error reports. input string // the string being scanned. start int // start position of this item. pos int // current position in the input. width int // width of last rune read from input. items chan item // channel of scanned items.} // stateFn represents the state of the scanner// as a function that returns the next state.type stateFn func(*lexer) stateFn func (l *lexer) run() { for state := lexStart; state != nil; { state = state(l) } close(l.items)}
其中 stateFn 就是狀態(tài)轉(zhuǎn)移方程，約定當 stateFn == nil 時，狀態(tài)機停止，即 nil 就是結(jié)束狀態(tài)的轉(zhuǎn)移方程。接下來只需要定義各個狀態(tài)轉(zhuǎn)移方程即可：
復制代碼
func lexStart(l *lexer) stateFn {}func lexLabel(l *lexer) stateFn {}func lexLeftParen(l *lexer) stateFn {}func lexRightParen(l *lexer) stateFn {}func lexEq(l *lexer) stateFn {}func lexValue(l *lexer) stateFn {}func lexBinaryOp(l *lexer) stateFn {}
每當狀態(tài)即將轉(zhuǎn)移時，stateFn 內(nèi)部就會將在本狀態(tài)中掃描到的詞語傳給 item channel，這個 channel 就是 lexer 與 parser 之間通信的媒介。
值得一提的是，Go 的模板引擎 template，就是按照上述方式構(gòu)建的，感興趣可以閱讀源碼。
