このシリーズでは、アプリカティブパーサーとパーサーコンビネータの仕組みを解説しています。
1. パーサーにラベルを付ける
以前の投稿のいくつかの失敗したコード例では、混乱するようなエラーが出ました。
let parseDigit = anyOf ['0'..'9']
run parseDigit "|ABC" // Failure "Expecting '9'. Got '|'"
parseDigitは数字の文字の選択として定義されているので、最後の選択（'9'）が失敗したときにそのエラーメッセージを受け取ります。
しかし、このメッセージはかなり混乱を招きます。実際に欲しいのは、「数字」に言及するエラーです。たとえば Failure "Expecting digit. Got '|'"のようなものです。
つまり、パーサーに「数字」のようなラベルを付ける方法と、失敗が発生したときにそのラベルを表示する方法が必要です。
以前の投稿でのParser型の定義を思い出してください。
type Parser<'a> = Parser of (string -> Result<'a * string>)
ラベルを追加するには、レコード構造に変更する必要があります。
type ParserLabel = string
/// パーサー構造はパース関数とラベルを持つ
type Parser<'a> = {
parseFn : (string -> Result<'a * string>)
label: ParserLabel
}
レコードには2つのフィールドがあります。パース関数（parseFn）とラベル（label）です。
一つの問題は、ラベルがパーサー自体にあるものの、Resultにはないことです。つまり、クライアントはエラーと一緒にラベルを表示する方法が分かりません。
そこで、エラーメッセージに加えてResultのFailureケースにもラベルを追加しましょう。
// エイリアス
type ParserLabel = string
type ParserError = string
type Result<'a> =
| Success of 'a
| Failure of ParserLabel * ParserError
ついでに、パース結果を表示するヘルパー関数も定義しましょう。
let printResult result =
match result with
| Success (value,input) ->
printfn "%A" value
| Failure (label,error) ->
printfn "Error parsing %s\n%s" label error
コードの更新
ParserとResultの定義を変更したので、bindPのような基本的な関数も変更する必要があります。
/// "bindP"はパーサー生成関数fとパーサーpを取り
/// pの出力をfに渡して新しいパーサーを作成する
let bindP f p =
let label = "unknown" // <====== "label"は新しい
let innerFn input =
...
match result1 with
| Failure (label,err) -> // <====== "label"は新しい
...
| Success (value1,remainingInput) ->
...
{parseFn=innerFn; label=label} // <====== "parseFn"と"label"は新しい
returnP、orElse、manyにも同様の変更を加える必要があります。完全なコードは、以下にリンクされたgistをご覧ください。
ラベルの更新
コンビネータを使って新しい複合パーサーを作成するとき、新しいラベルを割り当てたい場合があります。
これを行うには、元のparseFnを新しいラベルを返す別の関数に置き換えます。
コードは以下の通りです。
/// パーサーのラベルを更新する
let setLabel parser newLabel =
// 内部関数を変更して新しいラベルを使用する
let newInnerFn input =
let result = parser.parseFn input
match result with
| Success s ->
// 成功の場合、何もしない
Success s
| Failure (oldLabel,err) ->
// 失敗の場合、新しいラベルを返す
Failure (newLabel,err) // <====== ここで新しいラベルを使用
// パーサーを返す
{parseFn=newInnerFn; label=newLabel} // <====== ここで新しいラベルを使用
そして、これの中置バージョンを<?>として作成しましょう。
/// setLabelの中置バージョン
let ( <?> ) = setLabel
新しい機能をテストしてみましょう！
let parseDigit_WithLabel =
anyOf ['0'..'9']
<?> "digit"
run parseDigit_WithLabel "|ABC"
|> printResult
出力は以下のようになります。
Error parsing digit
Unexpected '|'
エラーメッセージがExpecting '9'ではなくError parsing digitになりました。かなり良くなりました！
デフォルトラベルの設定
andThenやorElseなどの特定のコンビネータのデフォルトラベルを、入力に基づいて設定することもできます。
/// 2つのパーサーを"A andThen B"として組み合わせる
let andThen p1 p2 =
let label = sprintf "%s andThen %s" (getLabel p1) (getLabel p2)
p1 >>= (fun p1Result ->
p2 >>= (fun p2Result ->
returnP (p1Result,p2Result) ))
<?> label // <====== カスタムラベルを提供
// 2つのパーサーを"A orElse B"として組み合わせる
let orElse parser1 parser2 =
// 新しいラベルを作る
let label = // <====== カスタムラベルを提供
sprintf "%s orElse %s" (getLabel parser1) (getLabel parser2)
let innerFn input =
... など ...
/// 文字のリストのいずれかを選択
let anyOf listOfChars =
let label = sprintf "any of %A" listOfChars
listOfChars
|> List.map pchar
|> choice
<?> label // <====== カスタムラベルを提供
2. "pchar"を"satisfy"に置き換える
これまでの実装で気になっていたのは、他のすべての関数の基礎となる基本的なプリミティブpcharです。
入力モデルと密接に結びついているのが問題です。バイナリ形式からバイトをパースしたり、他の種類の入力をパースしたりする場合はどうすればいいでしょうか。
pchar以外のコンビネータは疎結合なので、pcharも疎結合にできれば、あらゆる種類のトークンストリームをパースできるようになります。
それが理想的です。
ここで、私の好きな関数型プログラミングのスローガン「すべてをパラメータ化せよ！」を思い出してください。pcharの場合、charToMatchパラメータを削除し、関数（述語）に置き換えます。
新しい関数をsatisfyと呼びましょう。
/// 述語を満たす入力トークンにマッチする
let satisfy predicate label =
let innerFn input =
if String.IsNullOrEmpty(input) then
Failure (label,"入力がありません")
else
let first = input.[0]
if predicate first then // <====== ここで述語を使用
let remainingInput = input.[1..]
Success (first,remainingInput)
else
let err = sprintf "予期しない文字 '%c'" first
Failure (label,err)
// パーサーを返す
{parseFn=innerFn;label=label}
パラメータ以外でpcharの実装から変更されたのは、この1行だけです。
let satisfy predicate label =
...
if predicate first then
...
satisfyを使って、pcharを書き直せます。
/// 文字をパースする
let pchar charToMatch =
let predicate ch = (ch = charToMatch)
let label = sprintf "%c" charToMatch
satisfy predicate label
charToMatchをラベルとして設定している点に注目してください。以前はこのような改良は難しかったでしょう。
「ラベル」の概念がなかったため、pcharは有用なエラーメッセージを返せなかったからです。
satisfy関数を使うと、他のパーサーもより効率的に書けます。たとえば、数字のパースは元々このようでした。
/// 数字をパースする
let digitChar =
anyOf ['0'..'9']
しかし、述語を直接使うことで、より効率的に書き直せます。
/// 数字をパースする
let digitChar =
let predicate = Char.IsDigit
let label = "数字"
satisfy predicate label
同様に、より効率的な空白文字パーサーも作れます。
/// 空白文字をパースする
let whitespaceChar =
let predicate = Char.IsWhiteSpace
let label = "空白"
satisfy predicate label
3. エラーメッセージに位置とコンテキストを追加する
エラーメッセージをさらに改善するには、エラーが発生した行と列を表示するとよいでしょう。
単純な1行の入力なら、エラーの位置を追跡するのは簡単です。しかし、100行のJSONファイルをパースする場合、この情報は非常に役立ちます。
行と列を追跡するには、単純なstring入力をより複雑なものに置き換える必要があります。
まずはそこから始めましょう。
位置を追跡する入力の定義
まず、行と列を保存するPosition型と、列を1つ増やすヘルパー関数、行を1つ増やすヘルパー関数が必要です。
type Position = {
line : int
column : int
}
/// 初期位置を定義する
let initialPos = {line=0; column=0}
/// 列番号を増やす
let incrCol pos =
{pos with column=pos.column + 1}
/// 行番号を増やし、列を0にする
let incrLine pos =
{line=pos.line + 1; column=0}
次に、入力文字列と位置を1つの「入力状態」型に結合します。 行指向なので、入力文字列を1つの巨大な文字列ではなく行の配列として保存すると便利です。
/// 現在の入力状態を定義する
type InputState = {
lines : string[]
position : Position
}
また、文字列を初期のInputStateに変換する方法も必要です。
/// 文字列から新しいInputStateを作成する
let fromStr str =
if String.IsNullOrEmpty(str) then
{lines=[||]; position=initialPos}
else
let separators = [| "\r\n"; "\n" |]
let lines = str.Split(separators, StringSplitOptions.None)
{lines=lines; position=initialPos}
最後に、そして最も重要なのは、入力から次の文字を読み取る方法です。これをnextCharと呼びましょう。
nextCharの入力はInputStateですが、出力はどうすべきでしょうか。
- 入力が終わりの場合、次の文字がないことを示すために
Noneを返します。 - 文字が利用可能な場合は
Someを返します。 - さらに、列（または行）が増加しているため、入力状態も変更されています。
つまり、nextCharの入力はInputStateで、出力はchar option * InputStateのペアになります。
次の文字を返すロジックは以下のようになります。
- 入力の最後の文字にいる場合、EOF（
None）を返し、状態は変更しません。 - 現在の列が行の終わりでない場合、その位置の文字を返し、列位置を増やして状態を変更します。
- 現在の列が行の終わりの場合、改行文字を返し、行位置を増やして状態を変更します。
以下がnextCharの実装です。
// 現在の行を返す
let currentLine inputState =
let linePos = inputState.position.line
if linePos < inputState.lines.Length then
inputState.lines.[linePos]
else
"ファイル終端"
/// 入力から次の文字を取得します（存在する場合）
/// 存在しない場合はNoneを返します。更新された入力状態も返します
/// 型シグネチャ: InputState -> InputState * char option
let nextChar input =
let linePos = input.position.line
let colPos = input.position.column
// 3つのケース
// 1) 行数が最大行数以上の場合 ->
// ファイル終端を返す
// 2) 列位置が行の長さより小さい場合 ->
// その位置の文字を返し、列位置を増やす
// 3) 列位置が行の長さと等しい場合 ->
// 改行を返し、行位置を増やす
if linePos >= input.lines.Length then
input, None
else
let currentLine = currentLine input
if colPos < currentLine.Length then
let char = currentLine.[colPos]
let newPos = incrCol input.position
let newState = {input with position=newPos}
newState, Some char
else
// 行末なので、改行を返して次の行に移動
let char = '\n'
let newPos = incrLine input.position
let newState = {input with position=newPos}
newState, Some char
以前のstring実装とは異なり、元の行の配列は変更やコピーをしません。位置だけが変わります。これにより、位置が変わるたびに新しい状態を作成しても効率的です。
テキストはどこでも共有されているからです。
実装が機能するか簡単にテストしてみましょう。
readAllCharsというヘルパー関数を作り、異なる入力に対する結果を確認します。
let rec readAllChars input =
[
let remainingInput,charOpt = nextChar input
match charOpt with
| None ->
// 入力終了
()
| Some ch ->
// 最初の文字を返す
yield ch
// 残りの文字を返す
yield! readAllChars remainingInput
]
いくつかの入力例でテストします。
fromStr "" |> readAllChars // []
fromStr "a" |> readAllChars // ['a'; '\n']
fromStr "ab" |> readAllChars // ['a'; 'b'; '\n']
fromStr "a\nb" |> readAllChars // ['a'; '\n'; 'b'; '\n']
この実装は、入力の最後に改行がなくても改行を追加します。これは不具合ではなく、むしろ有用な特徴だと考えています。
パーサーを新しい入力形式に対応させる
ここでParser型を再び変更する必要があります。
まず、Failureケースで位置情報を返すようにします。エラーメッセージに表示するためです。
InputStateをそのまま使うこともできますが、この用途に特化した新しい型ParserPositionを定義するのが良いでしょう。
/// パーサーの位置情報をエラーメッセージ用に保存する
type ParserPosition = {
currentLine : string
line : int
column : int
}
InputStateをParserPositionに変換する方法も必要です。
let parserPositionFromInputState (inputState:Input) = {
currentLine = TextInput.currentLine inputState
line = inputState.position.line
column = inputState.position.column
}
最後に、ParserPositionを含めるようにResult型を更新します。
// Result型
type Result<'a> =
| Success of 'a
| Failure of ParserLabel * ParserError * ParserPosition
さらに、Parser型をstringからInputStateに変更します。
type Input = TextInput.InputState // 型エイリアス
/// Parser構造はパース関数とラベルを持つ
type Parser<'a> = {
parseFn : (Input -> Result<'a * Input>)
label: ParserLabel
}
この追加情報を使って、printResult関数を拡張し、現在の行のテキストとエラーの位置を示す矢印を表示できます。
let printResult result =
match result with
| Success (value,input) ->
printfn "%A" value
| Failure (label,error,parserPos) ->
let errorLine = parserPos.currentLine
let colPos = parserPos.column
let linePos = parserPos.line
let failureCaret = sprintf "%*s^%s" colPos "" error
printfn "%d行目 %d列目 %sのパースでエラー\n%s\n%s" linePos colPos label errorLine failureCaret
ダミーのエラー値でprintResultをテストしてみましょう。
let exampleError =
Failure ("識別子", "予期しない |",
{currentLine = "123 ab|cd"; line=1; column=6})
printResult exampleError
出力は以下のようになります。
1行目 6列目 識別子のパースでエラー
123 ab|cd
^予期しない |
以前よりもずっと分かりやすくなりました！
run関数の修正
run関数は今後、文字列ではなくInputStateを受け取る必要があります。しかし、文字列入力に対しても実行できる便利さは残したいところです。
そこで、2つのrun関数を作成しましょう。1つはInputStateを受け取り、もう1つはstringを受け取ります。
/// InputStateに対してパーサーを実行
let runOnInput parser input =
// 内部関数を入力で呼び出す
parser.parseFn input
/// 文字列に対してパーサーを実行
let run parser inputStr =
// 内部関数を入力で呼び出す
runOnInput parser (TextInput.fromStr inputStr)
コンビネータの修正
Failureケースに、これまでの2つではなく3つの項目が含まれるようになりました。
これにより一部のコードが動作しなくなりますが、修正は簡単です。今後同じ問題が起きないよう、専用のParserError型を作りたい気もします。ただし今回は、単にエラーを修正するにとどめておきます。
新しいsatisfyの実装です。
/// 述語を満たす入力トークンにマッチする
let satisfy predicate label =
let innerFn input =
let remainingInput,charOpt = TextInput.nextChar input
match charOpt with
| None ->
let err = "入力が終了しました"
let pos = parserPositionFromInputState input
//Failure (label,err) // <====== 旧バージョン
Failure (label,err,pos) // <====== 新バージョン
| Some first ->
if predicate first then
Success (first,remainingInput)
else
let err = sprintf "予期しない文字 '%c'" first
let pos = parserPositionFromInputState input
//Failure (label,err) // <====== 旧バージョン
Failure (label,err,pos) // <====== 新バージョン
// パーサーを返す
{parseFn=innerFn;label=label}
入力状態からパーサーの位置情報を作り、失敗時のコードはFailure (label,err,pos)となりました。
bindPも同様に修正します。
/// "bindP"はパーサー生成関数fとパーサーpを受け取り
/// pの出力をfに渡して新しいパーサーを作成する
let bindP f p =
let label = "unknown"
let innerFn input =
let result1 = runOnInput p input
match result1 with
| Failure (label,err,pos) -> // <====== 新しく位置情報（pos）を追加
// パーサー1からのエラーを返す
Failure (label,err,pos)
| Success (value1,remainingInput) ->
// fを適用して新しいパーサーを取得
let p2 = f value1
// 残りの入力で新しいパーサーを実行
runOnInput p2 remainingInput
{parseFn=innerFn; label=label}
他の関数も同様に修正します。
位置情報付きエラーのテスト
実際のパーサーでテストしてみましょう。
let parseAB =
pchar 'A' .>>. pchar 'B'
<?> "AB"
run parseAB "A|C"
|> printResult
出力は次のとおりです。
1行目 2列目 ABのパースでエラー
A|C
^予期しない文字 '|'
これで大きく改善しました。
4. ライブラリに標準パーサーを追加
前回の投稿では、文字列や整数のパーサーを作成しました。今回はそれらをコアライブラリに追加し、利用者がゼロから実装する必要がないようにします。
これらのパーサーはFParsecライブラリを参考にしています。
まず、文字列関連のパーサーから始めましょう。コードはこれまでの説明で理解できるはずなので、コメントは省略します。
/// 文字をパースする
let pchar charToMatch =
// ラベルは文字そのもの
let label = sprintf "%c" charToMatch
let predicate ch = (ch = charToMatch)
satisfy predicate label
/// 文字リストのいずれかを選択する
let anyOf listOfChars =
let label = sprintf "anyOf %A" listOfChars
listOfChars
|> List.map pchar // パーサーに変換
|> choice
<?> label
/// 文字リストを文字列に変換する
let charListToStr charList =
String(List.toArray charList)
/// 文字パーサーcpを使用して0個以上の文字の並びをパースする
/// パースした文字を文字列として返す
let manyChars cp =
many cp
|>> charListToStr
/// 文字パーサーcpを使用して1個以上の文字の並びをパースする
/// パースした文字を文字列として返す
let manyChars1 cp =
many1 cp
|>> charListToStr
/// 特定の文字列をパースする
let pstring str =
// ラベルは文字列そのもの
let label = str
str
// 文字のリストに変換
|> List.ofSeq
// 各文字をpcharにマップ
|> List.map pchar
// Parser<char list>に変換
|> sequence
// Parser<char list>をParser<string>に変換
|> mapP charListToStr
<?> label
pstringのテスト例です。
run (pstring "AB") "ABC"
|> printResult
// Success
// "AB"
run (pstring "AB") "A|C"
|> printResult
// 1行目 2列目 ABのパースでエラー
// A|C
// ^予期しない文字 '|'
空白文字のパーサー
パースにおいて、空白文字は重要です。最終的には無視することが多いですが、処理は必要です。
/// 空白文字をパースする
let whitespaceChar =
let predicate = Char.IsWhiteSpace
let label = "空白"
satisfy predicate label
/// 0個以上の空白文字をパースする
let spaces = many whitespaceChar
/// 1個以上の空白文字をパースする
let spaces1 = many1 whitespaceChar
空白文字のテスト例です。
run spaces " ABC"
|> printResult
// [' ']
run spaces "A"
|> printResult
// []
run spaces1 " ABC"
|> printResult
// [' ']
run spaces1 "A"
|> printResult
// 1行目 1列目 many1 空白のパースでエラー
// A
// ^予期しない文字 'A'
数値のパーサー
最後に、整数と浮動小数点数のパーサーが必要です。
/// 数字をパースする
let digitChar =
let predicate = Char.IsDigit
let label = "数字"
satisfy predicate label
// 整数をパースする
let pint =
let label = "整数"
// ヘルパー関数
let resultToInt (sign,digits) =
let i = digits |> int // オーバーフローは今のところ無視
match sign with
| Some ch -> -i // 整数を負にする
| None -> i
// 1つ以上の数字のパーサーを定義
let digits = manyChars1 digitChar
// "整数"は、オプションの符号 + 1つ以上の数字
opt (pchar '-') .>>. digits
|> mapP resultToInt
<?> label
// 浮動小数点数をパースする
let pfloat =
let label = "浮動小数点数"
// ヘルパー関数
let resultToFloat (((sign,digits1),point),digits2) =
let fl = sprintf "%s.%s" digits1 digits2 |> float
match sign with
| Some ch -> -fl // 浮動小数点数を負にする
| None -> fl
// 1つ以上の数字のパーサーを定義
let digits = manyChars1 digitChar
// 浮動小数点数は、符号、数字、小数点、数字（指数は今のところ無視）
opt (pchar '-') .>>. digits .>>. pchar '.' .>>. digits
|> mapP resultToFloat
<?> label
テスト例です。
run pint "-123Z"
|> printResult
// -123
run pint "-Z123"
|> printResult
// 1行目 2列目 整数のパースでエラー
// -Z123
// ^予期しない文字 'Z'
run pfloat "-123.45Z"
|> printResult
// -123.45
run pfloat "-123Z45"
|> printResult
// 1行目 5列目 浮動小数点数のパースでエラー
// -123Z45
// ^予期しない文字 'Z'
5. バックトラッキング
最後に議論すべき重要なトピックは「バックトラッキング」です。
たとえば、文字列A-1にマッチするパーサーと、文字列A-2にマッチするパーサーがあるとします。
入力がA-2の場合、最初のパーサーは3文字目で失敗し、2番目のパーサーが試行されます。
このとき、2番目のパーサーは3文字目からではなく、元の文字列の先頭から開始する必要があります。 つまり、入力ストリームの現在位置を元に戻し、最初の位置に戻る必要があるのです。
可変の入力ストリームを使用していれば、これは難しい問題かもしれません。しかし幸いなことに、私たちは不変データを使用しています。そのため、位置を「元に戻す」というのは、単に元の入力値を使用するだけです。
そして、これはまさにorElse（<|>）のようなコンビネータが行っていることです。
言い換えると、不変の入力状態を使用することで、バックトラッキングが「無料で」得られるのです。素晴らしいですね！
しかし、バックトラックしたくない場合もあります。たとえば、次のようなパーサーがあるとします。
forExpression= "for"キーワード、識別子、"in"キーワードなどifExpression= "if"キーワード、識別子、"then"キーワードなど
そして、これらを組み合わせた式パーサーを作成します。
expression=forExpression <|> ifExpression
ここで、入力ストリームがfor &&& in somethingだった場合、forExpressionパーサーは&&&のところでエラーになります。有効な識別子を期待しているからです。
この時点で、ifExpressionを試すためにバックトラックはしたくありません。むしろ、「'for'の後に識別子が必要です」といったエラーを表示したいのです。
ルールは次のようになります。入力が正常に消費された場合（この例では「for」キーワードが正常にマッチした場合）は、バックトラックしません。
このルールは、我々の単純なライブラリでは実装しませんが、FParsecのような本格的なライブラリではこれを実装しています。 また、必要に応じてこれを回避する方法も用意されています。
最終的なパーサーライブラリのリスト
パーシングライブラリは現在500行ほどのコードになっているため、ここでは全てを示しません。このgistで確認できます。
まとめ
この投稿では、より良いエラー処理といくつかの新しいパーサーを追加しました。
これで、JSONパーサーを組み立てるために必要なものが全て揃いました。 それが次の投稿のテーマです。
この投稿のソースコードはこのgistで入手できます。