構文解析

Scalaのparser combinatorを使って、簡単な構文解析を試してみる。
以下は、よくある四則演算に関数(sin,cos,exp,ln)を追加した例。関数の直前に単項演算子の'-'が来るときの対処がちょっと苦しいが、自然な形で書ける。(floatingPointNumberの方は、それ自身に単項演算子の'-'が含まれている)
'~'がparser combinatorの役割を果たすメソッドで、左右のparserを組み合わせてparserを作り出す。(フォントによって、'~'とマイナス記号が区別し辛いかもしれない)

import scala.util.parsing.combinator._
class FuncArith extends JavaTokenParsers {
  def expr: Parser[Any]   = term   ~ rep("+" ~ term | "-" ~ term)
  def term: Parser[Any]   = factor ~ rep("*" ~ factor | "/" ~ factor)
  def factor: Parser[Any] = floatingPointNumber | opt("-") ~ func_apply | "(" ~ expr ~ ")"
  def func_apply: Parser[Any] = func ~ "(" ~ expr ~ ")"
  def func: Parser[String] = "sin" | "cos" | "exp" | "ln"
}

"+" ~ term の中の"+"のように、parserではなく文字列リテラルを直接書けるのは、JavaTokenParsersのスーパークラスであるRegexParsersの中で、以下のように暗黙の型変換(String => Parser[String])が定義されているため。

 implicit def literal(s: String): Parser[String] = ...

構文解析後の処理を追加した例を以下に示す。
値を実際に計算して表示する。

$ scala FuncArith "1 + sin(3.14/2)"
input: 1 + sin(3.14/2)
result: [1.16] parsed: 1.9999996829318345

"^^"演算子の左側のparserの解析結果を入力として、^^の右側の処理が実行される。

import scala.util.parsing.combinator._

object FuncArith extends JavaTokenParsers {
  type R = Double

  def expr: Parser[R] = term ~
            rep("+" ~> term ^^ (t2 => (t1: R) => t1 + t2) |
                "-" ~> term ^^ (t2 => (t1: R) => t1 - t2)) ^^ {
    case first ~ fs => fs.foldLeft(first) { (x, f) => f(x) }
  }

  def term: Parser[R] = factor ~
            rep("*" ~> factor ^^ (f2 => (f1: R) => f1 * f2) |
                "/" ~> factor ^^ (f2 => (f1: R) => f1 / f2)) ^^ {
    case first ~ fs => fs.foldLeft(first) { (x, f) => f(x) }
  }

  def factor: Parser[R] = floatingPointNumber ^^ (_.toDouble)   |
      opt("-") ~ func_apply ^^ { case Some(_) ~ f => -1.0 * f
                                 case None    ~ f =>  f       } |
      "(" ~> expr <~ ")"

  def func_apply: Parser[R] = func ~ "(" ~ expr ~ ")" ^^ {
    case func ~ _ ~ expr ~ _ => func(expr)
  }

  def func: Parser[R => R] = "sin" ^^^ Math.sin _  |
                             "cos" ^^^ Math.cos _  |
                             "exp" ^^^ Math.exp _  |
                             "ln"  ^^^ Math.log _ 

  def main(args: Array[String]) {
    val s = args(0)
    println("input: " + s)
    println("result: " + parseAll(expr, s))
  }
}

適当なLispの例。

import scala.util.parsing.combinator._

object Lisp extends JavaTokenParsers {
  abstract class E
  case class Lsym(s: String)  extends E
  case class Lnum(i: Int)  extends E
  case class Llist(l: List[E]) extends E

  lazy val list: Parser[E] = "(" ~> rep(expr) <~ ")" ^^ { x => Llist(x) }
  lazy val num: Parser[E]  = """[+-]?[0-9]+""".r ^^ { s => Lnum(s.toInt) }
  lazy val sym: Parser[E]  = """[_a-zA-Z][_a-zA-Z0-9]+""".r ^^ { s => Lsym(s)}
  lazy val expr: Parser[E] = num | sym | list

  def main(args: Array[String]) {
    println(parseAll(expr, "(abc -2 3)"))
  }
}