← ./posts
· yuta

RDBMSを自作して学ぶ：第7章 SQLのパース

#database#rdbms#go

前回までで、ページ・バッファプール・ヒープファイル・B+木というストレージエンジンの部品がそろいました。今回からは、SQLを受け取って実行するSQLエンジンの実装に入ります。最初の一歩として、SQLの文字列をGoのプログラムで扱いやすい木構造に変換する**Lexer（字句解析器）とParser（構文解析器）**を実装します。

SQLを実行するまでの流れ

SQL文は、次の段階を経て実行されます。本章で扱うのは最初の2段階です。

"SELECT name FROM users WHERE id = 1"
        │
        ▼  Lexer（字句解析）……本章
[SELECT] [識別子:NAME] [FROM] [識別子:USERS] [WHERE] [識別子:ID] [=] [整数:1]
        │
        ▼  Parser（構文解析）……本章
抽象構文木（AST）
        │
        ▼  Planner（実行計画の作成）……第8章
        ▼  Executor（実行）……第8章
結果の行

サポートするSQL

第1章で決めたとおり、本シリーズのSQLは次の文に絞ります。

文 例
SELECT SELECT * FROM users WHERE age >= 20 AND name <> 'Bob'
SELECT（結合） SELECT users.name, orders.item FROM users JOIN orders ON users.id = orders.user_id
INSERT INSERT INTO users (id, name) VALUES (1, 'Alice')
CREATE TABLE CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(20))
トランザクション制御 BEGIN / COMMIT / ROLLBACK

型は INT と VARCHAR(n) の2種類です。WHERE句とON句では、比較演算子（=, <>, !=, <, >, <=, >=）と AND / OR / NOT、括弧が使えます。UPDATE・DELETE、NULL、負の数のリテラル、SELECT句での計算式などはサポートしません。

トランザクション制御文は、この章ではパースだけできるようにしておき、実際の処理は第10章以降で実装します。

字句解析（Lexer）

字句解析とは

SQLの文字列を1文字ずつ見ながら文法を解釈するのは大変です。そこでまず、文字列を意味のある最小単位（トークン）に切り分けます。これが字句解析です。

"SELECT id, name FROM users WHERE id >= 10"
  ↓
[SELECT] [識別子:ID] [,] [識別子:NAME] [FROM] [識別子:USERS]
[WHERE] [識別子:ID] [>=] [整数:10]

空白は読み捨て、>= のような2文字の演算子は1つのトークンにまとめます。キーワードと識別子（テーブル名・カラム名）の区別も、この段階で行います。

トークンの定義

// sql/lexer/token.go
package lexer

import "strings"

// TokenType はトークンの種別
type TokenType int

const (
    // 特殊
    EOF     TokenType = iota // 入力の終わり
    ILLEGAL                  // 不正な文字

    // リテラル
    IDENT  // 識別子: users, id など
    INT    // 整数リテラル: 1, 42
    STRING // 文字列リテラル: 'Alice'

    // キーワード
    SELECT
    FROM
    WHERE
    INSERT
    INTO
    VALUES
    CREATE
    TABLE
    INT_TYPE // 型名の INT
    VARCHAR
    PRIMARY
    KEY
    AND
    OR
    NOT
    JOIN
    ON
    BEGIN
    COMMIT
    ROLLBACK

    // 記号・演算子
    ASTERISK  // *
    COMMA     // ,
    SEMICOLON // ;
    LPAREN    // (
    RPAREN    // )
    DOT       // .
    EQ        // =
    NEQ       // <> または !=
    LT        // <
    GT        // >
    LTE       // <=
    GTE       // >=
)

var tokenNames = map[TokenType]string{
    EOF: "EOF", ILLEGAL: "ILLEGAL", IDENT: "識別子", INT: "整数", STRING: "文字列",
    ASTERISK: "*", COMMA: ",", SEMICOLON: ";", LPAREN: "(", RPAREN: ")", DOT: ".",
    EQ: "=", NEQ: "<>", LT: "<", GT: ">", LTE: "<=", GTE: ">=",
}

// keywords はキーワード（大文字）からTokenTypeへの対応表
var keywords = map[string]TokenType{
    "SELECT": SELECT, "FROM": FROM, "WHERE": WHERE,
    "INSERT": INSERT, "INTO": INTO, "VALUES": VALUES,
    "CREATE": CREATE, "TABLE": TABLE,
    "INT": INT_TYPE, "VARCHAR": VARCHAR, "PRIMARY": PRIMARY, "KEY": KEY,
    "AND": AND, "OR": OR, "NOT": NOT,
    "JOIN": JOIN, "ON": ON,
    "BEGIN": BEGIN, "COMMIT": COMMIT, "ROLLBACK": ROLLBACK,
}

func init() {
    for word, tt := range keywords {
        tokenNames[tt] = word
    }
}

// String はエラーメッセージなどで使うトークン種別の表示名を返す
func (tt TokenType) String() string {
    if name, ok := tokenNames[tt]; ok {
        return name
    }
    return "UNKNOWN"
}

// Token はトークンの種別と元の文字列を持つ
type Token struct {
    Type    TokenType
    Literal string
}

