自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

通過(guò) Goyacc 構(gòu)建 Elasticsearch Querystring 解析器 - 領(lǐng)域特定語(yǔ)言語(yǔ)法分析實(shí)踐

原創(chuàng) 精選
作者： 字節(jié)跳動(dòng)技術(shù)團(tuán)隊(duì)
開(kāi)發(fā)
本文嘗試實(shí)現(xiàn)的 Querystring 解析器本質(zhì)上是詞法分析器和語(yǔ)法分析器的組合。語(yǔ)法分析器由 Goyacc 生成；為了方便實(shí)現(xiàn)符合 Querystring 習(xí)慣的反轉(zhuǎn)義，詞法分析器是自行實(shí)現(xiàn)的。

背景

領(lǐng)域特定語(yǔ)言（DSL），如 SQL、Elasticsearch Querystring 等，往往是為專(zhuān)門(mén)的目的設(shè)計(jì)的。在特定的任務(wù)中，DSL 通過(guò)在表達(dá)能力上做的妥協(xié)換取在某一領(lǐng)域內(nèi)的高效。

在飛書(shū)套件日志系統(tǒng)的私有化研發(fā)過(guò)程中，為了符合研發(fā)同學(xué)查詢(xún)?nèi)罩镜牧?xí)慣，嘗試使用 Elasticquery Querystring（下簡(jiǎn)稱(chēng)為 Querystring）作為過(guò)濾器的查詢(xún)條件語(yǔ)句，由此需要可用的 Golang Querystring 解析器。由于目前開(kāi)源界無(wú)法找到完善的實(shí)現(xiàn)，嘗試使用 Goyacc 自行構(gòu)建。

Yacc 是一個(gè)被普遍采用的編譯器代碼生成器，生成出的代碼主要用于語(yǔ)法分析階段，常常與作為詞法分析器的 lex 匹配使用，使用 LALR 算法，將源代碼構(gòu)建為抽象語(yǔ)法樹(shù)（AST）。Goyacc 是 yacc 的 Golang 版本。

本文嘗試實(shí)現(xiàn)的 Querystring 解析器本質(zhì)上是詞法分析器和語(yǔ)法分析器的組合。語(yǔ)法分析器由 Goyacc 生成；為了方便實(shí)現(xiàn)符合 Querystring 習(xí)慣的反轉(zhuǎn)義，詞法分析器是自行實(shí)現(xiàn)的。Yacc 和它在各個(gè)語(yǔ)言上的實(shí)現(xiàn)，中文互聯(lián)網(wǎng)上較少有具體的介紹。本文會(huì)盡量詳細(xì)的描述 Goyacc 實(shí)踐中可能需要注意的點(diǎn)。所述的 Querystring 解析器代碼可在 https://github.com/bytedance/go-querystring-parser 此處查看。

框架

一套完整的應(yīng)用 Goyacc 的 DSL 解析器包含以下部分：

  1. 語(yǔ)法分析器（parser）
  2. 詞法分析器（lexer）
  • 較為簡(jiǎn)單的做法，是采用Scanner來(lái)進(jìn)行構(gòu)建；當(dāng)存在特殊需求時(shí)，一般自行構(gòu)建。
  1. AST 節(jié)點(diǎn)的定義
  2. 包裝實(shí)體與工具函數(shù)

大致流程為，語(yǔ)法分析器調(diào)用詞法分析器將源代碼拆解為基本「Token（記號(hào)）」，根據(jù)語(yǔ)法規(guī)程將若干個(gè)「Token」組合成「Expr（表達(dá)式）」（Token 本身也被作為 Expr 處理）。「Expr」的結(jié)構(gòu)構(gòu)建在「AST」中，得到結(jié)果。

語(yǔ)法分析器

語(yǔ)法分析（syntactic analysis，或 parsing）是根據(jù)某種給定的形式文法對(duì)由記號(hào)序列構(gòu)成的輸入文本進(jìn)行分析并確定其語(yǔ)法結(jié)構(gòu)的一種過(guò)程。

語(yǔ)法分析器的作用是進(jìn)行語(yǔ)法檢查、并構(gòu)建由輸入的記號(hào)組成的數(shù)據(jù)結(jié)構(gòu)（一般是語(yǔ)法分析樹(shù)、抽象語(yǔ)法樹(shù)等層次化的數(shù)據(jù)結(jié)構(gòu)）。語(yǔ)法分析器通常使用一個(gè)獨(dú)立的詞法分析器從輸入字符流中分離出一個(gè)個(gè)的「記號(hào)」，并將記號(hào)流作為其輸入。實(shí)際開(kāi)發(fā)中，語(yǔ)法分析器可以手工編寫(xiě)，也可以使用工具（半）自動(dòng)生成。

