ゼロからJSONパーサーを書く

このシリーズでは、アプリカティブパーサーとパーサーコンビネータの仕組みを見ていきます。

最初の投稿では、パーシングライブラリの基礎を作りました。
2番目の投稿では、他の多くの便利なコンビネータでライブラリを拡張しました。
3番目の投稿では、エラーメッセージを改善しました。
この最後の投稿では、これまでに作成したライブラリを使ってJSONパーサーを組み立てます。

まず何よりも、過去数回の投稿で開発したパーサーライブラリスクリプトをロードし、ParserLibrary名前空間をオープンする必要があります。

#load "ParserLibrary.fsx"

open System
open ParserLibrary

ParserLibrary.fsxはここからダウンロードできます。

1. JSONの仕様を表現するモデルの作成

JSONの仕様はjson.orgで確認できます。要約すると次のようになります。

valueはstring、number、bool、null、object、arrayのいずれかです。これらの構造は入れ子にできます。
stringは、ダブルクォートで囲まれた0個以上のUnicode文字の列です。バックスラッシュでエスケープします。
numberはC言語やJavaの数値とよく似ていますが、8進数と16進数は使いません。
booleanはtrueまたはfalseのリテラルです。
nullはnullリテラルです。
objectは名前と値のペアの順序なし集合です。
- 左波かっこ{で始まり、右波かっこ}で終わります。
- 各名前の後にコロン:が続き、ペアはカンマ,で区切ります。
arrayは値の順序付きコレクションです。
- 左かぎかっこ[で始まり、右かぎかっこ]で終わります。
- 値はカンマ,で区切ります。
任意のトークンのペア間に空白を入れられます。

F#では、この定義を自然に以下のようにモデル化できます。

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

JSONパーサーの作成目標は次のとおりです。

文字列を入力として、JValue値を出力できること。

2. `Null`と`Bool`から始める

まずは比較的簡単な、nullとブール値のリテラルをパースすることから始めましょう。

Nullのパース

nullリテラルのパースは簡単です。手順は次のとおりです。

“null”という文字列にマッチする。
結果をJNullケースにマップする。

コードは以下のようになります。

let jNull =
    pstring "null"
    |>> (fun _ -> JNull)  // JNullにマップ
    <?> "null"            // ラベルを付ける

パーサーが返す値は常に”null”なので、実際にはその値を気にしません。

このような状況はよくあるので、>>%という小さなユーティリティ関数を作り、より簡潔に書けるようにします。

// パーサーpを適用し、結果を無視して、xを返す。
let (>>%) p x =
    p |>> (fun _ -> x)

これでjNullを次のように書き直せます。

let jNull =
    pstring "null"
    >>% JNull   // 新しいユーティリティコンビネータを使う
    <?> "null"

テストしてみましょう。

run jNull "null"
// 成功: JNull

run jNull "nulp" |> printResult
// 行:0 列:3 nullのパースエラー
// nulp
//    ^予期しない 'p'

良さそうです。次は別のものを試してみましょう。

Boolのパース

boolパーサーはnullと似ています。

“true”にマッチするパーサーを作ります。
“false”にマッチするパーサーを作ります。
そして<|>を使ってそれらを選択します。

コードは以下のようになります。

let jBool =
    let jtrue =
        pstring "true"
        >>% JBool true   // JBoolにマップ
    let jfalse =
        pstring "false"
        >>% JBool false  // JBoolにマップ

    // trueとfalseの間で選択
    jtrue <|> jfalse
    <?> "bool"           // ラベルを付ける

いくつかのテストを行ってみましょう。

run jBool "true"
// 成功: JBool true

run jBool "false"
// 成功: JBool false

run jBool "truX" |> printResult
// 行:0 列:0 boolのパースエラー
// truX
// ^予期しない 't'

ただし、このエラーメッセージは誤解を招く可能性があります。この問題は、前回の投稿で説明したバックトラッキングに起因しています。 “true” が失敗したため、今は “false” をパースしようとしていて、 “t” が予期しない文字となっています。

3. `String`のパース

次はやや複雑な、文字列のパース処理に取り組みましょう。

文字列パースの仕様は以下のような”鉄道図”で表されています。

全ての図はjson.orgから引用。