// LookupIdent は識別子がキーワードならそのTokenTypeを、そうでなければIDENTを返す
func LookupIdent(ident string) TokenType {
    if tt, ok := keywords[strings.ToUpper(ident)]; ok {
        return tt
    }
    return IDENT
}

TokenType に String() メソッドを持たせているのは、Parserのエラーメッセージで「FROM を期待しましたが…」のように、トークン種別を読みやすく表示するためです。キーワードの表示名は keywords から自動で登録しています。

Lexerの実装

Lexerは、入力文字列上の現在位置を1文字ずつ進めながら、NextToken が呼ばれるたびにトークンを1つ切り出して返します。

// sql/lexer/lexer.go
package lexer

import "strings"

// Lexer はSQL文字列を先頭から読み、トークンを1つずつ切り出す
type Lexer struct {
    input   string
    pos     int  // 現在の文字の位置
    readPos int  // 次に読む文字の位置
    ch      byte // 現在の文字（入力の終わりでは0）
}

// New は新しいLexerを作る
func New(input string) *Lexer {
    l := &Lexer{input: input}
    l.readChar()
    return l
}

// Tokenize はSQL文字列全体をトークン列に変換する（末尾は必ずEOF）
func Tokenize(input string) []Token {
    l := New(input)
    var tokens []Token
    for {
        tok := l.NextToken()
        tokens = append(tokens, tok)
        if tok.Type == EOF {
            return tokens
        }
    }
}

// NextToken は次のトークンを返す
func (l *Lexer) NextToken() Token {
    l.skipWhitespace()

    var tok Token
    switch l.ch {
    case 0:
        return Token{EOF, ""}
    case '*':
        tok = Token{ASTERISK, "*"}
    case ',':
        tok = Token{COMMA, ","}
    case ';':
        tok = Token{SEMICOLON, ";"}
    case '(':
        tok = Token{LPAREN, "("}
    case ')':
        tok = Token{RPAREN, ")"}
    case '.':
        tok = Token{DOT, "."}
    case '=':
        tok = Token{EQ, "="}
    case '<':
        switch l.peekChar() {
        case '=':
            l.readChar()
            tok = Token{LTE, "<="}
        case '>':
            l.readChar()
            tok = Token{NEQ, "<>"}
        default:
            tok = Token{LT, "<"}
        }
    case '>':
        if l.peekChar() == '=' {
            l.readChar()
            tok = Token{GTE, ">="}
        } else {
            tok = Token{GT, ">"}
        }
    case '!':
        if l.peekChar() == '=' {
            l.readChar()
            tok = Token{NEQ, "!="}
        } else {
            tok = Token{ILLEGAL, "!"}
        }
    case '\'':
        return l.readString()
    default:
        if isLetter(l.ch) {
            ident := l.readIdentifier()
            return Token{LookupIdent(ident), ident}
        }
        if isDigit(l.ch) {
            return Token{INT, l.readNumber()}
        }
        tok = Token{ILLEGAL, string(l.ch)}
    }

    l.readChar()
    return tok
}

func (l *Lexer) readChar() {
    if l.readPos >= len(l.input) {
        l.ch = 0
    } else {
        l.ch = l.input[l.readPos]
    }
    l.pos = l.readPos
    l.readPos++
}

func (l *Lexer) peekChar() byte {
    if l.readPos >= len(l.input) {
        return 0
    }
    return l.input[l.readPos]
}

func (l *Lexer) skipWhitespace() {
    for l.ch == ' ' || l.ch == '\t' || l.ch == '\n' || l.ch == '\r' {
        l.readChar()
    }
}

// readIdentifier は識別子を読み、大文字に揃えて返す
// （テーブル名・カラム名は大文字小文字を区別しない）
func (l *Lexer) readIdentifier() string {
    start := l.pos
    for isLetter(l.ch) || isDigit(l.ch) {
        l.readChar()
    }
    return strings.ToUpper(l.input[start:l.pos])
}

func (l *Lexer) readNumber() string {
    start := l.pos
    for isDigit(l.ch) {
        l.readChar()
    }
    return l.input[start:l.pos]
}

// readString はシングルクォートで囲まれた文字列を読む（大文字化はしない）
func (l *Lexer) readString() Token {
    l.readChar() // 開きクォートを読み飛ばす
    start := l.pos
    for l.ch != '\'' {
        if l.ch == 0 {
            return Token{ILLEGAL, l.input[start-1 : l.pos]} // 閉じられていない文字列
        }
        l.readChar()
    }
    str := l.input[start:l.pos]
    l.readChar() // 閉じクォートを読み飛ばす
    return Token{STRING, str}
}

// isLetter は識別子に使える文字（ASCIIの英字とアンダースコア）かを判定する
func isLetter(ch byte) bool {
    return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z' || ch == '_'
}

func isDigit(ch byte) bool {
    return '0' <= ch && ch <= '9'
}

いくつかの方針を補足します。

構文解析（Parser）

抽象構文木（AST）

構文解析は、トークン列を文法に従って組み立て、SQL文の構造を表す木を作る処理です。この木を**抽象構文木（AST: Abstract Syntax Tree）**と呼びます。「抽象」とは、括弧やカンマのような、構造が決まった後は不要になる記号を取り除いていることを指します。

