Scalaでパーサーを作ってみる〜4:ブール値とif式

Scalaの勉強をはじめたので、とりあえず簡単なパーサーを作ってみてます。
http://d.hatena.ne.jp/nowokay/20111101#1320102262

前回で、簡単な計算ができるようになりました。
http://d.hatena.ne.jp/nowokay/20111105#1320463263

ということで、今回は、ブール値とif式を導入してみます。
ブール値はtrue/falseなんですが、「true」「false」といったリテラルは実装せず、比較演算子「<」だけ導入してみます。
そして、if式として「if(〜)〜else〜」という形式のものを導入します。

ASTオブジェクトは、これ。

case class IfExpr(cond:AST, pos:AST, neg:AST) extends AST
case class LessOp(left: AST, right:AST) extends AST

で、構文規則は、こう。

  //expr ::= cond | if
  def expr: Parser[AST] = condOp|ifExpr
  //if ::= "if" "(" expr ")" expr "else" expr
  def ifExpr: Parser[AST] = "if"~"("~>expr~")"~expr~"else"~expr^^{
    case cond~_~pos~_~neg => IfExpr(cond, pos, neg)
  }
  //cond ::= add {"<" add}
  def condOp: Parser[AST] = chainl1(add, 
    "<"^^{op => (left:AST, right:AST) => LessOp(left, right)})

if式は、一番最初に定義します。つまり一番優先度が低いということです。
「<」演算子も数式として一番優先度が低いので、一番最初に定義がきてます。

評価の実行はこうなります。

      case IfExpr(cond, pos, neg) =>{
          visit(cond) match{
            case true => visit(pos)
            case false => visit(neg)
          }
      }
      case LessOp(left, right) =>{
          (visit(left), visit(right)) match{
            case (lval:Int, rval:Int) => lval < rval
          }
      }

評価する数式を次のようにすると、27という結果がでました。やりました！

val expr = "3+(if (3 < 5) 12 * 2 else if(3+2) 15 + 3 else 0)"

ところで、ここでif式全体はカッコでくくってますが、これを省くと構文エラーになります。

val expr = "3+if (3 < 5) 12 * 2 else if(3+2) 15 + 3 else 0"

これは、「+」演算子がif式を項として直接もてるような構文規則になっていないからですね。Scalaでも式の途中にif式が出るときはカッコで囲まないと同様にエラーがでます。
ただし、この式はelse側のifの条件3+2とInt値になっているので、Scalaでは型エラーになります。

今回の数式パーサーでは、次のように条件を変更してelse側に処理がいったときに実行時にエラーが出ます。

val expr = "3+if (8 < 5) 12 * 2 else if(3+2) 15 + 3 else 0"

「<」演算子も、構文上は連続できるようになっていますが、実際には実行時に型エラーになります。

このようなエラーをパーサープログラムで出すようにしたいときは、TypeErrorのようなケースクラスを定義して、次のような感じでExprVisitorのvisitメソッドで各構文要素のmatchに「case _」を記述してエラーの処理を行えばいいと思います。

          visit(cond) match{
            case true => visit(pos)
            case false => visit(neg)
            case _ => TypeError("ifの条件で型エラー")
          }

ただ、この場合、２項演算子でどちらかがTypeErrorだったらエラーをそのまま返すように伝播させる必要があります。

      case AddOp(left, right) =>{
          (visit(left), visit(right)) match{
            case (lval:Int, rval:Int) => lval + rval
            case (e:TypeError, _) => e
            case (_, e:TypeError) => e
            case _ => TypeError("+演算子で型エラー")
          }
      }

これが面倒なので、今回はパーサープログラム内での実行時型エラーの処理は行いません。
まあ、例外投げればエラー伝播の面倒はないんですけどね。それなら今回はScala処理系の実行時エラーでいいかと。

ということで、ソースは次のようになってます。

package miniparser

import scala.util.parsing.combinator.RegexParsers

object Main {

  def main(args: Array[String]): Unit = {
    val expr = "3+(if (3 < 5) 12 * 2 else if(3+2) 15 + 3 else 0)"//"12-5*3+7*(2+5)*1+0"
    
    val parser = new MiniParser
    val ast = parser.parse(expr).get

    val visitor = new ExprVisitor
    var result = visitor.visit(ast);
    
    println(result)
  }
}

class ExprVisitor{
  def visit(ast:AST):Any = {
    ast match{
      case IfExpr(cond, pos, neg) =>{
          visit(cond) match{
            case true => visit(pos)
            case false => visit(neg)
          }
      }
      case LessOp(left, right) =>{
          (visit(left), visit(right)) match{
            case (lval:Int, rval:Int) => lval < rval
          }
      }
      case AddOp(left, right) =>{
          (visit(left), visit(right)) match{
            case (lval:Int, rval:Int) => lval + rval
          }
      }
      case SubOp(left, right) =>{
          (visit(left), visit(right)) match{
            case (lval:Int, rval:Int) => lval - rval
          }
      }
      case MulOp(left, right) =>{
          (visit(left), visit(right)) match{
            case (lval:Int, rval:Int) => lval * rval
          }
      }
      case IntVal(value) => value
    }
  }
}

trait AST
case class IfExpr(cond:AST, pos:AST, neg:AST) extends AST
case class LessOp(left: AST, right:AST) extends 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

class MiniParser extends RegexParsers{
  //expr ::= cond | if
  def expr: Parser[AST] = condOp|ifExpr
  //if ::= "if" "(" expr ")" expr "else" expr
  def ifExpr: Parser[AST] = "if"~"("~>expr~")"~expr~"else"~expr^^{
    case cond~_~pos~_~neg => IfExpr(cond, pos, neg)
  }
  //cond ::= add {"<" add}
  def condOp: Parser[AST] = chainl1(add, 
    "<"^^{op => (left:AST, right:AST) => LessOp(left, right)})
  //add ::= term {"+" term | "-" term}.
  def add:  Parser[AST] = chainl1(term,
    "+"^^{op => (left:AST, right:AST) => AddOp(left, right)}|
    "-"^^{op => (left:AST, right:AST) => SubOp(left, right)})
  //term ::= factor {"*" factor}
  def term : Parser[AST] = chainl1(factor, 
    "*"^^{op => (left:AST, right:AST) => MulOp(left, right)})
  //factor ::= intLiteral | "(" expr ")"
  def factor: Parser[AST] = intLiteral | "("~>expr<~")"^^{
    x=>x}
  //intLiteral ::= ["1"-"9"] {"0"-"9"}
  def intLiteral : Parser[AST] = """[1-9][0-9]*|0""".r^^{
    value => IntVal(value.toInt)}

  def parse(str:String) = parseAll(expr, str)
}