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

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

例えばHaskellの場合 ref

code:hs

import Text.Parsec

backtrack = try (sequence char 'a', char 'b') <|> sequence char 'a', char 'b'

main = do

parseTest backtrack "ab"

parseTest backtrack "ac"

parseTest ll "ab"

parseTest ll "ac"

backtrack

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

tryと<|>を組み合わせることでbacktrackできる

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

上の関数を見てみよう

code:hs

-- 「'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"をパースする前の状態に戻る