背景
領域特定語言（DSL），如 SQL、Elasticsearch Querystring 等，往往是為專門的目的設計的。在特定的任務中，DSL 通過在表達能力上做的妥協換取在某一領域內的高效。
在飛書套件日志系統的私有化研發過程中，為了符合研發同學查詢日志的習慣，嘗試使用 Elasticquery Querystring（下簡稱為 Querystring）作為過濾器的查詢條件語句，由此需要可用的 Golang Querystring 解析器。由于目前開源界無法找到完善的實現，嘗試使用 Goyacc 自行構建。
Yacc 是一個被普遍采用的編譯器代碼生成器，生成出的代碼主要用于語法分析階段，常常與作為詞法分析器的 lex 匹配使用，使用 LALR 算法，將源代碼構建為抽象語法樹（AST）。Goyacc 是 yacc 的 Golang 版本。
本文嘗試實現的 Querystring 解析器本質上是詞法分析器和語法分析器的組合。語法分析器由 Goyacc 生成；為了方便實現符合 Querystring 習慣的反轉義，詞法分析器是自行實現的。Yacc 和它在各個語言上的實現，中文互聯網上較少有具體的介紹。本文會盡量詳細的描述 Goyacc 實踐中可能需要注意的點。所述的 Querystring 解析器代碼可在 https://github.com/bytedance/go-querystring-parser 此處查看。
框架
一套完整的應用 Goyacc 的 DSL 解析器包含以下部分：
- 語法分析器（parser）
- 詞法分析器（lexer）
- 較為簡單的做法，是采用Scanner來進行構建；當存在特殊需求時，一般自行構建。
- AST 節點的定義
- 包裝實體與工具函數
大致流程為，語法分析器調用詞法分析器將源代碼拆解為基本「Token（記號）」，根據語法規程將若干個「Token」組合成「Expr（表達式）」（Token 本身也被作為 Expr 處理）。「Expr」的結構構建在「AST」中，得到結果。
語法分析器
語法分析（syntactic analysis，或 parsing）是根據某種給定的形式文法對由記號序列構成的輸入文本進行分析并確定其語法結構的一種過程。
語法分析器的作用是進行語法檢查、并構建由輸入的記號組成的數據結構（一般是語法分析樹、抽象語法樹等層次化的數據結構）。語法分析器通常使用一個獨立的詞法分析器從輸入字符流中分離出一個個的「記號」，并將記號流作為其輸入。實際開發中，語法分析器可以手工編寫，也可以使用工具（半）自動生成。
在本例中，即為工具自動生成。使用巴科斯范式描述對應的語法定義，并使用 goyacc 生成 golang 代碼，提供一個 LALR 語法分析器，并定義了供 lexer 返回的 token 定義。
安裝 Goyacc
在安裝了 golang 的環境中，執行：
go get -u golang.org/x/tools/cmd/goyacc
如安裝后無法正常運行，請檢查 $GOPATH/bin? 是否加入到了 $PATH 中。
Goyacc 語法定義文件
一個 yacc 語法定義文件，一般由以下若干部分構成。
頭部目標語言代碼
可參考「附錄一:L1-L3」，使用 %{? 和 }% 將需要的目標語言原生代碼段落包圍起來。目標語言往往涉及到語言應用中的一些頭部代碼。在例子里，golang 所需的包名稱定義等需要通過這一部分添加進來。其他的例子如常量的定義、結構體的定義等。
Union（集合）聲明
可參考「附錄一:L5-L9」，以 %union{}? 格式定義，只可定義一次?！窾nion」這一概念包含了下述類型聲明中的各個類型，及這些類型對應的目標語言類型（即 Golang 中的類型）。與 c 語言中 union 的概念類似，在目標代碼中（生成為 yySymType?），union 將被生成為一個結構體（struct），根據「類型聲明」，將匹配出的值放到結構體的對應字段中，作為存放/傳遞值的媒介而存在。在例子中，s?即為string?，類型聲明中凡是標記為 s 類型的「表達式」，都會被保存到s字段中。
Token（記號）聲明
可參考「附錄一:L11-L14」，以 %token 為行首的記號聲明列表。對于 lexer 會直接分析出的 token，需要通過「Token 聲明」來列出。Token 聲明本身不需要關注順序和組合，只需要單獨列出需要由 lexer 輸出的 token 類型即可。
Type（類型）聲明
可參考「附錄一:L11-L14」，以 %type <%TYPE%>? 為行首的記號聲明列表，%TYPE% 為本行所列舉的「Expr」將會保存到的 union 中的字段/類型。
聲明與語法定義規則間的分隔符
各個聲明與語法規則定義間，以 %% 分隔（L23）。
語法規則定義
可參考「附錄一:L25-L202」，語法規則使用巴科斯范式（Backus Normal Form，縮寫為 BNF）定義。在 Goyacc（及它仿造的 yacc）中，以摘自「附錄一:L53-L64」定義的一個 expr 為例，大致由以下部分構成：
searchLogicPart:
searchLogicSimplePart {
$$ = $1
}
|
searchLogicSimplePart tAND searchLogicPart {
$$ = NewAndCondition($1, $3)
}
|
searchLogicSimplePart tOR searchLogicPart {
$$ = NewOrCondition($1, $3)
};
L1 被定義的 expr 的名稱，本例中 expr 的名稱為searchLogicPart，在其他位置上將通過這個名稱來引用這個 expr 及其格式定義。
L2-L4、L6-L8、L10-L12 expr 語法規則，以 L6-L8 部分為例，由兩個部分構成：
L6 匹配格式，本語句由三個部分構成，分別是：
- 一個searchLogicSimplePart expr，在「附錄一:L66」處定義，邏輯語句的單一元素，或 NOT 邏輯元素，或使用括號強制優先結合的若干元素集合。
- 一個tAND? expr，實際上為 token，在 lexer 中分析并給出的類型，源碼中為AND。
- 一個searchLogicPart expr，即本段落中定義的語句。
- L7 行為（action），即匹配完成后對匹配到的元素進行的行為，在匹配格式后以{、} 包圍
- 實際上是代碼生成模板，以目標語言（Golang）完成
- $$ 將生成為當前 expr 的 union 中對應的字段
- 例如 L7 中的$$?，因searchLogicPart? 在 type 聲明中，使用的 type 是 q（見「附錄一:L20」），因此將生成為yyVAL.q。
- 以此類推，$1、$3? 分別將生成為第一個匹配項和第三個匹配項對應的類型字段，也即第一和第三匹配項的值，根據類型定義，即yyDollar[1].q? 和yyDollar[3].q。
- L7 在目標代碼中，將生成為yyVAL.q = NewAndCondition(yyDollar[1].q,yyDollar[3].q)，NewAndCondition 為另行定義的函數。也即使用匹配到的第一個項和第三個項，構成一個 AND 邏輯組合條件。
- 行為可以由不定行代碼生成模板構成。
L5、L9 使用| 分隔 expr 可能的語法規則，也就是說，將匹配三種規則中的任意一種。
L12 一個 expr 語法規則定義完成后，使用; 作為結尾。需要額外注意的點：
對語法的定義不應當有二義性，也不可以對不定個數的元素進行匹配。
在有需要的場景下，可以直接操作 parser 函數上下文中含有的其他變量。
- 如 AST 根的輸出，「附錄一:L27」語句。
Goyacc 的生成
使用命令 goyacc -o querystring.y.go querystring.y 生成目標語言代碼，在 yacc 定義中使用的 golang 函數/結構體等，都應當預先定義在同一包/目標語言代碼中。
目標語言代碼的使用
生成出的代碼，將包含一個主入口 yyParse? 函數。主入口函數接收 yyLexer 即詞法分析器實例這一參數。在實際使用中，可使用詞法分析器實例將分析結果 AST 返回。
詞法分析器
詞法分析（lexical analysis）是計算機科學中將字符序列轉換為記號（token）序列的過程。進行詞法分析的程序或者函數叫作詞法分析器（lexical analyzer，簡稱 lexer），也叫掃描器（scanner）。詞法分析器一般以函數的形式存在，供語法分析器調用。
這里的記號是一個字串，是構成源代碼的最小單位。在這個過程中，詞法分析器還會對記號進行分類。
在 Goyacc 的實際使用中，詞法分析器提供了三個特性：
- 詞法分析，即Lex(lval *yySymType) (tokenType int)? 函數，從源代碼流中，讀出下一個記號，將這一記號的值通過傳入的 union 指針返回（即lval?），將這一記號的類型通過返回值返回（即tokenType）。
- 錯誤記錄，即Error(s string) 函數。
- AST 的返回，由于 yyParse 沒有提供其他有效的返回途徑，這一實例還作為整體解析上下文來使用，帶回解析完成的 AST。
一個較為簡單的實現方式，是使用 Scanner 配合對字符的匹配，將值放置于傳入的指針，并返回對應的類型。由于 Querystring 在轉義/反轉義上的特殊習慣，本例中對應的 lexer 是自行實現的。
實現一個詞法分析器，大致需要以下部分：
- 一個字符串流，記錄了內容、目前讀到的位置等信息
- 當前狀態的管理
AST 節點的定義
根據語法的定義，構建 AST 的過程中，需要根據語義分別使用不同的節點類型，以方便對 AST 的使用。這一過程中，需要對 AST 節點進行定義。
在 Querystring AST 中，定義了以下類型的節點，并提供了若干工具函數：
- AndCondition，與邏輯條件
- OrCondition，或邏輯條件
- NotCondition，非邏輯條件
- MatchCondition，匹配條件，根據字段類型決定為全等匹配或全文匹配
- RegexpCondition，正則條件
- WildcardCondition，通配符條件
- NumberRangeCondition，數值 Range 條件，數值相關的各類條件都歸一到此類
- TimeRangeCondition，時間 Range 條件，時間相關的各類條件都歸一到此類
某些開源庫中，會在這一部分添加遍歷相關的 Method，以方便使用者對 AST 進行遍歷。
包裝實體與工具函數
由于語法分析器提供的函數多為私有函數，也需要通過詞法分析器對輸入的源代碼進行包裹，一般需要若干個工具函數。
本例中，主要提供了解析入口函數，主要功能為：輸入一個 Querystring 格式的字符串，使用 lexer 實例進行包裝，運行 parser，并返回過程中輸出的錯誤。
AST 的使用
Querystring 作為查詢條件，使用過程中，一般需要注意以下幾個問題：
- 查詢條件的優化。用戶輸入的查詢條件經常是無序的：有時相同的條件會多次出現在不同的位置，可以予以合并；對同一字段的過濾行為可以合并在一起，來降低 local cache 成本；有的條件可能是邏輯上無效的，可以剔除。
- 類型推斷。在數值類型中，根據 Elasticsearch 的官方實現，Querystring 中形似數字的值，可能作為整數、浮點數、字符串或時間處理。應當通過被過濾的數據的情況，對值的類型做二次推斷。
附錄一：Querystring goyacc 定義
也可通過 https://github.com/bytedance/go-querystring-parser/blob/main/querystring.y 查看
%{
package querystring
%}
%union {
s string
n int
q Condition
}
%token tSTRING tPHRASE tNUMBER
%token tAND tOR tNOT tTO tPLUS tMINUS tCOLON
%token tLEFTBRACKET tRIGHTBRACKET tLEFTRANGE tRIGHTRANGE
%token tGREATER tLESS tEQUAL
%type <s> tSTRING
%type <s> tPHRASE
%type <s> tNUMBER
%type <s> posOrNegNumber
%type <q> searchBase searchParts searchPart searchLogicPart searchLogicSimplePart
%type <n> searchPrefix
%%
input:
searchParts {
yylex.(*lexerWrapper).query = $1
};
searchParts:
searchPart searchParts {
$$ = NewAndCondition($1, $2)
}
|
searchPart {
$$ = $1
};
searchPart:
searchPrefix searchBase {
switch($1) {
case queryMustNot:
$$ = NewNotCondition($2)
default:
$$ = $2
}
}
|
searchLogicPart {
$$ = $1
};
searchLogicPart:
searchLogicSimplePart {
$$ = $1
}
|
searchLogicSimplePart tAND searchLogicPart {
$$ = NewAndCondition($1, $3)
}
|
searchLogicSimplePart tOR searchLogicPart {
$$ = NewOrCondition($1, $3)
};
searchLogicSimplePart:
searchBase {
$$ = $1
}
|
tLEFTBRACKET searchLogicPart tRIGHTBRACKET {
$$ = $2
}
|
tNOT searchLogicSimplePart {
$$ = NewNotCondition($2)
};
searchPrefix:
tPLUS {
$$ = queryMust
}
|
tMINUS {
$$ = queryMustNot
};
searchBase:
tSTRING {
$$ = newStringCondition($1)
}
|
tNUMBER {
$$ = NewMatchCondition($1)
}
|
tPHRASE {
phrase := $1
q := NewMatchCondition(phrase)
$$ = q
}
|
tSTRING tCOLON tSTRING {
q := newStringCondition($3)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON posOrNegNumber {
val := $3
q := NewNumberRangeCondition(&val, &val, true, true)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON tPHRASE {
q := NewMatchCondition($3)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON tGREATER posOrNegNumber {
val := $4
q := NewNumberRangeCondition(&val, nil, false, false)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON tGREATER tEQUAL posOrNegNumber {
val := $5
q := NewNumberRangeCondition(&val, nil, true, false)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON tLESS posOrNegNumber {
val := $4
q := NewNumberRangeCondition(nil, &val, false, false)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON tLESS tEQUAL posOrNegNumber {
val := $5
q := NewNumberRangeCondition(nil, &val, false, true)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON tGREATER tPHRASE {
phrase := $4
q := NewTimeRangeCondition(&phrase, nil, false, false)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON tGREATER tEQUAL tPHRASE {
phrase := $5
q := NewTimeRangeCondition(&phrase, nil, true, false)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON tLESS tPHRASE {
phrase := $4
q := NewTimeRangeCondition(nil, &phrase, false, false)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON tLESS tEQUAL tPHRASE {
phrase := $5
q := NewTimeRangeCondition(nil, &phrase, false, true)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON tLEFTRANGE posOrNegNumber tTO posOrNegNumber tRIGHTRANGE {
min := $4
max := $6
q := NewNumberRangeCondition(&min, &max, true, true)
q.SetField($1)
$$ = q
}
|
tSTRING tCOLON tLEFTRANGE tPHRASE tTO tPHRASE tRIGHTRANGE {
min := $4
max := $6
q := NewTimeRangeCondition(&min, &max, true, true)
q.SetField($1)
$$ = q
};
posOrNegNumber:
tNUMBER {
$$ = $1
}
|
tMINUS tNUMBER {
$$ = "-" + $2
};附錄二：參考鏈接
- https://godoc.org/golang.org/x/tools/cmd/goyacc
- https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form
- https://about.sourcegraph.com/go/gophercon-2018-how-to-write-a-parser-in-go/
- https://github.com/xwb1989/sqlparser
- https://www.lysator.liu.se/c/ANSI-C-grammar-y.html
