通过 Goyacc 构建 Elasticsearch Querystring 解析器 - 领域特定语言语法分析实践

领域特定语言（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 解析器包含以下部分：,大致流程为，语法分析器调用词法分析器将源代码拆解为基本「Token（记号）」，根据语法规程将若干个「Token」组合成「Expr（表达式）」（Token 本身也被作为 Expr 处理）。「Expr」的结构构建在「AST」中，得到结果。,语法分析（syntactic analysis，或 parsing）是根据某种给定的形式文法对由记号序列构成的输入文本进行分析并确定其语法结构的一种过程。,语法分析器的作用是进行语法检查、并构建由输入的记号组成的数据结构（一般是语法分析树、抽象语法树等层次化的数据结构）。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的「记号」，并将记号流作为其输入。实际开发中，语法分析器可以手工编写，也可以使用工具（半）自动生成。,在本例中，即为工具自动生成。使用巴科斯范式描述对应的语法定义，并使用 goyacc 生成 golang 代码，提供一个 LALR 语法分析器，并定义了供 lexer 返回的 token 定义。,在安装了 golang 的环境中，执行：,如安装后无法正常运行，请检查 $GOPATH/bin​ 是否加入到了 $PATH 中。,一个 yacc 语法定义文件，一般由以下若干部分构成。,可参考「附录一:L1-L3」，使用 %{​ 和 }% 将需要的目标语言原生代码段落包围起来。目标语言往往涉及到语言应用中的一些头部代码。在例子里，golang 所需的包名称定义等需要通过这一部分添加进来。其他的例子如常量的定义、结构体的定义等。,可参考「附录一:L5-L9」，以 %union{}​ 格式定义，只可定义一次。「Union」这一概念包含了下述类型声明中的各个类型，及这些类型对应的目标语言类型（即 Golang 中的类型）。与 c 语言中 union 的概念类似，在目标代码中（生成为 yySymType​），union 将被生成为一个结构体（struct），根据「类型声明」，将匹配出的值放到结构体的对应字段中，作为存放/传递值的媒介而存在。在例子中，s​即为string​，类型声明中凡是标记为 s 类型的「表达式」，都会被保存到s字段中。,可参考「附录一:L11-L14」，以 %token 为行首的记号声明列表。对于 lexer 会直接分析出的 token，需要通过「Token 声明」来列出。Token 声明本身不需要关注顺序和组合，只需要单独列出需要由 lexer 输出的 token 类型即可。,可参考「附录一:L11-L14」，以 %type <%TYPE%>​ 为行首的记号声明列表，%TYPE% 为本行所列举的「Expr」将会保存到的 union 中的字段/类型。,各个声明与语法规则定义间，以 %% 分隔（L23）。,可参考「附录一:L25-L202」，语法规则使用巴科斯范式（Backus Normal Form，缩写为 BNF）定义。在 Goyacc（及它仿造的 yacc）中，以摘自「附录一:L53-L64」定义的一个 expr 为例，大致由以下部分构成：,L1 被定义的 expr 的名称，本例中 expr 的名称为searchLogicPart，在其他位置上将通过这个名称来引用这个 expr 及其格式定义。,L2-L4、L6-L8、L10-L12 expr 语法规则，以 L6-L8 部分为例，由两个部分构成：,L6 匹配格式，本语句由三个部分构成，分别是：,L5、L9 使用| 分隔 expr 可能的语法规则，也就是说，将匹配三种规则中的任意一种。,L12 一个 expr 语法规则定义完成后，使用; 作为结尾。需要额外注意的点：,对语法的定义不应当有二义性，也不可以对不定个数的元素进行匹配。,在有需要的场景下，可以直接操作 parser 函数上下文中含有的其他变量。,使用命令 goyacc -o querystring.y.go querystring.y 生成目标语言代码，在 yacc 定义中使用的 golang 函数/结构体等，都应当预先定义在同一包/目标语言代码中。,生成出的代码，将包含一个主入口 yyParse​ 函数。主入口函数接收 yyLexer 即词法分析器实例这一参数。在实际使用中，可使用词法分析器实例将分析结果 AST 返回。,词法分析（lexical analysis）是计算机科学中将字符序列转换为记号（token）序列的过程。进行词法分析的程序或者函数叫作词法分析器（lexical analyzer，简称 lexer），也叫扫描器（scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。,这里的记号是一个字串，是构成源代码的最小单位。在这个过程中，词法分析器还会对记号进行分类。,在 Goyacc 的实际使用中，词法分析器提供了三个特性：,一个较为简单的实现方式，是使用 Scanner 配合对字符的匹配，将值放置于传入的指针，并返回对应的类型。由于 Querystring 在转义/反转义上的特殊习惯，本例中对应的 lexer 是自行实现的。,实现一个词法分析器，大致需要以下部分：,根据语法的定义，构建 AST 的过程中，需要根据语义分别使用不同的节点类型，以方便对 AST 的使用。这一过程中，需要对 AST 节点进行定义。,在 Querystring AST 中，定义了以下类型的节点，并提供了若干工具函数：,某些开源库中，会在这一部分添加遍历相关的 Method，以方便使用者对 AST 进行遍历。,由于语法分析器提供的函数多为私有函数，也需要通过词法分析器对输入的源代码进行包裹，一般需要若干个工具函数。,本例中，主要提供了解析入口函数，主要功能为：输入一个 Querystring 格式的字符串，使用 lexer 实例进行包装，运行 parser，并返回过程中输出的错误。,Querystring 作为查询条件，使用过程中，一般需要注意以下几个问题：,也可通过 https://github.com/bytedance/go-querystring-parser/blob/main/querystring.y 查看