バックトラッキングアルゴリズム

パースに失敗した時に、状態を巻き戻して、パースにをやり直す

import Text.Parsec

backtrack = try (sequence [char 'a', char 'b']) <|> sequence [char 'a', char 'b']
ll = sequence [char 'a', char 'b' <|> char 'c']

main = do
    parseTest backtrack "ab"
    parseTest backtrack "ac"
    parseTest ll        "ab"
    parseTest ll        "ac"

はオルタナティブで左辺を実行してみて失敗したら、右辺は処理されずにエラーになる

を組み合わせることでbacktrackできる

の左辺を実行してみて失敗したら、実行直前に戻って次に右辺を実行する

-- 「'a'の次に'b'が来る」を試してみて、ミスったら「'a'の次に'c'が来る」を試す
backtrack = try (sequence [char 'a', char 'b']) <|> sequence [char 'a', char 'b']
main = do
    parseTest backtrack "ab"	-- 関数定義内の左辺が成功。左辺だけ処理
    parseTest backtrack "ac"	-- 左辺をtryして失敗したので、右辺を実行

今回のケースでは、"ab"もしくは"ac"をパースしたいのだが、成功するかどうかわからないので、一度前者を試して、失敗したら"a"をパースする前の状態に戻る