この記事は RubyでDBMS Advent Calendar 2019 の3日目の記事です。

本日の概要

2日目はサーバに渡ってきた文字列をSQLとして解析するに当たって、
意味のある最小単位であるトークンに分解するところまで実装しました。(字句解析)
本日は後半のフェーズである構文解析を実装します。

実装はこちらのGitHubリポジトリに置いてあります。

構文解析とは

構文解析では、字句解析で分割したトークンの配列を、
予め定義した構文規則に照らし合わせていきます。
(広義には字句解析、構文解析を二つまとめて構文解析と呼ぶこともあるそうです)

BNF

BNFというプログラミング言語の構文を定義するのによく用いられる記法を用いて、
今回のオレオレSQLの構文定義をしていきます。
BNFについての解説は省略します。

SQL９２のBNFを見つけたので、こちらを参考に定義してみます。

<select statement> ::= SELECT <select list> FROM <string literal> [ WHERE <search condition> ]
<select list> ::= <asterisk> | <string literal> [ { <comma> <string literal> }... ]
<search condition> ::= <string literal> <comp operator> <row value>
<comp operator> ::= <equal> | <not equal> | <greater than> | <greater than equal> | <less than> | <less than equal>
<row value> ::= <numeric_literal> | <quote> <string literal> <quote>

<create statement> ::= CREATE TABLE <string literal> <table element list>
<table element list> ::= <left paren> <table element> [ { <comma> <table element> }... ] <right paren>
<table element> ::= <string literal> <data type>
<data type> ::= INT | VARCHAR

<insert_statement> ::= INSERT INTO <string literal> VALUES <left paren> <row value> [ { <comma> <row value> }... ] <right paren>

記法の差異は多々あるようですが、
[]で囲まれた部分は省略可能
{}...で0回以上の繰り返し
|はOR
となっています。

また、2日目で述べた通り、初期段階ではサポートするクエリは最小限に留めるため、SQL９２のBNFとは異なる部分も多々あります。
例えば FROM <string literal> の部分など、今後JOINを実装する際には、変更しなければなりませんね。

解析処理

定義したBNFの各要素ごとにメソッドに切り出し、
トークンを頭から一つずつ走査していくことで解析していきます。
再帰下降構文解析というらしいですが、詳細調べようとしたら沼にはまりそうだったのでご興味持たれた方は各自調べてみてください。

SELECT文に関する部分だけ抜き出してあります。
詳しくはGitHubをご覧いただければと思います。

rbdb/query/parser.rb

# frozen_string_literal: true

require 'rbdb/query/ast/select_statement'
require 'rbdb/query/ast/search_condition'

module Rbdb
  module Query
    class Parser
      def initialize(tokens)
        @tokens = tokens
        @cur = 0
      end

      def parse
        case @tokens[0].kind
        when :select_keyword
          select_statement
        when :create_keyword
          create_statement
        when :insert_keyword
          insert_statement
        else
          raise 'parse error'
        end
      end

      private

      def peek(n = 1)
        @cur += n
      end

      # 現在のトークンが期待する種別かを判定する
      # 期待するものの場合は、イテレータを一つ進め、トークンを返す
      # 期待しないものの場合は、イテレータは進めず、nilを返す
      def expect(kind)
        current_token = @tokens[@cur]
        return nil unless current_token.kind == kind
        peek
        current_token
      end

      # トークンが期待しないものの場合は、例外を発生させる
      # それ以外は#expectと同じ挙動
      def expect!(kind)
        current_token = expect(kind)
        raise 'parse error' unless current_token
        current_token
      end

      def select_statement
        expect!(:select_keyword)
        sl = select_list
        expect!(:from_keyword)
        table_name = expect!(:string_literal).value
        sc = search_condition if expect(:where_keyword)
        Rbdb::Query::Ast::SelectStatement.new(
          table_name: table_name,
          select_list: sl,
          search_condition: sc,
        )
      end

      def select_list
        return :asterisk if expect(:asterisk)
        columns = []
        columns << expect!(:string_literal).value
        while expect(:comma) do
          columns << expect!(:string_literal).value
        end
        columns
      end

      def search_condition
        lo = expect!(:string_literal).value
        co = comp_operator
        ro = row_value
        Rbdb::Query::Ast::SearchCondition.new(
          left_operand: lo,
          comp_operator: co,
          right_operand: ro,
        )
      end

      def comp_operator
        if expect(:equal) then
          :equal
        elsif expect(:not_equal) then
          :not_equal
        elsif expect(:greater_than) then
          :greater_than
        elsif expect(:greater_than_equal) then
          :greater_than_equal
        elsif expect(:less_than) then
          :less_than
        elsif expect(:less_than_equal) then
          :less_than_equal
        else
          raise 'parse error'
        end
      end

      def row_value
        nl = expect(:numeric_literal)
        return nl.value if nl
        expect!(:quote)
        sl = expect!(:string_literal)
        expect!(:quote)
        sl.value
      end
    end
  end
end

概ね各メソッドがBNFの定義と対応してるのが分かると思います。
どのように実装していくか少し悩んだのですが、
各々上記コメントの通り動作をする expect と expect! という2つのメソッドを用意しました。
次に来るべきトークン種別が必ず決まっている場合は expect! を用い、
OR条件のような部分では expect を用いるようにしています。

また、AST(抽象構文木)というNamespaceを切って、結果をこちらのクラスのインスタンスに保持しています。

rbdb/query/ast/select_statement.rb

# frozen_string_literal: true

module Rbdb
  module Query
    module Ast
      class SelectStatement
        def initialize(table_name:, select_list:, search_condition: nil)
          @table_name = table_name
          @select_list = select_list
          @search_condition = search_condition
        end
      end
    end
  end
end

rbdb/query/ast/search_condition.rb

# frozen_string_literal: true

module Rbdb
  module Query
    module Ast
      class SearchCondition
        def initialize(left_operand:, comp_operator:, right_operand:)
          @left_operand = left_operand
          @comp_operator = comp_operator
          @right_operand = right_operand
        end
      end
    end
  end
end

動作確認

デバッグ用に各ASTクラスに to_str メソッドをoverrideしたので、
このようにレスポンスで返してみます。

rbdb/server.rb

        tokens = Rbdb::Query::Lexer.new(query).scan
        ast = Rbdb::Query::Parser.new(tokens).parse
        # TODO:
        res.body += ast

クライアントからクエリを叩いてみます。

>> CREATE TABLE users (id int, name varchar);
--CREATE STATEMENT--
table: users
columns:
  name: id, data_type: int
  name: name, data_type: varchar

>> INSERT INTO users VALUES (1, 'hoge');
--INSERT STATEMENT--
table: users
values: 1, hoge,

>> SELECT id, name FROM users WHERE id = 1;
--SELECT STATEMENT--
table: users
columns: id, name,
condition: id equal 1

大丈夫そうですね!

まとめ

構文解析全般に関する筆者の知識不足な点もあり、詳細を省略したまま駆け足となってしまいましたが、
今回で一通り単なる文字列を意味のあるクエリとして解釈できるところまで到達できました。
明日は一旦はこちらを元に、揮発性のDB(rbdbコマンドを終了するとデータは消えてしまう)をとりあえず作ってみたいと思います。

RubyでDBMSを実装 構文解析(3日目)

本日の概要

構文解析とは

BNF

解析処理

動作確認

まとめ

RubyでDBMSを実装構文解析(3日目)