如何用Go写业务的表达式引擎

在Aviasales,我们在Go中重写了我们的搜索引擎。

该引擎的关键部分之一是业务规则引擎。 由于传入的参数很多,因此并不总是能够在代码中描述不断变化的业务规则。 为了解决这个问题,我们写了一个表达引擎。 我们的想法是让动态配置,而无需重新编译程序。

在这次演讲中,我已经解释了如何编写自己的表达式引擎。 从词法分析器,解析器和Go的静态类型反射开始,到编译程序的评估。

让我们从理论开始。 可能每个人都知道大多数编程语言都包含Lexer,Parser和Compiler。 但是因为我们正在编写表达式引擎而不是编译器,所以我们将有一个Evaler。 Lexer读取原始字符串并生成标记,解析器接收标记并生成抽象语法树,Evaler使用指定的上下文执行此树。

让我们从Lexer开始吧。

编写词法分析器有很多种方法,最常见的两种方法是使用一堆正则表达式,或者使用状态机。 我们将使用状态机。

Lexer逐字符地读取输入字符串,并生成由两个元素组成的标记:标记的类型和值。 对于表达式引擎,我们只需要几种类型的标记:

*名称 - 指定变量,

*数字 - 数字,

*文本文字用于字符串,

*操作者,

*标点符号和文件的特殊标记结束

为了描述状态机的状态,我们将使用一个特殊的函数,它接受一个词法分析器并返回下一个状态函数。

词法分析器本身将存储输入字符串,输入字符串中的位置以及生成的标记列表。

lex函数将状态机的状态存储在循环中,从特殊状态lexRoot开始,直到收到nil,通知lexer操作完成,之后我们可以返回生成的标记列表。

lexRoot从输入字符串中获取下一个字符,并决定将哪个状态“转到”状态机。例如,如果遇到引号字符,请转到lexQuote状态。

lexQuote吸收所有字符,直到遇到下一个引号,并生成一个带有文本类型和两个引号之间收集的值的标记(省略了跳过转义引号的代码)。 状态之后可以返回到lexRoot状态。

在lexing步骤完成后,我们会得到一个令牌及其值的列表。

要编写解析器,我们需要一个无上下文的语法,当然,有很多解析器生成器(比如goyacc和其他),但我想展示如何从头开始编写自己的解析器。我将告诉你如何编写一个简单的LL(1)递归下降解析器。首先,什么是无上下文语法?它是:

*一组终端符号(标记)。

*一组非终结符(句法变量)。

*一组制作,其中每个制作包括一个非终结点,称为制作的头部或左侧,箭头,以及一系列终端和/或非终端,称为制作的正文或右侧。

*指定其中一个非终结符作为起始符号。

我们来看一个简单的语法:

它由一个非终结S组成; 三个终端:+ ,1 ,a ; 三条生产规则; 和起始符号S.

例如,要从此语法中获取1 + 1 + a 输入行,我们从起始符号S开始,并使用第一个生成作为简单替换规则,将S替换为S + S.接下来,将S的第一个匹配项替换为1 根据第二个生产规则等等,直到我们得到原始字符串。 因此,证明该行属于该语法描述的语言。 此过程称为派生。

每次选择最左边的非终结符号时,我们都会得到这样的解析树,但如果我们每次都选择最右边的非终结符号,我们会得到另一个解析树,

重要的是要知道解析器是确定最左边的还是最右边的派生,因为这决定了代码片段的执行顺序。

例如,在下面的语法中,我们可以得到两个解析树,但只有正确的解析树才有效,因为我们知道运算符的顺序是什么。

输入是:x + y * z

如果语法语言中的字符串具有多个解析树,则该语法被认为是不明确的语法。

我们可以通过在语法中输入以下更正来解决问题。

我们添加了一个额外的非终结符,并隐含地鼓励操作者的正确优先级。

现在让我们将表达式语法转换为代码,每个生成规则转换为一个函数,并且生成体中的每个非终结符都表示为对相应函数的调用。 但是,我们立即遇到一个问题:第二个生产规则调用自身,我们的程序卡住了。 这称为左递归生产。 但是,我们可以再次略微修改我们的语法。

可以通过重写不正确的生产规则来消除左递归。

进入右递归生产:

现在考虑一个包含加法和乘法运算的更复杂的语法。

该语法包含左递归生成规则。 应用转换规则,我们可以将它们全部重写为左递归规则。

现在我们可以将语法重写为代码,因为现在生产的选择是在每次递归生成的开始。

让我们定义抽象语法树的节点。 为简单起见,我们的AST只包含一个节点 - binaryNode。 为简单起见,我们还用字符串替换标记结构。

我们介绍辅助函数Next和Match。 接下来返回标记列表中的下一个字符,并且匹配检查当前具有给定终端的名为lookahead的终端,如果匹配,则将前瞻移动到下一个终端。

此外,简单地重写生产规则,递归产品从终端开始,我们可以通过它选择要使用的产品,这里省略空产品(空的其他)。

在原子生成规则中,我们检查当前标记是否符合我们对atom的定义并将其添加到特殊堆栈中,该堆栈包含反向波兰表示法中的所有原子,并且在emit函数中从堆栈中获取最后两个元素,创建 binaryNode并将其放回堆栈,这称为Postfix算法)

现在我们可以调用我们的开始符号,如果一切顺利,我们没有发现任何恐慌,那么在堆栈顶部将是我们的抽象语法树。

可以通过此链接(goo.gl/Qxegrd)找到解析器的完整示例。 让我们尝试运行并测试我们的解析器,因为你看它是左递归的,它正确解析运算符的优先级并理解括号。

现在给Evaler。 要执行我们的AST,我们将扩展节点接口并添加eval()方法。

下面是为binaryNode实现eval()方法的示例,eval左右部分。 然后根据操作员执行操作。 请记住,为了使其工作,我们需要为常量和变量编写额外的AST节点。

让我们尝试运行我们的计算器并检查结果。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181129A0C6ZQ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券