このような図からパーサーを組み立てるには、ボトムアップで作業し、小さな”プリミティブ”パーサーを作成し、それらを組み合わせてより大きなものを作ります。

まずは「クォートとバックスラッシュ以外のUnicode文字」から始めましょう。簡単な条件を使っているので、satisfy関数を使えます。

let jUnescapedChar =
    let label = "文字"
    satisfy (fun ch -> ch <> '\\' && ch <> '\"') label

すぐにテストできます。

run jUnescapedChar "a"   // 成功 'a'

run jUnescapedChar "\\" |> printResult
// 行:0 列:0 文字のパースエラー
// \
// ^予期しない '\'

はい、うまくいきました。

エスケープ文字

次は、エスケープ文字の場合を考えましょう。

この場合、マッチさせる文字列のリスト（"\""、"\n"など）があり、それぞれに対して結果として使用する文字があります。

処理の流れは以下のとおりです。

まず、(マッチする文字列, 結果の文字)の形式のペアのリストを定義します。
それぞれに対して、pstring マッチする文字列 >>% 結果の文字を使ってパーサーを組み立てます。
最後に、choice関数を使ってこれらのパーサーをすべて組み合わせます。

コードは以下のようになります。

/// エスケープ文字をパースする
let jEscapedChar =
    [
    // (マッチする文字列, 結果の文字)
    ("\\\"",'\"')      // クォート
    ("\\\\",'\\')      // バックスラッシュ
    ("\\/",'/')        // スラッシュ
    ("\\b",'\b')       // バックスペース
    ("\\f",'\f')       // フォームフィード
    ("\\n",'\n')       // 改行
    ("\\r",'\r')       // キャリッジリターン
    ("\\t",'\t')       // タブ
    ]
    // 各ペアをパーサーに変換
    |> List.map (fun (toMatch,result) ->
        pstring toMatch >>% result)
    // そしてそれらを1つにまとめる
    |> choice
    <?> "エスケープ文字" // ラベルを設定

ここでもすぐにテストしてみましょう。

run jEscapedChar "\\\\" // 成功 '\'
run jEscapedChar "\\t"  // 成功 '\009'

run jEscapedChar "a" |> printResult
// 行:0 列:0 エスケープ文字のパースエラー
// a
// ^予期しない 'a'

うまく動作していますね！

Unicode文字

最後に取り組むのは、16進数を用いたUnicode文字のパース処理です。

処理の流れは以下のとおりです。

まず、バックスラッシュ、u、16進数の数字のプリミティブを定義します。
4つの16進数の数字を使って、これらを組み合わせます。
パーサーの出力が入れ子になったタプルになって扱いにくいため、数字をintに変換し、さらにcharに変換するヘルパー関数が必要です。

コードは以下のようになります。

/// Unicode文字をパースする
let jUnicodeChar =

    // "プリミティブ"パーサーを設定
    let backslash = pchar '\\'
    let uChar = pchar 'u'
    let hexdigit = anyOf (['0'..'9'] @ ['A'..'F'] @ ['a'..'f'])

    // パーサーの出力（入れ子になったタプル）を
    // 文字に変換する
    let convertToChar (((h1,h2),h3),h4) =
        let str = sprintf "%c%c%c%c" h1 h2 h3 h4
        Int32.Parse(str,Globalization.NumberStyles.HexNumber) |> char

    // メインパーサーを設定
    backslash  >>. uChar >>. hexdigit .>>. hexdigit .>>. hexdigit .>>. hexdigit
    |>> convertToChar

笑顔の絵文字 \u263A でテストしてみましょう。

run jUnicodeChar "\\u263A"

完全な`String`パーサー

ここまでの要素を組み合わせて、完全な文字列パーサーを作成します。

quoteのプリミティブを定義します。
jUnescapedChar、jEscapedChar、jUnicodeCharの選択肢としてjcharを定義します。
全体のパーサーは、2つの引用符の間に0個以上のjcharが来るものとします。

let quotedString =
    let quote = pchar '\"' <?> "quote"
    let jchar = jUnescapedChar <|> jEscapedChar <|> jUnicodeChar

    // メインパーサーを設定
    quote >>. manyChars jchar .>> quote

最後に、引用符で囲まれた文字列をJStringケースでラップし、ラベルを付けます。

