65.9K
CodeProject 正在变化。 阅读更多。
Home

用 C# 编写 SQL 词法分析器

Nicolas DESCARTES
starIconstarIconstarIconstarIconstarIcon

5.00/5 (2投票s)

2024年1月11日

CPOL

9分钟阅读

viewsIcon

4507

downloadIcon

102

如何编写 SQL 词法分析器？

引言

在本文中，我们将重温计算机科学的基础知识，重点关注有限自动机和编译等理论概念。我们的双重目标是：首先，阐明词法分析器的工作原理；其次，将这些基本原理应用于实际场景——为 SQL 构建一个精简的扫描器。

  • 词法分析，通常称为扫描或分词，是计算机科学中编译过程的初始阶段。它涉及检查一系列字符（源代码）以生成有意义的单元，称为标记（tokens）。这些标记是具有明确含义的编程语言的最小单元。

  • SQL 是一种用于管理和操作关系型数据库的领域特定语言。它是一种标准编程语言，专门设计用于与关系型数据库管理系统 (RDBMS) 中存储的数据进行交互和管理。

在本次讨论中，我们旨在揭示查询编译器如何处理 SQL 字符串并成功生成有意义结果的复杂性。重点将放在解决此过程中固有的挑战。

本文最初发布于此处。

什么是词法分析器？

首先，一个例子比冗长的解释更具说明性。因此，让我们考虑以下三个句子

  • Tha ader _guipoi je ?dftre !!klm。
  • Question be not address book this。
  • The cow is writing balloons。

第一个句子令人费解，至少在英语中如此，并且很可能在全世界所有语言中也是如此。此外，某些词以非法字符开头，例如感叹号。

第二个句子使用了有效的英语单词，但它们的排列方式使其完全没有意义。

第三个句子使用了有效的英语单词，并且它们的排列在语法上是正确的。然而，这些词的组合导致了胡言乱语，使其对任何人来说都毫无意义。

在更正式的词典中，第一个句子被认为是词法不正确的，第二个句子是词法正确但语法不正确的，最后一个句子是词法正确、语法正确但语义不正确的。

适用于人类语言的相同原则可以扩展到编程语言，并且过程是相同的：程序需要使用允许的词（词法分析），根据预定义的语法将它们组织成正确的序列（语法分析），并避免不合逻辑的赋值（语义分析）。

在计算机科学中，上述三个阶段构成了编译器的核心组件，并且占据了编译课程的很大一部分。在本系列中，我们将只专注于研究词法分析器。

要记住

词法分析器是一个过程，它检查编程语言的输入源代码并将其分解为一系列标记。这些标记代表语言的基本构建块，例如关键字、标识符、文字和运算符。

本质上，词法分析器通过将原始源代码转换为结构化的标记流来发挥关键作用，该标记流可以由编译器的后续阶段进一步处理。

如何进行词法分析？

词法分析器以一个 `string` 开始其过程，该 `string` 代表程序员编写的原始源代码（或者，在我们上面的类比中，人类说的句子）。目标是确定相应的标记序列。

什么是标记？

  • 输入 `string` 的每个单独组件，通常由空格分隔，通常被称为词素（lexeme）。例如，在给定句子中，'SELECT'、'*' 和 'Customers' 构成不同的词素。

  • 每个词素对应于所讨论语言中的一个词法类别，例如关键字、标识符、运算符或文字。例如，'SELECT' 是一个关键字，'Customers' 是一个标识符，'=' 代表一个运算符，等等。

  • 标记是这两个信息的组合：当前的词素及其相关类别。因此，标记的示例将是 (KEYWORD|SELECT) 或 (IDENTIFIER|Customers)。

乍一看，检测关键字似乎相对简单，因为它们的数量在每种语言中都是有限的。例如，下面的代码片段可以完成这项任务。

var keywords = [ "SELECT", "FROM", "WHERE" ];
var input = "SELECT * FROM Customers";
var lexemes = input.Split(new string[] { " " }, StringSplitOptions.None);
var tokens = new List<Token>();
foreach (var lexeme in lexemes)
{
    if (keywords.Contains(lexeme))
    {
        var token = new Token() { Lexeme = lexeme, Category = "KEYWORD" };
        tokens.Add(token);
    }
}

然而，在检测标识符时会出现挑战。由于标识符本质上可以是任何字符序列，因此不可能像上面代码中那样预定义所有可能的由用户创建的标识符。这就是专门数据结构——有限自动机——发挥作用的地方。

什么是有限自动机？

有限自动机是一种计算模型，它具有有限的状态集合、这些状态之间的转换以及驱动状态转换的输入字母表。它以离散的步骤操作，根据预定义的规则处理输入符号以在状态之间移动。

  • 状态是自动机在任何给定时间可以处于的有限的、不同的条件或情况集合。

  • 转换是定义自动机如何响应输入符号从一个状态转换到另一个状态的规则或函数。

  • 输入字母表是自动机在其操作过程中读取的输入符号集合。

  • 初始状态是自动机操作的起点，指示其初始条件。

  • 接受状态是当达到这些状态时，表示成功识别或接受输入序列的状态。

信息

有限自动机背后的理论非常复杂和引人入胜。虽然我们不会在这里探讨深奥的理论概念，例如确定性或非确定性自动机或非凡的克莱尼定理，但对这些主题感兴趣的读者可以参考《自动机理论、语言和计算导论》（霍普克罗夫特、莫特瓦尼、乌尔曼）以获得更全面的见解。

