本文介紹伴魚(yú)內(nèi)部服務(wù)報(bào)警平臺(tái)中匹配器模塊的演進(jìn)，及其利用 Lex 和 Yacc 同類(lèi)工具構(gòu)建 DSL 編譯器的過(guò)程。
背景
報(bào)警平臺(tái)是伴魚(yú)內(nèi)部各端、應(yīng)用、基礎(chǔ)設(shè)施等服務(wù)異常狀態(tài)信息的集散中心。整體流程如下圖所示：
信息源將信息投遞給報(bào)警平臺(tái)，后者將這些信息最終通過(guò)郵件、即時(shí)消息、電話(huà)呼叫的形式路由給理應(yīng)關(guān)心它的人。總體而言，路由的需求可以分為以下幾種：
為了滿(mǎn)足這樣的需求，報(bào)警平臺(tái)采用樹(shù)狀結(jié)構(gòu)組織路由信息，如下圖所示：
每個(gè)節(jié)點(diǎn)是一個(gè)路由節(jié)點(diǎn)，節(jié)點(diǎn)上可以?huà)燧d不同的規(guī)則，如抑制規(guī)則、通知規(guī)則；也可以存放不同的配置信息，如觸發(fā)報(bào)警的閾值，以及相關(guān)負(fù)責(zé)人及其團(tuán)隊(duì)的聯(lián)系方式。
根路由是所有異常信息的必經(jīng)之路，經(jīng)過(guò)這里的信息會(huì)路由給所有值班人員；一級(jí)子路由節(jié)點(diǎn)是所有的服務(wù)，經(jīng)過(guò)這里的信息會(huì)路由給該服務(wù)的負(fù)責(zé)人及其團(tuán)隊(duì)；如果有其它團(tuán)隊(duì)想要訂閱某服務(wù)的異常消息，如 A 團(tuán)隊(duì)想要了解 B 的崩潰 (panic) 信息，則可以在 B 節(jié)點(diǎn)下創(chuàng)建子路由 B Panic，并在上面配置 A 團(tuán)隊(duì)的聯(lián)系方式，從而達(dá)到訂閱目的。
那么如何判斷一條報(bào)警信息將經(jīng)過(guò)哪些路由節(jié)點(diǎn)，一條規(guī)則是否起作用？這就需要引入本文的主角：匹配器 ()，每個(gè)路由、每條規(guī)則上都會(huì)掛載一個(gè)匹配器，當(dāng)它成功匹配到報(bào)警信息時(shí)，路由和規(guī)則就會(huì)生效。一條典型的報(bào)警信息會(huì)有許多信息，我們不妨將它看作是任意數(shù)量的鍵值對(duì)，如：
復(fù)制代碼
{ "title": "Web 服務(wù) ServiceB 崩潰報(bào)警 ", "source": "192.168.0.1", "error_type": "panic", "project_name": "ServiceB", "project_source": "web", "details": "(call stack)", //...}我們可以試著寫(xiě)出路由節(jié)點(diǎn) 及 B Panic 的匹配器：
報(bào)警平臺(tái)的用戶(hù)需要親自配置部分路由和規(guī)則，能否定制一套簡(jiǎn)單、易上手的 DSL？如：
復(fù)制代碼
project_source = "web" AND project_name = "ServiceB"這樣即使用戶(hù)不是工程師，看過(guò)幾個(gè)例子后也能熟練地書(shū)寫(xiě)匹配表達(dá)式。
匹配表達(dá)式定義
匹配器表達(dá)式由原始表達(dá)式和復(fù)合表達(dá)式構(gòu)成。原始表達(dá)式是最小的匹配器，有完全匹配和正則匹配兩種：
復(fù)制代碼
# 完全匹配project_source = "web"# 正則匹配details =~ "duplicate key when insert"原始表達(dá)式的左手邊是報(bào)警信息的標(biāo)簽，不帶雙引號(hào)；原始表達(dá)式的右手邊是匹配文本，帶雙引號(hào)。不同的原始表達(dá)式可通過(guò)二元關(guān)系運(yùn)算，AND (且) 和 OR (或) ，組合成復(fù)合表達(dá)式如：
復(fù)制代碼
project_source = "web" AND project_name = "ServiceB" OR "error_type" = "panic"類(lèi)似于乘除之于加減，AND 的優(yōu)先級(jí)大于 OR，如果要改變優(yōu)先級(jí)，可通過(guò)增加括號(hào)來(lái)實(shí)現(xiàn)，如：
復(fù)制代碼
project_source = "web" AND (project_name = "ServiceB" OR "error_type" = "panic")編譯過(guò)程
一個(gè)完整的編譯過(guò)程大致分三階段：
前端：驗(yàn)證源碼的語(yǔ)法和語(yǔ)義，并解析成中間表述 ( , IR)中端：針對(duì) IR 作一些與目標(biāo) CPU 架構(gòu)無(wú)關(guān)的優(yōu)化后端：針對(duì)目標(biāo) CPU 架構(gòu)優(yōu)化并生成可執(zhí)行的機(jī)器指令
我們也可以將匹配器表達(dá)式理解成一門(mén)語(yǔ)言，但我們只需要將它轉(zhuǎn)化成合理的內(nèi)存數(shù)據(jù)結(jié)構(gòu)即可，因此這里只涉及到完整編譯過(guò)程的前端：
詞法分析 ( )：將完整的語(yǔ)句拆成詞語(yǔ)和標(biāo)點(diǎn)符號(hào)語(yǔ)法分析 ( )：根據(jù)語(yǔ)法規(guī)范，將詞語(yǔ)和標(biāo)點(diǎn)符合組合成抽象語(yǔ)法樹(shù) (AST)語(yǔ)義分析 ( )：向語(yǔ)法樹(shù)中添加語(yǔ)義信息，完成校驗(yàn)變量類(lèi)型等各種語(yǔ)義檢查生成中間表述 (IR )：轉(zhuǎn)化成合理的內(nèi)存數(shù)據(jù)結(jié)構(gòu)
以下就是匹配表達(dá)式的 IR：
復(fù)制代碼
type PrimitiveMatcher struct { Label string Text string IsRegexp bool re *regexp.Regexp} type Matcher struct { PrimitiveMatcher *PrimitiveMatcher IsCompound bool Operator MatcherOperator Operands []*Matcher}其中 既可以是原始匹配器 (表達(dá)式) 也可以是復(fù)合匹配器 (表達(dá)式)。
下面分別介紹報(bào)警平臺(tái)匹配器編譯器的兩個(gè)版本實(shí)現(xiàn)， V1 (MCV1) 和 V2 (MCV2)。
V1
在實(shí)現(xiàn) MCV1 時(shí)我們并未從編譯的角度看待這個(gè)模塊，而只是單純地想實(shí)現(xiàn)從表達(dá)式到 IR 的轉(zhuǎn)化。憑借工程師的本能，MCV1 將編譯的前端處理過(guò)程分成 3 步：
復(fù)制代碼
err = m.parseToken()if err != nil { return} err = m.toElements()if err != nil { return} return m.buildMatcher()將原始表達(dá)式轉(zhuǎn)化成一個(gè)詞語(yǔ)數(shù)組，是詞法分析的雛形，其整體過(guò)程如下：
復(fù)制代碼
for i, c := m.expr { hasLeftDoubleQuote := false switch c { case '(': //... case ')': //... case '=': //... case '~' //... default: //... }}需要許多狀態(tài)，如：
由于狀態(tài)較多，要同時(shí)考慮各種狀態(tài)及其之間的轉(zhuǎn)化過(guò)程，使得 足夠健壯，過(guò)程燒腦且容易出錯(cuò)。
遍歷詞語(yǔ)數(shù)組，構(gòu)建其中的原始表達(dá)式yy直播模板加載中，可以看作理解成是語(yǔ)法分析和語(yǔ)義分析的一部分，其整體過(guò)程如下：
復(fù)制代碼
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: // ...}這部分邏輯比較簡(jiǎn)單，遇到 = 或者 =~ 時(shí)看一下前后的詞語(yǔ)，看是否能構(gòu)成原始表達(dá)式。
遍歷 數(shù)組，構(gòu)建最終的樹(shù)狀復(fù)合表達(dá)式，其實(shí)就是中綴表達(dá)式的計(jì)算過(guò)程，是棧的典型應(yīng)用場(chǎng)景，利用操作符棧和操作數(shù)棧即可實(shí)現(xiàn)，其整體過(guò)程如下：
復(fù)制代碼
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 opStackMCV1 小結(jié)
MCV1 是憑借工程師本能構(gòu)建的一個(gè)模塊，優(yōu)勢(shì)就在于可以迅速地搭建原型，驗(yàn)證想法。從代碼健壯性角度看， 的狀態(tài)管理比較脆弱；從可讀性角度看，無(wú)法從邏輯中直接看出其所支持的語(yǔ)法，為后期維護(hù)造成障礙；從可擴(kuò)展性角度看， 目前只支持中綴表達(dá)式，如果有語(yǔ)法變化將整體邏輯產(chǎn)生較大影響；從效率角度看，編譯一次表達(dá)式需要 3 次遍歷，如果將 與 邏輯合并可以?xún)?yōu)化到 2 次。
V2
為了解決上述問(wèn)題，我們想到了 Lex 和 Yacc。Lex 是 ，能夠幫助我們生成詞法分析器 ( )；Yacc 是 ，能夠幫助我們生成解析器 ()，完成語(yǔ)法分析。Lex 和 Yacc 是 Unix 系統(tǒng)的原生工具，Linux 與 MacOS 平臺(tái)也都自帶這兩個(gè)工具。既然已經(jīng)有前人為我們?cè)詷?shù)，我們?yōu)槭裁床怀脵C(jī)乘涼？
Lex & Yacc
Lex 和 Yacc 的協(xié)作過(guò)程如下圖所示：
開(kāi)發(fā)者將構(gòu)詞規(guī)則和一些定制化邏輯 (C Code) 定義到 lex.l 文件中，利用 lex 命令生成詞法分析器；將語(yǔ)法規(guī)則和一些定制化邏輯定義到 .y 文件中，利用 yacc 命令生成解析器。詞法分析器的 yylex 方法將輸入文本轉(zhuǎn)化成 token，投喂給 ，后者根據(jù)語(yǔ)法和定制化邏輯將 token 流轉(zhuǎn)化成最終的目標(biāo)數(shù)據(jù)結(jié)構(gòu)，即 IR。
：
以一個(gè)支持加減運(yùn)算的計(jì)算機(jī)為例，先定義語(yǔ)法規(guī)則：
復(fù)制代碼
// parser.y%token NUMBER%% // 括號(hào)中的 $ 表示語(yǔ)法左手邊 (LHS) 的值// 括號(hào)中的 $1、$2、$3 表示語(yǔ)法右手邊 (RHS) 的值statement: expression { printf("= %d\n", $1); } ; expression: NUMBER '+' NUMBER { $ = $1 + $3; } | NUMBER '-' NUMBER { $ = $1 - $3; } | NUMBER { $ = $1; } ;第一行的 token 定義語(yǔ)法中的數(shù)據(jù)類(lèi)型，由于單個(gè)字符本身沒(méi)有歧義，在 Lex 和 Yacc 無(wú)需特別定義單字符 token，如 + 和 -，因此在這里我們只需要數(shù)字 。在第一個(gè) %% 之后，定義了計(jì)算器的語(yǔ)法，含義非常直白，可讀性強(qiáng)。
然后再定義構(gòu)詞規(guī)則：
復(fù)制代碼
// lex.l%{#include "y.tab.h"extern int yylval;%} %%[0-9]+ { yylval = atoi(yytext); return NUMBER; }[ \t] ;\n return 0;. return yytext[0];%%在兩個(gè) %% 中間的就是構(gòu)詞規(guī)則：
接下來(lái)只需要用 lex 和 yacc 命令生成詞法分析器和解析器，然后運(yùn)行即可：
復(fù)制代碼
# MacOS$ lex lex.l$ yacc -d parser.y$ gcc y.tab.c lex.yy.c -ly -ll -o calculator$ ./calculator> 128 + 128> = 256對(duì)比分析
從代碼健壯性角度上看，lex 生成的詞法分析器已經(jīng)經(jīng)受時(shí)間的檢驗(yàn)，開(kāi)發(fā)者大可相信其代碼的健壯性；從可讀性角度看，構(gòu)詞規(guī)則和語(yǔ)法規(guī)則定義簡(jiǎn)短，通俗易懂；從可擴(kuò)展性角度看，任何可以通過(guò)上下文無(wú)關(guān)文法 (-free ) 表達(dá)的語(yǔ)法都能支持；從效率角度看，yylex 與 可以流式地處理文本， 從 yylex 獲取詞語(yǔ)，即時(shí)地根據(jù)語(yǔ)法規(guī)則組合成 IR，這種做法使得編譯前端的工作只需要 1 次遍歷便可完成。但 lex 和 yacc 為了支持更復(fù)雜的場(chǎng)景，其生成的代碼也會(huì)更復(fù)雜，這也是效率與通用性權(quán)衡的表現(xiàn)。
Nex &
報(bào)警平臺(tái)使用 Go 語(yǔ)言編碼，直接使用 lex 和 yacc 需要引入 cgo，這也使得二者的使用門(mén)檻變高。好在 Go 官方提供了 ，方便我們?cè)?.y 中引入用 Go 語(yǔ)言編寫(xiě)的定制化邏輯；斯坦福的一位博士 Ben Lynn 開(kāi)源了它的 nex 項(xiàng)目，作為用 Go 語(yǔ)言原生開(kāi)發(fā)的詞法分析器生成器，能與 兼容，形成類(lèi)似 lex 和 yacc 一般的搭檔。接下來(lái)我們將利用 nex 和 來(lái)實(shí)現(xiàn)匹配器編譯器。
與計(jì)算器的例子類(lèi)似，我們先看語(yǔ)法規(guī)則中定義的數(shù)據(jù)類(lèi)型：
復(fù)制代碼
%union{ str string expr *MatchExpr pexpr *PrimitiveExpr} %token LABEL VALUE%token REG_EQ AND OR %type expr%type pexpr %type LABEL VALUE%type REG_EQ AND OR 其中，語(yǔ)法中的數(shù)據(jù)類(lèi)型包括：
此外我們還定義了原始表達(dá)式 pexpr 和復(fù)合表達(dá)式 expr 供定義語(yǔ)法規(guī)則時(shí)引用。由于語(yǔ)法中有多種關(guān)系運(yùn)算符，它們的優(yōu)先級(jí)不同，因此我們還需要定義運(yùn)算符的優(yōu)先級(jí)：
復(fù)制代碼
%left OR%left AND%left '(' ')'left 表示先從運(yùn)算符的 LHS 開(kāi)始計(jì)算，三者的優(yōu)先級(jí)關(guān)系是 OR < AND < '(' == ')'，非常直觀。最后進(jìn)入我們的語(yǔ)法規(guī)則：
復(fù)制代碼
// 匹配器表達(dá)式可以是空字符串，也可以是一個(gè)合法的表達(dá)式matcher: { setResult(yylex, &Matcher{}) }| expr { setResult(yylex, $1) } // 表達(dá)式可能以下之一：// 復(fù)合表達(dá)式：expr AND expr// 復(fù)合表達(dá)式：expr OR expr// 原始表達(dá)式：pexpr// 括號(hào)表達(dá)式：(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 }// 原始表達(dá)式要么是 LABEL = VALUE, 要么是 LABEL =~ VALUEpexpr: LABEL '=' VALUE { $ = &PrimitiveMatcher{Label:$1, Text:$3, IsRegex: false} }| LABEL REG_EQ VALUE { $ = &PrimitiveMatcher{Label:$1, Text:$3, IsRegex: true} }每條語(yǔ)法規(guī)則的含義已經(jīng)標(biāo)明在注釋中，在每條語(yǔ)法規(guī)則之后，是 Go 語(yǔ)言編碼的簡(jiǎn)單邏輯，告訴解析器在不同情況下如何拼裝 IR。搞定語(yǔ)法后，我們就可以定義構(gòu)詞規(guī)則：
復(fù)制代碼
/[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 }/[ \t\r\n]+/ { /* white spaces ignored */ }//package c最后使用 nex 和 就可以生成詞法分析器和解析器：
復(fù)制代碼
$ nex nex.l$ goyacc -o parser.go parser.y然后再把二者串起來(lái)即可：
復(fù)制代碼
// 忽略細(xì)節(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
完成上面的工作，本可以告一段落，但有一個(gè)問(wèn)題還困擾著我們：”為什么 Go 只推出了 yacc 的移植版本，而不順便推出 lex 的移植版本？“ 幾經(jīng)周折找到了 Rob Pike 2011 年的一次演講： “ in Go”。在演講中他認(rèn)為 ” lex 生成的代碼太多，過(guò)于復(fù)雜，用 Go 語(yǔ)言實(shí)現(xiàn)一個(gè)并非難事，且 Go 的 能方便地實(shí)現(xiàn) lex 和 yacc 的流水線協(xié)作。“ 盡管這種觀點(diǎn)也是在為 Go 站臺(tái)，我們還是決定試一試他提出的 方案。
詞法分析的過(guò)程，就是從輸入字符流起點(diǎn)掃描至終點(diǎn)的線性過(guò)程，在掃描期間，詞法分析器需要正確地判斷自己所處的狀態(tài)，以起點(diǎn)為例，剛開(kāi)始掃描，可能進(jìn)入 LABEL 狀態(tài)，也可能進(jìn)入 ( 狀態(tài)：
復(fù)制代碼
labela = "a" AND (labelb = "b" OR labelc = "c")↑ 在 LABEL 中 (labela = "a") OR labelb = "b"↑在'('中掃描完 VALUE 后，可能進(jìn)入結(jié)束狀態(tài)，也可能進(jìn)入 ) 狀態(tài)或 關(guān)系運(yùn)算符 狀態(tài)：
復(fù)制代碼
labela = "a" AND (labelb = "b" OR labelc = "c") ↑ 進(jìn)入 [關(guān)系運(yùn)算符] 狀態(tài)(labela = "a") ↑ 進(jìn)入 ')' 狀態(tài)labela = "a" ↑ 進(jìn)入 [結(jié)束] 狀態(tài)不難看出，這實(shí)際上就是一個(gè)狀態(tài)機(jī)，詳細(xì)的狀態(tài)轉(zhuǎn)移過(guò)程如下圖所示：
復(fù)制代碼
# start: [開(kāi)始]; leftParen: '('; label: [標(biāo)簽]; eq: [匹配符]; value: [文本];# rightParen: ')'; binaryOp: [關(guān)系運(yùn)算符]; end: [結(jié)束] +------------+ | rightParen | -------------+ +------------+ | ^ | | | | | +----------------------+ | ----------------+ | | v | v | | +-----------+ +-------+ +----+ +------------+ +-----+ | | | start | --> | label | --> | eq | --> | value | --> | end | | | +-----------+ +-------+ +----+ +------------+ +-----+ | | | ^ | | | | | | | | v | v | | +-----------+ | +------------+ | +- | leftParen | +--------------------- | binaryOp | <------------+ +-----------+ +------------+ ^ | +------------------------------------------+ 接下來(lái)就需要讓這個(gè)狀態(tài)機(jī)動(dòng)起來(lái)：
復(fù)制代碼
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)}其中 就是狀態(tài)轉(zhuǎn)移方程yy直播模板加載中，約定當(dāng) == nil 時(shí)，狀態(tài)機(jī)停止，即 nil 就是結(jié)束狀態(tài)的轉(zhuǎn)移方程。接下來(lái)只需要定義各個(gè)狀態(tài)轉(zhuǎn)移方程即可：
復(fù)制代碼
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 {}每當(dāng)狀態(tài)即將轉(zhuǎn)移時(shí)， 內(nèi)部就會(huì)將在本狀態(tài)中掃描到的詞語(yǔ)傳給 item ，這個(gè) 就是 lexer 與 之間通信的媒介。
值得一提的是，Go 的模板引擎 ，就是按照上述方式構(gòu)建的，感興趣可以閱讀源碼。
參考文獻(xiàn)
關(guān)注我并轉(zhuǎn)發(fā)此篇文章，私信我“領(lǐng)取資料”，即可免費(fèi)獲得InfoQ價(jià)值4999元迷你書(shū)！
友情鏈接： 餐飲加盟
地址：北京市海淀區(qū) 電話(huà)：010- 郵箱：@126.com
備案號(hào)：冀ICP備2024067069號(hào)-3 北京科技有限公司版權(quán)所有