Hatena::Groupocaml-nagoya

yoshihiro503の関数的日記

2009-07-11 (Sat)JavaでParserモナド

JavaでParserモナド

| 20:47 | JavaでParserモナド - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - JavaでParserモナド - yoshihiro503の関数的日記

Java で Parser モナドを書いてみた。

JavaGenerics(ポリモルフィズム)があるのでほとんどcastを使わず型安全に実装できたが型推論がないので型が非常に冗長になった。

このパーサーライブラリを使えば、例えばラムダ式のパーサーが次のように30行くらいで書ける。P.mbind, P.dbind, P.mor, P.mreturn はそれぞれ Haskellでいう >>=, >>, <|>, return に対応する。

    static Parser<LAMBDA> lambda () {
	return P.mor(P.map (T.ident, new Fun<String,LAMBDA>() {
		    public LAMBDA apply (final String v) {
			return new VAR(v);
		    } }),
	    P.mor (P.dbind(T.symbol('('), P.dbind(T.symbol('\\'), P.bind (T.ident, new Fun<String,Parser<LAMBDA>>() {
				public Parser<LAMBDA> apply (final String v) {
				    return P.dbind(T.symbol('.'), P.bind (lambda(), new Fun<LAMBDA,Parser<LAMBDA>>() {
						public Parser<LAMBDA> apply (final LAMBDA t) {
						    LAMBDA abs = new ABS(v,t);
						    return P.dbind(T.symbol(')'), P.mreturn (abs));
						} }));
				} }))),
		   P.bind(T.symbol('('), new Fun<Unit,Parser<LAMBDA>>() {
			   public Parser<LAMBDA> apply(Unit _) {
			       return P.bind(lambda(), new Fun<LAMBDA,Parser<LAMBDA>>() {
				       public Parser<LAMBDA> apply (final LAMBDA t1) {
					   return P.bind(lambda(), new Fun<LAMBDA,Parser<LAMBDA>>() {
						   public Parser<LAMBDA> apply (final LAMBDA t2) {
						       LAMBDA app = new APP(t1, t2);
						       return P.dbind(T.symbol(')'), P.mreturn (app));
						   } });
				       } });
			   } })));
    }

使い方

 $ java Main '((\x.x) ( \ y. (y y)) )'
パース成功: ((λx.x) (λy.(y y)))

パースした結果は以下の記事にかいてあったラムダ式を利用しようかと思ったけど、ちょっとそのままじゃ使えなかったので諦めた。

Java でラムダ - IT戦記

ソースコード全体は300行くらい

http://bitbucket.org/yoshihiro503/parsecinjava/src/

2009-04-26 (Sun)Rubyのパーサーを実装してみた

OCamlでRubyのパーサー

| 00:06 | OCamlでRubyのパーサー - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - OCamlでRubyのパーサー - yoshihiro503の関数的日記

Rubyサブセットmin_rubyのパーサーをOCamlで実装してみた

http://bitbucket.org/yoshihiro503/min_ruby/ (* 引っ越しました *)

http://bitbucket.org/yoshihiro503/ocamlruby/

プログラムは今のところ全部で232行

実装した構文
================

	- メソッド定義
	- クラス定義
	- 関数呼び出し
	- フィールド参照
	- 変数代入
	- if式
	- リテラル(数値、真偽値)
	- 四則演算
	- 大小比較
	- bool演算


まだないもの
====================
	
	- 文字, 文字列, 配列
	- 正規表現
	- ブロック構文
	- 範囲リテラル
	- シンボル
	- 省略可能な引数
	- 引数カッコの省略
	- インスタンス変数
	- 継承
	- モジュール

例えば次のコードパースできる。

class C
  def f (x, y)
    if (4 * x == 4 || 3 * (y+2) >= 6+1) then
      true
    else
      false
    end
  end
  
  def g ()
    f (0, 1)
  end
end

class D
  def foo ()
    puts 5
  end
end

def fib (n)
  if n <= 2 then
    0
  else
    (fib (n - 1)) + (fib (n - 2))
  end
end

puts (fib (3))

字句解析はgenlexモジュールを使って、パーサーはHaskellのParsecのようなコンビーネータを作って、それを使った。参考にしたのは以下の文献