/// JStringをパースする
let jString =
    // 文字列をJStringでラップ
    quotedString
    |>> JString           // JStringに変換
    <?> "引用符で囲まれた文字列"   // ラベルを追加

完成したjString関数をテストしてみましょう。

run jString "\"\""    // 成功 ""
run jString "\"a\""   // 成功 "a"
run jString "\"ab\""  // 成功 "ab"
run jString "\"ab\\tde\""      // 成功 "ab\tde"
run jString "\"ab\\u263Ade\""  // 成功 "ab?de"

4. `Number`のパース

数値のパース処理は、以下の”鉄道図”で表されます。

ここも、ボトムアップで作業を進めましょう。最も基本的な要素である単一の文字や数字から始めます。

let optSign = opt (pchar '-')

let zero = pstring "0"

let digitOneNine =
    satisfy (fun ch -> Char.IsDigit ch && ch <> '0') "1-9"

let digit =
    satisfy (fun ch -> Char.IsDigit ch ) "digit"

let point = pchar '.'

let e = pchar 'e' <|> pchar 'E'

let optPlusMinus = opt (pchar '-' <|> pchar '+')

次に、数値の”整数部”を組み立てます。これは以下のいずれかです。

数字の0
nonZeroInt: digitOneNineの後に0個以上の通常の数字が続くもの

let nonZeroInt =
    digitOneNine .>>. manyChars digit
    |>> fun (first,rest) -> string first + rest

let intPart = zero <|> nonZeroInt

nonZeroIntパーサーでは、digitOneNine（char型）の出力とmanyChars digit（string型）の出力を組み合わせる必要があるため、簡単なマップ関数が必要です。

オプションの小数部は、小数点の後に1つ以上の数字が続くものです。

let fractionPart = point >>. manyChars1 digit

指数部はeの後にオプションの符号が続き、さらに1つ以上の数字が続きます。

let exponentPart = e >>. optPlusMinus .>>. manyChars1 digit

これらのコンポーネントを使って、数値全体を組み立てることができます。

optSign .>>. intPart .>>. opt fractionPart .>>. opt exponentPart
|>> convertToJNumber
<?> "number"   // ラベルを追加

ただし、convertToJNumberはまだ定義していません。この関数は、パーサーが出力する4つ組を受け取り、それをfloat型に変換します。

float型の処理を自分で書くよりも、怠惰になって.NETフレームワークに変換させましょう！つまり、各コンポーネントを文字列に変換し、連結して、全体の文字列をfloat型に解析します。

問題は、符号や指数などのコンポーネントの一部がオプションであることです。渡された関数を使ってオプションを文字列に変換し、オプションがNoneの場合は空文字列を返すヘルパーを書きましょう。

|>?と呼ぶことにしますが、jNumberパーサー内でのみローカルに使用されるので、実際には重要ではありません。

// オプション値を文字列に変換するユーティリティ関数、もしくは存在しない場合は""を返す
let ( |>? ) opt f =
    match opt with
    | None -> ""
    | Some x -> f x

これでconvertToJNumberを作成できます。

符号は文字列に変換されます。
小数部は文字列に変換され、小数点が前に付きます。
指数部は文字列に変換され、指数の符号も文字列に変換されます。

let convertToJNumber (((optSign,intPart),fractionPart),expPart) =
    // 文字列に変換し、.NETに解析させる！ - 粗いが今のところはOK。

    let signStr =
        optSign
        |>? string   // 例: "-"

    let fractionPartStr =
        fractionPart
        |>? (fun digits -> "." + digits )  // 例: ".456"

    let expPartStr =
        expPart
        |>? fun (optSign, digits) ->
            let sign = optSign |>? string
            "e" + sign + digits          // 例: "e-12"

    // 部分を合わせてfloatに変換し、JNumberでラップする
    (signStr + intPart + fractionPartStr + expPartStr)
    |> float
    |> JNumber

かなり荒削りな実装で、文字列に変換するのは遅い可能性があるので、もっと良いバージョンを書くのは自由です。

これで、完全なjNumber関数に必要なものがすべて揃いました。

