FParsecでJSONパーサーを書いてみる話
F# Advent Calendar 2017の4日目の記事です。 NGK2017B昼の部でパーサーコンビネーターについてLTしてきたので、その内容について書きます。 ただし、内容は大幅に加筆修正しています。
PCさえあればいい。 from bleis tift
導入
世の中にはパースすべきものであふれています。 例えば、下記のようなものがあります。
構造を持ったものはそこら中にあります。 これらを処理するためにどうすればいいでしょうか。
一つの方法として、正規表現を使うというものがあります。 しかし、(本来の)正規表現ではネストする文法などは扱えません。 拡張機能として、ネストする文法が扱えるようになっているような処理系もあります。 しかし、そもそもそんな複雑な正規表現には近寄りたくないですよね。
では、文字列操作関数を駆使してどうにかする方法はどうでしょうか。 ごくシンプルなものならそれでもいいですが、すぐに限界が訪れます。 なんの指針もなしに書いてしまうと、機能拡張も保守も困難なひどいコードが出来上がります。
こういうものは、パーサーを使って処理するのがいいでしょう。
パーサーとは？
パーサーとは、一次元的な構造、例えば文字列などから構文木を作るものと言えます。
例えば、ログの中身から LogEntry のリスト構造にしたり、設定ファイルの中身から Config オブジェクトにしたり、ソースコードをASTに変換したりするものです。
では、パーサーはどのようにして作ればいいのでしょうか。 それには、おおざっぱに3つの方法があります。
- 手書き
- パーサージェネレーター
- パーサーコンビネーター
手書きによる方法
手書きによる方法では通常、LL法と呼ばれる手法により、再帰関数としてパーサーを書きます。 どのくらいの複雑さを持った文法を相手にしているのかが自明ではなくなるので、この方法に最初から手を出すのはおすすめしません。
パーサージェネレーターによる方法
文法規則のためのDSLを、パーサージェネレーターというツールを使い、その文法規則を解析するためのコードを生成する方法です。 文法規則を修正した際に、コードの再生成が必要になるため、手書きや後述のパーサーコンビネーターほど手軽ではありません。
パーサーコンビネーターによる方法
基本的なパーサーとパーサーを組み合わせるための関数から構成される、パーサーを作るためのライブラリです。 単なるライブラリなので、コードの生成などの追加のビルドプロセスを必要としません。 しかし、手書きやパーサージェネレーターに比べると処理速度の面で劣ることがあるため、頻繁に実行する必要がある場面では計測をするといいでしょう。
3つの方法をざっくりと紹介しましたが、まずは手軽なパーサーコンビネーターから始めてみるのがおすすめです*1。
パーサーコンビネーターの特徴
パーサーコンビネーターは次のような特徴を持ちます。
- パーサーが部品として再利用可能
- 各パーサー(部品)単位でテスト可能
- 表現力が高い
- パーサーを実行時に組み立てたりもできる
なにから始めればいいか
パーサーコンビネーターを使うと決めたとして、最初に取り組む題材にはどのようなものを選べばいいでしょうか。 ここでは、下記の3つの題材について考えてみます。
どの題材についても言えることですが、「すでにあるライブラリを使えばいい」という考えではいつまでたっても自分でパーサーが書けるようになりません。 パーサーが自分で書けるようになると、プログラマーとして対応できる範囲が広がり、文字列解析に対する判断力も上がります。 たとえすでにライブラリがあったとしても、練習としてそれらを自前で実装しなおすことには大きな意味があるのです。
数式
伝統的なものとして、簡単な数式があります。 四則演算からはじめて、かっこの追加や変数の追加など、発展も考えやすい題材です。 しかし、出来上がるものが地味なので、ありがたみや達成感が薄いのがつらいところです。
YAML
YAMLは設定ファイルなどで見かける形式です。 yaml.orgに仕様があります。 YAMLがパース出来るようになると、設定ファイルをオブジェクトに変換するコードが書けるようになるので、数式よりも達成感は大きいでしょう。 しかし、YAML1.0でもかなり巨大な仕様なので、最初の題材としてはあまりおすすめできません。
JSON
JSONは、設定ファイルのほかにもWebAPIのリクエストボディやレスポンスボディなど、様々な場所で使われています。 json.orgに仕様があります。 YAMLよりもはるかにコンパクトな仕様であり、さらに文法もパースしやすいように考えられたものになっています*2。 そのため、最初の題材としてはJSONがおすすめです。
もし、JSONで拍子抜けしてしまうようであれば、HOCONの機能をつけ足してみるとか、TOMLなど別の形式のパーサーを書いてみるといいでしょう。
パーサーを書く大まかな流れ
パーサーを書く流れとして、次の3つの手順を繰り返すのがいいでしょう。
- 解析したデータを格納するためのデータ構造を用意する
- パーサーを組み合わせて、パース結果を用意したデータ構造に変換する
- 作ったパーサーをテストし、通ったら1や2に戻る
JSONでの例
まずは、 [1,2,3] というJSONをパースできるところを目指します。
このJSONを表すのに必要最小限のデータ構造を考えます。
type Json = | JNumber of float // F#のfloatは64bit | JArray of Json list // F#では配列よりもlistの方が扱いやすい
[1,2,3] という文字列を、 JArray [JNumber 1.0; JNumber 2.0; JNumber 3.0] に変換できたらとりあえずの目標達成ということになります。
いきなり JNumber と JArray の2つに対応するのは難しいので、 JNumber を解析するパーサーだけを作ってみます。
このエントリでは、FParsecというF#用のパーサーコンビネーターライブラリを使います。
FParsecには pfloat という、浮動小数点数形式の文字列("1.5" とか)をパースするパーサーが用意されています*3。
このパーサーを使って浮動小数点数形式の文字列を解析すると、 float 型の結果が得られます。
let parseBy p str = // run関数はFParsecが用意している、パーサーを実行するための関数 match run p str with | Success (res, _, _) -> res | Failure (msg, _, _) -> failwithf "parse error: %s" msg "1.5" |> parseBy pfloat // => 1.5
欲しいのは、 float ではなく JNumber なので、結果を変換する必要があります。
そのための方法はいくつかありますが、最も手軽な方法として |>> 演算子を使ってみます。
let jnumber = pfloat |>> (fun x -> JNumber x)
|>> は左項のパーサーの結果を右項の関数によって変換する演算子です*4。
|>> 演算子の戻り値の型もパーサーになるため、ここで作った jnumber も先程用意した parseBy 関数に渡せます。
"1.5" |> parseBy jnumber // => JNumber 1.5
これでJSONの数値がパース出来るようになったので、次にJSONの配列に進みます。
let jarray = sepBy jnumber (pchar ',') |> between (pchar '[') (pchar ']') |>> (fun xs -> JArray xs)
新しいパーサーが3つ出てきました。
一番使われている pchar 関数は、指定された文字をパースするパーサーを返します。
sepBy 関数は、第一引数で指定されたパーサーが、第二引数で指定されたパーサーで区切られて連続するような文字列をパースするパーサーを返します。
"1,2,3" |> parseBy (sepBy jnumber (pchar ',')) // => [JNumber 1.0; JNumber 2.0; JNumber 3.0]
between 関数は、第一引数で指定されたパーサーと第二引数で指定されたパーサーの間に第三引数で指定されたパーサーが来るような文字列をパースするパーサーを返します。
コードでは第三引数はパイプライン演算子で渡しています。
jarray 全体を試してみましょう。
"[1,2,3]" |> parseBy jarray // => JArray [JNumber 1.0; JNumber 2.0; JNumber 3.0]
目標だった、 [1,2,3] のパースができるようになりました。
このようにして小さいパーサーを組み立てて確認しながら目標に向かっていきやすいのが、パーサーコンビネーターの素晴らしい点です。
はまりがちポイント
パーサーコンビネーターでパーサーを書く際に、入門者がはまりそうなポイントを見ていきましょう。
空白の無視
パーサーの前段には、レキサー(字句解析器)を置くことがあります。 レキサーは「文字列→トークン列」への変換を行い、パーサーは文字列を直接扱うのではなく、トークン列を扱うようにするのです。 レキサーで空白やコメントを読み飛ばすようにしておけば、それらを意識せずにパーサーが書けます。
しかし、パーサーコンビネーターによってはトークン列が扱えないものがあります。 今回使っているFParsecもそのうちの一つなので、本来いレキサーがやるような仕事もパーサーでやらなければなりません。
例えば、先程の jarray パーサーですが、空白を挟むとうまく動きません。
"[ 1, 2, 3 ]" |> parseBy jarray // => エラー
空白のスキップを下手に書くと、繰り返しや再帰と組み合わさった際に簡単に無限ループに陥ってしまいます。 そこで、空白スキップの戦略を決めておくといいでしょう。 例えば、各パーサーの「後ろの空白」を読み飛ばすようにし、最後に全体のパーサーの「前の空白」を読み飛ばすようにすれば、空白のスキップが実現できます。
let ws = spaces let jnumber = pfloat .>> ws |>> JNumber let jarray = sepBy jnumber (pchar ',' >>. ws) |> between (pchar '[' >>. ws) (pchar ']' >>. ws) |>> JArray let parseBy p str = match run (ws >>. p) str with | Success (res, _, _) -> res | Failure (msg, _, _) -> failwithf "parse error: %s" msg "[ 1, 2, 3 ]" |> parseBy jarray // => JArray [JNumber 1.0; JNumber 2.0; JNumber 3.0]
spaces は、0文字以上の空白文字をパースするパーサーです。
これまで見てきた pfloat や pchar と違い、パースした文字列を結果として返さない(unit を返す)点に注意してください。
spaces をそのまま使ってもいいのですが、長いので ws という別名(whitespaceの略)を与えています。
また、もしコメント機能を追加したいような場合でも、 ws の定義を変更すれば対応できます。
このパーサーのバリエーションとして、 spaces1 というものもあり、こちらは1文字以上の空白文字をパースします。
このように、サフィックスとして1が付くようなパーサーがほかにもあります。
例えば、 jarray の実装に使っている sepBy のバリエーションである sepBy1 などです。
こちらも、 sepBy は0回以上の繰り返しを表すのに対し、 sepBy1 は1回以上の繰り返しを表します。
.>> と >>. は、パーサーを連続して適用する演算子です。
ピリオドが付いている方を結果として使い、付いていない方はパースはしますが結果を捨てることを意味しています。
また、どちらの結果も保持する .>>. という演算子もあり、この場合結果はタプルになります。
let hi = pchar 'h' .>>. pchar 'i' |>> (fun (h, i) -> string h + string i) // 結果はタプルとして渡される let hi2 = pchar 'h' .>> pchar 'i' // pchar 'i' の結果は捨てる |>> (fun h -> string h) // 捨てたので結果に含まれない let hi3 = pchar 'h' >>. pchar 'i' // pchar 'h' の結果は捨てる |>> (fun i -> string i) // 捨てたので結果に含まれない "hi" |> parseBy hi // => "hi" "hi" |> parseBy hi2 // => "h" "hi" |> parseBy hi3 // => "i" // 捨てるとは言っても、パースしないわけではないので、 // 後続のパーサーが失敗すると全体として失敗する "ho" |> parseBy hi2 // => エラー
jarray の新しい定義をもう一度見てみます。
let jarray = sepBy jnumber (pchar ',' >>. ws) |> between (pchar '[' >>. ws) (pchar ']' >>. ws) |>> JArray
sepBy や between で .>> ではなく >>. を使っていますが、解析結果には含まれないため、どちらを使っても構いません。
しかし、 .>> よりも >>. の方が効率がいい場合があるため、どちらでもいい場合は >>. を使うようにするといいでしょう。
ちなみに、 p |> between popen pclose (popenとpcloseに挟まれたpをパースするパーサー)は popen >>. p .>> pclose (popenを解析して結果を捨て、pを解析し、pcloseを解析して結果を捨てるパーサー)と同じ意味になります。
let between popen pclose p = popen >>. p .>> pclose
実際には、 >>. と .>> がインライン展開されたような定義になっているため、速度を気にする場面では between を使うといいでしょう*5。
完全一致
これまで作ってきたパーサーですが、実はパース対象の文字列の後ろに余分なものがあってもパースが成功してしまいます(前方一致)。
"[1, 2, 3]]]]" |> parseBy jarray // => JArray [JNumber 1.0; JNumber 2.0; JNumber 3.0]
これでは困ることが多いので、 eof というパーサーを最後に合成するのが普通です。
let parseBy p str = // わかりやすさのため、between ws eof p ではなく >>. と .>> を使ったが、 // 一番上のレベルのパーサーなので速度上の問題にもならないはず match run (ws >>. p .>> eof) str with | Success (res, _, _) -> res | Failure (msg, _, _) -> failwithf "parse error: %s" msg
これで、完全一致しない場合はエラーになるようになりました。
文字列のエスケープ
JSONの文字列にはエスケープがあります。 エスケープを考えなくていい場合、文字列のパーサーは次のようにすればいいでしょう。
type Json = | JNumber of float | JString of string | JArray of Json list let jstring = manyChars (noneOf ['"']) |> between (pchar '"') (pchar '"') .>> ws |>> JString
noneOf 関数は、第一引数で指定された seq<char> に含まれる char 以外の文字にマッチするパーサーを返します。
// string は seq<char> でもあるので、 ['x'; 'y'; 'z'] の代わりに "xyz" と書いてもOK "a" |> parseBy (noneOf "xyz") // => 'a' "y" |> parseBy (noneOf "xyz") // => エラー
manyChars 関数は、 char を返すパーサーを受け取り、その0回以上の繰り返しをパースして、文字列に連結するパーサーを返します*6。
"abc" |> parseBy (manyChars (noneOf "xyz")) // => "abc" "axc" |> parseBy (manyChars (noneOf "xyz")) // => エラー
エスケープ非対応版の文字列パーサーを再掲します。
let jstring = manyChars (noneOf ['"']) // 「"」以外の文字の繰り返しが |> between (pchar '"') (pchar '"') // 「"」に挟まれているのが文字列 .>> ws |>> JString
これをエスケープに対応させるには、エスケープシーケンスとそうでないものを分割して考えます。
まず、エスケープされていない、普通の文字とは何かを考えてみます。 これは簡単で、「エスケープの開始文字()と、文字列の終了文字(")以外の文字」です。
let nonEscapedChar = noneOf ['\\'; '"']
次に、エスケープされた文字を考えてみます(\uxxxx形式は省略します)。 エスケープされた文字は、開始文字()から始まり、エスケープシーケンスの種類を表す文字が続きます。
let escapedChar = pchar '\\' >>. anyOf @"\""/bfnrt"
anyOf 関数は noneOf の逆で、引数で指定された seq<char> のうちの1文字をパースするパーサーを返します。
"a" |> parseBy (anyOf "abc") // => 'a' "c" |> parseBy (anyOf "abc") // => 'c' "z" |> parseBy (anyOf "abc") // => エラー
これで、エスケープされた文字もパース出来るようになりました。
@"\\" |> parseBy escapedChar // => '\\' @"\""" |> parseBy escapedChar // => '"' @"\n" |> parseBy escapedChar // => 'n'
しかし、これだけだと \n は改行文字ではなく n という文字になってしまうため、結果を変換する必要があります。
変換しなければならないのは、 b, f, n, r, t の5つです。
\, ", / は変換せず、そのまま使います。
let convEsc = function | 'b' -> '\b' | 'f' -> '\f' | 'n' -> '\n' | 'r' -> '\r' | 't' -> '\t' | c -> c // '\\', '"', '/' はそのまま使う let escapedChar = pchar '\\' >>. anyOf @"\""/bfnrt" |>> convEsc
これで、エスケープされていない文字のパーサーとエスケープされた文字のパーサーが手に入りました。
文字列は、その中の1文字1文字がどちらかでパース出来るものの並びになります。
<|> という演算子は、この「どちらか」を表すパーサーを作る演算子です。
"a" |> parseBy (pchar 'a' <|> pchar 'b') // => 'a' "b" |> parseBy (pchar 'a' <|> pchar 'b') // => 'b'
それさえわかれば、あとは簡単です。
let jstring = manyChars (nonEscapedChar <|> escapedChar) // どちらかの繰り返し |> between (pchar '"') (pchar '"') .>> ws |>> JString "\"abc\"" |> parseBy jstring // => JString "abc" "\"abc\\ndef\"" |> parseBy jstring // => JString "abc\ndef"
エスケープ非対応版を再掲しておきます。
manyChars に渡すパーサーだけ変えたことが分かります。
let jstring = manyChars (noneOf ['"']) |> between (pchar '"') (pchar '"') .>> ws |>> JString
選択されない選択肢
文字列パーサーの実装で紹介した <|> 演算子ですが、気を付けなければならないことがあります。
JSONには浮動小数点数しかありませんが、F#には整数があるので、整数と浮動小数点数を区別するようにしてみましょう。
type Json = //| JNumber of float | JInteger of int | JFloat of float | JString of string | JArray of Json list let ws = spaces // jnumberの定義を変更 let minusSign = opt (pchar '-') |>> Option.isSome let digit1to9 = anyOf ['1'..'9'] let integer = (many1Chars2 digit1to9 digit <|> pstring "0") |>> int let jinteger = minusSign .>>. integer |>> (fun (hasMinus, x) -> JInteger (if hasMinus then -x else x)) let jfloat = tuple3 minusSign integer (pchar '.' >>. integer) |>> (fun (hasMinus, i, flac) -> let f = float i + float ("0." + string flac) JFloat (if hasMinus then -f else f)) let jnumber = (jinteger <|> jfloat) .>> ws
pfloat よりもかなり複雑になりましたが、ほとんどjson.orgの定義を書き下しているだけです(指数表記は未対応です)。
opt 関数は、引数で指定されたパーサーが成功した場合 Some でくるみ、失敗した場合 None を返すパーサーを作ります。
引数で指定されたパーサーが失敗した場合でも、 opt 自体は成功するので、省略可能な構文要素を表すために使います。
JSONの数値の場合、負の符号は省略可能なので、 opt で実現しています。
digit は 0 から 9 までの文字をパースするパーサーです。
"-2" |> parseBy (opt (pchar '-') .>>. digit) // => (Some '-', '2') "1" |> parseBy (opt (pchar '-') .>>. digit) // => (None, '1')
many1Chars2 関数は、1回以上の繰り返しをパースするパーサーを返します。
manyChars や many1Chars に似ていますが、引数を2つ取り、最初の1回は1つめの引数のパーサーを、以降は2つめの引数のパーサーを使います。
複数桁の数値は、先頭に 0 を許しません(1230はOKだけど、0123はNG)。
それを簡単に実現するために、 many1Chars2 を使っています。
"1230" |> parseBy (many1Chars2 (anyOf ['1'..'9']) digit) // => "1230" "0123" |> parseBy (many1Chars2 (anyOf ['1'..'9']) digit) // => エラー
pstring 関数は、指定された文字列をパースするパーサーを返します。
many1Chars2 digit1to9 digit だけでは "0" がパース出来ないので、 <|> 演算子で pstring "0" を合成することで対応しています。
tuple3 関数は、3つのパーサーを受け取ってそれらの結果を3要素タプルにするパーサーを返します。
.>>. 演算子を2回使ってもいいのですが、 .>>. 演算子を複数回使う場合、2要素タプルがネストしてしまいます。
これを避けるために、 tuple3 が使えます。tuple2 から tuple5 まで用意されています。
"1.2" |> parseBy (digit .>>. pchar '.' .>>. digit) // => (('1', '.'), '2') "1.2" |> parseBy (tuple3 digit (pchar '.') digit) // => ('1', '.', '2')
浮動小数点数は、「符号」「整数部」「小数部」の3つに分割できるため、 tuple3 を使っています。
jnumber まわりの定義を再掲します。
let minusSign = opt (pchar '-') |>> Option.isSome let digit1to9 = anyOf ['1'..'9'] let integer = (many1Chars2 digit1to9 digit <|> pstring "0") |>> int let jinteger = minusSign .>>. integer |>> (fun (hasMinus, x) -> JInteger (if hasMinus then -x else x)) let jfloat = tuple3 minusSign integer (pchar '.' >>. integer) |>> (fun (hasMinus, i, flac) -> let f = float i + float ("0." + string flac) JFloat (if hasMinus then -f else f)) let jnumber = (jinteger <|> jfloat) .>> ws
これで動きそうに見えますが、実はこれでは動きません。
"1" |> parseBy jnumber // => JInteger 1 "2.0" |> parseBy jnumber // => エラー
エラーメッセージを見てみましょう。
parse error: Error in Ln: 1 Col: 2 2.0 ^ Expecting: decimal digit or end of input
2.0 の . の位置で、数値か入力終了を期待していた、と出ています。
入力終了を期待していたということなので、 eof の合成をしない場合にどういう挙動になるのか確認してみましょう。
let parseByJNumber str = match run jnumber str with // eofを合成しない | Success (res, _, _) -> res | Failure (msg, _, _) -> failwithf "parse error: %s" msg parseByJNumber "1" // => JInteger 1 parseByJNumber "2.0" // => JInteger 2
eof を合成している parseBy jnumber ではエラーになりましたが、eof を合成していない parseByJNumber では(JFloat 2.0 ではなく) JInteger 2 が返ってきました。
この結果が意味しているのは、 2.0 をパースする際、 2 までを読んで JInteger としてしまっており、 .0 が入力に残ったままになっているということです。
これは、 jfloat が成功する入力では必ず jinteger が成功してしまうことが原因です。
つまり、この jnumber の定義では jfloat が使われることはありません。
では、項を入れ替えてみてはどうでしょうか。
let jnumber = jfloat <|> jinteger
これであれば、 jfloat に失敗すれば jinteger が試されるため、問題ないように見えます。
しかし、今度は "1" のパースに失敗します。
parse error: Error in Ln: 1 Col: 2 1 ^ Note: The error occurred at the end of the input stream. Expecting: decimal digit or '.'
数値か . を期待していたけど、入力が終了してしまった、と言っています。
これは、 <|> 演算子が左項のパーサーが失敗しても、そのパーサーが消費した入力を戻さないことが原因です。
jnumber はまず jfloat を試しますが、 "1" が入力として与えられた際、整数部の入力までは成功します。
そして、小数点をパースしようとしますが . が見つからないため jfloat が失敗します。
この際に整数部を消費してしまったため、 jinteger が成功することはありません。
jinteger は数値を期待しているため、エラーがマージされ、「数値か . が期待されている」というメッセージになります。
この問題を最も手軽に解決するためには、失敗した際に入力を戻す*7パーサー attempt を合成します。
let jnumber = attempt jfloat <|> jinteger
attempt は入力を巻き戻すため、 attempt を使わずに済むなら使わない方が効率の良いパーサーになります。
<|> 演算子は、効率を重視してデフォルトの挙動が入力を巻き戻さないようになっているので、 attempt をやみくもに使うのはやめましょう。
attempt を使わずに今回の問題を解決する方法もあります。
例えば、 jinteger と jfloat を削除し、 jnumber の定義を次のように変更します。
let jnumber = tuple3 minusSign integer (opt (pchar '.' >>. integer)) |>> (function | (hasMinus, i, None) -> JInteger (if hasMinus then -i else i) | (hasMinus, i, Some flac) -> let f = float i + float ("0." + string flac) JFloat (if hasMinus then -f else f))
この定義は、小数点数以降を opt で省略可能にし、 |>> による変換部分で JInteger にするか JFloat にするかを決めています。
これにより、 attempt を使わずに整数と浮動小数点数を区別できるパーサーが手に入りました。
同じプレフィックス(今回の場合整数部)を持つ選択肢が3つ以上になった場合、 opt では解決できなくなります。
そのような場合でも、今回の手法を応用すれば解決可能です。
type Json = | JInteger of int | JFloat of float | JRational of int * int // 有理数を追加 | JString of string | JArray of Json list // ..略.. let jnum = // choice [p1; p2; ...; pn] は、 p1 <|> p2 <|> ... <|> pn と同じ意味で、高速 choice [ pchar '.' >>. integer |>> (fun frac i -> JFloat (float i + float ("0." + string frac))) pchar '/' >>. integer |>> (fun d n -> JRational (n, d)) preturn JInteger ] // preturnは、常に成功し、引数に指定した結果を返すパーサーを返す関数 let jnumber = tuple3 minusSign integer jnum |>> (fun (hasMinus, i, f) -> f (if hasMinus then -i else i))
再帰文法
さて、ここまでのパーサーでは、 JArray の要素に JInteger か JFloat しか許しません。
型の定義としては、 JString でも JArray 自体でもいいようになっていますので、この対応をしましょう。
現状の jarray の定義を確認しておきましょう。
let jarray = sepBy jnumber (pchar ',' >>. ws) |> between (pchar '[' >>. ws) (pchar ']' >>. ws) |>> JArray
sepBy に jnumber を渡していますね。
ここに自分自身が渡せればネストに対応できそうですが、F#ではそのようなことはできません。
let jarray = // jarrayの定義の中ではjarrayにアクセスできないのでコンパイルエラー sepBy (choice [jnumber; jstring; jarray]) (pchar ',' >>. ws) |> between (pchar '[' >>. ws) (pchar ']' >>. ws) |>> JArray
FParsecでは、このような再帰した文法を表現するために、 createParserForwardedToRef という関数を用意してくれています。
この関数は、パーサーとそのパーサーへの参照(ref 型)のタプルを返します。
そして、パーサーへの参照に定義を再代入により設定することで、再帰した文法が表現できます。
// jarray は、 jarrayRef を見るようになっている let jarray, jarrayRef = createParserForwardedToRef () // jarrayRef は ref 型なので、再代入できる jarrayRef := // 再帰したい場合は、 !jarrayRef ではなく、 jarray を使う sepBy (choice [jnumber; jstring; jarray]) (pchar ',' >>. ws) |> between (pchar '[' >>. ws) (pchar ']' >>. ws) |>> JArray
これで、配列内に数値以外も格納できるようになりました。
JObject に対応することを考え、 json というパーサーを作っておきましょう。
let json, jsonRef = createParserForwardedToRef () let jarray = sepBy json (pchar ',' >>. ws) |> between (pchar '[' >>. ws) (pchar ']' >>. ws) |>> JArray jsonRef := choice [jnumber; jstring; jarray]
これで、 jobject などを作った場合に choice の中に入れるだけで配列の要素としてオブジェクトが使えるようになります。
"[[], 1, \"aaa\"]" |> parseBy json // => JArray [JArray []; JInteger 1; JString "aaa"]
左再帰
JSONの文法はよく考えられているため、何も考えずに実装しても問題ないようにできています。 しかし、それでは勉強になりませんので、JSONを勝手に拡張して問題を起こしてみましょう。
このような入力をパース出来るようにしたいと思います。
[ 10 - 4 + 2, 20 ]
型の定義はこうでしょうか。
type NumExpr = | NEInteger of int // 簡単のためにfloatは省略 | NEAdd of NumExpr * NumExpr | NESub of NumExpr * NumExpr type Json = | JNumExpr of NumExpr | JArray of Json list // 簡単のためstringも省略
先程のJSON(拡張)をパースした結果は、このようになればいいでしょう。
JArray [ JNumExpr (NEAdd (NESub (NEInteger 10, NEInteger 4), NEInteger 2)) JNumExpr (NEInteger 20) ]
これをパースするパーサーを何も考えずに実装すると、次のようになるでしょう。
let ws = spaces let neinteger = pint32 .>> ws |>> NEInteger let numExpr, numExprRef = createParserForwardedToRef () let neadd = (numExpr .>> pchar '+' .>> ws) .>>. neinteger |>> NEAdd let nesub = (numExpr .>> pchar '-' .>> ws) .>>. neinteger |>> NESub numExprRef := choice [attempt neadd; attempt nesub; neinteger] let jnumExpr = numExpr |>> JNumExpr let json, jsonRef = createParserForwardedToRef () let jarray = sepBy json (pchar ',' >>. ws) |> between (pchar '[' >>. ws) (pchar ']' >>. ws) |>> JArray jsonRef := choice [jnumExpr; jarray] let parseBy p str = match run (ws >>. p .>> eof) str with | Success (res, _, _) -> res | Failure (msg, _, _) -> failwithf "parse error: %s" msg
しかし、このパーサーで "[ 10 - 4 + 2, 20 ]" をパースしようとすると StackOverflowException が発生します。
問題は、この辺りにあります。
let neadd = (numExpr .>> pchar '+' .>> ws) .>>. neinteger |>> NEAdd let nesub = (numExpr .>> pchar '-' .>> ws) .>>. neinteger |>> NESub numExprRef := choice [attempt neadd; attempt nesub; neinteger]
まず、 numExpr でパースしようとします。
choice の先頭に neadd があるので、 neadd でパースしようとします。
neadd の先頭に numExpr があるので、 numExpr でパースしようとします。
・・・戻ってきてしまいましたね。
このように、入力をなにも消費せずに再帰してしまうと、パースが先に進まずにスタックオーバーフローしてしまうのです。
このように、文法の先頭(左側)で再帰している文法を左再帰の文法といいます。
この問題を解決するために、ここでは再帰を繰り返しで表現する方法を使います。
// numExpr ::= neinteger (op neinteger)* let numExpr = neinteger .>>. (many (op .>>. neinteger)) // opの定義は後で
many 関数は、引数のパーサーの0回以上の繰り返しをパースするパーサーを返します。
このままでは、 numExpr パーサーの結果の型は NumExpr * (opの結果の型 * NumExpr) list になってしまいます。
これを NumExpr にしないといけません。
複数の NumExpr を一つの NumExpr にする必要があるので、 List.fold を使えばいいでしょう。
let numExpr = neinteger .>>. many (op .>>. neinteger) |>> (fun (i, xs) -> List.fold (fun crnt (op, next) -> // crnt, op, nextを使ってNEAdd, NESubを作る ...) i xs)
op は例えばこのような定義が考えられます。
type Op = Add | Sub let op = (pchar '+' .>> ws >>% Add) <|> (pchar '-' .>> ws >>% Sub)
>>% 演算子は、左項のパーサーが成功した場合に右項の値を返すパーサーを返します。
"a" |> parseBy (pchar 'a' >>% [1; 2; 3]) // => [1; 2; 3]
先程の op 定義の場合、 List.fold に渡す関数はこのようにすればいいでしょう。
let f crnt (op, next) = match op with | Add -> NEAdd (crnt, next) | Sub -> NESub (crnt, next)
これで、 "[ 10 - 4 + 2, 20 ]" がパース出来るようになりました。
"[ 10 - 4 + 2, 20 ]" |> parseBy json // => JArray // [JNumExpr (NEAdd (NESub (NEInteger 10,NEInteger 4),NEInteger 2)); // JNumExpr (NEInteger 20)]
さて、これでもいいのですが、 NEAdd に対応する Add, NESub に対応する Sub を定義する必要があるのが少し面倒です。
そこで、 op の結果の型を関数にして、 crnt と next を渡して NEAdd や NESub を返すようにしてみましょう。
let op = choice [ pchar '+' .>> ws >>% (fun a b -> NEAdd (a, b)) pchar '-' .>> ws >>% (fun a b -> NESub (a, b)) ] let numExpr = neinteger .>>. many (op .>>. neinteger) |>> (fun (i, xs) -> List.fold (fun crnt (f, next) -> f crnt next) i xs)
だいぶすっきりしました。
実は、これを一発でやってくれる chainl1 という関数がFParsecに用意されています。
let op = choice [ pchar '+' .>> ws >>% (fun a b -> NEAdd (a, b)) pchar '-' .>> ws >>% (fun a b -> NESub (a, b)) ] let numExpr = chainl1 neinteger op
便利ですね。
まとめ
最後の方はJSONに関係のない拡張をベースに説明しましたが、ここまでで数値、文字列、配列が実装できました。 残っている機能は次の通りです。
nulltrue/falseJFloatの指数表記対応\uXXXX形式の文字対応- オブジェクト
オブジェクト以外は簡単に対応できるでしょう。 オブジェクトも、配列を参考にすればそれほど難しくないと思うので、ぜひ実装してみてください。
年末年始は、パーサーを書いて過ごしましょう！
*1:お使いの言語がジェネリクスや無名関数をサポートしていないような場合はこの限りではありません。
*2:JSONを使うだけの場合、オブジェクトのキーとして文字列しか使えないことなどが煩わしく感じた方も多いと思います。しかし、パーサーを作る側の視点に立つと、それなりの表現能力を少ない労力で手に入れられるようによく考えられた仕様であるということに気付けるようになります。コメントくらいは欲しいですが・・・
*3:p はパーサーを表すプレフィックスです。FParsecでは、標準関数などと名前がかぶるパーサーには p プレフィックスを付けて区別できるようになっています。
*4:F#では流れる方向を意識した演算子が標準でも用意されており、その文化にFParsecも合わせるような演算子の使い方をしています。
*5:>>. に入っている最適化が between には入っていません。 >>. の前段に2つのパーサがあるため、コードが複雑になる事を嫌ったのかもしれません。
*6:1回以上の繰り返しの場合は many1Chars 関数を使います。 sepBy1 や spaces1 と違い、 many のサフィックスとして1が付く点に注意してください。 many / many1 というパーサーもあり、これは list を返しますが、 manyChars / many1Chars はリストを連結して文字列を返します。
*7:厳密に言うと、引数のパーサーを実行する前に現在の状態(入力のどこまで読んだかという位置情報など)を保持しておき、引数のパーサーが失敗した場合にパーサーの状態を戻します。
