如何用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节点。

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