[Ruby][Scheme] Micro Schemeの実装(9) Parserの改良 - 文字列に対応

へなちょこパーサを廃止し、文字列を扱えるようにパーサを実装した。
https://github.com/takeisa/uschemer/tree/v0.08

Lexerの実装

前回作成したTokenizerクラスで処理するトークンを定義する。
Lexerでは、一行毎にトークン分割をして、結果を配列に格納しておく。
get_tokenメソッドで、読み込んだトークンを一つを返す。
返すトークンが無い場合は、read_tokensメソッドを呼び出し、一行分のトークンを取得する。
unget_tokenメソッドで読み出したトークンを元の配列へ戻す。
これは、トークンを取得して、リストの最後の「)」トークンか判定し、違った場合に元に戻して、
リストのパースを継続するためである。

class Lexer
  def initialize(stream)
    @stream = stream
    @tokens = []

    @tokenizer = Tokenizer.new do |t|
      t.match(/\s+/) do |val|
        # skip
      end

      t.match(/(?:(?:-?[1-9][0-9]*)|0)(?:\.[0-9]+)?/) do |val|
        Token.new(:numeric, eval(val))
      end

      t.match(/"([^"]*)"/) do |val|
        Token.new(:string, val[1..-2])
      end

      t.match(/\(|\)/) do |val|
        Token.new(val.to_sym)
      end

      t.match(/[^\s\(\)]+/) do |val|
        Token.new(:ident, :"#{val}")
      end
    end
  end

  def get_token
    if @tokens.empty? then
      read_tokens
    end
    @tokens.shift
  end

  def read_tokens
    while @tokens.empty?
      line = @stream.readline.chomp
      next if line.empty?
      @tokens = @tokenizer.scan(line)
    end
  end

  def unget_token(token)
    @tokens.unshift(token)
  end
end

Parserの実装

S式のパースなので、非常に簡単だ。
以下のようにS式、リスト、アトムを定義し、再帰下降パーサとして実装した。
S式 := リスト || アトム
リスト := ( S式* )
アトム := 数値 || 文字列 || 識別子

class Parser
  def initialize(lexer)
    @lexer = lexer
  end

  def parse
    parse_sexp
  end

  def parse_sexp
    parse_list || parse_atom
  end

  def parse_list
    token = @lexer.get_token
    unless token.type == :'('
      @lexer.unget_token(token)
      return nil
    end
    list = []
    while TRUE
      token = @lexer.get_token
      if token.type == :')' then
        return list
      end
      @lexer.unget_token(token)
      list.push(parse_sexp)
    end
    list
  end

  def parse_atom
    token = @lexer.get_token
    token.value
  end
end

Parserのテスト

次のコードを実行する。
print Parser.new(Lexer.new(STDIN)).parse
(define (hello) ←入力
"hello") ←入力
[:define, [:hello], "hello"] ← 結果

うまく動いた。

Micro Scheme本体の修正

今回実装したパーサに差し替え、文字列を評価できるようにした。
実行例は以下の通り。

(define (hello) "hello, world!")
 ;=> [:hello,
 [:closure,
  [],
  "hello, world!",
  [{:hello=>[...]},
   {:true=>true, :false=>false},
   {:+=>
     [:built_in,
      #<Proc:0x879dcb0@/home/satoshi/workspace/uschemer/uschemer.rb:10 (lambda)>],
    ...snip...
    :>==>
     [:built_in,
      #<Proc:0x879db70@/home/satoshi/workspace/uschemer/uschemer.rb:18 (lambda)>]}]]]


(hello)
 ;=> "hello, world!"


そろそろテストコードが必要になってきた。
やっぱりRSpecあたりで書くのが順当かな。