最近のキーワード

2006年07月18日

TDP4R 1.3.3: chainlで四則演算

TDP4R 1.3.3でようやく四則演算くらいは楽に記述できるようになった。これは、HaskellのParsecなどのchainl/chainrに相当するものに、中置演算子の優先度も考慮して実装したもの。
例えば、配布アーカイブ中のsample6.rbから抜粋すると、このように書ける。
require 'tdp'

parser = TDParser.define{|g|
  g.plus = "+"
  g.minus = "-"
  g.mult = "*"
  g.div = "/"

  g.expr1 =
    chainl(prim, mult|div, plus|minus){|x|
      case x[1]
      when "+"
        x[0] + x[2]
      when "-"
        x[0] - x[2]
      when "*"
        x[0] * x[2]
      when "/"
        x[0] / x[2]
      end
    }

  g.prim =
    token(:int) >> proc{|x| x[0].value.to_i } |
    token("(") - expr1 - token(")") >> proc{|x| x[1] }

  def parse(str)
    tokenizer = TDPUtils::StringTokenizer[
      /\d+(?!\.\d)/ => :int,
      /\d+\.\d+/ => :real,
    ]
    expr1.parse(tokenizer.generate(str))
  end
}
これは、次のEBNFを記述したもの。
expr1 = expr2 ('+'|'-' expr2)*
expr2 = prim ('*'|'/' prim)*
prim  = ...
それにしても、この程度のことに、2003年から3,4年かかるとは… このライブラリに費やしたのは設計・実装でたぶん実質数週間くらいのはずなので、まるまる3,4年は放置状態ということだ。

余談1:
expr2はtdp4rで書いたものには現れず、展開してexpr1の中へ埋め込んでいる。 そのため、よりtdp4rの書式を反映すると以下のようなEBNF。

expr1 = (prim ('*'|'/' prim)*) ('+'|'-' (prim ('*'|'/' prim)*))*
prim = ...
ここで、A B* というパターンをleftrec(A,B)と記述することにすると、こうなる。
expr1 = leftrec(leftrec(prim, '*'|'/' prim), '+'|'-' leftrec(prim, '*'|'/' prim))
見てのとおり、inject(HaskellやMLではfoldl)を使えるパターンなので、実装においてもinjectを使ってルールを構成するようにしている。 ただ、このように素直に実装したので、速度の面では多少心配なところがあるが、今後可能ならば改良していくことにする。

余談2:
ある人から、標準添付にしてもいいのではというコメントをもらった。前にももらったけど、raccが直接スクリプト中に埋め込めるようになるだろうから(憶測)、需要があるのか多少気になっていた。TDP4Rならではの需要となると、次の2つだろう。

  • 動的にルールを変更できるということと、
  • 文字列のパース以外のものをパースできる
ただし、二つ目については、ストリームに対して処理を行うので、構造をもったものの場合、シーケンシャルな構造へエンコードしなければならない。その一つがXMLなどの木構造なのだけど、tree grammarからbalanced context-free grammarへ変換することを考えればいいだろうか?(このあたりの分野を最近勉強しだしただけ…) でも文字列にエンコードされてはraccでいいじゃんという話に… バカにもできるような美味しいネタはないだろうか?
参考:「Taxonomy of XML Schema Languages using Formal Language Theory」

余談3:
せっかくrubyforgeでホスティングしてもらっているのでgem化してみた。

$ gem install tdp4r
$ gem uninstall tdp4r
でインストール/アンインストールできます。
posted by ttate at 22:29| ☔| Comment(0) | TrackBack(0) | Ruby | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。