SELECT name FROM users WHERE age >= 20 AND name <> 'Bob'
  ↓
SelectStatement
├── Columns: [NAME]
├── From:    USERS
└── Where:   BinaryExpr(AND)
             ├── BinaryExpr(>=)
             │   ├── ColumnRef(AGE)
             │   └── IntLiteral(20)
             └── BinaryExpr(<>)
                 ├── ColumnRef(NAME)
                 └── StringLiteral('Bob')

ASTノードの定義

文（Statement）と式（Expression）をそれぞれインターフェースにし、具体的な構文ごとに構造体を定義します。インターフェースには中身のないメソッド（statementNode など）を持たせ、「文の型」「式の型」以外が混ざらないようにしています。

// sql/parser/ast.go
package parser

import (
    "fmt"
    "strconv"
)

// Statement はSQL文を表すASTノード
type Statement interface {
    statementNode()
}

// Expression は式を表すASTノード
type Expression interface {
    expressionNode()
    String() string
}

// ---- 文 ----

// SelectStatement は SELECT 文
type SelectStatement struct {
    Columns []*ColumnRef // nil なら SELECT *
    From    string
    Joins   []JoinClause
    Where   Expression // WHERE句がなければnil
}

// JoinClause は JOIN テーブル ON 条件
type JoinClause struct {
    Table string
    On    Expression
}

// InsertStatement は INSERT 文
type InsertStatement struct {
    Table   string
    Columns []string // カラムリストを省略した場合はnil
    Values  []Expression
}

// CreateTableStatement は CREATE TABLE 文
type CreateTableStatement struct {
    Table   string
    Columns []ColumnDef
}

// ColumnDef はCREATE TABLEのカラム定義
type ColumnDef struct {
    Name       string
    Type       string // "INT" または "VARCHAR"
    Length     int    // VARCHARの最大文字数
    PrimaryKey bool
}

// BeginStatement / CommitStatement / RollbackStatement はトランザクション制御文
type BeginStatement struct{}
type CommitStatement struct{}
type RollbackStatement struct{}

func (*SelectStatement) statementNode()      {}
func (*InsertStatement) statementNode()      {}
func (*CreateTableStatement) statementNode() {}
func (*BeginStatement) statementNode()       {}
func (*CommitStatement) statementNode()      {}
func (*RollbackStatement) statementNode()    {}

// ---- 式 ----

// ColumnRef はカラム参照（users.id のようにテーブル名で修飾してもよい）
type ColumnRef struct {
    Table string // 修飾なしなら空文字
    Name  string
}

// IntLiteral は整数リテラル
type IntLiteral struct {
    Value int64
}

// StringLiteral は文字列リテラル
type StringLiteral struct {
    Value string
}

// BinaryExpr は二項演算（比較演算子と AND / OR）
type BinaryExpr struct {
    Op    string // "=", "<>", "<", ">", "<=", ">=", "AND", "OR"
    Left  Expression
    Right Expression
}

// NotExpr は NOT 式
type NotExpr struct {
    Expr Expression
}

func (*ColumnRef) expressionNode()     {}
func (*IntLiteral) expressionNode()    {}
func (*StringLiteral) expressionNode() {}
func (*BinaryExpr) expressionNode()    {}
func (*NotExpr) expressionNode()       {}

func (e *ColumnRef) String() string {
    if e.Table != "" {
        return e.Table + "." + e.Name
    }
    return e.Name
}

func (e *IntLiteral) String() string    { return strconv.FormatInt(e.Value, 10) }
func (e *StringLiteral) String() string { return "'" + e.Value + "'" }
func (e *BinaryExpr) String() string {
    return fmt.Sprintf("(%s %s %s)", e.Left, e.Op, e.Right)
}
func (e *NotExpr) String() string { return fmt.Sprintf("(NOT %s)", e.Expr) }

式には String() を持たせて、((A = 1) AND (B = 2)) のように括弧付きで表示できるようにしました。木の形がひと目でわかるので、テストで構造を確かめるのに便利です。

再帰下降構文解析

Parserは再帰下降構文解析という方法で実装します。文法の規則1つにつき関数を1つ用意し、規則の中に別の規則が出てきたら、その関数を呼び出す、という素直な作り方です。本シリーズの文法を書き下すと、次のようになります（[ ] は省略可、{ } は0回以上の繰り返し）。

statement  := select | insert | create | BEGIN | COMMIT | ROLLBACK
select     := SELECT ( "*" | columnRef { "," columnRef } )
              FROM 識別子 { JOIN 識別子 ON expression } [ WHERE expression ]
insert     := INSERT INTO 識別子 [ "(" 識別子 { "," 識別子 } ")" ]
              VALUES "(" literal { "," literal } ")"
create     := CREATE TABLE 識別子 "(" columnDef { "," columnDef } ")"
columnDef  := 識別子 ( INT | VARCHAR "(" 整数 ")" ) [ PRIMARY KEY ]
columnRef  := 識別子 [ "." 識別子 ]

演算子の優先順位

