報國挺身日記 このページをアンテナに追加 RSSフィード

2010/04/10

[] 構文解析 21:09

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)"))
  }
}

2010/04/02

[][] DispatchでOAuth 20:46

Twitter APIのBASIC認証は2010年6月に「廃止予定」というのが気になっている。

今、Scalaの本を読んで勉強しているので、Scalaで何か書いてみたい。

Twitter APIについては、これまでJavaで Twitter4Jを使用してプログラムを書いていた。Scalaの場合でもTwitter4Jを使えば良いのだが、それだとScalaの勉強にはならないと思って、Scala用のOAuthライブラリを探してみた。

その結果、Dispatchというものしか見つけられなかったので、これを使ってstatus更新処理を書いてみると、以下のようになった。(出力されるAuthorize URLにアクセスして、そこから表示されるPINを入力する)

import dispatch._
import oauth._
import oauth.OAuth._

object TwitterTest {
  import Http._

  val CONSUMER_KEY    = "XXX...."
  val CONSUMER_SECRET = "XXX...."
  val CONSUMER = Consumer(CONSUMER_KEY, CONSUMER_SECRET)

  def main(args: Array[String]) {
    val http = fix(new Http)

    val req_token = http(Auth.request_token(CONSUMER))
    println(req_token)
    val authorize_url = Auth.authorize_url(req_token)
    println("Authorize URL: " + authorize_url.to_uri)
    print("PIN: ")
    var PIN = readLine

    val (access_token: Token, user_id: String, screen_name: String)
      = http(Auth.access_token(CONSUMER, req_token, PIN))
    println(access_token)
    println("ACCESS_TOKEN value: "  + access_token.value)
    println("ACCESS_TOKEN secret: " + access_token.secret)
    println("user_id: "     + user_id)
    println("screen_name: " + screen_name)

    val status = "更新テスト#1です。"
    val res = http(Status.update(status, CONSUMER, access_token))
    println(res)
  }

  def fix(http: Http): Http = {
    // WARNING 
    // Invalid cookie header: "Set-Cookie: .....
    // .... Unable to parse expires attribute: ....
    import org.apache.http.cookie.params.CookieSpecPNames

    http.client.getParams().
        setParameter(CookieSpecPNames.DATE_PATTERNS,
            java.util.Arrays.asList("EEE, dd MMM-yyyy-HH:mm:ss z",
                                    "EEE, dd MMM yyyy HH:mm:ss z"))
    http
  }
}

import json._
import JsHttp._

object Twitter {
  val host = :/("twitter.com")
}

object Auth {
  val svc = Twitter.host / "oauth"

  def request_token(consumer: Consumer): Handler[Token]
    = request_token(consumer, OAuth.oob)

  def request_token(consumer: Consumer, callback_url: String) = 
    svc.secure / "request_token" << OAuth.callback(callback_url) <@ consumer as_token
    
  def authorize_url(token: Token)    = svc / "authorize" <<? token
  def authenticate_url(token: Token) = svc / "authenticate" <<? token
  
  def access_token(consumer: Consumer, token: Token, verifier: String) = 
    svc.secure.POST / "access_token" <@ (consumer, token, verifier) >% { m =>
      (Token(m).get, m("user_id"), m("screen_name"))
    }
}

object Status extends Request(Twitter.host / "statuses") {
  def update(status: String, consumer: Consumer, token: Token) = 
        new UpdateStatusBuilder(status, consumer, token)

  class UpdateStatusBuilder(status: String, consumer: Consumer, token: Token) 
          extends Builder[Handler[JsObject]] {
    def product = Status / "update.json" << Map("status" -> status) <@
                    (consumer, token) ># obj
  }
}

fix()の処理は省いても動作するが、警告が表示されるので追加しておいた。

Dispatchの使い方自体がよくわからないので苦労したが、型情報を頼りに試行錯誤した結果、とにかく動いた。