yuji1982の日記 このページをアンテナに追加 RSSフィード

2008-06-27

[]シンプルで高速な構文解析ライブラリ「Parsec」を.NETで使う^^

Parsecって何?

Parsec 高速なコンビネータパーサ

Parsec は Haskellモナドパーサコンビネータライブラリで、文脈依存文法や無限先読み文法を解析できますが、 LL文法と同等の性能を出します。

コンビネータパーサはプログラムの他の部分と同じプログラミング言語を使って書かれます。文法の形式化 (Yacc) とそこで使われるプログラミング言語 (C) のギャップがありません。ユーザはたったひとつの言語を学ぶだけで済みます!


参考参考

最強のパーザー、Parser Combinator - 純粋関数型雑記帳

404 Error - FC2ブログ

ライブドアブログ(livedoor Blog)| 読みたいブログが見つかる

これは魅力的><

僕が今欲しいのはまさにこれじゃないか!!!

で、いろんな言語に移植されてるみたいです。

.NETでも使えるやつ

NParsec、C#で使えるよー NParsec+Tutorial

FParsec、F#で使えるよー FParsec Documentation

さて、どっち使うか?

って、考えるまでもなく、FParsecですねw

NParsecのソースだと、魅力は半減(C#3.0だと少しは違うんでしょうけど、まぁ、無理やりですよね)

英語読めないので、機械と人の手を借りて読みましたが、

この先は誤った解釈などがあるかもしれませんが、悪しからず^^;

Introductionから

  • FParsecはDaan LeijenさんのHaskell用パーサコンビネータライブラリをF#に移植したもの。
  • Unicode、4GBを超える大きなファイルに対応してます。
  • 設計、実装は最適化されてて、大きな要求も十分な性能をもたらす。
  • FParsecはBSDライセンス

FParsecはコンビネータでできてる

コ、コンビネータのことは、Y Combinatorが凄すぎる! - yuji1982の日記の件で調べたけど、何とか理解した程度。。

SとかKとかI、、ですよねー><

と、濁しておしまい。

実際、活用してるかっつーと、全くしてなかったけど、でも、パーサコンビネータ見ると、コンビネータっておもしろいなー、と思う

環境構築から

必要なもの

準備手順

  1. FParsecCSとFParsecをビルド。
  2. F#のプロジェクトを追加して、参照パスに"-I ..\\..\\Build\\Debug -R FParsecCS.dll -R FParsec.dll"を追加。※-Iのパスは上の二つのdllがある場所
  3. 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

実際は、こういうunion typeじゃなくて構造体らしい。(パフォーマンスのため)

でもアクティブパターンがあるから、このunion typeのように使えるらしい。

なるほどねー^^

では、早速具体的な例から

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のような定義済みパーサを組み合わせて行くわけですね。

エラーにすると?

run simple "C++"

にしてみる。

結果

= Failure
Error in Ln: 1 Col: 2
C++
 ^
Expecting: '#'

なるほどなるほど

ちょっとだけ、じっくり見てみる
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 : ParserResult<char*char> = Success ('a','b')

これを元の形で考えてみる。

let 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のおかげなんですが、これは何なのか?

いげ太センセーが紹介してくれてます。

ページが見つかりません:@nifty

ページが見つかりません:@nifty

ページが見つかりません:@nifty

僕はまだイマイチ理解できてませんが、モナドライクなわけですね。

とりあえずは、、楽にしてくれる便利なものってことで^^;

ファイルから入力して解析する方法

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<char> = Success 'a'

run (anyChar) "abc";;
val it : ParserResult<char> = Success 'a'

run (string "ab") "abc";;
val it : ParserResult<string> = Success "ab"

run (satisfy (fun c->c<>'a')) "bcd";;
val it : ParserResult<char> = Success 'b'

run (anyString 4) "abcde";;
val it : ParserResult<string> = Success "abcd"

選択

<|>

run (char 'a' <|> char 'b') "abc";;
val it : ParserResult<char> = Success 'a'

run (char 'a' <|> char 'b') "bc";;
val it : ParserResult<char> = Success 'b'

choice

run (choice [(char 'a');(char 'b')]) "abc";;
val it : ParserResult<char> = Success 'a'

choice [p1; p2; p3; ...] は p1 <|> p2 <|> p3 <|> と同じ。

でもchoiceの方が効率がいいらしい(?)

.>>、>>.

.の付いてる側を取得して、付いてない方は消費するだけ?でいいのかな

run (char 'a' .>> char 'b') "abc";;
val it : ParserResult<char> = Success 'a'

run (char 'a' >>. char 'b') "abc";;
val it : ParserResult<char> = Success 'b'

とりあえず、おk

繰り返し

many、skipMany

run (many digit) "123abc";;
val it : ParserResult<char list> = Success ['1'; '2'; '3']

なるほど、数字を複数処理したわけですね、、と言うことは間に文字を入れると、、

run (many digit) "12a3bc"
>val it : ParserResult<char list> = Success ['1'; '2']

うんうん、おk ※前から思ってるけど、カナ打ちの僕が「おk」って、、違いますよねw

run (skipMany (char 'a') >>. char 'b') "aaaabc";;
val it : ParserResult<char> = Success 'b'

manyTill、skipManyTill

run (manyTill (char 'a') (char 'b')) "aaaabca";;
val it : ParserResult<char list> = Success ['a'; 'a'; 'a'; 'a']

run (skipManyTill (char 'a') (char 'b')) "aaaabca";;
val it : ParserResult<unit> = Success ()

おそらくbは消費してますよね?

run ( (skipManyTill (char 'a') (char 'b') ) >>.char 'c') "aaaabca";;
val it : ParserResult<char> = Success 'c'

うん、おk

manyと文字の組み合わせ

manyChars、manySatisfy

run (manyChars (char 'a')) "aaba";;
val it : ParserResult<string> = Success "aa"

run (manySatisfy (fun c->c<>'z')) "abczdef";;
val it : ParserResult<string> = Success "abc"

セパレータで区切られた解析

sepBy, endBy sepEndBy

run (sepBy (anyString 2) (char ';')) "ab;cd;ef";;
val it : ParserResult<string list> = Success ["ab"; "cd"; "ef"]

run (sepEndBy (anyString 2) (char ';')) "ab;cd;ef;";;
val it : ParserResult<string list> = Success ["ab"; "cd"; "ef"]

sepEndByは最後にセパレータがあっても良い。sepByだとエラー。

run (endBy (manyChars (satisfy (fun c->c<>';'))) (char ';')) "abcdef;";;

val it : ParserResult<string list> = Success ["abcdef"]

パイプライン

|>>

run (digit |>> fun c -> Char.code c- Char.code '0') "1";;

val it : ParserResult<int> = Success 1

消費しないパーサ

lookAhead、followedBy、notFollowedBy

run ( (lookAhead (string "ab") ) >>. (manyChars anyChar) ) "abc";;
val it : ParserResult<string> = Success "abc"

追記

between

> run (between (char '(') (char ')') (regex "[^)]+")) "(abc)";;
val it : ParserResult<string> = Success "abc"

脳が痛がってるので、今回はここまで>< (たぶん追記します)

まだ理解してないものメモ

chainl1


最後に注意!!

FParsec Documentationで、以下の"ような"ことが書かれてるので注意です!

このページのFParsecは未リリース版です。

かなり総合的なテストは行われてますが、まだバグがあると思われるので、

もし製品環境で使う場合は、徹底的にテストする必要がありますよ。

いげ太いげ太 2008/06/28 00:44 ああぁぅわわわゎ。僕の記事が引用されてる><

えと、僕もまだまだあやふやな理解でしかないのですが、computation expressions がなにしてるかは、以下の記事を見ていただくのがよいかも(?)です。ちなみに、sequence comprehensions も computation expressions の一種ですね。

http://igeta.cocolog-nifty.com/blog/2008/03/seq_brute_force.html

つまりなにかというと、computation expressions ってのは、ごく簡単には「関数ネストめんどくせ。フラットに書きたいし、その方が見た目わかりやすいし」という欲求を達成するための言語機能(シンタックスシュガー)です。で、ネストされた関数群ってのは、計算がドミノ倒しに行われるわけで、すなわち、computation expressions(≒モナド)は計算をつなぐもの、と表現されたりするわけです。

そしてさらに、computation expressions は、M<’a> 型の値をスマートに記述するための機能でもあります。Maybe<’a> 型で説明させてもらうと、Maybe<’a> を使うときってのは結局 ’a に関心事があるわけです。’a を Maybe で包むのは、計算の都合上そうしているというに過ぎません。つまり「途中で失敗するかもしれない計算」のためにそうしているのであり、実際に関心があるのは ’a の値ですよね。

ここに ! ありなしの秘密あります。たとえば let と let!。let はふつーに束縛するのですが、let! は Maybe<’a> の値から Maybe の皮をはいだ ’a の値を束縛するのです。そして、return と return! では、’a の値を Maybe で包んで返す場合には return を、すでに Maybe で包まれてる値をそのまま返す場合に return! を使う、といった具合。

let と return で、一瞬、! の役割が逆転してるような印象を受けるかもしれませんが、そうではありません。! のあるなしは、はぐか、包むかの違いで使い分けるものではありません。単に、その式で扱う値が Maybe<’a> である場合に ! 付きのキーワードを使えばよいのです。

以上、あんまりよくわかってないいげ太によるあんまりよくわからない補足説明でした。たぶんいろいろ間違えてると思いますが、大雑把な感じはつかめるかな、なんて(^^;;

# ていうか FParsec すげぇ!

yuji1982yuji1982 2008/06/30 15:07 いげ太さん

コメントありがとうございます><
まだピンと来てないですが、目的はわかるような気がしてます(多分、気がしてるだけですがw)

後でブログと合わせてゆっくり読ませて頂きます^^

CMasCMas 2009/02/13 10:22 古い記事に申し訳ありません。
F#もFParsecも初心者が、FParsecでForthもどきを作ろうとしているのですが、if..else..thenのパースで困ってます。
比較演算子と「if」が出現したら、「..」にあたる式をパースしたいのですが、else、thenをForthのワード(関数実行)と解釈してしまうのです。
予約語である、else、thenが出現したら、sepEndByを抜けたいのですが、どうしたらいいかわからなくて、もんもんとしています。
貧弱な知識で書いたのが、以下のリストですが、無事thenでsepEndByを抜けるものの、最期に""が付いてしまいます。
なんか、稚拙な誤りを犯しているようで、不安でなりません。

type Parser<'a> = Parser<'a,unit>

let eof2char: Parser<_> =
parse { do! eof
return ' '};;
let delimiter: Parser<_> =
parse { let! d = (whitespace <|> (anyOf "\n\t") <|> eof2char)
return d;};;
let parseThen: Parser<_> =
parse { let! topChar = pstring "then"
do! (followedBy (delimiter) "err_msg")
let! nokori = manyChars letter
return topChar + nokori};;
let termWithThen: Parser<_> =
parse { let! _ = lookAhead (parseThen)
return ""};;

let expr: Parser<_> =
parse { let! th = termWithThen
return th}
<|> parse { let! lit = many1Chars digit
return lit}
<|> parse { let! wd = many1Chars letter
return wd};;

run (sepEndBy expr (many1Chars whitespace)) "123 ABC then 345";;
実行結果
> run (sepEndBy expr (many1Chars whitespace)) "123 ABC then 345";;
val it : ParserResult<string list> = Success ["123"; "ABC"; ""]

> run (sepEndBy expr (many1Chars whitespace)) "123 ABC thenHoge 345";;
val it : ParserResult<string list>
= Success ["123"; "ABC"; "thenHoge"; "345"]
thenHogeは、thenではないので、ちゃんとパースされる。

以上、よろしくお願いします。

yuji1982yuji1982 2009/02/17 00:06 CMasさん

コメントありがとうございます。
久しぶりに挑戦してみようと思ったら、最近F#もFParsecもずっと触ってなくて
全然書けなくなってしまいましたorz

なので、見当違いなこと言ってたらごめんなさい><
>最期に""が
に関しては、termWithThenでthenが見つかったら、return ""としている部分だと思います。

FParsecって最新のFSharpに対応してたんですね!知りませんでした^^;

CMasCMas 2009/02/20 08:25 お騒がせしましたが、「else」、「then」を、セパレータ側にセットすることで解決しました。
「空白、\t、\n、eof」が続く「else」「then」を「lookAhead」してからパースするパーサを、先の例の「whitespace」をパースするセパレータの前に、<|>で結んでセパレータのパーサとします。
 そうすると、「sepEndBy」が、「else」または「then」パーサでセパレータのパースを成功したとき、「空白、\t、\n、eof」が続いているはずですが、引き続き実行される本来のパーサは、文字を消費することなく失敗しますので、「sepEndBy」を抜けてきます。
 この「文字を消費することなく失敗」したとき、「sepEndBy」を抜けてくる、という事を理解していなかった、というのが恥ずかしながら、問題点だったわけです。
 ちなみに、この「if」構文のあと、昨日に、for構文、while構文をインプリメントしまして、私のForthが一応完成しました。
 初心者のごりごりプログラムですが、http://www.cmas60.com に、経過とソースを掲載してあります。
 「還暦プログラマ」の、(ひや)汗と、涙の苦闘の結果をご覧ください。
 「これはひでー」とか、「こうしたほうがいいよ」という意見は、大歓迎です。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/yuji1982/20080627/1214558307