F# 50行で書くパーサコンビネータ
グラフ理論は速攻で三日坊主になってしまったけれども、
ネタができたのでかなり久しぶりに更新してみる。
まず最初に、今回作成したプログラムはあくまで勉強用のものなので
真面目にパーサを書きたい人はFParsec
を使うほうが100万倍良いとおもいます。
というわけで、タイトルにもあるとおり、
最小限の機能だけを詰め込んだパーサコンビネータをF#で書いてみた。理論の知識は適当なので、用語とか変なところがあったら聞き流してください(それでいいのか
なお、以下のプログラムは、変数名に日本語の文字列を使っているので
試す場合はUTF-8で保存が必要です(あるいはパーサ名だけアルファベットに変えてください)
→設定法
#light "off" //文字列の範囲チェック let check1 (str:string) p = if p < str.Length then true else false;; let check2 (str:string) p = if p <= str.Length then true else false;; //1文字を認識するパーサ。predが真となるときマッチなのでnot述語もこれで記述 //基本的なパーサの作成はこの関数でしか行わない let genp pred (str:string) (p:int) = if check1 str p then if pred str.[p] then (true,p,p+1) else (false,p,p) else (false,p,-1);; //選択e1/e2に相当するパーサコンビネータ。F#には|,||, ||| まで定義されてるのでこんな名前に・・ let (||||) pa pb (str:string) (p:int) = let (result,ps,pe) = pa str p in if result then (true,p,pe) else let (resultb,psb,peb) = pb str p in if resultb then (true,p,peb) else (false,p,p);; //並びe1 e2に相当するパーサコンビネータ。選択にあわせてこんな名前に・・ let (>>>>) pa pb (str:string) p = let (result,ps,pe) = pa str p in if result then let (resultb,psb,peb) = pb str pe in if resultb then (true,p,peb) else (false,p,p) else (false,p,p);; //ゼロ個以上の繰り返しに相当するパーサコンビネータ。もっとすっきり書けないかな let many pa (str:string) p = let rec aux pa str (lastresult,rs,re) = let (result,ps,pe) = pa str re in if result then aux pa str (result,ps,pe) else (lastresult,rs,re) in let (result,ps,pe) as r = pa str p in if result then let (_,_,re) = aux pa str r in (true,p,re) else if check2 str p then (true,p,p) else (false,p,-1);; //1個以上の繰り返しに相当するパーサコンビネータ let many1 pa (str:string) p= pa >>>> (many pa);; //省略可能に相当するパーサコンビネータ let option pa (str:string) p = let (result,ps,pe) as r = pa str p in if result then r else if check2 str p then (true,p,p)else (false,p,-1);; //↑パーサはここまで //実際にパースしてみる //パース対象文字列とパーサの結果を取り、表示する関数 let print_match (str:string) (_,s,e) = str.Substring(s,e-s) |> print_any;; let csv_parser = let 改行 = genp ((=)'\n') in let カンマ = genp ((=)',') in let スペース = genp ((=) ' ') in let タブ = genp ((=) '\t') in let ダブルクォート = genp ((=)'"') in let ダブルクォート以外の文字 = genp ((<>)'"') in let 空白文字 = many (スペース |||| タブ) in let カンマダブルクォート改行以外の文字 = genp (fun x -> (x<>'\n')&&(x<>',')&&(x<>'"')) in let ダブルクォート2個 = ダブルクォート >>>> ダブルクォート in let クォート文字列 = many (ダブルクォート以外の文字 |||| ダブルクォート2個) in let ただの文字列 = many カンマダブルクォート改行以外の文字 in let CSVの値 = (空白文字 >>>> ダブルクォート >>>> クォート文字列 >>>> ダブルクォート >>>> 空白文字) |||| ただの文字列 in let CSVの行 = CSVの値 >>>> (many (カンマ >>>> CSVの値)) >>>> 改行 in many CSVの行;; let str = "comma,separated,value\nlotsofcomma,,,,,,,,,newlines\n\n\nthis line don't have eol" in printfn "#####input#####"; print_any str;printfn ""; printfn "#####output##########"; let matched = csv_parser str 0 in matched |> print_match str;printfn ""; printf "matched " |> ignore;print_any matched|>ignore; printfn "";;
このパーサは出来るだけ長くマッチした部分が返ってくる。
最後に改行がない場合はCSVとは見なされない定義になってるので
マッチ結果は途中までとなっている。
なお、CSVの定義については
このサイトを参考にさせて頂きました。
以下、超かいつまんだプログラムの説明
パーサの型(string -> int -> bool * int * int)
パーサ対象は文字列限定
入力：パース対象文字列->対象文字列のパース開始位置
出力：(パースが成功したか、パースを始めた位置、パースを終えた位置)
パーサ
条件が真となるときに1文字読み込むパーサだけ定義。
後は全てパーサを合成して使用する
パーサコンビネータ
選択：2つのパーサが両方真なら真。さもなくば偽
並び：2つのパーサのどちらかが真なら真。さもなくば偽。
繰り返し：与えられたパーサが真の間いけるところまでいって真を返す。
Greedyに動作するので、動作途中の位置からのバックトラックはない、はず。
おそらく、PEGと同じ動作だと思う
さらなる拡張に向けて
比較的簡単な拡張
1．文字を消費せず先読みするパーサの追加
2．文字列リテラルを直接与えられるパーサの追加(合成するだけ)
3．与えられた文字列全体がマッチしたかどうかの判定
パース成功=「入力文字の長さとマッチ結果のパースを終えた位置が等しいか」で判定する
4．パーサに引数を追加し、一つ前にマッチしたパース結果を持たせる
→これで構文木みたいなのが作れるので、
後は構文木を処理するプログラムを書けばマイプログラミング言語が完成？
5．パースに対応するアクションを実行出来るようにする(パーサの引数を増やす)
ただ、バックトラック対応を考えると
構文木を作ってからそれに対してアクションを設定するほうが楽かも
頑張る拡張
1.スキップパーサの作成と、一時的にスキップパーサをOFFにする構文の追加(Boost.spiritにあるやつ)
2.左再帰への対応(HaskellのParsecにはchainlというのがあるらしい。どうやるんだろう？)
3.動的計画法を使ってPackrat Parser？に変える(同じ位置に対するあるパーサの読み込みは1回だけにする)
4.Monadic Parserにする(Computation Expressionの利用)
以上、CSVパーサも入っているのでソース全体は80行弱だけど
パーサ部分は50行に収まりました。
