読者です 読者をやめる 読者になる 読者になる

kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Macro PEG 0.0.7 リリース

今回から、sbt-releaseを使ってリリース作業を半自動化してみました。便利ですね、sbt-release。sbt-sonatypeと組み合わせれば、最初にリリース番号と、次のSNAPSHOTバージョン番号答えるだけで後は全自動。

それはともかく、今回のリリースでは、パーザコンビネータを実装してみました。

昨日のエントリでなんかメモ書きしていたのですが

kmizu.hatenablog.com

Macro PEGとParser Combinatorとの関係についてだいぶ理解が進んだので、とりあえず実装してみた感じです。

回文を表すMacro PEG Combinator(MacroPEGParsers)は次のようになります。

object Palindrome {
  lazy val S: MacroParser[Any] = P("") ~ !any
  def P(r: MacroParser[Any]): MacroParser[Any] = "a" ~ refer(P("a" ~ r)) / "b" ~ refer(P("b" ~ r)) / r
}

規則Pに該当するものが引数rを取っているのがポイントです。これはMacro PEGでは、

S = P("") !.; 
P(r) = "a" P("a" r) / "b" P("b" r) / r;

次のようになっています。ほぼ一対一対応しています。

MacroParsersでも評価戦略はcall-by-nameになっていますが(普通に実装するとそうなる)、call-by-value Macro PEGというのを無理くり考えることはできるものの、あまり意味がないのではと考えました。