Sprache: Or と XOr はどう違うのか

C# の Parser ライブラリ Sprache は Haskell の Parsec の影響を受け（多分）、モナドが Linq の記法に上手く溶け込んでいて非常に見事なライブラリだと思う。 使ってると色々とコツだったり分からないことだったりが出てきたので記す。まずは Or と XOr の違いについて。

ソースコードについて追っかけて記事にしてもいいと思うが、 結論としては first（左側の Parser）が、入力を一つでも消費（つまり先頭から部分一致）した上でマッチに失敗すると、second の方の Parser には目もくれず、即座にマッチ失敗として評価するのが XOr()。 最初のマッチが失敗したら、この Parser への入力開始位置までバックトラックして second との判定結果を戻り値とするのが Or() 。Parsec でいうと try を使うのが Or 使わないのが XOr と思えばいい様だ。

言葉での説明を見ても何を云ってるか分からないかもしれないが、例を見ればすぐわかると思う。

var or_p = Parser.String("string").Or(Parser.String("sling")).Text();
var xor_p = Parser.Sting("string").XOr(Parser.String("sling")).Text();

こういう Parser があったとして、TryParse(input文字列) すると以下のような Result が返る。文字列は result.Value、bool は result.WasSuccessful の値とする

input文字列	or_p	xor_p
string	"string"	"string"
sling	"sling"	false

そして、最初のマッチが入力と全く一致せず、input 文字列を一切消費しない様な場合には、XOr でも二番目の Parser に判定が委ねられることになる。

var exclude = Parser.String("string").XOr(Parser.String("String")).Text();

この Parser に "String" を入力すると、"string" 側の Parser は入力文字列を消費しないので、そのまま "String" 側 Parser で判定が行われ、"String" がマッチする結果となる。 一般的にはバックトラックがあるとパフォーマンスが落ちるので、バックトラックさせないに越したことはなく、可能な限り XOr を使うのが吉と思われる。

ここから実用する上では役には立たない話。

XOr というのは、一般的な論理演算としての排他的論理和(xor)の結果としては、 文字列の完全マッチを「真」とするならば、上の例の場合 1 xor 0 = 1, 0 xor 1 = 1 という演算になるのでしっくり来るのだが、 両辺が「真」となる様なパーサを作って試してみたところ、これも「真」と判定された。論理演算としての xor はもちろん 1 xor 1 = 0 なので、 「それやと or と一緒やん？」という話になってしまう。 パーサの動作としては、上の様な動きをしてくれる方が嬉しいので全く不満は無いのだが、パーサ界隈ではこういう動きを xor というのが普通なのだろうか？