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

本日の概要

初日は特に中身のないechoサーバとクライアントで終わってしまいましたが、
本日から実際にサーバに渡ってきた文字列をSQLとして解析していきます。
本日はその中でも前半のフェーズである字句解析を実装します。

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

字句解析とは

字句解析とは、ただの文字列をそれ以上分割できない意味のある最小単位(トークン)に分割する処理です。
例として、以下のSQLを想定した文字列をトークンに分割してみます。

SELECT id,email FROM users WHERE id=5;

文字列	種別	値
SELECT	select keyword	-
id	string literal	id
,	comma	-
email	string literal	email
FROM	from keyword	-
users	string literal	users
WHERE	where keyword	-
id	string literal	id
=	equal	-
5	numeric literal	5
;	semicolon

(種別の部分は筆者の勝手な命名となります)
一部トークン(リテラル)には値も含まれます。
とりあえず、classとして切り出しておきます。

rbdb/query/token.rb

# frozen_string_literal: true

module Rbdb
  module Query
    class Token
      attr_reader :kind, :value
      def initialize(kind, value = nil)
        @kind = kind
        @value = value
      end
    end
  end
end

クエリ設計

では、早速分割処理を実装していきたいところですが、
今後の初期開発でサポートする最低限のクエリを決めておきます。

CREATE文

型はint, varcharのみ。
制約などは含まず。

INSERT文

CREATE文でデフォルト値を指定できないので、全カラムを指定するもののみ。

INSERT INTO table_name VALUES (value1, value2);

SELECT文

* による全カラム指定と一部カラムのみ指定どちらも可能。
WHERE句あり。
条件部分は単純な operand (=|<>|<=|>=|<|>) operand のようなもののみ。

解析処理

では、Lexer(字句解析器という意味)というクラスを作って実装していきます。

rbdb/query/lexer.rb

# frozen_string_literal: true

require 'rbdb/query/token'

module Rbdb
  module Query
    class Lexer
      def initialize(query)
        @query = query
        @sio = StringIO.new(@query)
        @tokens = []
      end

      def scan
        while ch = @sio.read(1) do
          if ch == "'" then
            @tokens << Token.new(:quote)
          elsif ch == '(' then
            @tokens << Token.new(:left_paren)
          elsif ch == ')' then
            @tokens << Token.new(:right_paren)
          elsif ch == '*' then
            @tokens << Token.new(:asterisk)
          elsif ch == ',' then
            @tokens << Token.new(:comma)
          elsif ch == ';' then
            @tokens << Token.new(:semicolon)
          elsif ch == '=' then
            @tokens << Token.new(:equal)
          elsif ch == '<' then
            _next = @sio.read(1)
            if _next == '>' then
              @tokens << Token.new(:not_equal)
            elsif _next == '=' then
              @tokens << Token.new(:less_than_equal)
            else
              back
              @tokens << Token.new(:less_than)
            end
          elsif ch == '>' then
            _next = @sio.read(1)
            if _next == '=' then
              @tokens << Token.new(:greater_than_equal)
            else
              back
              @tokens << Token.new(:greater_than)
            end
          elsif ch =~ /[A-Za-z]/ then
            buf = ch
            while _next = @sio.read(1) do
              if _next =~ /[A-Za-z0-9_]/ then
                buf += _next
              else
                back
                break
              end
            end
            _keyword = keyword(buf)
            if _keyword then
              @tokens << Token.new(_keyword)
            else
              @tokens << Token.new(:string_literal, buf)
            end
          elsif ch =~ /[0-9]/ then
            buf = ch
            has_period = false
            while _next = @sio.read(1) do
              if _next =~ /[0-9\.]/ then
                raise 'tokenize error' if has_period && _next == '.'
                has_period = true if _next == '.'
                buf += _next
              else
                back
                break
              end
            end
            if has_period then
              @tokens << Token.new(:numeric_literal, buf.to_f)
            else
              @tokens << Token.new(:numeric_literal, buf.to_i)
            end
          end
        end
        @tokens
      end

      def back
        @sio.seek(-1, IO::SEEK_CUR)
      end

      def keyword(str)
        case str.upcase
        when "SELECT"
          :select_keyword
        when "FROM"
          :from_keyword
        when "WHERE"
          :where_keyword
        when "INSERT"
          :insert_keyword
        when "INTO"
          :into_keyword
        when "VALUES"
          :values_keyword
        when "CREATE"
          :create_keyword
        when "TABLE"
          :table_keyword
        when "INT"
          :int_keyword
        when "VARCHAR"
          :varchar_keyword
        end
      end
    end
  end
end

大分長いメソッドや、ネストが激しくなってしまいましたが………
StringIO クラスを用いて、先頭から一文字ずつ走査していきます。
' や ( など一文字目でそのトークン種別を決定できるものもある一方で、
< は、 <> や <= , < など複数の可能性があるため、
さらに文字の読み込みを進めることで判定します。
また、backというメソッドを用意して、不要な読み込みをしてしまった場合一文字前に戻るようにしています。
アルファベットから始まる文字列は、予約語に当てはまるかをチェックした上で、それ以外を文字列リテラルと解釈します。

動作確認

1日目でそのままechoしていたクエリの代わりに、
分割したTokenクラスをinspectしてそのままレスポンスで返してみます。

rbdb/server.rb


        tokens = Rbdb::Query::Lexer.new(query).scan
        # TODO:
        tokens.each do |token|
          res.body += token.inspect
          res.body += "\n"
        end

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

>> SELECT id,email FROM users WHERE id=5;
#<Rbdb::Query::Token:0x00007f7feb0c5360 @kind=:select_keyword, @value=nil>
#<Rbdb::Query::Token:0x00007f7feb0c51a8 @kind=:string_literal, @value="id">
#<Rbdb::Query::Token:0x00007f7feb0c5130 @kind=:comma, @value=nil>
#<Rbdb::Query::Token:0x00007f7feb0c4bb8 @kind=:string_literal, @value="email">
#<Rbdb::Query::Token:0x00007f7feb0c4578 @kind=:from_keyword, @value=nil>
#<Rbdb::Query::Token:0x00007f7ffb05faa0 @kind=:string_literal, @value="users">
#<Rbdb::Query::Token:0x00007f7ffb05f690 @kind=:where_keyword, @value=nil>
#<Rbdb::Query::Token:0x00007f7ffb05f4d8 @kind=:string_literal, @value="id">
#<Rbdb::Query::Token:0x00007f7ffb05f460 @kind=:equal, @value=nil>
#<Rbdb::Query::Token:0x00007f7ffb05f398 @kind=:numeric_literal, @value=5>
#<Rbdb::Query::Token:0x00007f7ffb05f348 @kind=:semicolon, @value=nil>

大丈夫そうですね!

まとめ

筆者は自作コンパイラなどに手を出したこともないので、
今回初めて字句解析を実装したのですが、なかなか思ってたよりも愚直な処理になりますね。

明日は分割したもののただの配列でしかないTokenたちをSQLの構文として解析していく予定です。

RubyでDBMSを実装 字句解析(2日目)