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

kmizuの日記

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

日本語ぽく書ける(?)パーザコンビネータ

Scala PEG

以前作ったScalaのtoyプログラム色々眺めてたら、なんか発掘されたので、せっかくなので貼っておく。

object ぴーいーじーぱーざこんびねーた {
  type 構文規則 = 構文解析器[Any]
  abstract class 構文解析器[+A] extends (String => Option[(A, String)]) {
    def または[B >: A](that: => 構文解析器[B]): 構文解析器[B] = parserOf{in =>
      this(in) orElse that(in)
    }
    def の次に[B](that: => 構文解析器[B]): 構文解析器[(A, B)] = parserOf{in => 
      for((r1, rest1) <- this(in);
          (r2, rest2) <- that(rest1)) yield ((r1, r2), rest2)
    }
    def に次を適用する[B](f: A => B): 構文解析器[B] = parserOf{in => 
      for((r, rest) <- this(in)) yield (f(r), rest)
    }
    def が0回または1回 : 構文解析器[Option[A]] = parserOf{in => 
      this(in).map{p => (Some(p._1), p._2)}.orElse(Some(None, in))
    }
    def が0回以上 : 構文解析器[List[A]] = parserOf{in => 
      def parse(in: String) : (List[A], String) = {
        this(in) match {
          case Some((r, rest)) => val (r2, rest2) = parse(rest); (r::r2, rest2)
          case None => (Nil, in)
        }
      }
      Some(parse(in))
    }
    def が1回以上 : 構文解析器[List[A]] = (this の次に (this が0回以上)) に次を適用する {p => p._1::p._2}
    def 以外を先読み : 構文解析器[Unit] = parserOf{in => 
      this(in) match {
        case Some(_) => None
        case None => Some((), in)
      }
    }
    def を先読み: 構文解析器[Unit] = (this 以外を先読み) 以外を先読み
  }
  def 文字列(param: String): 構文解析器[String] = parserOf{in =>
    if(in startsWith param) Some(param, (in substring(param length)))
    else None
  }
  lazy val どれでも1文字: 構文解析器[String] = parserOf{in => 
    if(in.length > 0) Some(in substring(0, 1), in substring 1) else None
  }
  def parserOf[A](f: String => Option[(A, String)]): 構文解析器[A] = 
    new 構文解析器[A] {
      def apply(param: String): Option[(A, String)] = f(param)
    }
  implicit def 文字列からパーザへ(param: String) = 文字列(param)
}

利用側は次のような感じ。あ^n い^n う^n(n > 0)という言語を表現するPEGの構文規則。

import ぴーいーじーぱーざこんびねーた._
object ゆーざ {
  lazy val あ: 構文規則 = "あ" の次に (あ が0回または1回) の次に "い"
  lazy val い: 構文規則 = "い" の次に (い が0回または1回) の次に "う"
  lazy val あいう: 構文規則 = ((あ の次に ("い" 以外を先読み)) を先読み) の次に ("あ" が1回以上) の次に い の次に ("う" 以外を先読み)
}
println(ゆーざ あいう(args(0)))