CppGuide社区
目录

13.查询语言：解析器

# 13. 查询语言：解析器

我们要为数据库添加的最后一项功能是查询语言。查询语言将我们已实现的所有功能以一种便于用户使用的接口呈现出来。

# 13.1 语法

# 13.1.1 语句

我们设计的语法看起来类似SQL，而SQL的语法类似于英语。

create table table_name (
    a type1,
    b type2,
   ...,
    index (c, b, a),
    index (d, e, f),
    primary key (a, b)
);

select expr... from table_name conditions limit x, y;
insert into table_name (cols...) values (a, b, c)...;
delete from table_name conditions limit x, y;
update table_name set a = expr, b = expr,... conditions limit x, y;
1
2
3
4
5
6
7
8
9
10
11
12
13

# 13.1.2 条件

不过，我们语言中的条件与SQL有所不同。SQL使用WHERE子句来选择行，而我们将条件分为索引条件和非索引条件。

  1. INDEX BY子句显式地为查询选择索引。它表示一个基于索引的点查询或范围查询，范围可以是开区间或闭区间。它还可以控制行的顺序。
select expr... from table_name index by a = 1;
select expr... from table_name index by a > 1;
select expr... from table_name index by a > 1 and a < 5;
1
2
3
  1. FILTER子句在不使用索引的情况下选择行。INDEX BY和FILTER子句都是可选的。
select expr... from table_name index by condition1 filter condition2;
select expr... from table_name filter condition2;
1
2

# 13.1.3 表达式

该语言在SELECT语句、FILTER条件和UPDATE语句中还包含任意表达式。表达式是递归的二元或一元运算。

以下是我们语言中的运算符列表，按运算符优先级排序：

-a
a * b, a / b
a + b, a - b
a = b, a < b,... -- 所有比较运算符
NOT a
a AND b
a OR b
(a, b, c,...) -- 元组
1
2
3
4
5
6
7
8

# 13.2 运算符优先级和递归

我们从解析表达式开始。表达式就像树结构，所以我们先定义树结构。

// 语法树
type QLNode struct {
    Value //  Type,  I64,  Str
    Kids []QLNode
}

// 语法树节点类型
const (
    QL_UNINIT = 0
    // 标量
    QL_STR = TYPE_BYTES
    QL_I64 = TYPE_INT64
    // 二元运算符
    QL_CMP_GE = 10 //  >=
    QL_CMP_GT = 11 //  >
    // 更多运算符；省略……
    // 一元运算符
    QL_NOT = 50
    QL_NEG = 51
    // 其他
    QL_SYM = 100 // 列
    QL_TUP = 101 // 元组
    QL_ERR = 200 // 错误；来自解析或求值
)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

与结构本身一样，解析表达式的过程也是递归的。我们从简单的例子开始。

考虑语言的一个子集，其中仅包含加法运算和列名：

a
a + b
a + b + c +...
1
2
3

解析该语言的伪代码如下：

def parse_add():
    node = parse_column()
    while parse('+'):
        right = parse_column()
        node = QLNode(type='+', kids=[node, right])
    return node
1
2
3
4
5
6

现在我们添加乘法运算符，它具有不同的优先级。我们修改表达式a + b，子表达式a或b可能是乘法运算，在加法之前应该先进行乘法运算（例如：当b为c * d时）。我们添加一个递归层级来处理这个问题：

def parse_add():
    node = parse_mul()
    while parse('+'):
        right = parse_mul()
        node = QLNode(type='+', kids=[node, right])
    return node

def parse_mul():
    node = parse_column()
    while parse(' * '):
        right = parse_column()
        node = QLNode(type=' * ', kids=[node, right])
    return node
1
2
3
4
5
6
7
8
9
10
11
12
13

注意，parse_add在解析子表达式时会递归调用parse_mul，而parse_mul又会递归调用parse_column。从这里我们可以看出规律：

  1. 每个运算符优先级都由一个递归层级来解析。
  2. 先执行的运算符在递归的底层进行解析。

# 13.3 解析表达式

我们将上述伪代码转换为实际代码。

Parser结构体在解析时存储输入中的当前位置。每个解析函数都将其作为参数。

type Parser struct {
    input []byte
    idx   int
    err   error
}
1
2
3
4
5

最高层级的解析是元组表达式（例如：(a, b, c,...)），然后是OR运算符，接着是AND运算符，以此类推。