/// JNumberをパースする
let jNumber =

    // "プリミティブ"パーサーを設定
    let optSign = opt (pchar '-')

    let zero = pstring "0"

    let digitOneNine =
        satisfy (fun ch -> Char.IsDigit ch && ch <> '0') "1-9"

    let digit =
        satisfy (fun ch -> Char.IsDigit ch ) "digit"

    let point = pchar '.'

    let e = pchar 'e' <|> pchar 'E'

    let optPlusMinus = opt (pchar '-' <|> pchar '+')

    let nonZeroInt =
        digitOneNine .>>. manyChars digit
        |>> fun (first,rest) -> string first + rest

    let intPart = zero <|> nonZeroInt

    let fractionPart = point >>. manyChars1 digit

    let exponentPart = e >>. optPlusMinus .>>. manyChars1 digit

    // オプション値を文字列に変換するユーティリティ関数、もしくは存在しない場合は""を返す
    let ( |>? ) opt f =
        match opt with
        | None -> ""
        | Some x -> f x

    let convertToJNumber (((optSign,intPart),fractionPart),expPart) =
        // 文字列に変換し、.NETに解析させる！ - 粗いが今のところはOK。

        let signStr =
            optSign
            |>? string   // 例: "-"

        let fractionPartStr =
            fractionPart
            |>? (fun digits -> "." + digits )  // 例: ".456"

        let expPartStr =
            expPart
            |>? fun (optSign, digits) ->
                let sign = optSign |>? string
                "e" + sign + digits          // 例: "e-12"

        // 部分を合わせてfloatに変換し、JNumberでラップする
        (signStr + intPart + fractionPartStr + expPartStr)
        |> float
        |> JNumber

    // メインパーサーを設定
    optSign .>>. intPart .>>. opt fractionPart .>>. opt exponentPart
    |>> convertToJNumber
    <?> "number"   // ラベルを追加

少し長くなりましたが、各コンポーネントは仕様に従っているので、まだ十分に読みやすいと思います。

テストを始めましょう。

run jNumber "123"     // JNumber 123.0
run jNumber "-123"    // JNumber -123.0
run jNumber "123.4"   // JNumber 123.4

失敗するケースはどうでしょうか？

run jNumber "-123."   // JNumber -123.0 -- 失敗するはず！
run jNumber "00.1"    // JNumber 0      -- 失敗するはず！

予想外の結果が出ています！これらのケースは確実に失敗するはずですよね？

いえ、そうではありません。-123.のケースで起こっていることは、パーサーが小数点まですべてを消費して停止し、小数点を次のパーサーにマッチさせるために残しているのです！つまり、エラーではありません。

同様に、00.1のケースでは、パーサーは最初の0だけを消費して停止し、残りの入力（0.4）を次のパーサーにマッチさせるために残しています。これもエラーではありません。

これを適切に修正するのは範囲外なので、パーサーに空白を追加して強制的に終了させましょう。

let jNumber_ = jNumber .>> spaces1

では、もう一度テストしてみましょう。

run jNumber_ "123"     // JNumber 123.0
run jNumber_ "-123"    // JNumber -123.0

run jNumber_ "-123." |> printResult
// 行:0 列:4 numberとmany1 whitespaceのパースエラー
// -123.
//     ^予期しない '.'

エラーが適切に検出されるようになりました。

小数部をテストしてみましょう。

run jNumber_ "123.4"   // JNumber 123.4

run jNumber_ "00.4" |> printResult
// 行:0 列:1 numberとmany1 whitespaceのパースエラー
// 00.4
//  ^予期しない '0'

次に指数部をテストします。

// 指数のみ
run jNumber_ "123e4"     // JNumber 1230000.0

// 小数部と指数部
run jNumber_ "123.4e5"   // JNumber 12340000.0
run jNumber_ "123.4e-5"  // JNumber 0.001234

ここまでのところ、すべて良好です。前進しましょう！

5. `Array`のパース

次はArrayのケースです。ここでも鉄道図を使用して実装をガイドします。

ここでもプリミティブから始めます。各トークンの後にオプションの空白を追加していることに注意してください。

let jArray =

    let left = pchar '[' .>> spaces
    let right = pchar ']' .>> spaces
    let comma = pchar ',' .>> spaces
    let value = jValue .>> spaces

そして、カンマで区切られた値のリストを作成し、リスト全体を左右のかっこで囲みます。

