正規表現とバイトコードとInstOpと部屋と私

メモ書きに近いです。

正規表現のバイトコードを見る

"regexp/syntax" を import して

pattern := `a|b`
exp, _ := syntax.Parse(pattern, syntax.Perl)
prog, _ := syntax.Compile(exp.Simplify())

fmt.Println(prog)

的な感じで見られる。

  0     fail
  1*    rune "ab" -> 2
  2     match

* が今いるところで各命令に従って移動しつつ match に行ければマッチ、 fail ならばマッチせず、という感じです。

type InstOp

どんな命令があるかという一覧は type InstOp 見れば良さそう

https://golang.org/pkg/regexp/syntax/#InstOp

const (
        InstAlt InstOp = iota
        InstAltMatch
        InstCapture
        InstEmptyWidth
        InstMatch
        InstFail
        InstNop
        InstRune
        InstRune1
        InstRuneAny
        InstRuneAnyNotNL
)

おそらくバイトコードの命令( rune とか match ) みたいなやつに Inst 付けただけだと思われるけど、厳密な対応はズレているかもしれない

正規表現とバイトコード

実際の正規表現とバイトコードの対応は以下。

a

  0     fail
  1*    rune1 "a" -> 2
  2     match

ab

  0     fail
  1*    rune1 "a" -> 2
  2     rune1 "b" -> 3
  3     match

a|b

  0     fail
  1*    rune "ab" -> 2
  2     match

a|c

  0     fail
  1*    rune "aacc" -> 2
  2     match

a*

  0     fail
  1     rune1 "a" -> 2
  2*    alt -> 1, 3
  3     match

(a)

  0     fail
  1*    cap 2 -> 2
  2     rune1 "a" -> 3
  3     cap 3 -> 4
  4     match

a?

  0     fail
  1     rune1 "a" -> 3
  2*    alt -> 1, 3
  3     match

a?

  0     fail
  1     rune1 "a" -> 3
  2*    alt -> 1, 3
  3     match

a+

  0     fail
  1*    rune1 "a" -> 2
  2     alt -> 1, 3
  3     match

^

  0     fail
  1*    empty 4 -> 2
  2     match

$

  0     fail
  1*    empty 8 -> 2
  2     match

[a-c]

  0     fail
  1*    rune "ac" -> 2
  2     match

a{1,3}

  0     fail
  1*    rune1 "a" -> 5
  2     rune1 "a" -> 4
  3     rune1 "a" -> 6
  4     alt -> 3, 6
  5     alt -> 2, 6
  6     match

a{3}

  0     fail
  1*    rune1 "a" -> 2
  2     rune1 "a" -> 3
  3     rune1 "a" -> 4
  4     match

a{3,}

  0     fail
  1*    rune1 "a" -> 2
  2     rune1 "a" -> 3
  3     rune1 "a" -> 4
  4     alt -> 3, 5
  5     match

.

  0     fail
  1*    anynotnl -> 2
  2     match

[^a]

  0     fail
  1*    rune "\x00`b\U0010ffff" -> 2
  2     match

\d

  0     fail
  1*    rune "09" -> 2
  2     match

\D

  0     fail
  1*    rune "\x00/:\U0010ffff" -> 2
  2     match

まぁこの辺を抑えておけば後は組み合わせだと思うので良さそう。

気になること

• a|c が rune "aacc" になっている理由
• [^a] とか \D のそれ以外系
• Perl フラグ以外
• 上の例に出てこない InstOp

ZWJ Sequence

👨‍👩‍👧‍👧

  0     fail
  1*    rune1 "\U0001f468" -> 2
  2     rune1 "\u200d" -> 3
  3     rune1 "\U0001f469" -> 4
  4     rune1 "\u200d" -> 5
  5     rune1 "\U0001f467" -> 6
  6     rune1 "\u200d" -> 7
  7     rune1 "\U0001f467" -> 8
  8     match

なるほどなぁ