式の解析では、演算子の優先順位が問題になります。a = 1 OR b = 2 AND c = 3 は、SQLでは AND が OR より強く結びつくので、a = 1 OR (b = 2 AND c = 3) と解釈しなければなりません。

再帰下降構文解析では、優先順位の低い演算子から順に関数を分け、低い方の関数が高い方の関数を呼び出す形にすると、優先順位が自然に表現できます。

expression := or
or         := and { OR and }             ← 最も弱い
and        := not { AND not }
not        := NOT not | comparison
comparison := primary [ 比較演算子 primary ]
primary    := 整数 | 文字列 | columnRef | "(" expression ")"   ← 最も強い

parseOr は、まず parseAnd を呼んで左辺を読みます。parseAnd は AND でつながった部分をまとめて読んでから返ってくるので、AND の部分が先に1つの木にまとまります。その後に OR が続けば、それを右辺と結んでいきます。括弧で囲まれた式は primary から expression を呼び直すことで、どの深さでも最も強く結びつきます。

Parserの実装

まず入口の Parse と、先頭のトークンで文の種類を振り分ける parseStatement です。

// Parser はトークン列を先頭から読み、ASTを組み立てる（再帰下降構文解析）
type Parser struct {
    tokens []lexer.Token
    pos    int
}

// Parse はSQL文字列を1文ぶん解析してASTを返す
func Parse(input string) (Statement, error) {
    p := &Parser{tokens: lexer.Tokenize(input)}

    stmt, err := p.parseStatement()
    if err != nil {
        return nil, err
    }
    // 末尾のセミコロンは省略可。その後に何か残っていたらエラーにする
    if p.current().Type == lexer.SEMICOLON {
        p.advance()
    }
    if p.current().Type != lexer.EOF {
        return nil, p.unexpected()
    }
    return stmt, nil
}

func (p *Parser) parseStatement() (Statement, error) {
    switch p.current().Type {
    case lexer.SELECT:
        return p.parseSelect()
    case lexer.INSERT:
        return p.parseInsert()
    case lexer.CREATE:
        return p.parseCreateTable()
    case lexer.BEGIN:
        p.advance()
        return &BeginStatement{}, nil
    case lexer.COMMIT:
        p.advance()
        return &CommitStatement{}, nil
    case lexer.ROLLBACK:
        p.advance()
        return &RollbackStatement{}, nil
    default:
        return nil, fmt.Errorf("parser: 未対応の文です: %q", p.current().Literal)
    }
}

Parse は、文を1つ読み終えた後に入力が残っていないかを確かめています。この確認を省くと、SELECT * FROM t WHERE a = 1 b = 2 のような誤った文でも、a = 1 まで読んだところで成功扱いになり、残りが黙って無視されてしまいます。

SELECT・INSERT・CREATE TABLE の各文は、文法をそのままコードにしたような形になります。

func (p *Parser) parseSelect() (*SelectStatement, error) {
    p.advance() // SELECT
    stmt := &SelectStatement{}

    if p.current().Type == lexer.ASTERISK {
        p.advance()
    } else {
        for {
            col, err := p.parseColumnRef()
            if err != nil {
                return nil, err
            }
            stmt.Columns = append(stmt.Columns, col)
            if p.current().Type != lexer.COMMA {
                break
            }
            p.advance()
        }
    }

    if _, err := p.expect(lexer.FROM); err != nil {
        return nil, err
    }
    table, err := p.expectIdent()
    if err != nil {
        return nil, err
    }
    stmt.From = table

    for p.current().Type == lexer.JOIN {
        p.advance()
        joinTable, err := p.expectIdent()
        if err != nil {
            return nil, err
        }
        if _, err := p.expect(lexer.ON); err != nil {
            return nil, err
        }
        on, err := p.parseExpression()
        if err != nil {
            return nil, err
        }
        stmt.Joins = append(stmt.Joins, JoinClause{Table: joinTable, On: on})
    }

    if p.current().Type == lexer.WHERE {
        p.advance()
        where, err := p.parseExpression()
        if err != nil {
            return nil, err
        }
        stmt.Where = where
    }
    return stmt, nil
}

func (p *Parser) parseInsert() (*InsertStatement, error) {
    p.advance() // INSERT
    if _, err := p.expect(lexer.INTO); err != nil {
        return nil, err
    }
    table, err := p.expectIdent()
    if err != nil {
        return nil, err
    }
    stmt := &InsertStatement{Table: table}

    if p.current().Type == lexer.LPAREN {
        p.advance()
        for {
            col, err := p.expectIdent()
            if err != nil {
                return nil, err
            }
            stmt.Columns = append(stmt.Columns, col)
            if p.current().Type != lexer.COMMA {
                break
            }
            p.advance()
        }
        if _, err := p.expect(lexer.RPAREN); err != nil {
            return nil, err
        }
    }

    if _, err := p.expect(lexer.VALUES); err != nil {
        return nil, err
    }
    if _, err := p.expect(lexer.LPAREN); err != nil {
        return nil, err
    }
    for {
        val, err := p.parseLiteral()
        if err != nil {
            return nil, err
        }
        stmt.Values = append(stmt.Values, val)
        if p.current().Type != lexer.COMMA {
            break
        }
        p.advance()
    }
    if _, err := p.expect(lexer.RPAREN); err != nil {
        return nil, err
    }
    return stmt, nil
}