let jArray =
    ...

    // リストパーサーを設定
    let values = sepBy1 value comma

    // メインパーサーを設定
    between left values right
    |>> JArray
    <?> "array"

待ってください - このjValueは何でしょうか？

let jArray =
    ...
    let value = jValue .>> spaces    // <=== この"jValue"は何？
    ...

仕様では、Arrayは値のリストを含むことができると言っています。そこで、それらをパースできるjValueパーサーがあると仮定しましょう。

しかし、JValueをパースするには、まずArrayをパースする必要があります！

パースにおける一般的な問題に遭遇しました - 相互に再帰的な定義です。Arrayを作るにはJValueパーサーが必要ですが、JValueを作るにはArrayパーサーが必要です。

これにどう対処すればよいでしょうか？

前方参照

解決策は前方参照を使うことです。今すぐにArrayパーサーを定義するためにダミーのJValueパーサーを使用し、後で前方参照を「本物の」JValueパーサーで修正します。

これは、可変参照が便利な場面の1つです！

このために、ヘルパー関数が必要です。処理の流れは次のようになります。

後で置き換えられるダミーパーサーを定義します。
入力ストリームをダミーパーサーに転送する実際のパーサーを定義します。
実際のパーサーとダミーパーサーへの参照の両方を返します。

クライアントが参照を修正すると、実際のパーサーはダミーパーサーを置き換えた新しいパーサーに入力を転送します。

コードは以下のようになります。

let createParserForwardedToRef<'a>() =

    let dummyParser=
        let innerFn input : Result<'a * Input> = failwith "未修正の転送されたパーサー"
        {parseFn=innerFn; label="unknown"}

    // プレースホルダーParserへの参照
    let parserRef = ref dummyParser

    // ラッパーParser
    let innerFn input =
        // プレースホルダーに入力を転送
        runOnInput !parserRef input
    let wrapperParser = {parseFn=innerFn; label="unknown"}

    wrapperParser, parserRef

これを使って、JValue型のパーサーのプレースホルダーを作成できます。

let jValue,jValueRef = createParserForwardedToRef<JValue>()

`Array`パーサーの完成

Arrayパーサーに戻ると、jValueプレースホルダーを使用してコンパイルが成功するようになりました。

let jArray =

    // "プリミティブ"パーサーを設定
    let left = pchar '[' .>> spaces
    let right = pchar ']' .>> spaces
    let comma = pchar ',' .>> spaces
    let value = jValue .>> spaces

    // リストパーサーを設定
    let values = sepBy1 value comma

    // メインパーサーを設定
    between left values right
    |>> JArray
    <?> "array"

今すぐにテストしようとすると、参照を修正していないため例外が発生します。

run jArray "[ 1, 2 ]"

// System.Exception: 未修正の転送されたパーサー

そこで、とりあえず参照を既に作成したパーサーの1つ、たとえばjNumberを使うように修正しましょう。

jValueRef := jNumber

これで配列内に数値のみを使用する限り、jArray関数を正常にテストできます！

run jArray "[ 1, 2 ]"
// 成功 (JArray [JNumber 1.0; JNumber 2.0],

run jArray "[ 1, 2, ]" |> printResult
// 行:0 列:6 arrayのパースエラー
// [ 1, 2, ]
//       ^予期しない ','

6. `Object`のパース

ObjectのパーサーはArrayのものと非常によく似ています。

まず、鉄道図を見てみましょう。

これを使って、パーサーを直接作成できるので、コメントなしで提示します。

let jObject =

    // "プリミティブ"パーサーを設定
    let left = pchar '{' .>> spaces
    let right = pchar '}' .>> spaces
    let colon = pchar ':' .>> spaces
    let comma = pchar ',' .>> spaces
    let key = quotedString .>> spaces
    let value = jValue .>> spaces

    // リストパーサーを設定
    let keyValue = (key .>> colon) .>>. value
    let keyValues = sepBy1 keyValue comma

    // メインパーサーを設定
    between left keyValues right
    |>> Map.ofList  // keyValueのリストをMapに変換
    |>> JObject     // JObjectでラップ
    <?> "object"    // ラベルを追加

（ただし、現時点では値として数値のみがサポートされていることを覚えておいてください）テストして正常に動作することを確認しましょう。

