【Rust】データベースを自作する Part3 - SQLパーサーを書く

シリーズ一覧

Part	タイトル	内容
1	B-Treeって何？データ構造から理解する	B-Treeの実装
2	ページ管理とバッファプール	ディスクI/Oの抽象化
3	SQLパーサーを書く	← 今ここ
4	クエリ実行エンジン	実行計画と処理
5	トランザクションとWAL	ACID特性の実装
6	インデックスとクエリ最適化	高速化の仕組み

はじめに

SELECT * FROM users WHERE age > 18

このSQLをデータベースはどうやって理解してるの？

答えはパーサー。

文字列を解析して、「何をしたいのか」を構造化したデータ（AST）に変換する。

今回はRustで本格的なSQLパーサーを実装していこう。

パーサーの構成

SQLパーサーは2段階で処理する：

"SELECT * FROM users"
        ↓
   ① 字句解析（Lexer）
        ↓
[SELECT] [*] [FROM] [users]  ← トークン列
        ↓
   ② 構文解析（Parser）
        ↓
   SelectStatement {
     columns: [Wildcard],
     from: "users"
   }                         ← AST（抽象構文木）

AST（抽象構文木）の定義

まずはパース結果の「型」を定義する。

SQL文の種類

/// SQL文
#[derive(Debug, Clone, PartialEq)]
pub enum Statement {
    Select(SelectStatement),
    Insert(InsertStatement),
    Update(UpdateStatement),
    Delete(DeleteStatement),
    CreateTable(CreateTableStatement),
    DropTable(DropTableStatement),
}

SELECT文

/// SELECT文
#[derive(Debug, Clone, PartialEq)]
pub struct SelectStatement {
    /// 選択するカラム
    pub columns: Vec<SelectColumn>,
    /// FROM句のテーブル名
    pub from: String,
    /// WHERE句（オプション）
    pub where_clause: Option<Expression>,
    /// ORDER BY句（オプション）
    pub order_by: Option<Vec<OrderByClause>>,
    /// LIMIT句（オプション）
    pub limit: Option<u64>,
}

/// SELECTするカラム
#[derive(Debug, Clone, PartialEq)]
pub enum SelectColumn {
    Wildcard,           // *
    Column(String),     // カラム名
}

INSERT文

/// INSERT文
#[derive(Debug, Clone, PartialEq)]
pub struct InsertStatement {
    pub table: String,
    pub columns: Option<Vec<String>>,
    pub values: Vec<Vec<Value>>,
}

WHERE句の式

/// 式（WHERE句などで使用）
#[derive(Debug, Clone, PartialEq)]
pub enum Expression {
    /// リテラル値
    Literal(Value),
    /// カラム参照
    Column(String),
    /// 二項演算（age > 18 など）
    BinaryOp {
        left: Box<Expression>,
        op: BinaryOperator,
        right: Box<Expression>,
    },
    /// 論理演算（AND, OR）
    LogicalOp {
        left: Box<Expression>,
        op: LogicalOperator,
        right: Box<Expression>,
    },
}

/// 二項演算子
#[derive(Debug, Clone, PartialEq)]
pub enum BinaryOperator {
    Eq,      // =
    NotEq,   // !=
    Lt,      // <
    LtEq,    // <=
    Gt,      // >
    GtEq,    // >=
    Like,    // LIKE
}

字句解析器（Lexer）

SQL文字列をトークンに分解する。

トークンの定義

#[derive(Debug, Clone, PartialEq)]
pub enum TokenKind {
    // キーワード
    Select, From, Where, Insert, Into, Values,
    Update, Set, Delete, Create, Table, Drop,
    And, Or, Not, Null, Is, Like,
    Order, By, Asc, Desc, Limit,
    Primary, Key,
    
    // データ型
    Integer, Text, Real, Boolean,
    
    // 識別子・リテラル
    Identifier(String),
    StringLiteral(String),
    NumberLiteral(i64),
    FloatLiteral(f64),
    
    // 演算子
    Eq, NotEq, Lt, LtEq, Gt, GtEq,
    
    // 記号
    Comma, Semicolon, LParen, RParen, Asterisk,
    
    Eof,
}

Lexerの実装

pub struct Lexer {
    input: Vec<char>,
    position: usize,
}

impl Lexer {
    pub fn new(input: &str) -> Self {
        Lexer {
            input: input.chars().collect(),
            position: 0,
        }
    }

    /// 全トークンを取得
    pub fn tokenize(&mut self) -> Result<Vec<Token>, String> {
        let mut tokens = Vec::new();
        
        loop {
            let token = self.next_token()?;
            let is_eof = token.kind == TokenKind::Eof;
            tokens.push(token);
            if is_eof {
                break;
            }
        }
        
        Ok(tokens)
    }
}