在本例中，即為工具自動(dòng)生成。使用巴科斯范式描述對(duì)應(yīng)的語(yǔ)法定義，并使用 goyacc 生成 golang 代碼，提供一個(gè) LALR 語(yǔ)法分析器，并定義了供 lexer 返回的 token 定義。

安裝 Goyacc

在安裝了 golang 的環(huán)境中，執(zhí)行：

go get -u golang.org/x/tools/cmd/goyacc

如安裝后無(wú)法正常運(yùn)行，請(qǐng)檢查 $GOPATH/bin? 是否加入到了 $PATH 中。

Goyacc 語(yǔ)法定義文件

一個(gè) yacc 語(yǔ)法定義文件，一般由以下若干部分構(gòu)成。

頭部目標(biāo)語(yǔ)言代碼

可參考「附錄一:L1-L3」，使用 %{? 和 }% 將需要的目標(biāo)語(yǔ)言原生代碼段落包圍起來(lái)。目標(biāo)語(yǔ)言往往涉及到語(yǔ)言應(yīng)用中的一些頭部代碼。在例子里，golang 所需的包名稱(chēng)定義等需要通過(guò)這一部分添加進(jìn)來(lái)。其他的例子如常量的定義、結(jié)構(gòu)體的定義等。

Union（集合）聲明

可參考「附錄一:L5-L9」，以 %union{}? 格式定義，只可定義一次?！窾nion」這一概念包含了下述類(lèi)型聲明中的各個(gè)類(lèi)型，及這些類(lèi)型對(duì)應(yīng)的目標(biāo)語(yǔ)言類(lèi)型（即 Golang 中的類(lèi)型）。與 c 語(yǔ)言中 union 的概念類(lèi)似，在目標(biāo)代碼中（生成為 yySymType?），union 將被生成為一個(gè)結(jié)構(gòu)體（struct），根據(jù)「類(lèi)型聲明」，將匹配出的值放到結(jié)構(gòu)體的對(duì)應(yīng)字段中，作為存放/傳遞值的媒介而存在。在例子中，s?即為string?，類(lèi)型聲明中凡是標(biāo)記為 s 類(lèi)型的「表達(dá)式」，都會(huì)被保存到s字段中。

Token（記號(hào)）聲明

可參考「附錄一:L11-L14」，以 %token 為行首的記號(hào)聲明列表。對(duì)于 lexer 會(huì)直接分析出的 token，需要通過(guò)「Token 聲明」來(lái)列出。Token 聲明本身不需要關(guān)注順序和組合，只需要單獨(dú)列出需要由 lexer 輸出的 token 類(lèi)型即可。

Type（類(lèi)型）聲明

可參考「附錄一:L11-L14」，以 %type <%TYPE%>? 為行首的記號(hào)聲明列表，%TYPE% 為本行所列舉的「Expr」將會(huì)保存到的 union 中的字段/類(lèi)型。

聲明與語(yǔ)法定義規(guī)則間的分隔符

各個(gè)聲明與語(yǔ)法規(guī)則定義間，以 %% 分隔（L23）。

語(yǔ)法規(guī)則定義

可參考「附錄一:L25-L202」，語(yǔ)法規(guī)則使用巴科斯范式（Backus Normal Form，縮寫(xiě)為 BNF）定義。在 Goyacc（及它仿造的 yacc）中，以摘自「附錄一:L53-L64」定義的一個(gè) expr 為例，大致由以下部分構(gòu)成：

searchLogicPart:
searchLogicSimplePart {
    $$ = $1
}
|
searchLogicSimplePart tAND searchLogicPart {
    $$ = NewAndCondition($1, $3)
}
|
searchLogicSimplePart tOR searchLogicPart {
    $$ = NewOrCondition($1, $3)
};

L1 被定義的 expr 的名稱(chēng)，本例中 expr 的名稱(chēng)為searchLogicPart，在其他位置上將通過(guò)這個(gè)名稱(chēng)來(lái)引用這個(gè) expr 及其格式定義。

L2-L4、L6-L8、L10-L12 expr 語(yǔ)法規(guī)則，以 L6-L8 部分為例，由兩個(gè)部分構(gòu)成：

