utf8.md

autoscale: true slidenumber: true

UTF-8をデコードするオートマトン

---

UTF-8の概要

https://ja.wikipedia.org/wiki/UTF-8

---

オートマトン

https://ja.wikipedia.org/wiki/有限オートマトン

状態と遷移の定義表で書ける

---

UTF-8のデコード

バイト列を読み取る

→ Unicode Codeopint １つ → 不正なシーケンス

---

デコーダオートマトン

初期状態S0

1バイト読む → 次の状態に進む

---

1バイト

状態 x 文字 → 次の状態

char table[][256] = {
	{ ... }, // S0
	{ ... }, // S1
	{ ... }, // S2
	// ...
}

---

実例

正規表現エンジン Onigmo

https://github.com/k-takata/Onigmo/blob/669ac9997619954c298da971fcfacccf36909d05/enc/utf_8.c#L77-L222

---

歴史

---

(いつ？) Oniguruma が生まれる (2004？) RubyがOniguruma(Onigmo?)を取り込む https://github.com/ruby/ruby/commit/5770336f8be4ac6dbdff43587fda2b508d3786de (2007？) Ruby版Onigurumaにオートマトンが実装 https://github.com/ruby/ruby/commit/69406aad505414de34dc8b560ac1eadf147b0dbc#diff-3d0809782296d6cdcf6889ddbb19631d (2011？) Onigmoが生まれる https://github.com/k-takata/Onigmo/commit/95e6c10e535f655b87b645ebc3e029a0ec9e242b (2011？) OnigmoがRuby版からオートマトンを取り込む https://github.com/k-takata/Onigmo/commit/ce13b17b955e0b6dfc6606b1fdbd4755590b360b#diff-67dbe0b8e37d5cc1946b981346e1c0a6

---

UTF-8