func (p *Parser) parseCreateTable() (*CreateTableStatement, error) {
    p.advance() // CREATE
    if _, err := p.expect(lexer.TABLE); err != nil {
        return nil, err
    }
    table, err := p.expectIdent()
    if err != nil {
        return nil, err
    }
    stmt := &CreateTableStatement{Table: table}

    if _, err := p.expect(lexer.LPAREN); err != nil {
        return nil, err
    }
    for {
        col, err := p.parseColumnDef()
        if err != nil {
            return nil, err
        }
        stmt.Columns = append(stmt.Columns, col)
        if p.current().Type != lexer.COMMA {
            break
        }
        p.advance()
    }
    if _, err := p.expect(lexer.RPAREN); err != nil {
        return nil, err
    }
    return stmt, nil
}

// カラム名 (INT | VARCHAR(n)) [PRIMARY KEY]
func (p *Parser) parseColumnDef() (ColumnDef, error) {
    name, err := p.expectIdent()
    if err != nil {
        return ColumnDef{}, err
    }
    col := ColumnDef{Name: name}

    switch p.current().Type {
    case lexer.INT_TYPE:
        p.advance()
        col.Type = "INT"
    case lexer.VARCHAR:
        p.advance()
        if _, err := p.expect(lexer.LPAREN); err != nil {
            return col, err
        }
        tok, err := p.expect(lexer.INT)
        if err != nil {
            return col, err
        }
        n, err := strconv.Atoi(tok.Literal)
        if err != nil || n <= 0 {
            return col, fmt.Errorf("parser: VARCHARの長さが不正です: %s", tok.Literal)
        }
        if _, err := p.expect(lexer.RPAREN); err != nil {
            return col, err
        }
        col.Type = "VARCHAR"
        col.Length = n
    default:
        return col, fmt.Errorf("parser: 未対応の型です: %q", p.current().Literal)
    }

    if p.current().Type == lexer.PRIMARY {
        p.advance()
        if _, err := p.expect(lexer.KEY); err != nil {
            return col, err
        }
        col.PrimaryKey = true
    }
    return col, nil
}

カンマ区切りのリストは「要素を1つ読む → カンマでなければ抜ける → カンマを読み飛ばす」というループで読み、ループを抜けた後で閉じ括弧を expect しています。どの繰り返しでも必ずトークンを1つ以上読み進めるか、エラーで抜けるので、) が欠けた入力でもループが止まらなくなることはありません。

式の解析は、先ほどの優先順位の規則がそのまま関数になっています。

func (p *Parser) parseExpression() (Expression, error) {
    return p.parseOr()
}

func (p *Parser) parseOr() (Expression, error) {
    left, err := p.parseAnd()
    if err != nil {
        return nil, err
    }
    for p.current().Type == lexer.OR {
        p.advance()
        right, err := p.parseAnd()
        if err != nil {
            return nil, err
        }
        left = &BinaryExpr{Op: "OR", Left: left, Right: right}
    }
    return left, nil
}

func (p *Parser) parseAnd() (Expression, error) {
    left, err := p.parseNot()
    if err != nil {
        return nil, err
    }
    for p.current().Type == lexer.AND {
        p.advance()
        right, err := p.parseNot()
        if err != nil {
            return nil, err
        }
        left = &BinaryExpr{Op: "AND", Left: left, Right: right}
    }
    return left, nil
}

func (p *Parser) parseNot() (Expression, error) {
    if p.current().Type == lexer.NOT {
        p.advance()
        expr, err := p.parseNot()
        if err != nil {
            return nil, err
        }
        return &NotExpr{Expr: expr}, nil
    }
    return p.parseComparison()
}

var comparisonOps = map[lexer.TokenType]string{
    lexer.EQ: "=", lexer.NEQ: "<>", lexer.LT: "<", lexer.GT: ">", lexer.LTE: "<=", lexer.GTE: ">=",
}

func (p *Parser) parseComparison() (Expression, error) {
    left, err := p.parsePrimary()
    if err != nil {
        return nil, err
    }
    op, ok := comparisonOps[p.current().Type]
    if !ok {
        return left, nil
    }
    p.advance()
    right, err := p.parsePrimary()
    if err != nil {
        return nil, err
    }
    return &BinaryExpr{Op: op, Left: left, Right: right}, nil
}

func (p *Parser) parsePrimary() (Expression, error) {
    switch p.current().Type {
    case lexer.INT, lexer.STRING:
        return p.parseLiteral()
    case lexer.IDENT:
        return p.parseColumnRef()
    case lexer.LPAREN:
        p.advance()
        expr, err := p.parseExpression()
        if err != nil {
            return nil, err
        }
        if _, err := p.expect(lexer.RPAREN); err != nil {
            return nil, err
        }
        return expr, nil
    default:
        return nil, p.unexpected()
    }
}

