PEG の実装

Ruby

PEG 意見交換会に参加できなくて悔しいので、Ruby で書いた PEG の実装を晒します。

http://dame.dyndns.org/misc/misc/rpeg-20071125.zip


入力は Pappy 風の言語です。下は PEG のパーサを PEG で書いたもの (rpeg.rpeg) です。

parser RPegParser:

{
require "rpeg"
KEYWORDS = %w(parser top debug)
include RPeg
}

top grammar

grammar =
    "parser":keyword name:identifier ":":sym
    c1:raw_code?
    "top":keyword top0:identifier tops:(",":sym t:identifier -> { t })*
    nts:nonterminal*
    c2:raw_code?
    !char
    -> { Grammar.new(name, (c1 || "") + (c2 || ""), [top0] + tops, nts) }

(snip)


この記述を rpegd.rb で処理すると、パーサの Ruby コードが生成されます。

$ ruby rpegd.rb rpeg.rpeg > foo.rb


付属している PEG のパーサ rparser.rb も同じ方法で生成されています。

$ diff foo.rb rparser.rb
$


制限は以下の通りで、実用には耐えません。

  • エラーハンドリングは全くありません。
  • 最適化も全然してません。
  • Ruby のコード断片の中で副作用のあるコードを書いたらわけわからなくなる可能性があります。
  • 変数名の衝突に気をつけてください。下で r2 を r に変えたら、最初の r:seq_rule の r を上書きしてしまってわけわからなくなります。
    r:seq_rule rs:("/":sym r2:seq_rule -> { r2 })* -> { RuleAlt.new([r] + rs) }


勉強会参加者の人がもっといい実装を用意してたら完全に無意味なエントリになる予定です。