run jObject """{ "a":1, "b"  :  2 }"""
// JObject (map [("a", JNumber 1.0); ("b", JNumber 2.0)]),

run jObject """{ "a":1, "b"  :  2, }""" |> printResult
// 行:0 列:18 objectのパースエラー
// { "a":1, "b"  :  2, }
//                   ^予期しない ','

7. すべてを組み合わせる

最後に、choiceコンビネータを使用して6つのパーサーすべてを組み合わせ、これを先ほど作成したJValueパーサー参照に割り当てることができます。

jValueRef := choice
    [
    jNull
    jBool
    jNumber
    jString
    jArray
    jObject
    ]

これで全ての準備が整いました！

完全なパーサーのテスト：例1

パースを試みるJSONの文字列の例を挙げてみましょう。

let example1 = """{
    "name" : "Scott",
    "isMale" : true,
    "bday" : {"year":2001, "month":12, "day":25 },
    "favouriteColors" : ["blue", "green"]
}"""
run jValue example1

結果は次のようになります。

JObject
    (map
        [("bday", JObject(map
                [("day", JNumber 25.0);
                ("month", JNumber 12.0);
                ("year", JNumber 2001.0)]));
        ("favouriteColors", JArray [JString "blue"; JString "green"]);
        ("isMale", JBool true);
        ("name", JString "Scott")
        ])

完全なパーサーのテスト：例2

こちらはjson.orgの例ページからのものです。

let example2= """{"widget": {
    "debug": "on",
    "window": {
        "title": "Sample Konfabulator Widget",
        "name": "main_window",
        "width": 500,
        "height": 500
    },
    "image": {
        "src": "Images/Sun.png",
        "name": "sun1",
        "hOffset": 250,
        "vOffset": 250,
        "alignment": "center"
    },
    "text": {
        "data": "Click Here",
        "size": 36,
        "style": "bold",
        "name": "text1",
        "hOffset": 250,
        "vOffset": 100,
        "alignment": "center",
        "onMouseUp": "sun1.opacity = (sun1.opacity / 100) * 90;"
    }
}}  """

run jValue example2

結果は次のようになります。

JObject(map
    [("widget",JObject(map
            [("debug", JString "on");
            ("image",JObject(map
                [("alignment", JString "center");
                    ("hOffset", JNumber 250.0); ("name", JString "sun1");
                    ("src", JString "Images/Sun.png");
                    ("vOffset", JNumber 250.0)]));
            ("text",JObject(map
                [("alignment", JString "center");
                    ("data", JString "Click Here");
                    ("hOffset", JNumber 250.0);
                    ("name", JString "text1");
                    ("onMouseUp", JString "sun1.opacity = (sun1.opacity / 100) * 90;");
                    ("size", JNumber 36.0);
                    ("style", JString "bold");
                    ("vOffset", JNumber 100.0)]));
            ("window",JObject(map
                [("height", JNumber 500.0);
                    ("name", JString "main_window");
                    ("title", JString "Sample Konfabulator Widget");
                    ("width", JNumber 500.0)]))]))]),

JSONパーサーの完全なリスト

以下がJSONパーサーの完全なリストです - 約250行の有用なコードです。

以下に表示されているソースコードは、このgistでも利用可能です。

#load "ParserLibrary.fsx"

open System
open ParserLibrary