func pExprTuple(p *Parser, node *QLNode) {
    kids := []QLNode{{}}
    pExprOr(p, &kids[len(kids)-1])
    for pKeyword(p, ",") {
        kids = append(kids, QLNode{})
        pExprOr(p, &kids[len(kids)-1])
    }
    if len(kids) > 1 {
        node.Type = QL_TUP
        node.Kids = kids
    } else {
        *node = kids[0] // 不是元组
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 13.3.1 解析关键字

pKeyword函数从输入中匹配一个或多个单词，并推进当前位置。

// 顺序匹配多个关键字
func pKeyword(p *Parser, kwds...string) bool {
    save := p.idx
    for _, kw := range kwds {
        skipSpace(p)
        end := p.idx + len(kw)
        if end > len(p.input) {
            p.idx = save
            return false
        }

        // 不区分大小写匹配
        ok := strings.EqualFold(string(p.input[p.idx:end]), kw)
        // 标记终止

        if ok && isSym(kw[len(kw)-1]) && end < len(p.input) {
            ok =!isSym(p.input[end])
        }
        if!ok {
            p.idx = save
            return false
        }

        p.idx += len(kw)
    }
    return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

skipSpace函数如其名所示，用于跳过空格。isSym的含义将在后面解释。

# 13.3.2 通用化

根据优先级列表，pExprOr应该递归调用AND运算符的解析函数（pExprAnd）。但是运算符优先级很多，所以我们将其通用化。

func pExprOr(p *Parser, node *QLNode) {
    pExprBinop(p, node, []string{"or"}, []uint32{QL_OR}, pExprAnd)
}

func pExprBinop(
    p *Parser, node *QLNode,
    ops []string, types []uint32, next func(*Parser, *QLNode),
) {
    assert(len(ops) == len(types))
    left := QLNode{}
    next(p, &left)

    for more := true; more; {
        more = false
        for i := range ops {
            if pKeyword(p, ops[i]) {
                new := QLNode{Value: Value{Type: types[i]}}
                new.Kids = []QLNode{left, {}}
                next(p, &new.Kids[1])

                left = new
                more = true
                break
            }
        }
    }

    *node = left
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

pExprBinop是解析二元运算符的通用函数。它接受一个具有相同优先级的运算符列表，并尝试用其中每个运算符进行解析。下一个优先级的解析器通过next参数进行参数化。

按优先级排序的二元解析器列表：

func pExprOr(p *Parser, node *QLNode) {
    pExprBinop(p, node, []string{"or"}, []uint32{QL_OR}, pExprAnd)
}
func pExprAnd(p *Parser, node *QLNode) {
    pExprBinop(p, node, []string{"and"}, []uint32{QL_AND}, pExprNot)
}
func pExprNot(p *Parser, node *QLNode) //  NOT a
func pExprCmp(p *Parser, node *QLNode) //  a < b,...
func pExprAdd(p *Parser, node *QLNode) //  a + b, a - b
func pExprMul(p *Parser, node *QLNode) {
    pExprBinop(p, node,
        []string{"*", "/", "%"}, []uint32{QL_MUL, QL_DIV, QL_MOD}, pExprUnop)
}
func pExprUnop(p *Parser, node *QLNode)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

pExprNot和pExprUnop是一元运算符，它们比二元运算符简单得多。

func pExprUnop(p *Parser, node *QLNode) {
    switch {
    case pKeyword(p, "-"):
        node.Type = QL_NEG
        node.Kids = []QLNode{{}}

        pExprAtom(p, &node.Kids[0])
    default:
        pExprAtom(p, node)
    }
}
1
2
3
4
5
6
7
8
9
10
11

# 13.3.3 解析名称

pExprAtom 函数处于解析的最底层。它会解析列名、整数、字符串，或者一对括号，遇到括号时会递归调用最高层级的函数 pExprTuple。

func pExprAtom(p *Parser, node *QLNode) {
    switch {
    case pKeyword(p, "("):
       pExprTuple(p, node)
       if!pKeyword(p, ")") {
          pErr(p, node, "unclosed parenthesis")
       }
    case pSym(p, node):
    case pNum(p, node):
    case pStr(p, node):
    default:
       pErr(p, node, "expect symbol, number or string")
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

pErr 函数会将错误存储在 Parser 结构体中。为了使代码简洁，即使发生错误，解析器也会继续执行。这就是为什么这里没有错误处理代码。

pSym 函数用于解析列名。它只是按照规则匹配字符，也可以用正则表达式来实现。

func pSym(p *Parser, node *QLNode) bool {
    skipSpace(p)

    end := p.idx
    if!(end < len(p.input) && isSymStart(p.input[end])) {
       return false
    }
    end++
    for end < len(p.input) && isSym(p.input[end]) {
       end++
    }
    if pKeywordSet[strings.ToLower(string(p.input[p.idx:end]))] {
       return false // 不允许
    }

    node.Type = QL_SYM
    node.Str = p.input[p.idx:end]
    p.idx = end
    return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

pSym 函数的辅助函数：

var pKeywordSet = map[string]bool{
    "from":   true,
    "index":  true,
    "filter": true,
    "limit":  true,
}

func isSym(ch byte) bool {
    r := rune(ch)
    return unicode.IsLetter(r) || unicode.IsNumber(r) || r == '_'
}

func isSymStart(ch byte) bool {
    return unicode.IsLetter(rune(ch)) || ch == '_' || ch == '@'
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 13.4 解析语句

以下是 SELECT 语句的结构体。

// 查询的通用结构：INDEX BY、FILTER、LIMIT
type QLScan struct {
    Table  string
    // INDEX BY xxx
    Key1   QLNode // 比较条件，可选
    Key2   QLNode // 比较条件，可选
    // FILTER xxx
    Filter QLNode // 布尔条件，可选
    // LIMIT x, y
    Offset int64
    Limit  int64
}

// stmt: select
type QLSelect struct {
    QLScan
    Names  []string // 表达式 AS 名称
    Output []QLNode // 表达式列表
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

以及所有其他语句：

// stmt: update
type QLUpdate struct {
    QLScan
    Names  []string
    Values []QLNode
}

// stmt: insert
type QLInsert struct {
    Table string
    Mode  int
    Names []string
    Values [][]QLNode
}

// stmt: delete
type QLDelete struct {
    QLScan
}

// stmt: create table
type QLCreateTable struct {
    Def TableDef
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

语句可以通过开头的几个单词来区分。

func pStmt(p *Parser) interface{} {
    switch {
    case pKeyword(p, "create", "table"):
       return pCreateTable(p)
    case pKeyword(p, "select"):
       return pSelect(p)
    case pKeyword(p, "insert", "into"):
       return pInsert(p, MODE_INSERT_ONLY)
    case pKeyword(p, "replace", "into"):
       return pInsert(p, MODE_UPDATE_ONLY)
    case pKeyword(p, "upsert", "into"):
       return pInsert(p, MODE_UPSERT)
    case pKeyword(p, "delete", "from"):
       return pDelete(p)
    case pKeyword(p, "update"):
       return pUpdate(p)
    default:
       pErr(p, nil, "unknown stmt")
       return nil
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

我们仅以 SELECT 语句为例。解析器由几个部分组成。

func pSelect(p *Parser) *QLSelect {
    stmt := QLSelect{}

    // SELECT xxx
    pSelectExprList(p, &stmt)

    // FROM table
    if!pKeyword(p, "from") {
       pErr(p, nil, "expect FROM table")
    }
    stmt.Table = pMustSym(p)

    // INDEX BY xxx FILTER yyy LIMIT zzz
    pScan(p, &stmt.QLScan)

    if p.err != nil {
       return nil
    }
    return &stmt
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

我们深入研究一下 pSelectExprList 函数，它由更细粒度的组件构成。

func pSelectExprList(p *Parser, node *QLSelect) {
    pSelectExpr(p, node)
    while pKeyword(p, ",") {
       pSelectExpr(p, node)
    }
}

func pSelectExpr(p *Parser, node *QLSelect) {
    expr := QLNode{}
    pExprOr(p, &expr)
    name := ""
    if pKeyword(p, "as") {
       name = pMustSym(p)
    }

    node.Names = append(node.Names, name)
    node.Output = append(node.Output, expr)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

此时，其余代码应该很容易理解了。我们将在下一章学习如何执行解析后的语句。

12.并发读写
14.查询语言：执行

← 14.查询语言：执行→

最近更新
01
C++语言面试问题集锦 目录与说明
03-27
02
第一章 auto与类型推导
03-27
03
第二章 关键字static及其不同用法
03-27
更多文章>
Copyright © 2024-2025 沪ICP备2023015129号 张小方 版权所有