a wandering wolf

Does a wandering wolf dreams of a wondering, sometimes programming sheep?

このエントリーをはてなブックマークに追加

FParsec 日本語チュートリアル

本記事は、F# 製のパーザライブラリ FParsec のチュートリアルを和訳したものです。

FParsec Documentation FParsec tutorial (English)

この和訳ドキュメントはチュートリアル本文のみを日本語に翻訳したものであり、その他のページは未翻訳です。 そのため、本文中に張られたリンクには原文に遷移するものがあります。

また、原文の意味を損なわない程度に訳文を砕いている箇所があります。 誤解がないように気をつけましたが、もしかしたら元の意味とずれてしまっているところがあるかもしれないことを予めご了承ください。

本記事は原文に則り Creative Commons Attribution-NonCommercial 3.0 Unported (CC BY-NC 3.0) の下でライセンスしています。 原文の著作権はライブラリ作者である Stephan Tolksdorf 氏に帰属します。 日本語の内容についておかしな箇所がありましたら、私までご連絡いただけると助かります。 その他、本記事についてはコメントもしくはTwitter(@gab_km)宛にお気軽にどうぞ。

4 チュートリアル

このチュートリアルでは FParsec の基本的な概念を紹介します。私たちの目的は FParsec のライブラリを用いてどうやってパーザ・アプリケーションを構築できるかへの直感を身につけてもらう事です。私たちは基本となるアイディアのみカバーし、また大雑把に FParsec の API を見て回るのみですが、 ユーザーズガイドAPI リファレンス 、そして Sample フォルダ内にあるサンプルパーザの助けによって、より深く FParsec を探究できるだけの十分な領域をカバーできればと思います。

4.1 事前準備

FParsec は2つの DLL: FParsec.dll と FParsecCS.dll としてビルドされています。これらの DLL をビルドする一番簡単な方法は Build/VS9 (Visual Studio 2008用) と Build/VS10 (Visual Studio 2010用) のフォルダにある Visual Studio ソリューションファイルを使う事です。FParsec を使うどんなプロジェクトも両方の DLL を参照しなければなりません。詳しくは ダウンロードとインストール をご覧ください。

FParsec にある全ての型とモジュールは FParsec 名前空間内で宣言されています。この名前空間には幾つかの基本クラス (CharStreamReply のような) や4つの F# モジュール、すなわち下記のモジュールを含んでいます。

  • Primitives 、基本的な型の定義とパーザ・コンビネータを含みます
  • CharParsers 、文字、文字列および数字用のパーザと入力ストリームにパーザを適用するための関数を含みます
  • Error 、パーザのエラーメッセージを生成、処理および整形するための型とヘルパー関数を含みます
  • StaticMapping 、最適化された関数への静的なキー・値のマッピングをコンパイルするための関数を含みます

このチュートリアルの全てのコードスニペットは FParsec 名前空間をオープンしているものと仮定します:

open FParsec

FParsec 名前空間をオープンするとまた、自動的に PrimitivesCharParsers および Error モジュールもオープンします。

注記

このチュートリアルの全てのコードは Samples/Tutorial プロジェクトに含まれています。このチュートリアルを読んでいる間、このプロジェクトを開いておけば、とても役に立つでしょう。例えば、識別子の上にマウスを重ねることで推論された型を Intellisense のポップアップから得ることができます。そしてもしライブラリの関数がどう実装されているのか気になったら、コンテキストメニューの「 定義へ移動 」をクリックすればそのソースコードを見ることができます。

4.2. 小数ひとつのパース

FParsec で入力をパースするには2つのステップを踏みます:

  1. パーザを構築する
  2. 入力にパーザを適用する

文字列中の小数ひとつをパースするという単純な例で始めてみましょう。

この場合の最初のステップ、パーザの構築は取るに足りないもので、なぜなら CharParsers モジュールがすでに組み込みの浮動小数点パーザを用意してくれているからです:

val pfloat: Parser<float,'u>

ジェネリック型 Parser<'Result,'UserState> は FParsec にある全てのパーサの型です。リファレンス内のハイパーリンクを追いかけてみれば、 Parser が関数型の型略称であることが分かるでしょう。しかしながら、この点において私たちは Parser の型の詳細に踏み込む必要はありません。最初の型引数はパーザの結果の型を表すということに気を付けておけば十分です。ですので、 pfloat の場合はパーザが成功したら float 型の浮動小数点数を返すということを型が私たちに教えてくれます。このチュートリアルでは”user state”は使わないので、しばらく2番目の型引数については無視しておいてください。

文字列に pfloat パーザを適用するために、 CharParsers モジュールにある run 関数を使います:

val run: Parser<'Result,unit> -> string -> ParserResult<'Result,unit>

run は入力に対して走らせるパーザとして CharParsers モジュールが提供しているいくつかの関数うちでのもっとも単純なものです。他の関数は、例えばファイルの内容や System.IO.Stream に直接パーザを実行できるようにします。

run は最初の引数として渡されたパーザと2番目の引数として渡された文字列を適用して ParserResult の値の形でパーザの戻り値を返します。 ParserResult 型は2つのケース: SuccessFailure を持つ判別共用体です。パーザが成功した場合、 ParserResult の値は結果の値を持ち、そうでない場合はエラーメッセージを持ちます。

テストを単純にするために、結果の値やエラーメッセージを印字する小さなヘルパー関数を書いてみましょう:

let test p str =
    match run p str with
    | Success(result, _, _)   -> printfn "Success: %A" result
    | Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg

このヘルパー関数を適当な箇所に配置することで、

test pfloat "1.25"

を実行して

Success: 1.25

という出力をすることで pfloat をテストできます。