トークン読み取りの実装

fn next_token(&mut self) -> Result<Token, String> {
    self.skip_whitespace();
    
    if self.position >= self.input.len() {
        return Ok(Token::new(TokenKind::Eof, self.position));
    }
    
    let ch = self.current_char();
    
    let kind = match ch {
        ',' => { self.advance(); TokenKind::Comma }
        ';' => { self.advance(); TokenKind::Semicolon }
        '(' => { self.advance(); TokenKind::LParen }
        ')' => { self.advance(); TokenKind::RParen }
        '*' => { self.advance(); TokenKind::Asterisk }
        '=' => { self.advance(); TokenKind::Eq }
        '<' => {
            self.advance();
            if self.current_char() == '=' {
                self.advance();
                TokenKind::LtEq
            } else if self.current_char() == '>' {
                self.advance();
                TokenKind::NotEq  // <>
            } else {
                TokenKind::Lt
            }
        }
        '\'' => self.read_string()?,
        _ if ch.is_ascii_digit() => self.read_number()?,
        _ if ch.is_ascii_alphabetic() => self.read_identifier_or_keyword(),
        _ => return Err(format!("Unexpected character: {}", ch)),
    };
    
    Ok(Token::new(kind, start_pos))
}

キーワード判定

識別子を読んだ後、キーワードかどうかチェックする。

fn read_identifier_or_keyword(&mut self) -> TokenKind {
    // 識別子を読み取る
    let s = self.read_while(|c| c.is_ascii_alphanumeric() || c == '_');
    let upper = s.to_uppercase();
    
    // キーワードチェック
    match upper.as_str() {
        "SELECT" => TokenKind::Select,
        "FROM" => TokenKind::From,
        "WHERE" => TokenKind::Where,
        "INSERT" => TokenKind::Insert,
        "INTO" => TokenKind::Into,
        "VALUES" => TokenKind::Values,
        "UPDATE" => TokenKind::Update,
        "AND" => TokenKind::And,
        "OR" => TokenKind::Or,
        // ... 他のキーワード
        _ => TokenKind::Identifier(s),  // キーワードじゃなければ識別子
    }
}

字句解析のテスト

#[test]
fn test_simple_select() {
    let mut lexer = Lexer::new("SELECT * FROM users");
    let tokens = lexer.tokenize().unwrap();
    
    assert_eq!(tokens[0].kind, TokenKind::Select);
    assert_eq!(tokens[1].kind, TokenKind::Asterisk);
    assert_eq!(tokens[2].kind, TokenKind::From);
    assert_eq!(tokens[3].kind, TokenKind::Identifier("users".to_string()));
    assert_eq!(tokens[4].kind, TokenKind::Eof);
}

構文解析器（Parser）

トークン列をASTに変換する。

Parserの構造

pub struct Parser {
    tokens: Vec<Token>,
    position: usize,
}

impl Parser {
    pub fn new(sql: &str) -> Result<Self, String> {
        let mut lexer = Lexer::new(sql);
        let tokens = lexer.tokenize()?;
        Ok(Parser { tokens, position: 0 })
    }

    pub fn parse(&mut self) -> Result<Statement, String> {
        match self.current_token_kind() {
            TokenKind::Select => self.parse_select(),
            TokenKind::Insert => self.parse_insert(),
            TokenKind::Update => self.parse_update(),
            TokenKind::Delete => self.parse_delete(),
            TokenKind::Create => self.parse_create(),
            TokenKind::Drop => self.parse_drop(),
            _ => Err(format!("Unexpected token: {:?}", self.current_token())),
        }
    }
}

SELECT文のパース

fn parse_select(&mut self) -> Result<Statement, String> {
    self.expect(TokenKind::Select)?;
    
    // カラムリスト
    let columns = self.parse_select_columns()?;
    
    // FROM
    self.expect(TokenKind::From)?;
    let from = self.expect_identifier()?;
    
    // WHERE（オプション）
    let where_clause = if self.current_token_kind() == TokenKind::Where {
        self.advance();
        Some(self.parse_expression()?)
    } else {
        None
    };
    
    // ORDER BY（オプション）
    let order_by = if self.current_token_kind() == TokenKind::Order {
        self.advance();
        self.expect(TokenKind::By)?;
        Some(self.parse_order_by_list()?)
    } else {
        None
    };
    
    // LIMIT（オプション）
    let limit = if self.current_token_kind() == TokenKind::Limit {
        self.advance();
        Some(self.expect_number()? as u64)
    } else {
        None
    };
    
    Ok(Statement::Select(SelectStatement {
        columns, from, where_clause, order_by, limit,
    }))
}

式のパース（演算子の優先順位）

WHERE句の式をパースするときは演算子の優先順位を考慮する必要がある。

