Scala: Haskell 本の引き写しでパーサジェネレータ
「プログラミング Haskell
…できた。Haskell 版から変えたところとしては、入力文字列にパーサを適用した際には、Scala らしく Option[(A, String)] を返すようにした、Haskell で [Char] であるところは、適宜 String にした、程度か。案外そのまま行けますね、というよりも、Scala が Haskell を色濃く反映しているんですね。
abstract trait Parser[A] {
def apply(inp: String): Option[(A, String)]
def parse(inp: String) = apply(inp)
def map[B](f: (A) => B) = {
def p_parse = parse _
new Parser[B] {
def apply(inp: String) = {
p_parse(inp) match {
case None => None
case Some((v, out)) => Some((f(v), out))
}
}
}
}
def flatMap[B](f: (A) => Parser[B]): Parser[B] = {
def p_parse = parse _
new Parser[B] {
def apply(inp: String) = {
p_parse(inp) match {
case None => None
case Some((v, out)) => f(v)(out)
}
}
}
}
def +++(q: Parser[A]) = {
def p_parse = parse _
new Parser[A] {
def apply(inp: String) = {
p_parse(inp) match {
case None => q.parse(inp)
case s @ Some(_) => s
}
}
}
}
}
def return_[A](v: A): Parser[A] = {
new Parser[A] { def apply(inp: String) = { Some((v, inp)) } }
}
def failure[A]: Parser[A] = {
new Parser[A] { def apply(inp: String) = { None } }
}
def item: Parser[Char] = new Parser[Char] {
def apply(inp: String) = inp match {
case "" => None
case _ => Some((inp.head, inp.tail))
}
}
def parse[A](p: Parser[A], inp: String): Option[(A, String)] = p(inp)
/*
parse(return_(1), "abc")
res1: Option[(Int, String)] = Some((1,abc))
parse(failure, "abc")
res2: Option[(Nothing, String)] = None
parse(item, "abc")
res3: Option[(Char, String)] = Some((a,bc))
*/
/*
def p = for {
x <- item
_ <- item
y <- item
} yield (x, y)
p: Parser[(Char, Char)]
def p_dash = item.flatMap(x =>
item.flatMap(__ =>
item.map(y =>
(x, y) )))
p_dash: Parser[(Char, Char)]
parse(p, "abcdef")
res4: Option[((Char, Char), String)] = Some(((a,c),def))
parse(p, "ab")
res5: Option[((Char, Char), String)] = None
*/
/*
parse(item +++ return_('d'), "abc")
res6: Option[(Char, String)] = Some((a,bc))
parse(failure +++ return_('d'), "abc")
res7: Option[(Char, String)] = Some((d,abc))
parse(failure +++ failure, "abc")
res8: Option[(Nothing, String)] = None
*/
def sat(p: (Char) => Boolean): Parser[Char] = for {
x <- item
r <- if (p(x)) return_(x) else failure
} yield (r)
def digit = sat(_.isDigit)
def lower = sat(_.isLower)
def upper = sat(_.isUpper)
def letter = sat(_.isLetter)
def alphanum = letter +++ digit
def char(x: Char) = sat(x.==)
/*
parse(digit, "123")
res9: Option[(Char, String)] = Some((1,23))
parse(digit, "abc")
res10: Option[(Char, String)] = None
parse(char('a'), "abc")
res11: Option[(Char, String)] = Some((a,bc))
parse(char('a'), "123")
res12: Option[(Char, String)] = None
*/
// これは文字列を返すパーサとする。Scala の String は List[Char] ではない
def string(s: String): Parser[String] = s match {
case "" => return_("")
case _ => for {
x <- char(s.head)
xs <- string(s.tail)
} yield (x +: xs)
}
/*
parse(string("abc"), "abcdef")
res13: Option[(String, String)] = Some((abc,def))
parse(string("abc"), "ab1234")
res14: Option[(String, String)] = None
*/
object Many {
def many[A](p: Parser[A]): Parser[List[A]] = {
many1(p) +++ return_(Nil)
}
def many1[A](p: Parser[A]): Parser[List[A]] = {
for {
v <- p
vs <- many(p)
} yield (v :: vs)
}
}
import Many._
/*
parse(many(digit), "123abc")
res15: Option[(List[Char], String)] = Some((List(1, 2, 3),abc))
parse(many(digit), "abcdef")
res16: Option[(List[Char], String)] = Some((List(),abcdef))
parse(many1(digit), "abcdef")
res17: Option[(List[Char], String)] = None
*/
// 仕方ないので文字列にしておく
def ident = for {
x <- lower
xs <- many(alphanum)
} yield ((x :: xs).foldLeft("")(_ + _))
// これも
def nat: Parser[Int] = for {
xs <- many1(digit)
} yield (xs.foldLeft("")(_ + _).toInt)
def space: Parser[Unit] = for {
_ <- many(sat(_.isWhitespace))
} yield (Unit)
/*
parse(ident, "abc def")
res0: Option[(java.lang.String, String)] = Some((abc, def))
parse(nat, "123 abc")
res1: Option[(Int, String)] = Some((123, abc))
parse(space, " abc")
res2: Option[(Unit, String)] = Some(((),abc))
*/
def token[A](p: Parser[A]): Parser[A] = for {
_ <- space
v <- p
_ <- space
} yield (v)
def identifier: Parser[String] = token(ident)
def natural: Parser[Int] = token(nat)
def symbol(xs: String): Parser[String] = token(string(xs))
/*
def p: Parser[List[Int]] = for {
_ <- symbol("[")
n <- natural
ns <- many(
for {
_ <- symbol(",")
x <- natural
} yield (x)
)
_ <- symbol("]")
} yield (n :: ns)
parse(p, " [1, 2, 3] ")
res19: Option[(List[Int], String)] = Some((List(1, 2, 3),))
parse(p, "[1, 2,]")
res20: Option[(List[Int], String)] = None
*/
def int: Parser[Int] = (
for {
_ <- symbol("-")
n <- natural
} yield (- n)
) +++ natural
object Expr {
def expr: Parser[Int] = for {
t <- term
r <- (
for {
_ <- symbol("+")
e <- expr
} yield (t + e)
) +++ (
for {
_ <- symbol("-")
e <- expr
} yield (t - e)
) +++ return_(t)
} yield (r)
def term: Parser[Int] = for {
f <- factor
r <- (
for {
_ <- symbol("*")
t <- term
} yield (f * t)
) +++ (
for {
_ <- symbol("/")
t <- term
} yield (f / t)
) +++ return_(f)
} yield (r)
def factor: Parser[Int] = (
for {
_ <- symbol("(")
e <- expr
_ <- symbol(")")
} yield (e)
) +++ int
}
import Expr._
/*
parse(expr, "2*3+4")
res26: Option[(Int, String)] = Some((10,))
parse(expr, "2*(3+4)")
res28: Option[(Int, String)] = Some((14,))
parse(expr, "2 * (3 + 4)")
res30: Option[(Int, String)] = Some((14,))
parse(expr, "2*3-4")
res33: Option[(Int, String)] = Some((2,))
parse(expr, "-1")
res36: Option[(Int, String)] = Some((-1,))
parse(expr, "(-3 * 4 * - 2) / 6")
res43: Option[(Int, String)] = Some((4,))
*/