不正な指数を持つ数値リテラルを用いた pfloat のテスト

test pfloat "1.25E 3"

Failure: Error in Ln: 1 Col: 6
1.25E 3
     ^
Expecting: decimal digit

というエラーメッセージを生成します。

4.3 角カッコに挟まれた小数のパース

FParsec でパーザを実装することは大体は低レベルなパーザを組み合わせて高レベルなパーザを作ることを意味します。ライブラリが提供するプリミティブなパーサから始めて、最終的に完全な入力のためのパーザを1つ得られるまでより高レベルなパーザへとこれらを次々と結合させていきます。

以下のセクションでは、それぞれを構築する様々なサンプルのパーザを議論することでこのアプローチを説明します。このセクションでは角カッコに挟まれた浮動小数点数用のとても単純なパーザから始めていきます:

let str s = pstring s
let floatBetweenBrackets = str "[" >>. pfloat .>> str "]"

注記

このコードやその他のコードスニペットをコンパイルしようとして F# の「値制限」についてのコンパイルエラーが発生したら、 セクション4.10 をご覧ください。

strfloatBetweenBrackets の定義にはまだ紹介していない3つのライブラリ関数、 pstring>>. 、そして .>> を含んでいます。

関数

val pstring: string -> Parser<string,'u>

は文字列を引数に取り、その文字列のためのパーザを返します。このパーザが入力ストリームに適用されると、入力ストリームにある後続の文字が与えられた文字列と一致するかどうかチェックします。文字が文字列全体と一致すると、パーザはその文字を消費、つまりその文字を読み飛ばします。そうでなければ、入力を消費することなく失敗します。パーザが成功すると、パーザの結果として与えられた文字列を返しもしますが、文字列が定数である限りはこの結果を使うことはほとんどないでしょう。

pstring 関数は組み込みの F# 関数である string を隠してしまうので、 string と名付けられていません。一般に、組み込みの F# 関数名と衝突してしまう FParsec のパーザ名は p という一文字を先頭に付けています。 pfloat はこの命名規約のもう一つの例です。

少しばかりのキータイプを節約するために、 pstringstr と省略しています。なので、例えば str "["'[' という文字をスキップするパーザです。

二項演算子 >>..>> は以下のような型を持ちます:

val (>>.): Parser<'a,'u> -> Parser<'b,'u> -> Parser<'b,'u>
val (.>>): Parser<'a,'u> -> Parser<'b,'u> -> Parser<'a,'u>

これらのシグネチャから分かる通り、どちらの演算子も2引数のパーザから新しいパーザを構築するパーザコンビネータです。 p1 >>. p2 というパーザは p1p2 を順番にパースし p2 の結果を返します。 p1 .>> p2 というパーザもまた p1p2 を順番にパースしますが、 p2 ではなく p1 の結果を返します。それぞれのケースでドットは結果を返す側のパーザを指し示しています。 p1 >>. p2 .>> p3 と両方の演算子を組み合わせると、 p1p2p3 と順番にパースし、 p2 の結果を返すパーザが得られます。

注記

いくらか不明確な「 p1p2 を順番にパースし」という言い回しで私たちが本当に伝えたかったのは:

パーザ p1 は入力に適用され、もし p1 が成功したら p2 が残りの入力に適用されます。2つのパーザのどちらかが失敗した場合、パーザたちは即座にエラーメッセージを伝播します

ということです。

FParsec のドキュメントで、私たちはよく「 p をパースする」または「 p の発生をパースする」というような表現を、技術的にはより正確な「パーザ p を残りの入力に適用し、もし p が成功したら…」の代わりによく使っておりますが、正確な意味は文脈から明らかであればいいなと望んでいます。

以下のテストは floatBetweenBrackets が期待したとおりに正しい入力をパースし、不正な入力に出くわした時に有益なエラーメッセージを生成するのを示してくれます:

> test floatBetweenBrackets "[1.0]";;
Success: 1.0

> test floatBetweenBrackets "[]";;
Failure: Error in Ln: 1 Col: 2
[]
 ^
Expecting: floating-point number

