背景Domain-specificlanguages(DSLs)，例如SQL、ElasticsearchQuerystring等，通常是为专门用途而设计的。在特定任务中，DSL通过牺牲表现力来换取特定领域的高效率。在飞书套件日志系统私有化研发过程中，为了顺应研发同学查询日志的习惯，我们尝试使用ElasticqueryQueryString（以下简称QueryString）作为查询条件语句过滤器，它需要一个可用的Golang查询字符串解析器。由于目前开源社区找不到完整的实现，尝试使用Goyacc自己搭建。Yacc是一种广泛使用的编译器代码生成器。生成的代码主要用于语法分析阶段。它经常与lex搭配使用，作为词法分析器。使用LALR算法，将源代码构建到抽象语法树(AST)中。Goyacc是yacc的Golang版本。本文试图实现的Querystring解析器本质上是词法分析器和解析器的结合。解析器由Goyacc生成；为了方便实现符合Querystring惯用语的反义，词法分析器自行实现。Yacc及其各种语言的实现，中文网上很少有具体的介绍。本文将尝试详细描述Goyacc练习中可能需要注意的点。所描述的Querystring解析器代码可以在https://github.com/bytedance/go-querystring-parser此处查看。Framework一个完整的应用Goyacc的DSL解析器包括以下几个部分：解析器（parser）词法分析器（lexer）比较简单，就是用Scanner来搭建；有特殊需要时，一般自己搭建。AST节点定义封装实体和工具函数的一般流程是语法分析器调用词法分析器将源代码拆解成基本的“Tokens（标记）”，并根据语法过程)”（Token本身也被当作Expr）。在“AST”中构建“Expr”的结构，并得到结果。句法分析（或语法分析）是分析由标记序列组成的输入文本，并根据给定的形式语法确定其语法结构的过程。语法分析器的作用是进行语法检查，构建由输入的token组成的数据结构（一般是语法分析树、抽象语法树等分层数据结构）。解析器通常使用单独的词法分析器从输入字符流中分离出单独的“标记”，并将标记流作为其输入。在实际开发中，解析器可以手动编写，也可以使用工具（半）自动生成。在这种情况下，它是由工具自动生成的。使用Backus-NaurForm描述对应的文法定义，使用goyacc生成golang代码，提供LALR解析器，定义词法分析器返回的token定义。安装Goyacc在安装了golang的环境中，执行：goget-ugolang.org/x/tools/cmd/goyacc如果安装后无法正常运行，请检查$PATH中是否添加了$GOPATH/bin。Goyacc语法定义文件一个yacc语法定义文件一般由以下几个部分组成。header中的目标语言代码请参考“附录1：L1-L3”，用%{和}%包围需要的目标语言本地代码段落。目标语言在语言应用中往往会涉及到一些头代码。示例中需要通过这部分添加golang需要的包名的定义。其他的例子还有常量的定义，结构体的定义等。Union（集合）声明可以参考《附录1：L5-L9》，以%union{}格式定义，并且只能定义一次。“Union”的概念包括后面类型声明中的各个类型，以及这些类型对应的目标语言类型（即Golang中的类型）。类似于c语言中union的概念，在目标代码（生成为yySymType）中，union会被生成为一个结构体（struct），并根据“类型声明”，将匹配到的值放入对应的字段中在结构中，它作为存储/传输值的媒介而存在。示例中，s为字符串，任何在类型声明中标记为s类型的“表达式”都会保存在s字段中。token声明可以参考“附录1：L11-L14”以%token开头的token声明列表。对于词法分析器要直接解析的token，需要通过“TokenDeclaration”列出来。token声明本身不需要关注顺序和组合，只需要列出词法分析器需要输出的token类型即可。类型（type）声明可以参考《附录1：L11-L14》，以%type<%TYPE%>开头的token声明列表，%TYPE%就是这一行列出的“Expr”，会被保存到字段中/联合中的类型。语句和语法定义规则之间的分隔符在每个语句和语法规则定义（L23）之间用%%分隔。语法规则的定义请参考“附录1：L25-L202”。文法规则以巴科斯范式（缩写为BNF）定义。在Goyacc（及其仿版yacc）中，以“附录1：L53-L64”中定义的一个expr为例，大致由以下几部分组成：searchLogicPart:searchLogicSimplePart{$$=$1}|searchLogicSimpleParttANDsearchLogicPart{$$=NewAndCondition($1,$3)}|searchLogicSimpleParttORsearchLogicPart{$$=NewOrCondition($1,$3)};L1是定义的expr的名称。本例中expr的名称为searchLogicPart，其他位置会用到引用这个expr及其格式定义。L2-L4、L6-L8、L10-L12expr语法规则，以L6-L8部分为例，由两部分组成：L6匹配格式，本句由三部分组成，即：一个searchLogicSimplePartexpr，在“附录1：L66”，逻辑语句的单个元素，或NOT逻辑元素，或使用括号强制优先组合的一组元素。一个tANDexpr其实就是一个token，是词法分析器分析给出的类型，源码就是AND。AsearchLogicPartexpr，本段中定义的语句。L7动作（action），即匹配完成后对被匹配元素执行的行为，匹配格式后用{，}括起来，实际上是一个代码生成模板，在目标语言（Golang）中完成$$会是生成为当前exprunion中对应的字段，比如L7中的$$，会生成为yyVAL.q，因为searchLogicPart在类型声明中使用的类型是q（见《附录1：L20》）。以此类推，将生成$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语法规则后，使用;作为结束。需要特别注意的地方：语法的定义不能有歧义，不允许匹配不定数量的元素。在必要的场景下，可以直接操作解析器函数上下文中包含的其他变量。如AST根的输出，“附录1：L27”语句。Goyacc的生成使用命令goyacc-oquerystring.y.goquerystring.y生成目标语言代码，yacc定义中使用的golang函数/结构体应该预先定义在同一个包/目标语言代码中。使用目标语言代码生成的代码将包含一个主要入口yyParse函数。主入口函数接收参数yyLexer，是词法分析器的实例。在实际使用中，可以使用词法分析器实例返回分析结果AST。词法分析器词法分析是计算机科学中将字符序列转换为记号序列的过程。进行词法分析的程序或函数称为词法分析器（简称lexer），也称为扫描器。词法分析器一般以函数的形式存在，供语法分析器调用。这里的token是一个字符串，是构成源码的最小单位。在此过程中，词法分析器还会对标记进行分类。在Goyacc的实际使用中，词法分析器提供了三个特性：词法分析，即Lex(lval*yySymType)(tokenTypeint)函数，从源码流中读取下一个token，并转换token的值由传递的联合指针（即lval）返回，而这个token的类型由返回值（即tokenType）返回。错误记录，即Error(sstring)函数。AST的返回，由于yyParse没有提供其他有效的返回方法，所以这个实例也作为整体的解析上下文，将解析后的AST带回来。更简单的实现方式是使用Scanner来匹配字符，将值放在传入的指针中，返回对应的类型。由于Querystring在escaping/unescaping上的特殊习惯，本例中对应的lexer是自己实现的。实现一个词法分析器一般需要以下几个部分：一个字符串流，记录内容和当前读取位置等信息。当前状态管理AST节点的定义。不同的节点类型用于促进AST的使用。在这个过程中，需要定义AST节点。QuerystringAST中定义了以下几种类型的节点，并提供了几个工具函数：AndCondition，逻辑条件OrCondition，或逻辑条件NotCondition，非逻辑条件MatchCondition，匹配条件，根据判断为全文匹配还是全文匹配字段类型RegexpCondition，正则条件WildcardCondition，通配符条件NumberRangeCondition，数值Range条件，各种数值相关条件归一化为此类TimeRangeCondition，时间Range条件，时间相关各种条件归一化为此类一些开源库，Traversal-这部分会增加相关方法，方便用户遍历AST。封装实体和实用函数由于解析器提供的大部分函数都是私有函数，输入的源代码需要被词法分析器打包，一般需要几个实用函数。本例主要提供分析入口功能。主要功能是：输入一个Querystring格式的字符串，用词法分析器实例对其进行包装，运行解析器，返回过程中的错误输出。AST使用Querystring作为查询条件。在使用过程中，一般需要注意以下问题：查询条件的优化。用户输入的查询条件经常乱序：有时同一个条件多次出现在不同的位置，可以组合；可以合并同一个字段的过滤行为，降低本地缓存的开销；有些条件可能在逻辑上无效是可以消除的。类型推断。在numeric类型中，按照Elasticsearch官方的实现，Querystring中看起来像数字的值可能会被当作整数、浮点数、字符串或者时间来处理。值的类型应该根据被过滤数据的情况二次推断。附件一：Querystringgoyacc定义也可以通过https://github.com/bytedance/go-querystring-parser/blob/main/querystring.y查看%{packagequerystring%}%union{sstringnintqCondition}%令牌tSTRINGtPHRASEtNUMBER%tokentANDtORtNOTtTOtPLUStMINUStCOLON%tokentLEFTBRACKETtRIGHTBRACKETtLEFTRANGEtRIGHTRANGE%tokentGREATERtLESStEQUAL%typetSTRING%typetPHRASE%typetNUMBER%typesearchBasesearchPartssearchPartsearchLogicPartsearchLogicSimplePart%type
