パーサを書きなれよう

コンパイラのバックエンドを作っていて、あとはフロントエンドをくっつければ完成なわけですが、
フロントエンドも１からささっと作りたいけど、疲れて作れないのは悔しい。
ということで、１からささっとパーサを作る練習をしております。

scalaで、clean bookの簡単なインタプリタを参考に作ったパーサを使ってましたが、
どちらかといえば、whileループで書いたもののほうが簡単でシンプルでいいんだけど、
せっかくだから、末尾再帰化した関数で書いてみるとすっきりするんじゃないかと思って書き直してみました。
書きかけを家で書いて、会社来て覚えてたので、30分くらいで書けました。
ということで、こいつを覚えておけば、パーサは30分で作れて
ここから、もう一段かませてコンパイラ用ASTを作るプログラムを作ってつなげれば完成。
もしくは、このプログラム改造してAST出力を一気にやってしまうのも手です。

使い方は

scala parse "a(1+2)*3*4"

のように使います。

object parse {
  def main(argv:Array[String]) {
    val s = argv(0)
    println(parse(s))
  }

  def apply(s:String):Any = {
    var src = s
    var token = ""
    var ptoken = ""
    val regs = """(?s)^[ \r\n\t]*([0-9]+|[+\-*\/\(\)]|[a-zA-Z_][a-zA-Z_]*|)(.*$)""".r

    def lex():String = {
      ptoken = token
      src match {
        case regs(a,b) => token = a; src = b
        case _ => throw new Exception("syntax error")
      }
      ptoken
    }
    def eat(f:Any):Any = {
      if(lex() != f) throw new Exception("expected error "+f+ " found" + ptoken)
      f
    }

    def pres(t:String):Any = t match {
      case "-" => ("op",0)
      case "(" => ("p",0,")")
      case _ => -1
    }
    def infs(t:String):Any = t match {
      case "+" => ("l", 10)
      case "*" => ("l", 20)
      case "=" => ("r", 5)
      case "(" => ("p", 0, ")")
      case _ => -1
    }
    def exp(p:Int):Any = {
      def pre(t:String):Any = {
        pres(t) match {
          case ("op",np:Int) if(np >= p) => (t, exp(np))
          case ("p", np:Int, ep) => val e = exp(np); (t, e, eat(ep))
          case _ => t
        }
      }
      val t = pre(lex())
      def inf(t:Any):Any = {
        val op = token
        infs(op) match {
          case ("l", np:Int) if(np > p) => lex(); (t, op, exp(np))
          case ("r", np:Int) if(np >= p) => lex(); (t, op, exp(np))
          case ("p", np:Int, ep) => lex(); val e = exp(np); (t, op, e, eat(ep))
          case _ => t
        }
      }
      inf(t)
    }
    lex()
    exp(0)
  }
}