func (p *Parser) parseLiteral() (Expression, error) {
    tok := p.current()
    switch tok.Type {
    case lexer.INT:
        p.advance()
        v, err := strconv.ParseInt(tok.Literal, 10, 64)
        if err != nil {
            return nil, fmt.Errorf("parser: 整数に変換できません: %s", tok.Literal)
        }
        return &IntLiteral{Value: v}, nil
    case lexer.STRING:
        p.advance()
        return &StringLiteral{Value: tok.Literal}, nil
    default:
        return nil, p.unexpected()
    }
}

// カラム名 または テーブル名.カラム名
func (p *Parser) parseColumnRef() (*ColumnRef, error) {
    name, err := p.expectIdent()
    if err != nil {
        return nil, err
    }
    if p.current().Type != lexer.DOT {
        return &ColumnRef{Name: name}, nil
    }
    p.advance()
    col, err := p.expectIdent()
    if err != nil {
        return nil, err
    }
    return &ColumnRef{Table: name, Name: col}, nil
}

parseOr と parseAnd のループでは、読んだ式を左辺に積み上げていくので、a AND b AND c は ((a AND b) AND c) という左結合の木になります。

最後に、トークンを読み進めるヘルパーです。

func (p *Parser) current() lexer.Token {
    if p.pos >= len(p.tokens) {
        return lexer.Token{Type: lexer.EOF}
    }
    return p.tokens[p.pos]
}

func (p *Parser) advance() {
    if p.pos < len(p.tokens) {
        p.pos++
    }
}

// expect は現在のトークンがttなら読み進めて返し、違えばエラーを返す
func (p *Parser) expect(tt lexer.TokenType) (lexer.Token, error) {
    tok := p.current()
    if tok.Type != tt {
        return tok, fmt.Errorf("parser: %s を期待しましたが %s でした", tt, describe(tok))
    }
    p.advance()
    return tok, nil
}

func (p *Parser) expectIdent() (string, error) {
    tok, err := p.expect(lexer.IDENT)
    return tok.Literal, err
}

func (p *Parser) unexpected() error {
    if tok := p.current(); tok.Type == lexer.ILLEGAL {
        return fmt.Errorf("parser: 不正な文字があります: %q", tok.Literal)
    }
    return fmt.Errorf("parser: 予期しないトークンです: %s", describe(p.current()))
}

func describe(tok lexer.Token) string {
    if tok.Type == lexer.EOF {
        return "文の終わり"
    }
    return fmt.Sprintf("%q", tok.Literal)
}

テストを書く

Lexerのテストは、入力とトークン列の組を並べたテーブル駆動テストにします。

// sql/lexer/lexer_test.go
package lexer_test

import (
    "testing"

    "github.com/yourname/go-rdbms/sql/lexer"
)

func TestTokenize(t *testing.T) {
    tests := []struct {
        input string
        want  []lexer.Token
    }{
        {
            "SELECT id, name FROM users WHERE id >= 10",
            []lexer.Token{
                {Type: lexer.SELECT, Literal: "SELECT"},
                {Type: lexer.IDENT, Literal: "ID"},
                {Type: lexer.COMMA, Literal: ","},
                {Type: lexer.IDENT, Literal: "NAME"},
                {Type: lexer.FROM, Literal: "FROM"},
                {Type: lexer.IDENT, Literal: "USERS"},
                {Type: lexer.WHERE, Literal: "WHERE"},
                {Type: lexer.IDENT, Literal: "ID"},
                {Type: lexer.GTE, Literal: ">="},
                {Type: lexer.INT, Literal: "10"},
                {Type: lexer.EOF, Literal: ""},
            },
        },
        {
            "insert into t values ('Alice', 42);",
            []lexer.Token{
                {Type: lexer.INSERT, Literal: "INSERT"},
                {Type: lexer.INTO, Literal: "INTO"},
                {Type: lexer.IDENT, Literal: "T"},
                {Type: lexer.VALUES, Literal: "VALUES"},
                {Type: lexer.LPAREN, Literal: "("},
                {Type: lexer.STRING, Literal: "Alice"}, // 文字列リテラルは大文字にしない
                {Type: lexer.COMMA, Literal: ","},
                {Type: lexer.INT, Literal: "42"},
                {Type: lexer.RPAREN, Literal: ")"},
                {Type: lexer.SEMICOLON, Literal: ";"},
                {Type: lexer.EOF, Literal: ""},
            },
        },
        {
            "a <> b != c <= d.e_1",
            []lexer.Token{
                {Type: lexer.IDENT, Literal: "A"},
                {Type: lexer.NEQ, Literal: "<>"},
                {Type: lexer.IDENT, Literal: "B"},
                {Type: lexer.NEQ, Literal: "!="},
                {Type: lexer.IDENT, Literal: "C"},
                {Type: lexer.LTE, Literal: "<="},
                {Type: lexer.IDENT, Literal: "D"},
                {Type: lexer.DOT, Literal: "."},
                {Type: lexer.IDENT, Literal: "E_1"},
                {Type: lexer.EOF, Literal: ""},
            },
        },
    }

    for _, tt := range tests {
        t.Run(tt.input, func(t *testing.T) {
            got := lexer.Tokenize(tt.input)
            if len(got) != len(tt.want) {
                t.Fatalf("トークン数不一致: want %d, got %d (%v)", len(tt.want), len(got), got)
            }
            for i := range tt.want {
                if got[i] != tt.want[i] {
                    t.Errorf("%d番目: want %+v, got %+v", i, tt.want[i], got[i])
                }
            }
        })
    }
}