(*
// --------------------------------
JSON仕様（https://www.json.org/より）
// --------------------------------

JSON仕様は[json.org](https://www.json.org/)で確認できます。ここで要約します：

* `value`は`string`、`number`、`bool`、`null`、`object`、`array`のいずれかです。
  * これらの構造は入れ子にできます。
* `string`は、ダブルクォートで囲まれた0個以上のUnicode文字の列で、バックスラッシュによるエスケープを使用します。
* `number`はC言語やJavaの数値とよく似ていますが、8進数と16進数の形式は使用しません。
* `boolean`は`true`または`false`のリテラルです。
* `null`は`null`リテラルです。
* `object`は名前/値のペアの順序なし集合です。
  * オブジェクトは{ (左波かっこ)で始まり} (右波かっこ)で終わります。
  * 各名前の後には: (コロン)が続き、名前/値のペアは, (カンマ)で区切られます。
* `array`は値の順序付きコレクションです。
  * 配列は[ (左かぎかっこ)で始まり] (右かぎかっこ)で終わります。
  * 値は, (カンマ)で区切られます。
* 任意のトークンのペアの間に空白を挿入できます。

*)

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


// ======================================
// 前方参照
// ======================================

/// 前方参照を作成する
let createParserForwardedToRef<'a>() =

    let dummyParser=
        let innerFn input : Result<'a * Input> = failwith "未修正の転送されたパーサー"
        {parseFn=innerFn; label="unknown"}

    // プレースホルダーParserへの参照
    let parserRef = ref dummyParser

    // ラッパーParser
    let innerFn input =
        // プレースホルダーに入力を転送
        runOnInput !parserRef input
    let wrapperParser = {parseFn=innerFn; label="unknown"}

    wrapperParser, parserRef

let jValue,jValueRef = createParserForwardedToRef<JValue>()

// ======================================
// ユーティリティ関数
// ======================================

// パーサーpを適用し、結果を無視して、xを返す。
let (>>%) p x =
    p |>> (fun _ -> x)

// ======================================
// JNullのパース
// ======================================

let jNull =
    pstring "null"
    >>% JNull   // JNullにマップ
    <?> "null"  // ラベルを付ける

// ======================================
// JBoolのパース
// ======================================

let jBool =
    let jtrue =
        pstring "true"
        >>% JBool true   // JBoolにマップ
    let jfalse =
        pstring "false"
        >>% JBool false  // JBoolにマップ

    // trueとfalseの間で選択
    jtrue <|> jfalse
    <?> "bool"           // ラベルを付ける


// ======================================
// JStringのパース
// ======================================

/// エスケープされていない文字をパースする
let jUnescapedChar =
    satisfy (fun ch -> ch <> '\\' && ch <> '\"') "char"

/// エスケープされた文字をパースする
let jEscapedChar =
    [
    // (マッチする文字列, 結果の文字)
    ("\\\"",'\"')      // クォート
    ("\\\\",'\\')      // バックスラッシュ
    ("\\/",'/')        // スラッシュ
    ("\\b",'\b')       // バックスペース
    ("\\f",'\f')       // フォームフィード
    ("\\n",'\n')       // 改行
    ("\\r",'\r')       // キャリッジリターン
    ("\\t",'\t')       // タブ
    ]
    // 各ペアをパーサーに変換
    |> List.map (fun (toMatch,result) ->
        pstring toMatch >>% result)
    // そしてそれらを1つにまとめる
    |> choice

/// Unicode文字をパースする
let jUnicodeChar =

    // "プリミティブ"パーサーを設定
    let backslash = pchar '\\'
    let uChar = pchar 'u'
    let hexdigit = anyOf (['0'..'9'] @ ['A'..'F'] @ ['a'..'f'])

    // パーサーの出力（入れ子になったタプル）を
    // 文字に変換する
    let convertToChar (((h1,h2),h3),h4) =
        let str = sprintf "%c%c%c%c" h1 h2 h3 h4
        Int32.Parse(str,Globalization.NumberStyles.HexNumber) |> char

    // メインパーサーを設定
    backslash  >>. uChar >>. hexdigit .>>. hexdigit .>>. hexdigit .>>. hexdigit
    |>> convertToChar


/// クォートで囲まれた文字列をパースする
let quotedString =
    let quote = pchar '\"' <?> "クォート"
    let jchar = jUnescapedChar <|> jEscapedChar <|> jUnicodeChar

    // メインパーサーを設定
    quote >>. manyChars jchar .>> quote

/// JStringをパースする
let jString =
    // 文字列をJStringでラップ
    quotedString
    |>> JString           // JStringに変換
    <?> "クォートで囲まれた文字列"   // ラベルを追加

// ======================================
// JNumberのパース
// ======================================

/// JNumberをパースする
let jNumber =

    // "プリミティブ"パーサーを設定
    let optSign = opt (pchar '-')

    let zero = pstring "0"

    let digitOneNine =
        satisfy (fun ch -> Char.IsDigit ch && ch <> '0') "1-9"

    let digit =
        satisfy (fun ch -> Char.IsDigit ch ) "digit"

    let point = pchar '.'

    let e = pchar 'e' <|> pchar 'E'

    let optPlusMinus = opt (pchar '-' <|> pchar '+')

    let nonZeroInt =
        digitOneNine .>>. manyChars digit
        |>> fun (first,rest) -> string first + rest

    let intPart = zero <|> nonZeroInt

    let fractionPart = point >>. manyChars1 digit

    let exponentPart = e >>. optPlusMinus .>>. manyChars1 digit

    // オプション値を文字列に変換するユーティリティ関数、もしくは存在しない場合は""を返す
    let ( |>? ) opt f =
        match opt with
        | None -> ""
        | Some x -> f x

    let convertToJNumber (((optSign,intPart),fractionPart),expPart) =
        // 文字列に変換し、.NETに解析させる！ - 粗いが今のところはOK。

        let signStr =
            optSign
            |>? string   // 例: "-"

        let fractionPartStr =
            fractionPart
            |>? (fun digits -> "." + digits )  // 例: ".456"

        let expPartStr =
            expPart
            |>? fun (optSign, digits) ->
                let sign = optSign |>? string
                "e" + sign + digits          // 例: "e-12"

        // 部分を合わせてfloatに変換し、JNumberでラップする
        (signStr + intPart + fractionPartStr + expPartStr)
        |> float
        |> JNumber

    // メインパーサーを設定
    optSign .>>. intPart .>>. opt fractionPart .>>. opt exponentPart
    |>> convertToJNumber
    <?> "number"   // ラベルを追加

// ======================================
// JArrayのパース
// ======================================

let jArray =

    // "プリミティブ"パーサーを設定
    let left = pchar '[' .>> spaces
    let right = pchar ']' .>> spaces
    let comma = pchar ',' .>> spaces
    let value = jValue .>> spaces

    // リストパーサーを設定
    let values = sepBy1 value comma

    // メインパーサーを設定
    between left values right
    |>> JArray
    <?> "array"

// ======================================
// JObjectのパース
// ======================================


let jObject =

    // "プリミティブ"パーサーを設定
    let left = pchar '{' .>> spaces
    let right = pchar '}' .>> spaces
    let colon = pchar ':' .>> spaces
    let comma = pchar ',' .>> spaces
    let key = quotedString .>> spaces
    let value = jValue .>> spaces

    // リストパーサーを設定
    let keyValue = (key .>> colon) .>>. value
    let keyValues = sepBy1 keyValue comma

    // メインパーサーを設定
    between left keyValues right
    |>> Map.ofList  // keyValueのリストをMapに変換
    |>> JObject     // JObjectでラップ
    <?> "object"    // ラベルを追加

// ======================================
// jValue参照の修正
// ======================================

// 前方参照を修正
jValueRef := choice
    [
    jNull
    jBool
    jNumber
    jString
    jArray
    jObject
    ]

まとめ

この投稿では、前回までの投稿で開発したパーサーライブラリを使用してJSONパーサーを組み立てました。

パーサーライブラリを作り、それを使って実際のパーサーをゼロから組み立てたことで、パーサーコンビネータの仕組みと、その有用性について十分に理解できたことを願っています。

最初の投稿で述べたことを繰り返しますが、この技術を本番環境で使う場合は、実運用に最適化された、F#用のFParsecライブラリを調査することをお勧めします。

また、F#以外の言語を使用している場合でも、ほぼ確実にパーサーコンビネータライブラリが利用可能です。

パーサーコンビネータ全般についての詳細情報は、FParsecに影響を与えたHaskellライブラリである”Parsec”でインターネット検索してください。
FParsecの使用例については、以下の投稿のいずれかを試してみてください：

ありがとうございました！

この投稿のソースコードはこのgistで利用可能です。

ゼロからJSONパーサーを書く

1. JSONの仕様を表現するモデルの作成

2. NullとBoolから始める

Nullのパース

Boolのパース

3. Stringのパース

エスケープ文字

Unicode文字

完全なStringパーサー

4. Numberのパース

5. Arrayのパース

前方参照

Arrayパーサーの完成

6. Objectのパース

7. すべてを組み合わせる

完全なパーサーのテスト：例1

完全なパーサーのテスト：例2

JSONパーサーの完全なリスト

まとめ

2. `Null`と`Bool`から始める

3. `String`のパース

完全な`String`パーサー

4. `Number`のパース

5. `Array`のパース

`Array`パーサーの完成

6. `Object`のパース