L6 匹配格式，本語(yǔ)句由三個(gè)部分構(gòu)成，分別是：

  • 一個(gè)searchLogicSimplePart expr，在「附錄一:L66」處定義，邏輯語(yǔ)句的單一元素，或 NOT 邏輯元素，或使用括號(hào)強(qiáng)制優(yōu)先結(jié)合的若干元素集合。
  • 一個(gè)tAND? expr，實(shí)際上為 token，在 lexer 中分析并給出的類(lèi)型，源碼中為AND。
  • 一個(gè)searchLogicPart expr，即本段落中定義的語(yǔ)句。
  • L7 行為（action），即匹配完成后對(duì)匹配到的元素進(jìn)行的行為，在匹配格式后以{、} 包圍
  • 實(shí)際上是代碼生成模板，以目標(biāo)語(yǔ)言（Golang）完成
  • $$ 將生成為當(dāng)前 expr 的 union 中對(duì)應(yīng)的字段
  • 例如 L7 中的$$?，因searchLogicPart? 在 type 聲明中，使用的 type 是 q（見(jiàn)「附錄一:L20」），因此將生成為yyVAL.q。
  • 以此類(lèi)推，$1、$3? 分別將生成為第一個(gè)匹配項(xiàng)和第三個(gè)匹配項(xiàng)對(duì)應(yīng)的類(lèi)型字段，也即第一和第三匹配項(xiàng)的值，根據(jù)類(lèi)型定義，即yyDollar[1].q? 和yyDollar[3].q。
  • L7 在目標(biāo)代碼中，將生成為yyVAL.q = NewAndCondition(yyDollar[1].q,yyDollar[3].q)，NewAndCondition 為另行定義的函數(shù)。也即使用匹配到的第一個(gè)項(xiàng)和第三個(gè)項(xiàng)，構(gòu)成一個(gè) AND 邏輯組合條件。
  • 行為可以由不定行代碼生成模板構(gòu)成。

L5、L9 使用| 分隔 expr 可能的語(yǔ)法規(guī)則，也就是說(shuō)，將匹配三種規(guī)則中的任意一種。

L12 一個(gè) expr 語(yǔ)法規(guī)則定義完成后，使用; 作為結(jié)尾。需要額外注意的點(diǎn)：

對(duì)語(yǔ)法的定義不應(yīng)當(dāng)有二義性，也不可以對(duì)不定個(gè)數(shù)的元素進(jìn)行匹配。

在有需要的場(chǎng)景下，可以直接操作 parser 函數(shù)上下文中含有的其他變量。

  • 如 AST 根的輸出，「附錄一:L27」語(yǔ)句。

Goyacc 的生成

使用命令 goyacc -o querystring.y.go querystring.y 生成目標(biāo)語(yǔ)言代碼，在 yacc 定義中使用的 golang 函數(shù)/結(jié)構(gòu)體等，都應(yīng)當(dāng)預(yù)先定義在同一包/目標(biāo)語(yǔ)言代碼中。

目標(biāo)語(yǔ)言代碼的使用

生成出的代碼，將包含一個(gè)主入口 yyParse? 函數(shù)。主入口函數(shù)接收 yyLexer 即詞法分析器實(shí)例這一參數(shù)。在實(shí)際使用中，可使用詞法分析器實(shí)例將分析結(jié)果 AST 返回。

詞法分析器

詞法分析（lexical analysis）是計(jì)算機(jī)科學(xué)中將字符序列轉(zhuǎn)換為記號(hào)（token）序列的過(guò)程。進(jìn)行詞法分析的程序或者函數(shù)叫作詞法分析器（lexical analyzer，簡(jiǎn)稱(chēng) lexer），也叫掃描器（scanner）。詞法分析器一般以函數(shù)的形式存在，供語(yǔ)法分析器調(diào)用。

這里的記號(hào)是一個(gè)字串，是構(gòu)成源代碼的最小單位。在這個(gè)過(guò)程中，詞法分析器還會(huì)對(duì)記號(hào)進(jìn)行分類(lèi)。

在 Goyacc 的實(shí)際使用中，詞法分析器提供了三個(gè)特性：

  • 詞法分析，即Lex(lval *yySymType) (tokenType int)? 函數(shù)，從源代碼流中，讀出下一個(gè)記號(hào)，將這一記號(hào)的值通過(guò)傳入的 union 指針?lè)祷兀磍val?），將這一記號(hào)的類(lèi)型通過(guò)返回值返回（即tokenType）。
  • 錯(cuò)誤記錄，即Error(s string) 函數(shù)。
  • AST 的返回，由于 yyParse 沒(méi)有提供其他有效的返回途徑，這一實(shí)例還作為整體解析上下文來(lái)使用，帶回解析完成的 AST。

一個(gè)較為簡(jiǎn)單的實(shí)現(xiàn)方式，是使用 Scanner 配合對(duì)字符的匹配，將值放置于傳入的指針，并返回對(duì)應(yīng)的類(lèi)型。由于 Querystring 在轉(zhuǎn)義/反轉(zhuǎn)義上的特殊習(xí)慣，本例中對(duì)應(yīng)的 lexer 是自行實(shí)現(xiàn)的。

實(shí)現(xiàn)一個(gè)詞法分析器，大致需要以下部分：

  • 一個(gè)字符串流，記錄了內(nèi)容、目前讀到的位置等信息
  • 當(dāng)前狀態(tài)的管理