> test floatBetweenBrackets "[1.0";;
Failure: Error in Ln: 1 Col: 5
[1.0
    ^
Note: The error occured at the end of the input stream.
Expecting: ']'

4.4 パーザの抽象化

FParsec の大きな力の1つは自分のパーザ抽象を定義するのが簡単なことです。

前のセクションから floatBetweenBrackets を例として借りてきましょう。もし文字列の間にある他の要素もパースしたいと思ったら、この目的にあったあなた特製のコンビネータを定義できるでしょう:

let betweenStrings s1 s2 p = str s1 >>. p .>> str s2

そしてこのコンビネータの助けを借りて、 floatInBrackets や他のパーザを定義できます:

let floatBetweenBrackets = pfloat |> betweenStrings "[" "]"
let floatBetweenDoubleBrackets = pfloat |> betweenStrings "[[" "]]"

注記

あなたが F# が初めてという場合:

pfloat |> betweenString "[" "]" は単に betweenStrings "[" "]" pfloat を書く別の方法です。

2つの別のものの間にパーザを適用する必要が頻繁にあると気がついたら、より踏み込んで以下のように betweenStrings を分解してみましょう:

let between pBegin pEnd p  = pBegin >>. p .>> pEnd
let betweenStrings s1 s2 p = p |> between (str s1) (str s2)

これは既に FParsec に組み込みのコンビネータなので、実際は between を定義する必要はありません。

もちろん、これらはすべて大したことのない例です。しかし FParsec が単なる F# のライブラリであって外部のパーザ生成ツールでないので、定義可能な抽象に制限がないのです。必要とする入力を何でも取り、その入力に対して適宜複雑な計算を行い、そして特別な目的のパーザやパーザコンビネータを返すような関数を書くことができます。

例えば、正規表現のパターンを入力に受け取り、そのパターンに従う入力をパースする Parser を返すような関数を書くことができるでしょう。この関数は、別のパーザを使ってパターンを AST にパースし、この AST をコンパイルして特殊用途のパーザ関数を作ることができます。代わりに、そのパターンから .NET の正規表現を構築し、入力ストリームに regex をダイレクトに適用する(これは組み込みの regex パーザが実際にやっていることです)ために FParsec の CharStream APIを使うパーザ関数を返すことができます。

もうひとつの例は、拡張可能なパーザアプリケーションです。辞書や他のデータ構造にパーザ関数を保持し適切な拡張プロトコルを定義することで、新しいパーザを動的に登録したり既存のパーザを変更したりするプラグインが使えるようになります。

可能性は本当に限りがありません。しかし、これらの可能性を使いつくす前に、まずは FParsec の基礎に馴染んでおく必要があります。

4.5. 小数リストのパース

浮動小数点数1つをどのようにパースするか、もう3セクションに亘って議論してきたので、そろそろもっとやりがいのあるもの、浮動小数点数リストのパースに取り組んでみる頃です。

まず括弧の中にある浮動小数点の列、つまり ("[" float "]")* のような EBNF 形式のテキストをパースする必要があるとしましょう。この形式における正しい入力文字列は例えば """[1.0]""[2][3][4]" です。

カッコの間に挟まれた浮動小数点数用のパーザが既にあるので、シーケンスをパースするためにこのパーザを繰り返し適用する方法だけが必要になります。これが many コンビネータがある由縁です:

val many: Parser<'a,'u> -> Parser<'a list,'u>

パーザ many p はパーザ p が失敗するまで繰り返し p に適用する、つまり p が現れる限り「貪欲に」パースしていきます。 p の結果は現れた順にリストとして返されます。

いくつかの簡単なテストで many floatInBrackets が期待したとおりに動いてくれることを確かめられます:

> test (many floatBetweenBrackets) "";;
Success: []
> test (many floatBetweenBrackets) "[1.0]";;
Success: [1.0]
> test (many floatBetweenBrackets) "[2][3][4]";;
Success: [2.0; 3.0; 4.0]

もし floatBetweenBrackets入力を消費した後に 失敗したら、連結されたパーザも同様に失敗します:

> test (many floatBetweenBrackets) "[1][2.0E]";;
Failure: Error in Ln: 1 Col: 9
[1][2.0E]
        ^
Expecting: decimal digit

many は空のシーケンスに対しても成功する事に気をつけましょう。少なくとも一つの要素が必要であれば、代わりに many1 を使うことができます:

> test (many1 floatBetweenBrackets) "(1)";;
Failure: Error in Ln: 1 Col: 1
(1)
^
Expecting: '['

Tip

もし最後に表示されるエラーメッセージを、低レベルな str "[" パーザについてのものから高レベルな floatBetweenBrackets パーザに関する表現の方が好ましいなら、以下に示す例のように <?> 演算子を使うことができるでしょう。

> test (many1 (floatBetweenBrackets <?> "float between brackets")) "(1)";;
Failure: Error in Ln: 1 Col: 1
(1)
^
Expecting: float between brackets

エラーメッセージのカスタマイズについてより学ぶためにユーザーズガイドの セクション5.8 をご一読ください。

もし一続きの箇所をスキップしたいだけで、パーザ結果のリストが必要ないのであれば、 manymany1 の代わりに最適化されたコンビネータ skipManyskipMany1 を使うことができます。

列をパースするためのコンビネータでその他によく使われるのは sepBy です:

val sepBy: Parser<'a,'u> -> Parser<'b,'u> -> Parser<'a list, 'u>

sepBy は引数として「要素」のパーザと「区切り」のパーザをとり、要素を区切りで分割したリスト用のパーザを返します。EBNF記法では sepBy p pSep(p (pSep p)*)? として書けるでしょう。 many と似たように、 sepBy変種がいくつも あります。

sepBy のおかげで、浮動小数点数がコンマで区切られた、より読みやすいリスト形式をパースできます:

floatList: "[" (float ("," float)*)? "]"

この形式における正しい入力は例えば "[]""[1.0]""[2,3,4]" です。

この形式の単純な実装は

let floatList = str "[" >>. sepBy pfloat (str ",") .>> str "]"

です。

正しいテスト文字列で floatList をテストすると期待する結果が得られます:

> test floatList "[]";;
Success: []
> test floatList "[1.0]";;
Success: [1.0]
> test floatList "[4,5,6]";;
Success: [4.0; 5.0; 6.0]

不正な入力でテストすると floatList は役に立つエラーメッセージを出してくれます:

> test floatList "[1.0,]";;
Failure: Error in Ln: 1 Col: 6
[1.0,]
     ^
Expecting: floating-point number

> test floatList "[1.0,2.0";;
Failure: Error in Ln: 1 Col: 9
[1.0,2.0
        ^
Note: The error occurred at the end of the input stream.
Expecting: ',' or ']'

4.6 空白の扱い

FParsec は空白(スペース、タブ、改行、など)を別の入力として扱うので、私たちの floatList パーザはまだ空白に対処できません:

> test floatBetweenBrackets "[1.0, 2,0]";;
Failure: Error in Ln: 1 Col: 5
[1.0, 2.0]
    ^
Expecting: ']'

もしパーザに空白を無視させたいのなら、パーザ定義の中でこれを明確にする必要があります。

まず、何を空白として受け入れるか定義する必要があります。簡単のために、組み込みの spaces パーザだけを使いますが、これは(空も含めた) ' ''\t''\r' および '\n' という文字の列をまとめてスキップします。

let ws = spaces

次に、空白を無視したいすべての箇所で ws パーザを挿入しないといけません。一般に、後戻り(以下で説明します)の必要を減らすために、ひとつ要素をパースした後で空白をスキップする、つまり先頭からの空白ではなく後ろに連なる空白をスキップするのがベストです。よって、括弧と数字の後にあるどんな空白もスキップしてしまうよう、2箇所に ws を入れます:

let str_ws s = pstring s .>> ws
let float_ws = pfloat .>> ws
let numberList = str_ws "[" >>. sepBy float_ws (str_ws ",") .>> str_ws "]"

簡単なテストで numberList が空白を無視しているのが分かります:

> test numberList @"[ 1 ,
                          2 ] ";;
Success: [1.0; 2.0]

もし2行目にあるエラーを教えたい場合、FParsec が自動的に行数を記録してくれているのを見ることができます:

> test numberList @"[ 1,
                         2; 3]";;

Failure: Error in Ln: 2 Col: 27
                         2; 3]
                           ^
Expecting: ',' or ']'

私たちの numberList パーザはまだ先頭にある空白をスキップしませんが、それは他のパーザが後ろに続くすべての空白をスキップしてくれていることと併せれば必要がないからです。もし浮動小数点数リストだけの入力ストリーム全体をパースしたいのであれば、以下のパーザが使えます:

let numberListFile = ws >>. numberList .>> eof

ファイル終端パーザ eof はストリームの終端に到達していない場合にエラーを生成します。これは入力がすっかり消費されきったか確かめるのに便利です。 eof パーザ無しだと以下のテストはエラーを生成しないでしょう:

> test numberListFile " [1, 2, 3] [4]";;
Failure: Error in Ln: 1 Col: 12
[1, 2, 3] [4]
          ^
Expecting: end of input

4.7 文字列データのパース

FParsec には文字や文字列、数値、そして空白のための様々な組み込みパーザが含まれています。この章では文字と文字列のパーザを少し紹介します。利用可能なすべてのパーザの概要は、リファレンスにある パーザ概要 を参照してください。

pstring パーザ(str と省略)をいくつか適用したものは既に見てきており、それらは入力にある文字列定数を単純にスキップするものでした。 pstring パーザが成功したら、スキップした文字列をパーザ結果として返してもいました。以下の例はこれを実演してみたものです:

> test (many (str "a" <|> str "b")) "abba";;
Success: ["a"; "b"; "b"; "a"]

この例では、どちらかが選ばれる2つのパーザを結びつけるために <|> コンビネータも使いました。このコンビネータの詳細について以下で議論してみましょう。

注記

私たちは pstringpstring "a" をどちらも「パーザ」と言っています。厳密に言うと、 pstring は文字列を引数にとり Parser を返す関数ですが、(パラメータをとる)パーザとして単に述べた方が便利です。

pstring パーザの結果が必要ない場合、 skipString パーザを使うことが出来ますが、これは引数の文字列の代わりに unit の値 () を返します。この場合、返す文字列が定数なので、 pstringskipString のどちらを使おうとパフォーマンスに何の違いも出てきません。しかし、他の組み込みパーザやコンビネータのほとんどについて、一般により速いので、パーザ結果の値を必要としない時は「skip」が名前の最初についているものを使うようにした方が良いでしょう。 パーザ概要 を見れば、たくさんの組み込みパーザやコンビネータに「skip」付きのものが見られるでしょう。

もし大文字と小文字を区別しない文字列定数をパースしたい場合、 pstringCIskipStringCI を使うことが出来ます。例えば:

> test (skipStringCI "<float>" >>. pfloat) "<FLOAT>1.0";;
Success: 1.0

格納されている文字がある基準を満たさないといけないような文字列変数をパースする必要がある、ということはよくあります。例えば、プログラミング言語中の識別子はしばしば文字かアンダースコアで始まり、文字や数字、アンダースコアが続く必要があります。こんな識別子をパースするために、以下のようなパーザを使うことが出来ます:

let identifier =
    let isIdentifierFirstChar c = isLetter c || c = '_'
    let isIdentifierChar c = isLetter c || isDigit c || c = '_'

    many1Satisfy2L isIdentifierFirstChar isIdentifierChar "identifier"
    .>> ws // 後続の空白をスキップします

ここで many1Satisfy2L 文字列パーザを使いましたが、これは文字述語(つまり、入力に文字をとり、真偽値を返すような関数)を基に文字列をパースするためのいくつかあるプリミティブのひとつです。最初の文字が最初の文字述語を満たし、残りの文字が2番目の述語を満たす(なので名前に「Satisfy2」が入っています)ような1つ以上の文字(なので名前に「many1」が入っています)からなる任意のシーケンスをパースします。3番目の引数から与えられる文字列のラベル(なので名前に「L」がh(ry)は期待する入力を表すためにエラーメッセージ中で使われます。

以下のテストでこのパーザがどのように働くか分かります:

> test identifier "_";;
Success: "_"
> test identifier "_test1=";;
Success: "_test1"
> test identifier "1";;
Failure: Error in Ln: 1 Col: 1
1
^
Expecting: identifier

Tip

もしユニコード XID 構文に基づく識別子をパースしたいのであれば、組み込みの identifier パーザを使うと良いでしょう。

多くの文字列形式はとても複雑なのでいくつかの文字や文字列の基本パーザを組み合わせる必要があります。例えば、以下の文字列リテラル形式を考えてみましょう:

stringLiteral: '"' (normalChar|escapedChar)* '"'
normalChar:    any char except '\' and '"'
escapedChar:   '\\' ('\\'|'"'|'n'|'r'|'t')

この文法を FParsec に単純に変換するとこんな感じになります:

let stringLiteral =
    let normalChar = satisfy (fun c -> c <> '\\' && c <> '"')
    let unescape c = match c with
                     | 'n' -> '\n'
                     | 'r' -> '\r'
                     | 't' -> '\t'
                     | c   -> c
    let escapedChar = pstring "\\" >>. (anyOf "\\nrt\"" |>> unescape)
    between (pstring "\"") (pstring "\"")
            (manyChars (normalChar <|> escapedChar))

この例では、まだ紹介していないいくつかのライブラリ関数を使っています:

  • satisfy は与えられた述語関数を満たす任意の文字をパースします。
  • anyOf は引数の文字列に含まれる任意の文字をパースします。
  • パイプラインコンビネータ |>> は右側の関数 (unescape) を左側のパーザ (anyOf "\\nrt\"") の結果に適用します。
  • 選択コンビネータ <|> は左側のパーザが失敗した場合に右側のパーザを適用するので、 normalChar <|> escapedChar は普通の文字とエスケープ文字の両方をパースできます。(このオペレータについて2つ後のセクションでさらに詳しく議論します)
  • manyChars は与えられた文字パーザで文字シーケンスをパースし、結果を文字列として返します。

いくつかのテスト入力で stringLiteral パーザをテストしてみましょう:

> test stringLiteral "\"abc\"";;
Success: "abc"
> test stringLiteral "\"abc\\\"def\\\\ghi";;
Success: "abc"def\ghi"
> test stringLiteral "\"abc\\def"";;
Failure: Error in Ln: 1 Col: 6
"abc\def"
     ^
Expecting: any char in '\nrt"'

文字ごとに文字列リテラルをパースする代わりに、「スニペットごとに」パースすることが出来ます:

let stringLiteral2 =
    let normalCharSnippet = many1Satisfy (fun c -> c <> '\\' && c <> '"')
    let escapedChar = pstring "\\" >>. (anyOf "\\nrt\"" |>> function
                                                           | 'n' -> "\n"
                                                           | 'r' -> "\r"
                                                           | 't' -> "\t"
                                                           | c   -> string c)
    between (pstring "\"") (pstring "\"")
            (manyStrings (normalCharSnippet <|> escapedChar))

ここで manyStrings コンビネータを使いましたが、これは与えられた文字列パーザで文字列シーケンスをパースし、結合した形式で文字列を返します。

注記

少なくとも1文字を消費するために normalCharSnippet が必要、つまり manySatisfy の代わりに many1Satisfy を使う必要があります。そうでなければ入力を消費しなくても、 escapedChar が決して呼ばれなくても、そして manyStrings が例外を投げて無限ループを止めてしまっても、 normalCharSnippet は成功するでしょう。

many1Satisfy のような最適化されたパーザを使って文字列を塊でパースするのは、 manyCharssatisfy を使って文字単位でパースするよりふつうは多少速いです。この場合では、2つある普通の文字スニペットが少なくとも1つのエスケープされた文字で分けられなくてはならないことに気がつけば、私たちのパーザをさらに速くすることが出来ます:

let stringLiteral3 =
    let normalCharSnippet = manySatisfy (fun c -> c <> '\\' && c <> '"')
    let escapedChar = (* stringLiteral2 のように *)
    between (pstring "\"") (pstring "\"")
            (stringsSepBy normalCharSnippet escapedChar)

stringsSepBy コンビネータは、(2番目の引数パーザでパースされた)他の文字列で区切られた文字列シーケンスを(最初の引数パーザで)パースします。本コンビネータは区切り文字を含むすべてのパースされた文字列を、ひとつの連結した文字列として返します。

stringLiteral3normalCharSnippet の定義の中で many1Satisfy の代わりに manySatisfy を使っていることに気をつけましょう、そのために普通の文字で区切られていないエスケープ文字をパースできるのです。 escapedChar が入力を消費せずにパースを成功できないので、これは無限ループを引き起こすことが出来ません。

4.8 パーザの連続的な適用

連続して複数のパーザを適用し、それらの結果のひとつだけが必要だという時はいつでも、ぴったりな演算子 >>..>> がやってくれます。しかし、それらのパーザ結果が複数必要になったら、これらのコンビネータでは十分でありません。そんな場合、 pipe2 から pipe5 コンビネータを使うことが出来ますが、これらは連続して複数のパーザを適用し、集約した結果を計算する関数に個々の結果をすべて渡します。

例えば、 pipe2 コンビネータ

val pipe2: Parser<'a,'u> -> Parser<'b,'u> -> ('a -> 'b -> 'c) -> Parser<'c, 'u>

で、2つのパーザ p1p2 を連続して適用して、 p1p2 の結果である x1x2 で、 f x1 x2 と関数適用した結果を返すパーザ pipe2 p1 p2 f を構築できます。

以下の例で、2数のかけ算をパースするのに pipe2 を使います:

let product = pipe2 float_ws (str_ws "*" >>. float_ws)
                    (fun x y -> x * y)
> test product "3 * 5";;
Success: 15.0

pipe2~5 コンビネータは特に AST オブジェクトの構築に便利です。以下の例で、 pipe3 を使って StringConstant オブジェクトに定義した文字列定数をパースします:

type StringConstant = StringConstant of string * string

let stringConstant = pipe3 identifier (str_ws "=") stringLiteral
                           (fun id _ str -> StringConstant(id, str))
> test stringConstant "myString = \"stringValue\"";;
Success: StringConstant ("myString","stringValue")

パース結果をタプルとして返したいだけなら、予め定義済みの tuple2~5 パーザを利用できます。例えば、 tuple2 p1 p2pipe2 p1 p2 (fun x1 x2 -> (x1, x2)) と同じです。

tuple2 パーザは .>>. という名の演算子の下でも使うことができて、 tuple2 p1 p2 の代わりに p1 .>>. p2 と書くことができます。以下の例でこの演算子を使いコンマで区切られた数字のペアをパースします:

> test (float_ws .>>. (str_ws "," >>. float_ws)) "123, 456";;
Success: (123.0, 456.0)

以降、 >>に1つか2つのドットがついた表記 を直感的に分かってもらえるといいなと思います。

もし引数が5より多い pipetuple パーザが必要なら、今あるものを使って簡単に構築可能です。例えば、 pipe7 パーザをどうやって定義したらいいか思いつきますか?この脚注でやり方が分かります: [1]

4.9 代替パース

「文字列データのパース」のセクションで、既に選択コンビネータ <|> を手短に紹介しました:

val (<|>): Parser<'a,'u> -> Parser<'a,'u> -> Parser<'a,'u>

このコンビネータは与えられた入力の状況で複数の取り得る入力形式をサポートできるようにします。例えば、上のセクションでエスケープしていない文字用のパーザとエスケープされた文字用のパーザを連結して両方をサポートするパーザ、 normalChar <|> escapedChar を作るのに <|> を使いました。

<|> がどのように機能するか分かるもう一つの例は真偽値変数用の以下に挙げるパーザです:

let boolean =     (stringReturn "true"  true)
              <|> (stringReturn "false" false)

ここで stringReturn パーザも使いましたが、これは最初に渡された引数の文字列定数をスキップして、パースに成功したら2番目に渡された引数の値を返します。

いくつか入力を渡して boolean パーザをテストします:

> test boolean "false";;
Success: false
> test boolean "true";;
Success: true
> test boolean "tru";;
Failure: Error in Ln: 1 Col: 1
tru
^
Expecting: 'false' or 'true'

<|> コンビネータの振る舞いには2つの重要な特徴があります。

  • 左側のパーザが失敗する場合だけ、 <|> は右側のパーザを試行します。最長マッチルールを実装してはいません。
  • しかし、左側のパーザが 入力を消費することなく 失敗する場合のみ、右側のパーザを試行します。

2点目から得られる帰結は、 <|> の左側のパーザが失敗する前に空白を消費してしまうので、以下のテストは失敗してしまうということです。

> test ((ws >>. str "a") <|> (ws >>. str "b")) " b";;
Failure: Error in Ln: 1 Col: 2
 b
 ^
Expecting: 'a'

運良く、 ws をくくり出すことでこのパーザを簡単に修正することができます。

> test (ws >>. (str "a" <|> str "b")) " b";;
Success: "b"

なぜ <|> がこんな振る舞いをするのか、最初のパーザが入力を消費した後に失敗しても <|> に代わりのパーザを試行する必要がある状況を如何に対処するか、そういうものに興味が出てきたら、ユーザーガイドの セクション5.6セクション5.7 をご覧ください。

もし2つより多くのパーサを選択可能にしてみたくなったら、 p1 <|> p2 <|> p3 <|> ... のように複数の <|> 演算子をつなげることができますし、あるいは choice コンビネータを使うことができて、これは choice [p1; p2; p3; ...] のように引数としてパーザ列を受け入れます。

4.10 F# の値制限

FParsec で自分のパーサを書き始めたり、上記のコードスニペットを各々コンパイルしてみたりすると、しばしば F# や FParsec の初心者が頭をかいて悩むことになるコンパイラの事案: 値制限 に出くわすことになるでしょう。このセクションでは、値制限と FParsec のプログラムでどう対処するかを説明します。

注記

一瞬このセクションの議論が技術的すぎるなと思ったら、ひとまず次のセクションに飛んで、「値制限」のコンパイラメッセージを実際に初めて目にした時に戻ってきましょう。

F# の値制限は以下のコードスニペットがコンパイルできない理由です:

open FParsec
let p = pstring "test"

ですが、以下のコードスニペットは問題なくコンパイルできます [2] :

open FParsec
let p = pstring "test"
run p "input"

最初のサンプルで生成されたコンパイラエラーは以下のとおりです:

error FS0030: Value restriction.
The value 'p' has been inferred to have generic type
    val p : Parser<string,'_a'>
Either make the arguments to 'p' explicit or,
if you do not intend for it to be generic, add a type annotation.

FParsec を使って作業する時、特にインタラクティブコンソールを使って作業している時に、遅かれ早かれこれかよく似たエラーメッセージを目にするでしょう。運がいいことに、この手のエラーは普通、簡単に回避することができます。

上記の最初のスニペットにある問題は、F# がこの状況でジェネリック型を許可していないにもかかわらず、F# コンパイラが p の値が未解決のジェネリック型を持っていると推論していることです。 pstring 関数の戻り値の型は Parser<string,'u> で、その型パラメータ 'uCharStream のユーザ状態の型を表しています。最初のスニペットではこの型パラメータに制約を掛けるものが何もないので、コンパイラはパーザの値 p を 型 Parser<string,'_a> で、 '_a を未解決の型パラメータを表すものと推論します。

run 関数の最初の引数として p を使うことでユーザ状態型に制約を掛けているため、2番目のスニペットではこの問題は起きません。 runParser<'t,unit> 型のパーザだけを受け入れるので、コンパイラは p を非ジェネリック型の Parser<string,unit> と推論するのです。

この例は FParsec のプログラムで値制限に対処する方法を2つ提案しています。

  • 同じコンパイル単位 にある後の計算で使うことで、非パーザ値の型がジェネリック型に制限されるか確認する
  • パーザ値の型に手動で制約をかけるために明白な型注釈を与える(大抵は、キーとなる箇所に型注釈を付ければパーザモジュール全体で十分となります)

しばしば以下のような型省略をいくつか定義しておくと便利です。

type UserState = unit // もちろん unit じゃなければならないことはないです
type Parser<'t> = Parser<'t, UserState>

こんな省略を入れておくと、型注釈は

let p : Parser<_> = pstring "test"

というようにシンプルになります。

もちろん、非ジェネリック型にパーザ値の型を制約づけるのは、実際にジェネリック型が必要ない場合の解決策に過ぎません。ジェネリック値が必要な場合、例えば F# リファレンス や Dmitry Lomov 氏の ブログエントリ で説明されているような、別のテクニックを適用しなければなりません。しかし、FParsec の Parser の値(パラメータをとるパーザ関数ではなく)は、大抵は固定のユーザ状態型をもつ特定のパーザを適用するコンテキストのもとに使われるだけです。そんな状況では、型に制約をかけるのは型制限エラーを避けるための全くもって妥当な方策なのです。

4.11 JSON のパース

いまや私たちは FParsec の基本を議論したところなので、私たちは現実世界のパーザ例: JSON パーザに取り組むのにいい準備ができました。

JSON (JavaScript Object Notation) は単純で軽量な構文を持つテキストベースのデータ交換形式です。構文の説明は json.org または RFC 4626 で見つけることができます。

多くのアプリケーションにおいて、ある特定のオブジェクトを表す JSON ファイルを扱わなくてはならないだけです。このようなコンテキストでは、時に、特定の JSON ファイル用に特化したパーザを書くのが妥当であることがあります。ですが、このチュートリアルではより一般的なアプローチをたどってみます。任意の一般的な JSON ファイルを AST、つまりファイルの内容を表現する中間データ構造にパースできるパーザを実装しましょう。アプリケーションはこのデータ構造を都合良くクエリして必要な情報を抽出できます。これは XML ドキュメントのドキュメントツリーとして表現されるデータ構造を構築する XML パーザのやり方によく似たアプローチです。このアプローチの大きな利点は JSON パーザ自身が再利用可能になり、特定のパースロジックのドキュメントが JSON ドキュメントの AST を処理する単純な関数の形で表現できることです。

F# で AST を実装する自然な方法は判別共用体の助けを借りることです。 JSON specification を見れば、JSON の値は文字列、数値、真偽値、null、角括弧内に値をコンマ区切りしたリスト、そして中括弧で囲ったキーと値のペアの列によるオブジェクトだと分かるでしょう。

私たちのパーザでは、JSON の値を表現するために以下のような共用体を使います。

type Json = JString of string
          | JNumber of float
          | JBool   of bool
          | JNull
          | JList   of Json list
          | JObject of Map<string, Json>

ここで値の列を表現するために F# の list 型を、キー・値のペアを表現するために Map 型を選択しましたが、これらの型は F# で処理をするのに特に便利だからです。 [3] JListJObject の値が自身に Json 値を含んでいるので、 Json 型は再帰的であることに気をつけましょう。私たちのパーザはこの再帰的構造を反映しなければなりません。

Tip

もしあなたが FParsec 初心者で少し時間があるなら、JSON パーザを自力で(リファレンスの助けを借りつつ)実装してみるのはいい練習になるでしょう。このチュートリアルは既にあなたの必要とすることすべてをカバーしており、JSON の文法は十分に簡単なので、そんなに時間がかからないはずです。もちろん、詰まった時はいつでも下記に示す実装を参考にできます。

簡単な null と真偽値の場合をカバーするところからパーザを実装し始めましょう。

let jnull = stringReturn "null" JNull
let jbool =     (stringReturn "true"  (JBool true))
            <|> (stringReturn "false" (JBool false))

JSON の数値形式は多くのプログラミング言語で使われる典型的な浮動小数点数の形式を基にしており、それゆえ FParsec の組み込み pfloat パーザでパースできるので、数値の場合の対処も簡単です:

let jnumber = pfloat |>> JNumber

(F# が JNumber のオブジェクトコンストラクタを関数引数として渡せるようにしていることを気にしておきましょう)

もし pfloat がサポートする正確な数値形式と JSON の定義にある数値形式を比較するなら、 pfloat が JSON の形式の上位集合をサポートしていることが分かるでしょう。JSON の形式と比較して、 pfloat パーザは NaNInfinity 値も認識し、先頭のプラス記号やゼロも受け入れ、Java や C99 の16進浮動小数点形式までサポートしています。コンテキスト次第で、この振る舞いはパーザの特徴とも制限とも言えます。ほとんどのアプリケーションにはおそらく問題にならないでしょうし、JSON RFC は JSON パーザは JSON 文法の上位集合をサポートしても良いと明確に述べています。しかし、もし JSON の数値形式そのものだけサポートしたいのであれば、設定可能な numberLiteral パーザ(pfloat のソースでこれがどのようにやっているかご覧になってみてください)を基にしてより簡単にそんな浮動小数点パーザを実装することができます。

JSON の文字列形式は実装するのにほんの少しだけ手間がかかりますが、 セクション4.7stringLiteral パーザたちで似たような形式を既にパースしてきたので、私たちの目的にそれらのパーザの1つを適合させればいいのです:

let stringLiteral =
    let escape = anyOf "\"\\/bfnrt"
                 |>> function
                     | 'b' -> "\b"
                     | 'f' -> "\u000C"
                     | 'n' -> "\n"
                     | 'r' -> "\r"
                     | 't' -> "\t"
                     | c   -> string c // その他の文字はそのままにします
    let unicodeEscape =
        // 16進文字 ([0-9a-fA-F]) を数値 (0-15) に変換します
        let hex2int c = (int c &&& 15) + (int c >>> 6)*9

        str "u" >>. pipe4 hex hex hex hex (fun h3 h2 h1 h0 ->
            (hex2int h3)*4096 + (hex2int h2)*256 + (hex2int h1)*16 + hex2int h0
            |> char |> string
        )

    let escapedCharSnippet = str "\\" >>. (escape <|> unicodeEscape)
    let normalCharSnippet  = manySatisfy (fun c -> c <> '"' && c <> '\\')

    between (str "\"") (str "\"")
            (stringsSepBy normalCharSnippet escapedCharSnippet)

stringLiteral はエスケープ済みの文字スニペットで区切られた普通の文字スニペットの列として文字列リテラルをパースします。普通の文字スニペットは '"''\\' の文字を含まない任意の文字シーケンスです。エスケープ済み文字スニペットは '\\''\"''/''b''f''n''r''t' 、そしてユニコードのエスケープのいずれかがバックスラッシュに続くものです。ユニコードのエスケープは 'u' とそれに続く UTF-16 コードポイントを表す4桁の16進数です。

どんなリストやオブジェクトも自身に任意の JSON 値を含むことができるので、JSON のリストとオブジェクトの文法ルールは再帰的です。それゆえ、リストやオブジェクトの文法ルール用のパーザを書くために、まだそんなパーザは構築できていないにもかかわらず、任意の JSON 値用のパーザを参照する方法が必要になります。こういうことはコンピューティングではよく有ることで、別の回り道を導入することでこの問題を解決できます:

let jvalue, jvalueRef = createParserForwardedToRef<Json, unit>()

名前から推測したかもしれませんが、 createParserForwardedToRef はすべての呼び出しを参照セルにあるパーザ(jvalueRef)に転送するパーザ(jvalue)を生成します。はじめに、参照セルはダミーのパーザを保持しますが、参照セルは可変であり、一度構築し終えたら、あとでダミーパーザを実際の値を持つパーザに置き換えることができます。

JSON RFC はスペース、(水平)タブ、ラインフィード、そしてキャリッジリターンだけを空白文字として許可しており、空白をパースするために組み込みの spaces パーザを使うことができます:

let ws = spaces

JSON リストとオブジェクトの両方とも括弧の間に「要素」があるコンマ区切りのリストとして構文的に表現されており、それらにおいて括弧、コンマ、そしてリスト要素の前後にある空白は許されます。以下の補助関数を使ってこのようなリストを便利にパースすることができます:

let listBetweenStrings sOpen sClose pElement f =
    between (str sOpen) (str sClose)
            (ws >>. sepBy (pElement .>> ws) (str "," >>. ws) |>> f)

この関数は4つの引数をとります。それは、開始文字、終了文字、要素のパーザ、そしてパースした要素のリストに適用する関数です。

この関数のおかげで以下のように JSON リスト用のパーザを定義できます:

let jlist = listBetweenStrings "[" "]" jvalue JList

JSON オブジェクトはキー・値のペアのリストなので、キー・値ペア用のパーザが必要です:

let keyValue = stringLiteral .>>. (ws >>. str ":" >>. ws >>. jvalue)

(.>>. の両側の点は、両側にあるパーザの結果はタプルとして返されることを示していることを思い出しましょう)

keyValue パーザを listBetweenStrings に渡すことで JSON オブジェクト用のパーザを得ることができます:

let jobject = listBetweenStrings "{" "}" keyValue (Map.ofList >> JObject)

JSON 値の取り得るすべての値に対するパーザを定義したので、JSON 値用の完成形パーザを得るために、相異なる場合を choice パーザで連結することができます:

do jvalueRef := choice [jobject
                        jlist
                        jstring
                        jnumber
                        jtrue
                        jfalse
                        jnull]

jvalue パーザは先頭や後続の空白を受け入れないので、以下のようにして、完全な JSON ドキュメント用に私たちのパーザを定義する必要があります:

let json = ws >>. jvalue .>> ws .>> eof

このパーザは完全な JSON の入力ストリームを消費しようとし、成功したらパーザ結果として入力の Json AST を返します。

そして、これで JSON パーザについておしまいです。もしいくつかサンプルの入力をこのパーザに試してみたくなったら、 Samples フォルダにある JSON プロジェクトをご覧ください。

4.12 さてどうする?

もしこのチュートリアルが FParsec へのもっと深い導入への渇望を刺激したなら、 ユーザーズガイド に向かってください。もし自分のパーザを書くのが待ちきれないのなら、 パーザ概要 のページをブックマークし、 Samples フォルダにあるパーザ例を軽く眺めたりしてハックし始めましょう。どこかで詰まったりしたらユーザーズガイドをいつでも参照できます。


[1]
let pipe7 p1 p2 p3 p4 p5 p6 p7 f =
    pipe4 p1 p2 p3 (tuple4 p4 p5 p6 p7)
          (fun x1 x2 x3 (x4, x5, x6, x7) -> f x1 x2 x3 x4 x5 x6 x7)
[2]2つの FParsec DLL を参照しておくことが前提です。
[3]もし巨大なシーケンスやオブジェクトをパースする必要があるなら、JList や JObject のそれぞれに配列や辞書型を使う方が妥当かもしれません。