Scalaでパーサーを作ってみる〜2:構文木の作成

Scalaの勉強をはじめたので、とりあえず簡単な数式パーサーを作ってみてます。


前回は、とりあえず構文規則を定義しました。
Scalaでパーサーを作ってみる〜1:構文定義 - きしだのはてな


今回は、その構文規則からASTオブジェクトを生成しようと思います。
基底になるASTトレイトを用意して、それぞれの構文要素を定義します。

  trait AST
  case class AddOp(left: AST, right:AST) extends AST
  case class SubOp(left: AST, right:AST) extends AST
  case class MulOp(left: AST, right:AST) extends AST
  case class IntVal(value: Int) extends AST


構文ルールでAST要素を生成するようにします。Parserの型パラメータもAnyからASTに変えておきます。

    //intLiteral ::= ["1"-"9"] {"0"-"9"}
    def intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^{
      case value => IntVal(value.toInt)
    }


ここで

case value => IntVal(value.toInt)

というのは

_ match{
  case value => IntVal(value.toInt)
}

の略ですね、たぶん。
そしてさらに

x => x match{
  case value => IntVal(value.toInt)
}

の略ですね。
Scalaは、こういう省略表記がそこかしこにちりばめられてて、不思議表記がいろいろできるようになります。ぱっと見で、やりたいことそのままになるので、わかりやすい。ただ、書かれた内容から構文を推測するのが難しいんで、「よくわかんないけどこう書いたら動く」ってのが多くなりそう。


あと、構文が組み合わされている部分は、パターンマッチで分解しています。

    //factor ::= intLiteral | "(" expr ")"
    def factor: Parser[AST] = intLiteral | "("~expr~")"^^{
      case _~exp~_ => exp
    }

パターンマッチ便利。ぼくは、パターンマッチを使うためにScala始めました。ラムダだけならGroovyでもいいわけで。


実行するとこんな結果がでました。改行やインデントは後付です。

[1.17] parsed: AddOp(AddOp(SubOp(IntVal(12),MulOp(IntVal(5),IntVal(3))),
                           MulOp(IntVal(7),AddOp(IntVal(2),IntVal(5)))),
                     IntVal(0))


ソースの全体はこんな感じ。
それと、構文規則の定義でexprが直接足し算・引き算をあらわしてたんですけど、addという構文規則を追加しています。

続きを読む