優先順位（低い → 高い）:
  OR
  AND
  NOT
  比較演算子（=, <, >, <=, >=, LIKE）

これを再帰下降パーサーで実装：

fn parse_expression(&mut self) -> Result<Expression, String> {
    self.parse_or_expression()
}

fn parse_or_expression(&mut self) -> Result<Expression, String> {
    let mut left = self.parse_and_expression()?;
    
    while self.current_token_kind() == TokenKind::Or {
        self.advance();
        let right = self.parse_and_expression()?;
        left = Expression::LogicalOp {
            left: Box::new(left),
            op: LogicalOperator::Or,
            right: Box::new(right),
        };
    }
    
    Ok(left)
}

fn parse_and_expression(&mut self) -> Result<Expression, String> {
    let mut left = self.parse_comparison()?;
    
    while self.current_token_kind() == TokenKind::And {
        self.advance();
        let right = self.parse_comparison()?;
        left = Expression::LogicalOp {
            left: Box::new(left),
            op: LogicalOperator::And,
            right: Box::new(right),
        };
    }
    
    Ok(left)
}

fn parse_comparison(&mut self) -> Result<Expression, String> {
    let left = self.parse_primary()?;
    
    let op = match self.current_token_kind() {
        TokenKind::Eq => BinaryOperator::Eq,
        TokenKind::NotEq => BinaryOperator::NotEq,
        TokenKind::Lt => BinaryOperator::Lt,
        TokenKind::LtEq => BinaryOperator::LtEq,
        TokenKind::Gt => BinaryOperator::Gt,
        TokenKind::GtEq => BinaryOperator::GtEq,
        TokenKind::Like => BinaryOperator::Like,
        _ => return Ok(left),
    };
    
    self.advance();
    let right = self.parse_primary()?;
    
    Ok(Expression::BinaryOp {
        left: Box::new(left),
        op,
        right: Box::new(right),
    })
}

動作確認

実際にパースしてみよう。

let queries = [
    "SELECT * FROM users",
    "SELECT id, name FROM users WHERE age > 18",
    "SELECT * FROM products WHERE price >= 100 AND stock > 0",
    "SELECT * FROM orders ORDER BY created_at DESC LIMIT 10",
    "INSERT INTO users (name, age) VALUES ('Alice', 25)",
    "UPDATE users SET name = 'Charlie' WHERE id = 1",
    "DELETE FROM users WHERE id = 1",
    "CREATE TABLE products (id INTEGER PRIMARY KEY, name TEXT NOT NULL)",
    "DROP TABLE temp_data",
];

for sql in queries {
    println!("SQL: {}", sql);
    match parse_sql(sql) {
        Ok(stmt) => println!("  → {:?}", stmt),
        Err(e) => println!("  → Error: {}", e),
    }
}

実行結果：

SQL: SELECT * FROM users
  → SELECT from 'users'
     columns: [Wildcard]

SQL: SELECT id, name FROM users WHERE age > 18
  → SELECT from 'users'
     columns: [Column("id"), Column("name")]
     has WHERE clause

SQL: SELECT * FROM products WHERE price >= 100 AND stock > 0
  → SELECT from 'products'
     columns: [Wildcard]
     has WHERE clause

SQL: SELECT * FROM orders ORDER BY created_at DESC LIMIT 10
  → SELECT from 'orders'
     columns: [Wildcard]
     ORDER BY: [OrderByClause { column: "created_at", ascending: false }]
     LIMIT: 10

SQL: INSERT INTO users (name, age) VALUES ('Alice', 25)
  → INSERT into 'users'
     1 row(s)

SQL: CREATE TABLE products (id INTEGER PRIMARY KEY, name TEXT NOT NULL)
  → CREATE TABLE 'products'
     - id Integer PRIMARY KEY
     - name Text NOT NULL

ちゃんとパースできてる！

パーサーの改善ポイント

今回の実装は基本形。実用的なパーサーにするには：

機能	説明
エラーリカバリー	構文エラー時に続けてパースを試みる
位置情報	エラー発生箇所を行・列で表示
サブクエリ	SELECT内のSELECT対応
JOIN	テーブル結合の構文
関数	COUNT(), SUM() などの集約関数
GROUP BY / HAVING	グループ化と条件

まとめ

今回作ったもの：

• AST定義: SQL文を表現する型
• Lexer: 文字列→トークン列
• Parser: トークン列→AST

SQLパーサーの基本は再帰下降パーサー。

各SQL句に対応するパース関数を用意して、トークンを消費しながらASTを構築する。

次回はこのASTを使って実際にデータを操作する「クエリ実行エンジン」を実装していく！

この記事が役に立ったら、いいね・ストックしてもらえると嬉しいです！