func TestTokenize_UnterminatedString(t *testing.T) {
    tokens := lexer.Tokenize("SELECT 'abc")
    if tokens[1].Type != lexer.ILLEGAL {
        t.Errorf("閉じていない文字列はILLEGALになるはず: got %v", tokens[1])
    }
}

Parserのテストでは、String() で式の木の形を確かめます。誤った入力がエラーになること（そして無限ループにならないこと）もテストしておきます。

// sql/parser/parser_test.go
package parser_test

import (
    "fmt"
    "testing"

    "github.com/yourname/go-rdbms/sql/parser"
)

func TestParse_Select(t *testing.T) {
    stmt, err := parser.Parse("SELECT id, name FROM users WHERE id = 1")
    if err != nil {
        t.Fatal(err)
    }
    sel, ok := stmt.(*parser.SelectStatement)
    if !ok {
        t.Fatalf("SelectStatementではない: %T", stmt)
    }
    if sel.From != "USERS" {
        t.Errorf("テーブル名不一致: got %s", sel.From)
    }
    if len(sel.Columns) != 2 || sel.Columns[0].Name != "ID" || sel.Columns[1].Name != "NAME" {
        t.Errorf("カラム不一致: got %v", sel.Columns)
    }
    if got := sel.Where.String(); got != "(ID = 1)" {
        t.Errorf("WHERE句不一致: got %s", got)
    }
}

func TestParse_SelectAll(t *testing.T) {
    stmt, err := parser.Parse("SELECT * FROM products;")
    if err != nil {
        t.Fatal(err)
    }
    if sel := stmt.(*parser.SelectStatement); sel.Columns != nil {
        t.Errorf("SELECT * のときColumnsはnilのはず: got %v", sel.Columns)
    }
}

func TestParse_WherePrecedence(t *testing.T) {
    tests := []struct {
        where string
        want  string
    }{
        {"a = 1 AND b = 2", "((A = 1) AND (B = 2))"},
        {"a = 1 OR b = 2 AND c = 3", "((A = 1) OR ((B = 2) AND (C = 3)))"},
        {"(a = 1 OR b = 2) AND c = 3", "(((A = 1) OR (B = 2)) AND (C = 3))"},
        {"NOT a = 1 AND b <> 'x'", "((NOT (A = 1)) AND (B <> 'x'))"},
    }
    for _, tt := range tests {
        stmt, err := parser.Parse("SELECT * FROM t WHERE " + tt.where)
        if err != nil {
            t.Fatalf("%s: %v", tt.where, err)
        }
        if got := stmt.(*parser.SelectStatement).Where.String(); got != tt.want {
            t.Errorf("%s: want %s, got %s", tt.where, tt.want, got)
        }
    }
}

func TestParse_Join(t *testing.T) {
    stmt, err := parser.Parse(
        "SELECT users.name, orders.amount FROM users JOIN orders ON users.id = orders.user_id")
    if err != nil {
        t.Fatal(err)
    }
    sel := stmt.(*parser.SelectStatement)
    if sel.Columns[0].String() != "USERS.NAME" {
        t.Errorf("修飾付きカラム不一致: got %s", sel.Columns[0])
    }
    if len(sel.Joins) != 1 || sel.Joins[0].Table != "ORDERS" {
        t.Fatalf("JOIN句不一致: got %+v", sel.Joins)
    }
    if got := sel.Joins[0].On.String(); got != "(USERS.ID = ORDERS.USER_ID)" {
        t.Errorf("ON句不一致: got %s", got)
    }
}

func TestParse_Insert(t *testing.T) {
    stmt, err := parser.Parse("INSERT INTO users (id, name) VALUES (42, 'Bob')")
    if err != nil {
        t.Fatal(err)
    }
    ins := stmt.(*parser.InsertStatement)
    if ins.Table != "USERS" || len(ins.Columns) != 2 || len(ins.Values) != 2 {
        t.Fatalf("INSERT文の解析結果が不正: %+v", ins)
    }
    if ins.Values[0].String() != "42" || ins.Values[1].String() != "'Bob'" {
        t.Errorf("VALUES不一致: got %v", ins.Values)
    }
}

func TestParse_CreateTable(t *testing.T) {
    stmt, err := parser.Parse("CREATE TABLE orders (id INT PRIMARY KEY, user_id INT, memo VARCHAR(20))")
    if err != nil {
        t.Fatal(err)
    }
    ct := stmt.(*parser.CreateTableStatement)
    want := []parser.ColumnDef{
        {Name: "ID", Type: "INT", PrimaryKey: true},
        {Name: "USER_ID", Type: "INT"},
        {Name: "MEMO", Type: "VARCHAR", Length: 20},
    }
    if len(ct.Columns) != len(want) {
        t.Fatalf("カラム数不一致: got %d", len(ct.Columns))
    }
    for i := range want {
        if ct.Columns[i] != want[i] {
            t.Errorf("カラム%d: want %+v, got %+v", i, want[i], ct.Columns[i])
        }
    }
}