上述定义非常正式，对于不熟悉这些数据结构的读者来说可能不太容易理解。因此，我们将采用图形化方法来阐述并使这种非常有用的结构具体化。

一个简单的示例

想象一个场景，我们旨在设计一个用于识别单词 `SELECT` 的数据结构。下图说明了此过程中的步骤。

  • 从状态 1（在上图中以红色表示）开始，并使用字符串 "SELECT"，我们启动该过程。由于字符串以 'S' 开头，我们尝试转换到具有 'S' 标记转换的状态。由于存在这样的转换，我们进入状态 2。
  • 随后，遇到字符 'E'，我们再次重复该过程——从状态 2 转换到另一个具有 'E' 标记转换的状态。
  • 这种模式一直持续到我们到达状态 7。在我们的示例中，状态 7 以绿色突出显示，表示一个接受状态。这表明我们可以在这里结束该过程并确定已识别的字符串，在本例中，它正是 "SELECT"。

这个结构能识别单词 FROM 吗？

我们再次从状态 1（我们的初始状态）开始该过程。然而，这次我们使用字符串 "FROM"。鉴于此字符串以 'F' 开头，我们尝试转换到具有 'F' 标记转换的状态。由于不存在这样的转换，我们陷入僵局，并且显而易见，此结构无法识别单词 FROM。

为了纠正这个问题，有必要通过引入所需的状​​态来增强我们的结构。

这个结构能识别单词 SEL 吗？

  • 我们再次从状态 1 开始该过程，使用字符串 "SEL"。由于字符串以 'S' 开头，我们尝试转换到具有 'S' 标记转换的状态。由于存在这样的转换，我们继续进行。
  • 重复该过程，我们在状态 4 遇到阻塞，因为字符串已用尽。鉴于状态 4 不是接受状态，我们推断此结构不识别单词 SEL。

所以呢？

上述结构是有限自动机

  • 状态由所有圆圈的集合表示（在本例中为 1 到 7）。
  • 六个转换用单个字符标记；从一个状态到另一个状态的转换只有在存在用当前字符标记的转换时才可能发生。
  • 输入字母表由字母数字字符序列组成。
  • 初始状态用红色表示。
  • 接受状态用绿色表示。

重要

当且仅当自动机从初始状态开始，通过字符串的组成字符进行转换，能够到达其中一个接受状态时，它才能识别一个字符串。

就其本身而言，当前的数据结构几乎没有实际用途，因为识别单词 `SELECT` 无需如此复杂的机制即可完成。然而，设想一下如何使用此结构来识别标识符。

识别标识符

为了说明，我们假设标识符仅由字母字符序列组成，不允许使用数字字符。例如，“Customers”被视为标识符，而“state03”则不是，因为它包含非字母字符（0 和 3）。此外，我们强制要求标识符必须至少包含一个字符。

有了这个规定，以下自动机就能够识别标识符。

我们从状态 1 开始处理，使用字符串 "Customers"。由于字符串以 'C' 开头，我们尝试转换到具有 'C' 标记转换的状态。成功找到这样的转换后，我们进入状态 2。继续整个过程，我们可以消费所有字符并以一个接受状态结束。我们得出结论，Customers 被识别为标识符。

重要提示 1

我们可以观察到，在这种情况下，存在从一个状态到自身的转换。自动机的定义允许这种转换。

重要提示 2

值得注意的是，与它所要执行的任务相比，最终的结构是多么的简单。只需两个状态和少量转换，我们现在就可以完成一个在没有这种数据结构帮助下可能显得相当复杂的任务。

现在是将这些概念付诸实践的时候了，我们将用一个基本的 SQL 词法分析器来示例上述想法。

什么是 SQL？

SQL 是一种所有关系数据库都在使用的历史悠久的语言。在此讨论中，我们假设读者对该技术有熟练的理解，无需复习。我们的目标是检查类似以下示例的字符串。

SELECT *
FROM Customers c
WHERE c.Id = 10100

SELECT c.Name, c.Age
FROM Customers c
WHERE c.Id = 10100 AND c.Age <= 35

Customers SELECT WHERE Id FROM

SELECT *
FROM Customers04

定义类别

为了说明目的，我们将词素分为七个不同的类别，如下表所示。

名称 示例
关键词 SELECT, FROM, ...
操作符 =, <>, LIKE, ...
标识符 Customers, Id, ...
标点符号 ., !, (, ...
NUMBER 1, 7653, ...
字面量 'john', '%michel%', ...
ALL *

构建自动机

我们需要为上述每个类别构建一个自动机。为了说明，我们将概述文字的自动机。其他的相对简单，可以在 C# 源代码中找到。

从状态 1 开始，只有通过 ' 字符才能转换到状态 2。一旦进入状态 2，允许任意数量的字母字符，最终，只有通过另一个 ' 字符才能转换到状态 3。如果输入字符串耗尽，我们可以得出结论它是一个文字。否则，我们需要探索另一个类别。

理论已足够，现在我们将着手在 C# 中实际实现一个 SQL 词法分析器。然而，为了简洁起见，请参考此链接查看代码。

历史

  • 2024 年 1 月 11 日：初始版本
© . All rights reserved.