编写词法分析器有很多种方法，最常见的两种方法

在 Aviasales，我们用 Go 重写了我们的搜索引擎。

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

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

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

让我们从 Lexer 开始。

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

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

名称 – 指定变量、数字 – 数字、字符串的文本文字、运算符、标点符号和特殊的文件结尾标记

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

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

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

lexRoot 从输入字符串中取出下一个字符并决定哪个状态“进入”状态机。例如，如果遇到引号字符，则转到 lexQuote 状态。

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

词法分析步骤完成后，我们得到一个标记列表及其值。

要编写解析器，我们需要上下文无关的语法，当然，有很多解析器生成器（如 goyacc 等），但我想展示如何从头开始编写自己的解析器。我将向您展示如何编写一个简单的 LL(1） 递归下降解析器。首先，什么是上下文无关语法？它是：

一组终端符号（标记）。一组非终结符号（语法变量）。一组产生式，其中每个产生式包括一个非终端，称为产生式的头部或左侧，一个箭头，以及一系列终端和/或非终端，称为产生式的主体或右侧。指定一个非终结符号作为开始符号。让我们看一个简单的语法：

它由一个非终结符 S 组成；三个接线端：+、1、a；三个生产规则；和一个开始符号 S。

例如，要从这个语法中得到 1+1+a 输入行，我们从起始符号 S 开始词法分析器的输入是什么，并使用第一代作为简单的替换规则，将 S 替换为 S+S。接下来，根据第二个产生式规则将第一个匹配替换为 1，依此类推，直到我们得到原始字符串。因此，证明该行属于该文法所描述的语言。这个过程称为推导。

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

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

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

输入为：x + y * z

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

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

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

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

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

输入右递归产生式：

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

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

现在我们可以将语法重写为代码，因为现在选择生成是在每个递归构建的开始。

让我们定义抽象语法树的节点。为简单起见，我们的 AST 仅包含一个节点 – binaryNode。为简单起见，我们还将标签结构替换为字符串。

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

另外，简单地重写生产规则，递归产品从我们可以选择使用产品的终端开始，这里省略了空产品（空的其他）。

在原子生成规则中，我们检查当前标记是否与我们对 atom 的定义匹配，并将其添加到包含所有以反向波兰表示法的原子的特殊堆栈中，并在发射函数中从堆栈元素中获取最后两个元素，创建一个 binaryNode并将其放回堆栈，这称为后缀算法）

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

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

现在到 Evaler。为了执行我们的 AST，我们将扩展节点接口并添加一个 eval() 方法。

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

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