Ruby で packrat parser

Ruby

packrat parsing というパーサの実装方法があります。特徴は、再帰下降パーサ + 無限先読み可能 + memoize*1 という感じです。僕が下手な説明をするより、英語わからなくても Haskell わかればわかる素晴らしいスライドやPappy (reference implementation) を参照してもらったほうがいいです。

で、練習として Ruby で packrat parser を使って足し算と掛け算だけの電卓を作ってみました。

$ ruby arith.rb
1 + 2 + 3
=> 6
1 + 2 * 3
=> 7
1 + 2 * (3 + 4)
=> 15

文法はこんな感じ。

式　　　　　 = 空白 加算式 文字列終端
加算式　　　 = 乗算式 ("+" 乗算式)*
乗算式　　　 = プリミティブ ("*" プリミティブ)*
プリミティブ = 数値 / "(" 加算式 ")"
(他省略)

以下は加算式とプリミティブの実際の定義。全コードは絶望的に長いので最後に載せます。

# 加算式 = 乗算式 ("+" 乗算式)*
def add
  cache(:add) do                   # memoize のためのラッパ
    v = mul                        # 乗算式読み込み
    vs = many do                   # 0 回以上の繰り返し
      s = sym                      # シンボル読み込み
      no_parse unless s == "+"     # シンボルが "+" 以外だったら失敗
                                   # バックトラックして別の候補を探す
      v2 = mul                     # 乗算式読み込み
      v2
    end
    vs.inject(v) {|v2, z| v2 + z } # 計算して返す
  end
end

# プリミティブ = 数値 / "(" 加算式 ")"
def prim
  cache(:prim) do                  # memoize のためのラッパ
    try(                           # 順序つき OR
      proc { v = decimal; v },     # 数値読み込み
      proc do
        s = sym                    # シンボル読み込み
        no_parse unless s == "("   # シンボルが "(" 以外だったら失敗
        v = add                    # 加算式
        s = sym                    # シンボル読み込み
        no_parse unless s == ")"   # シンボルが "(" 以外だったら失敗
        v
      end
    )
  end
end

try(proc { ... }, proc { ... }, ...) がいけてないのですが、他にいい書き方を思いつきませんでした。


ついでに Pappy を移植する感じで Parsing Expression Grammar の処理系も作ってみましたが、いまいちなのでそのうち。今のところ

  • 最適化を省いたのですごく遅い
  • エラーハンドリングがよくわからなくて実装できてないのですごくデバッグしにくい
  • Pappy の文法が微妙に気に入らない

という感じです。


で、packrat parsing / PEG の感触ですが、

  • (+) conflict とか考えなくていいのがとても幸せ
  • (+) 構文解析がプログラム的にどう行われているか想像しやすい (バックトラック) のがとても幸せ
  • (-) 文法のそこら中で空白を読み飛ばすことを明示しないといけないのを忘れやすい
  • (?) 実用性 (スケーラビリティ・モジュラリティ) はまだわからない
  • (?) 正規表現の代替になるかどうかは、やっぱりうまいリテラルが設計できるかどうか次第

という感じです。


以下ソース。

# packrat parsing ライブラリ
class Packrat
    def initialize(string)
        @string = string
        @index = 0
        @cache = {}
    end

    # memoize のためのラッパ
    def cache(s)
        if (@cache[s] ||= {}).include?(@index)
            v, i = @cache[s][@index]
            i ? (@index = i; v) : no_parse
        else
            begin
                i = @index
                v = yield
                @cache[s][i] = [v, @index]
                v
            rescue NoParse
                @cache[s][i] = nil
                raise
            end
        end
    end

    # パース失敗
    def no_parse
        raise NoParse
    end
    class NoParse < StandardError
    end

    # 順序つき OR
    def try(*ary)
        i = @index
        ary.each do |a|
            begin
                return a.call
            rescue NoParse
                @index = i
            end
        end
        no_parse
    end

    # 先読み AND
    def followed_by
        f = true
        i = @index
        begin
            yield
            f = false
        rescue NoParse
        end
        @index = i
        f ? no_parse : nil
    end

    # 先読み NOT
    def not_followed_by
        f = false
        i = @index
        begin
            yield
            f = true
        rescue NoParse
        end
        @index = i
        f ? no_parse : nil
    end

    # 0 回以上繰り返し
    def many
        try(
            proc { many1 { yield } },
            proc { [] }
        )
    end

    # 1 回以上繰り返し
    def many1
        v = yield
        vs = many { yield }
        [v] + vs
    end

    # 任意の 1 文字にマッチ
    def any_char
        c = @string[@index]
        @index += 1
        c ? c.chr : no_parse
    end

    # pred を満たす 1 文字にマッチ
    def satisfy_char
        c = any_char
        yield(c) ? c : no_parse
    end

    # 指定した 1 文字にマッチ
    def char(ch)
        c = any_char
        c == ch ? c : no_parse
    end

    # 指定した文字列にマッチ
    def string(str)
        str.each_byte do |ch|
            c = any_char
            no_parse if c != ch.chr
        end
        str
    end
end

# 足し算と掛け算だけの電卓
class ArithPackrat < Packrat
    # 式 = 空白 加算式 文字列終端
    # expr = space v:add !any_char -> {v}
    def expr
        cache(:expr) do
            space; v = add; not_followed_by { any_char }; v
        end
    end

    # 加算式 = 乗算式 ("+" 乗算式)*
    # add = v:mul vs:("+" mul)* -> { vs.inject(v) {|v2, z| v2 + z } }
    def add
        cache(:add) do
            v = mul
            vs = many do
                s = sym
                no_parse unless s == "+"
                v2 = mul
                v2
            end
            vs.inject(v) {|v2, z| v2 + z }
        end
    end

    # 乗算式 = プリミティブ ("*" プリミティブ)*
    # mul = v:prim vs:("*" prim)* -> { vs.inject(v) {|v2, z| v2 * z } }
    def mul
        cache(:mul) do
            v = prim
            vs = many do
                s = sym
                no_parse unless s == "*"
                v2 = prim
                v2
            end
            vs.inject(v) {|v2, z| v2 * z }
        end
    end

    # プリミティブ = 数値 ("(" 加算式 ")")*
    # prim = v:decimal -> {v} / "(":sym v:add ")":sym -> {v}
    def prim
        cache(:prim) do
            try(
                proc { v = decimal; v },
                proc do
                    s = sym
                    no_parse unless s == "("
                    v = add
                    s = sym
                    no_parse unless s == ")"
                    v
                end
            )
        end
    end

    # 数値 = (正規表現で \d にマッチする文字)+ space
    # decimal = cs:(c:any_char &{ c[/^\d/] })+ space -> { cs.join.to_i }
    def decimal
        cache(:decimal) do
            cs = many1 { satisfy_char {|c| c[/^\d/] } }
            space
            cs.join.to_i
        end
    end

    # 数値 = ("+" / "*" / "(" / ")") space
    # sym = s:("+" / "*" / "(" / ")") space -> {s}
    def sym
        cache(:sym) do
            s = try(
                proc { char "+" },
                proc { char "*" },
                proc { char "(" },
                proc { char ")" }
            )
            space
            s
        end
    end

    # 空白 = (正規表現で \s にマッチする文字)*
    # space = (c:any_char &{ c[/^\s$/] })*
    def space
        cache(:space) do
            many { satisfy_char {|c| c[/^\s$/] } }
        end
    end
end

while line = $<.gets
    puts "=> " + ArithPackrat.new(line).expr.to_s
end

*1:遅延評価をうまく使えば明示的に memoize しないで済みます。