シンプルで高速な構文解析ライブラリ「Parsec」を.NETで使う^^
Parsecって何?
Parsec は Haskell のモナドパーサコンビネータライブラリで、文脈依存文法や無限先読み文法を解析できますが、 LL文法と同等の性能を出します。
コンビネータパーサはプログラムの他の部分と同じプログラミング言語を使って書かれます。文法の形式化 (Yacc) とそこで使われるプログラミング言語 (C) のギャップがありません。ユーザはたったひとつの言語を学ぶだけで済みます！
参考参考
2004-07-30
http://alohakun.blog7.fc2.com/blog-entry-654.html
ライブドアブログ（livedoor Blog）｜ 読みたいブログが見つかる
これは魅力的＞＜
僕が今欲しいのはまさにこれじゃないか!!!
で、いろんな言語に移植されてるみたいです。
.NETでも使えるやつ
NParsec、C#で使えるよー NParsec+Tutorial
FParsec、F#で使えるよー FParsec Documentation
さて、どっち使うか?
って、考えるまでもなく、FParsecですねw
NParsecのソースだと、魅力は半減(C#3.0だと少しは違うんでしょうけど、まぁ、無理やりですよね)
英語読めないので、機械と人の手を借りて読みましたが、
この先は誤った解釈などがあるかもしれませんが、悪しからず＾＾；
FParsecはコンビネータでできてる
コ、コンビネータのことは、Y Combinatorが凄すぎる！ - yuji1982の日記の件で調べたけど、何とか理解した程度。。
SとかKとかI、、ですよねー＞＜
と、濁しておしまい。
実際、活用してるかっつーと、全くしてなかったけど、でも、パーサコンビネータ見ると、コンビネータっておもしろいなー、と思う
環境構築から
必要なもの
- C#のビルド環境
- F#の1.9.4.15以降 download
- FParsec FParsec-downloadのhereから
準備手順
- FParsecCSとFParsecをビルド。
- F#のプロジェクトを追加して、参照パスに"-I ..\\..\\Build\\Debug -R FParsecCS.dll -R FParsec.dll"を追加。※-Iのパスは上の二つのdllがある場所
- F#のソースには、以下が必要
#light open FParsec.Primitives open FParsec.CharParser
これでOK。。と。
では、FParsecの勉強開始
パーサコンビネータは一つもしくは複数のパーサを引数として取り、「結合された」パーサを返す関数です。とな。
まさに、コンビネータってやつですね!
で、これが基本形のようです。
type GenParser<'a,'s> when 's :> IState = 's -> Reply<'a,'s>
「FParsecのすべての基本コンビネータと派生コンビネータは、この型のパーサが引数になる」
んー、わかるけど、､具体的に使わないとピンと来ないな^^;
結果はこんなやつらしいです。
type Reply<'a, 's> =
| ConsumedOk of 'a * 's * ParserError |
| ConsumedError of ParserError |
| EmptyOk of 'a * 's * ParserError |
| EmptyError of ParserError |
では、早速具体的な例から
type Parser<'a> = Parser<'a,unit>
let simple: Parser<_> =
parse {let! c = upper
do! skipChar '#'
return c}
ふむふむ、、これを呼んでみる。
let main()=
print_any(run simple "F#")
System.Console.ReadKey(false) |> ignore
結果
Success 'F'
なるほど
simpleってパーサに"F#"を渡すと、結果型のFになる。
この結果は、charパーサの結果型らしいです。
type ParserResult<'a> = Success of 'a
| Failure of string * ParserError
つまり、upperって言う大文字一文字のパーサと、skipCharって言う(たぶん検査だけして取得しない?)パーサーを
合成(結合?)して、simpleってパーサを作ったわけですね!
で、このupperのような定義済みパーサを組み合わせて行くわけですね。
ちょっとだけ、じっくり見てみる
let simple: Parser<_> =
parse {let! c = upper
do! skipChar '#'
return c}
このparse {}って書き方は何でしょう?よく見ると、letじゃなくてlet!ですし、do!ってのもありますね。
これはcomputation expressionsと言う、シンタックスシュガーのようです。
let parseXY = parseX >>= fun x ->
parseY >>= fun y ->
preturn (x, y)
こんな書き方を、
let parseXY = parse {let! x = parseX
let! y = parseY
return (x, y)}
こうできるらしいです。
computation expressionsの前に元のやつを、もうちょっとだけ見てみる
まず単純な文字パーサに代えて考えてみるlet parseXY = parse {let! x = anyChar
let! y = anyChar
return (x, y)}
文字を二つ(xとy)タプルで返すパーサになります。
結果は
val it : ParserResultlet parseXY = anyChar >>= fun x -> anyChar >>= fun y ->preturn (x, y)>>=とpreturn >>= val (>>=): GenParser<'a,'s> -> ('a -> GenParser<'b,'s>) -> GenParser<'b,'s> preturn let preturn x = fun state -> EmptyOk x state NoError >>=でパーサーを結合して、最後に結果を取るためのパーサpreturnを使ってるってことですね。 んー、わかるにはわかりますが、、ややこいです。 そこでcomputation expressionsに頼るわけですね。
computation expressionsはモナドライク!?
let parseXY = parse {let! x = anyChar
let! y = anyChar
return (x, y)}
わかり易くこう書けるのは、computation expressionsのおかげなんですが、これは何なのか?
いげ太センセーが紹介してくれてます。
http://igeta.cocolog-nifty.com/blog/2008/02/computation_exp.html
http://igeta.cocolog-nifty.com/blog/2008/04/maybe.html
http://igeta.cocolog-nifty.com/blog/2008/04/f_monad.html
僕はまだイマイチ理解できてませんが、モナドライクなわけですね。
とりあえずは、、楽にしてくれる便利なものってことで^^;
ファイルから入力して解析する方法
runParserOnFile simple () "test.txt" System.Encoding.Default
FParsecのパーサーをいろいろ見る
FParsec Documentation 文字系 いろいろあるんですねー char, anyChar, anyCharOrNL, upper, lower, letter, digit
newline, unicodeNewline
whitespace, spaces, unicodeWhitespace
satisfy
string anyString
regex
manyChars, manySatisfy, manyCharsTill, manyTillString
skipped
いくつか試してみる
run (char 'a') "abc";; val it : ParserResult選択 <|>= Success 'a' run (anyChar) "abc";; val it : ParserResult = Success 'a' run (string "ab") "abc";; val it : ParserResult = Success "ab" run (satisfy (fun c->c<>'a')) "bcd";; val it : ParserResult = Success 'b' run (anyString 4) "abcde";; val it : ParserResult = Success "abcd"
run (char 'a' <|> char 'b') "abc";; val it : ParserResultchoice= Success 'a' run (char 'a' <|> char 'b') "bc";; val it : ParserResult = Success 'b'
run (choice [(char 'a');(char 'b')]) "abc";; val it : ParserResultchoice [p1; p2; p3; ...] は p1 <|> p2 <|> p3 <|> と同じ。 でもchoiceの方が効率がいいらしい(?) .>>、>>. .の付いてる側を取得して、付いてない方は消費するだけ？でいいのかな= Success 'a'
run (char 'a' .>> char 'b') "abc";; val it : ParserResultとりあえず、おk 繰り返し many、skipMany= Success 'a' run (char 'a' >>. char 'b') "abc";; val it : ParserResult = Success 'b'
run (many digit) "123abc";; val it : ParserResultなるほど、数字を複数処理したわけですね、、と言うことは間に文字を入れると、、= Success ['1'; '2'; '3']
run (many digit) "12a3bc" >val it : ParserResultうんうん、おk ※前から思ってるけど、カナ打ちの僕が「おk」って、、違いますよねｗ= Success ['1'; '2']
run (skipMany (char 'a') >>. char 'b') "aaaabc";; val it : ParserResultmanyTill、skipManyTill= Success 'b'
run (manyTill (char 'a') (char 'b')) "aaaabca";; val it : ParserResultおそらくbは消費してますよね？= Success ['a'; 'a'; 'a'; 'a'] run (skipManyTill (char 'a') (char 'b')) "aaaabca";; val it : ParserResult = Success ()
run ( (skipManyTill (char 'a') (char 'b') ) >>.char 'c') "aaaabca";; val it : ParserResultうん、おk manyと文字の組み合わせ manyChars、manySatisfy= Success 'c'
run (manyChars (char 'a')) "aaba";; val it : ParserResultセパレータで区切られた解析 sepBy, endBy sepEndBy= Success "aa" run (manySatisfy (fun c->c<>'z')) "abczdef";; val it : ParserResult = Success "abc"
run (sepBy (anyString 2) (char ';')) "ab;cd;ef";; val it : ParserResultsepEndByは最後にセパレータがあっても良い。sepByだとエラー。 run (endBy (manyChars (satisfy (fun c->c<>';'))) (char ';')) "abcdef;";; val it : ParserResult= Success ["ab"; "cd"; "ef"] run (sepEndBy (anyString 2) (char ';')) "ab;cd;ef;";; val it : ParserResult = Success ["ab"; "cd"; "ef"]
| >> |
run ( (lookAhead (string "ab") ) >>. (manyChars anyChar) ) "abc";; val it : ParserResult追記 between= Success "abc"
> run (between (char '(') (char ')') (regex "[^)]+")) "(abc)";;
val it : ParserResult = Success "abc"
