用Go构建一个SQL解析器

为了简单起见，我们将处理子选择、函数、复杂嵌套表达式和所有 SQL 风格都支持的其他特性。这些特性与我们将要使用的策略紧密相关。

1分钟理论

一个解析器包含两个部分：

词法分析：也就是“Tokeniser”

语法分析：AST 的创建

词法分析

让我们用例子来定义一下。“Tokenising”以下查询：

SELECT id, name FROM 'users.csv' 

表示提取构成此查询的“tokens”。tokeniser 的结果像这样：

[]string{"SELECT", "id", ",", "name", "FROM", "'users.csv'"} 

语法分析

这部分实际上是我们查看 tokens 的地方，确保它们有意义并解析它们来构造出一些结构体，以一种对将要使用它的应用程序更方便的方式表示查询(例如，用于执行查询，用颜色高亮显示它)。在这一步之后，我们会得到这样的结果：

query{ 

    Type: "Select", 

    TableName: "users.csv", 

    Fields: ["id", "name"], 

} 

有很多原因可能会导致解析失败，所以同时执行这两个步骤可能会比较方便，并在出现错误时可以立即停止。

策略

我们将定义一个像这样的解析器：

type parser struct { 

  sql             string        // The query to parse 

  i               int           // Where we are in the query 

  query           query.Query   // The "query struct" we'll build 

  step            step          // What's this? Read on... 

} 

// Main function that returns the "query struct" or an error 

func (p *parser) Parse() (query.Query, error) {} 

// A "look-ahead" function that returns the next token to parse 

func (p *parser) peek() (string) {} 

// same as peek(), but advancing our "i" index 

func (p *parser) pop() (string) {} 

直观地说，我们首先要做的是“peek() 第一个 token”。在基础的SQL语法中，只有几个有效的初始 token：SELECT、UPDATE、DELETE等;其他的都是错误的。代码像这样：

switch strings.ToUpper(parser.peek()) { 

case "SELECT": 

  parser.query.type = "SELECT" // start building the "query struct" 

  parser.pop() 

  // TODO continue with SELECT query parsing... 

case "UPDATE": 

  // TODO handle UPDATE 

// TODO other cases... 

default: 

  return parser.query, fmt.Errorf("invalid query type") 

} 

我们基本上可以填写 TODO 和让它跑起来!然而，聪明的读者会发现，解析整个 SELECT 查询的代码很快会变得混乱，而且我们有许多类型的查询需要解析。所以我们需要一些结构。

有限状态机

FSMs 是一个非常有趣的话题，但我们来这里不是为了讲这个，所以不会深入介绍。让我们只关注我们需要什么。

在我们的解析过程中，在任何给定的点(与其说“点”，不如称其称为“节点”)，只有少数 token 是有效的，在找到这些 token 之后，我们将进入新的节点，其中不同的 token 是有效的，以此类推，直到完成对查询的解析。我们可以将这些节点关系可视化为有向图：

点转换可以用一个更简单的表来定义，但是：

我们可以直接将这个表转换成一个非常大的 switch 语句。我们将使用那个我们之前定义过的 parser.step 属性：

func (p *parser) Parse() (query.Query, error) { 

  parser.step = stepType // initial step 

  for parser.i < len(parser.sql) { 

    nextToken := parser.peek() 

    switch parser.step { 

    case stepType: 

      switch nextToken { 

      case UPDATE: 

        parser.query.type = "UPDATE" 

        parser.step = stepUpdateTable 

      // TODO cases of other query types 

      } 

    case stepUpdateSet: 

      // ... 

    case stepUpdateField: 

      // ... 

    case stepUpdateComma: 

      // ... 

    } 

    parser.pop() 

  } 

  return parser.query, nil 

}