こんにちは Racc

2007年5月30日

パーサジェネレーター

HelloCupと言ったとき、私はダーティポインタを処理する必要のない言語でyaccベースのパーサを見ていました。もう1つの試す価値のある選択肢はRubyです。Rubyには標準ライブラリにyaccのようなパーサが組み込まれています。それは必然的にraccと呼ばれています。

Raccは、rubyと文法構文の間で興味深い相互作用があります。パーサクラスを生成するraccファイルで文法を定義します。

ここでも簡単なハローワールドの例を作成します。入力テキストは次のとおりです。

item camera
item laser

次のモデルクラスを使用して、カタログ内にアイテムオブジェクトを生成します。

class Item
  attr_reader :name
  def initialize name
    @name = name
  end
end

class Catalog 
  extend Forwardable
  def initialize
    @items = []
  end
  def_delegators :@items, :size, :<<, :[] 
end

Forwardableは、メソッドをインスタンス変数に委譲できる便利なライブラリです。この場合、@itemsリストに一連のメソッドを委譲します。

これを読み込んだ内容をテストします。

class Tester < Test::Unit::TestCase
  def testReadTwo
    parser = ItemParser.new
    parser.parse "item camera\nitem laser\n"
    assert_equal 2, parser.result.size
    assert_equal 'camera', parser.result[0].name
    assert_equal 'laser', parser.result[1].name
  end
  def testReadBad
    parser = ItemParser.new
    parser.parse "xitem camera"
    fail
    rescue #expected
  end   
end

ファイルをビルドしてテストを実行するには、簡単なrakeファイルを使用します。

# rakefile...
task :default => :test

file 'item.tab.rb' => 'item.y.rb' do
  sh 'racc item.y.rb'
end

task :test => 'item.tab.rb' do 
  require 'rake/runtest'
  Rake.run_tests 'test.rb'
end

raccコマンドはシステムにインストールする必要があります。Ubuntuでは、apt-getで簡単にインストールしました。このコマンドは、入力ファイルを受け取り、inputFileName.tab.rbという名前のファイルを作成します。

パーサ文法クラスは特殊な形式ですが、yaccのような人には非常に馴染み深い形式です。この簡単な例では、次のようになります。

#file item.y.rb...
class ItemParser
  token 'item'  WORD
  rule
    catalog: item | item catalog;
    item: 'item' WORD {@result << Item.new(val[1])};
end

tokens句は、lexerから取得するトークンを宣言します。文字列'item'とWORDをシンボルとして使用します。rule句は、yaccの通常のBNF形式のプロダクションルールを開始します。予想通り、中括弧内にアクションを記述できます。ルールの要素を参照するには、val配列を使用します。したがって、val[1]はyaccの$2に相当します（rubyは0ベースの配列インデックスを使用していますが、私はそれを許容しています）。ルールから値を返したい場合（yaccの$$に相当）、それを変数resultに代入します。

raccを使用する上で最も複雑な部分は、lexerを整理することです。Raccは、トークンを生成するメソッドを呼び出すことを期待しています。各トークンは、最初の要素がトークンのタイプ（トークン宣言と一致）であり、2番目の要素が値（valに表示されるもの - 通常はテキスト）である2要素の配列です。トークンストリームの終わりは[false, false]でマークします。raccを使用したサンプルコードでは、文字列に対して正規表現マッチングを使用します。ほとんどの場合、より良い選択肢は、標準のrubyライブラリにあるStringScannerを使用することです。

このスキャナーを使用して、文字列をトークンの配列に変換できます。

#file item.y.rb....
---- inner
def make_tokens str
  require 'strscan'
  result = []
  scanner = StringScanner.new str
  until scanner.empty?
    case
      when scanner.scan(/\s+/)
        #ignore whitespace
      when match = scanner.scan(/item/)
        result << ['item', nil]
      when match = scanner.scan(/\w+/)
        result << [:WORD, match]
      else
        raise "can't recognize  <#{scanner.peek(5)}>"
    end
  end
  result << [false, false]
  return result
end

スキャナーをパーサーに統合するために、raccでは生成されたパーサークラスにコードを配置できます。これを行うには、文法ファイルにコードを追加します。宣言---- innerは、生成されたクラス内に入るコードをマークします（生成されたファイルの先頭と末尾にもコードを配置できます）。テストでparseメソッドを呼び出しているので、それを実装する必要があります。

#file item.y.rb....
---- inner
attr_accessor :result

def parse(str)
  @result = Catalog.new
  @tokens = make_tokens str
  do_parse
end

do_parseメソッドは、生成されたパーサーを開始します。これにより、next_tokenを呼び出して次のトークンを取得するため、そのメソッドを実装し、innerセクションに含める必要があります。

#file item.y.rb....
---- inner
def next_token
  @tokens.shift
end

これでraccをファイルで使用するのに十分です。しかし、試行錯誤するうちに、スキャナーが思ったより煩雑だと感じています。lexerにマッチングするパターンとそれらで何を返すかを伝えるだけでよいのです。このようなものです。

#file item.y.rb....
---- inner
def make_lexer aString
  result = Lexer.new
  result.ignore /\s+/
  result.keyword 'item'
  result.token /\w+/, :WORD
  result.start aString
  return result
end

これを機能させるには、StringScannerが提供する基本機能の上に、独自のlexerラッパーを作成します。以下は、lexerを設定し、上記の構成を処理するためのコードです。

class Lexer...
  require 'strscan'
  def initialize 
    @rules = []
  end
  def ignore pattern
    @rules << [pattern, :SKIP]
  end
  def token pattern, token
    @rules << [pattern, token]
  end
  def keyword aString
    @rules << [Regexp.new(aString), aString]
  end
  def start aString
    @base = StringScanner.new aString
  end

スキャンを実行するには、StringScannerを使用して、ルールを入力ストリームと比較する必要があります。

class Lexer...
  def next_token
    return [false, false] if @base.empty?
    t = get_token
    return (:SKIP == t[0]) ? next_token : t
  end
  def get_token
    @rules.each do |key, value|
      m = @base.scan(key)
      return [value, m] if m
    end 
    raise  "unexpected characters  <#{@base.peek(5)}>"
  end

次に、パーサーのコードを変更して、代わりにこのlexerを呼び出すことができます。

#file item.y.rb....
---- inner
def parse(arg)
  @result = Catalog.new
  @lexer = make_lexer arg
  do_parse
end

def next_token
  @lexer.next_token
end

これにより、ルールの定義を改善できるだけでなく、文法がlexerを制御できるようになります。これは、一度に1つのトークンしか取得しないため、後で字句状態を実装するメカニズムを提供します。

全体的に、raccはセットアップと使用が非常に簡単です。ただし、yaccを知っていることが前提です。ドキュメントは、大まかに言えば最小限です。Webサイトには簡単なマニュアルとサンプルコードがあります。また、raccに関する非常に役立つプレゼンテーションもあります。また、Mingle内の優れたカスタマイズ言語に使用しているMingleチームからもいくつかのヒントを得ました。