AST 節(jié)點(diǎn)的定義

根據(jù)語(yǔ)法的定義，構(gòu)建 AST 的過(guò)程中，需要根據(jù)語(yǔ)義分別使用不同的節(jié)點(diǎn)類(lèi)型，以方便對(duì) AST 的使用。這一過(guò)程中，需要對(duì) AST 節(jié)點(diǎn)進(jìn)行定義。

在 Querystring AST 中，定義了以下類(lèi)型的節(jié)點(diǎn)，并提供了若干工具函數(shù)：

  • AndCondition，與邏輯條件
  • OrCondition，或邏輯條件
  • NotCondition，非邏輯條件
  • MatchCondition，匹配條件，根據(jù)字段類(lèi)型決定為全等匹配或全文匹配
  • RegexpCondition，正則條件
  • WildcardCondition，通配符條件
  • NumberRangeCondition，數(shù)值 Range 條件，數(shù)值相關(guān)的各類(lèi)條件都?xì)w一到此類(lèi)
  • TimeRangeCondition，時(shí)間 Range 條件，時(shí)間相關(guān)的各類(lèi)條件都?xì)w一到此類(lèi)

某些開(kāi)源庫(kù)中，會(huì)在這一部分添加遍歷相關(guān)的 Method，以方便使用者對(duì) AST 進(jìn)行遍歷。

包裝實(shí)體與工具函數(shù)

由于語(yǔ)法分析器提供的函數(shù)多為私有函數(shù)，也需要通過(guò)詞法分析器對(duì)輸入的源代碼進(jìn)行包裹，一般需要若干個(gè)工具函數(shù)。

本例中，主要提供了解析入口函數(shù)，主要功能為：輸入一個(gè) Querystring 格式的字符串，使用 lexer 實(shí)例進(jìn)行包裝，運(yùn)行 parser，并返回過(guò)程中輸出的錯(cuò)誤。

AST 的使用

Querystring 作為查詢(xún)條件，使用過(guò)程中，一般需要注意以下幾個(gè)問(wèn)題：

  • 查詢(xún)條件的優(yōu)化。用戶(hù)輸入的查詢(xún)條件經(jīng)常是無(wú)序的：有時(shí)相同的條件會(huì)多次出現(xiàn)在不同的位置，可以予以合并；對(duì)同一字段的過(guò)濾行為可以合并在一起，來(lái)降低 local cache 成本；有的條件可能是邏輯上無(wú)效的，可以剔除。
  • 類(lèi)型推斷。在數(shù)值類(lèi)型中，根據(jù) Elasticsearch 的官方實(shí)現(xiàn)，Querystring 中形似數(shù)字的值，可能作為整數(shù)、浮點(diǎn)數(shù)、字符串或時(shí)間處理。應(yīng)當(dāng)通過(guò)被過(guò)濾的數(shù)據(jù)的情況，對(duì)值的類(lèi)型做二次推斷。

附錄一：Querystring goyacc 定義

也可通過(guò) 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
責(zé)任編輯：未麗燕 來(lái)源： 字節(jié)跳動(dòng)技術(shù)團(tuán)隊(duì)
語(yǔ)法分析器GoyaccAST
相關(guān)推薦

2021-06-07 21:02:44

語(yǔ)言業(yè)務(wù)領(lǐng)域

2009-08-27 09:16:48

F#中DSL原型設(shè)計(jì)

2020-03-04 11:20:22

DSL開(kāi)發(fā)領(lǐng)域特定語(yǔ)言

2009-03-12 14:31:15

QCon

2011-08-25 10:24:27

Lua

2021-03-18 10:56:59

SpringMVC參數(shù)解析器

2019-07-05 08:39:39

GoSQL解析器

2011-09-23 09:47:48

編程

2010-01-12 09:39:58

C++語(yǔ)言

2011-02-24 13:52:46

Opera 11HTML5

2009-03-19 09:26:05

RSS解析器MagpieRSS

2009-06-19 11:42:09

Scala計(jì)算器解析

2017-08-21 16:36:12

語(yǔ)法樹(shù)AST解析器HTML5

2020-12-02 10:13:45

JacksonJDK解析器

2010-02-22 13:38:50

Python解析器

2010-02-22 16:51:03

Python 解析器

2021-06-11 09:21:20

開(kāi)源SQL Parser詞法語(yǔ)法分析器

2023-05-29 08:00:00

ChatGPT人工智能機(jī)器學(xué)習(xí)

2024-12-17 06:20:00

MySQLSQL語(yǔ)句數(shù)據(jù)庫(kù)

2022-02-14 13:58:32

操作系統(tǒng)JSON格式鴻蒙
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)