2013年5月18日土曜日

[Ruby][Scheme] Micro Schemeの実装(9) Parserの改良 - Tokenizerの実装


今のParserは文字列を認識できないため、改良することにした。

冗長なコード

コードを1行ずつ読み込み、トークン分割する部分を書いていたが、以下のコードのように、冗長になってしまい、あまり美しくない。

scanner = StringScanner.new(line)
until scanner.eos?
  scanner.scan(/\s+/)

  value = scanner.scan(/-?[1-9][0-9]*(?:\.[0-9]+)?/)
  if val then
    @tokens.push Token.new(:numeric, eval(value))
    next
  end

  value = scanner.scan(/"([^"]*)"/)
  if val then
    @tokens.push Token.new(:string, value[1..-2])
    next
  end

  value = scanner.scan(/\(|\)/)
  if val then
    @tokens.push Token.new(:"#{value}")
    next
  end

  value = scanner.scan(/[^\s\(\)]+/)
  if val then
    @tokens.push Token.new(:ident, :"#{value}")
    next
  end

  raise "Invalid token error: #{line}"
end



DSL的に

もう少しDSL的に書けるかなと思い、トークン分割するクラスを作ってみた。

次のようなコードで書けるようになった。

tokenizer = Tokenizer.new do |t|
  t.match(/\s+/)                        {} # skip
  t.match(/-?[1-9][0-9]*(?:\.[0-9]+)?/) { |val| "numeric:" + val }
  t.match(/"([^"]*)"/)                  { |val| "string:" + val[1..-2] }
  t.match(/\(|\)/)                      { |val| "symbol:" + val }
  t.match(/[^\s\(\)]+/)                 { |val| "ident:" + val }
end


p tokenizer.scan('(one 2 "three" 4.5)')
# => ["symbol:(", "ident:one", "numeric:2", "string:three", "numeric:4.5", "symbol:)"]


おぉ。ちょっと、すっきり♪


作成したTokenizerクラス


コード

require 'strscan'

class Tokenizer
  def initialize
    @pattern_operations = []
    yield self if block_given?
  end

  def match(pattern, &operation)
    @pattern_operations.push [pattern, operation]
  end

  def scan(string)
    @tokens = []
    scanner = StringScanner.new(string)
    until scanner.eos?
      matched = false
      @pattern_operations.each do |pattern_operaion|
        pattern, operation = pattern_operaion
        val = scanner.scan(pattern)
        if val then
          token = operation.call(val)
          @tokens.push(token) if token
          matched = true
          break
        end
      end
      unless matched
        raise "invalid token error"
      end
    end
    @tokens
  end
end


説明

(1)コンストラクタで自分自身をyieldして、ブロックで定義できるようにする。
Metaprogramming Rubyでは 自己Yield と呼んでいる。
(2)matchメソッドが呼ばれる度に、トークンにマッチさせるパターンと、そのブロックをリストに積む。
(3)scanメソッドでは解析する文字列を受け取り、(2)で記録したパターンを順次適用し、一致した場合に、対応するブロックを実行する。
(4)ブロックが返す結果をトークンとして配列に積む。
(5)すべて文字列の処理を完了で、トークンの配列を返す。
(6)処理できないトークンの場合はエラー。

次はこのクラスを使って、LexerとParserを作成しよう。