func TestParse_TransactionStatements(t *testing.T) {
    tests := map[string]parser.Statement{
        "BEGIN":     &parser.BeginStatement{},
        "commit;":   &parser.CommitStatement{},
        "ROLLBACK;": &parser.RollbackStatement{},
    }
    for input, want := range tests {
        stmt, err := parser.Parse(input)
        if err != nil {
            t.Fatalf("%s: %v", input, err)
        }
        if fmt.Sprintf("%T", stmt) != fmt.Sprintf("%T", want) {
            t.Errorf("%s: want %T, got %T", input, want, stmt)
        }
    }
}

func TestParse_Errors(t *testing.T) {
    inputs := []string{
        "SELECT * FROM",                          // テーブル名がない
        "SELECT * FROM t WHERE a = 1 b = 2",      // 余計なトークンが残る
        "INSERT INTO t (a, b VALUES (1, 2)",      // 閉じ括弧がない（無限ループしない）
        "INSERT INTO t VALUES (1, 2",             // 閉じ括弧がない
        "CREATE TABLE t (id TEXT)",               // 未対応の型
        "SELECT * FROM t WHERE name = 'unclosed", // 閉じていない文字列
        "DELETE FROM t",                          // 未対応の文
    }
    for _, input := range inputs {
        if _, err := parser.Parse(input); err == nil {
            t.Errorf("エラーになるはず: %s", input)
        } else {
            t.Logf("%-45s → %v", input, err)
        }
    }
}
go test ./sql/... -v

期待される出力（=== RUN の行は省略）：

--- PASS: TestTokenize (0.00s)
    --- PASS: TestTokenize/SELECT_id,_name_FROM_users_WHERE_id_>=_10 (0.00s)
    --- PASS: TestTokenize/insert_into_t_values_('Alice',_42); (0.00s)
    --- PASS: TestTokenize/a_<>_b_!=_c_<=_d.e_1 (0.00s)
--- PASS: TestTokenize_UnterminatedString (0.00s)
PASS
ok      github.com/yourname/go-rdbms/sql/lexer    0.220s
--- PASS: TestParse_Select (0.00s)
--- PASS: TestParse_SelectAll (0.00s)
--- PASS: TestParse_WherePrecedence (0.00s)
--- PASS: TestParse_Join (0.00s)
--- PASS: TestParse_Insert (0.00s)
--- PASS: TestParse_CreateTable (0.00s)
--- PASS: TestParse_TransactionStatements (0.00s)
    parser_test.go:146: SELECT * FROM                                 → parser: 識別子 を期待しましたが 文の終わり でした
    parser_test.go:146: SELECT * FROM t WHERE a = 1 b = 2             → parser: 予期しないトークンです: "B"
    parser_test.go:146: INSERT INTO t (a, b VALUES (1, 2)             → parser: ) を期待しましたが "VALUES" でした
    parser_test.go:146: INSERT INTO t VALUES (1, 2                    → parser: ) を期待しましたが 文の終わり でした
    parser_test.go:146: CREATE TABLE t (id TEXT)                      → parser: 未対応の型です: "TEXT"
    parser_test.go:146: SELECT * FROM t WHERE name = 'unclosed        → parser: 不正な文字があります: "'unclosed"
    parser_test.go:146: DELETE FROM t                                 → parser: 未対応の文です: "DELETE"
--- PASS: TestParse_Errors (0.00s)
PASS
ok      github.com/yourname/go-rdbms/sql/parser   0.398s

ここまでのコード全体像

go-rdbms/
├── storage/                       ← ストレージエンジン（第3〜6章）
│   ├── page/
│   ├── disk/
│   ├── buffer/
│   ├── heap/
│   └── btree/
└── sql/
    ├── lexer/
    │   ├── token.go               ← トークンの定義（本章）
    │   └── lexer.go               ← 字句解析（本章）
    └── parser/
        ├── ast.go                 ← ASTノードの定義（本章）
        └── parser.go              ← 再帰下降構文解析（本章）

Lexer・Parserの設計で意識したポイント

① 字句解析と構文解析を分ける

空白の読み飛ばしや2文字演算子の判定をLexerに任せることで、Parserは「次のトークンは何か」だけを見て文法を組み立てられます。

② 文法の規則ごとに関数を1つ作る

再帰下降構文解析では、文法とコードがほぼ1対1に対応します。文法を拡張するときも、対応する関数を追加・修正するだけで済みます。

③ 優先順位を関数の呼び出し階層で表す

or → and → not → comparison → primary の順に呼び出すことで、優先順位の高い演算子が木の深い位置（先に評価される位置）に来ます。

④ 入力を最後まで読み切ったかを確かめる

文の後ろに余計なトークンが残っていたらエラーにします。誤った文を黙って部分的に実行してしまうことを防ぎます。

まとめ

次章では、このASTを受け取って実行計画を作り、実際にデータを読み書きするPlannerとExecutorを実装します。