正規表現マッチの原則3 (1/3) 35 分岐を選択するごとに、選択しない方(ステート)を覚えておく 覚えておく情報 文字列上の目印位置 正規表現(図)上の目印位置 キャプチャ位置 照合に失敗したら、覚えておいたステートから再開 → バックトラック バックトラックはLIFO型 バックトラックのときは、最近覚えたものを使う → LIFO (last in first out)