Ruby を余すところなく愛する�人のための�「オートマトンと形式言語理論」入門
hsjoihs (はすじょい)�[佐藤 弘崇]
Ruby を
Ruby を
余すところなく
愛する
Ruby を
余すところなく
愛する
このような Ruby の仕様に驚く他言語ユーザーは多い
このような Ruby の仕様に驚く他言語ユーザーは多い
このような Ruby の仕様に驚く他言語ユーザーは多い
かくいう私も�小学生の頃に�[1,3,4,5].size - 1 が通って�[1,3,4,5].size -1 が通らないことを知り�かなり驚いたのを未だに覚えている
ということで、
ということで、
なぜ Ruby は�こんな驚きをもたらす�仕様を採用したのか
という問いを……
ということで、
なぜ Ruby は�こんな驚きをもたらす�仕様を採用したのか
という問いを……
ということで、
なぜ Ruby は�こんな驚きをもたらす�仕様を採用したのか
果たして立てるべきなのか？
という問いを……
ということで、
なぜ Ruby は�こんな驚きをもたらす�仕様を採用したのか
果たして立てるべきなのか？
ホンマか？
むしろ、立てるべき問いは逆向きではないか？
むしろ、立てるべき問いは逆向きではないか？
むしろ、立てるべき問いは逆向きではないか？
「なぜ多くの他言語ユーザーは、↓ を見て驚きを抱いてしまうのか」�のほうこそ深掘りしがいがあるのではないか？
多くの他言語ユーザーが（無意識に）有している固定観念
多くの他言語ユーザーが（無意識に）有している固定観念
[ | 1 | , | 3 | , | 4 | , | 5 | ] | . | s | i | z | e | | - | 1 |
多くの他言語ユーザーが（無意識に）有している固定観念
[ | 1 | , | 3 | , | 4 | , | 5 | ] | . | s | i | z | e | | - | 1 |
括弧 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 括弧 | 雑多 | 英数 | 英数 | 英数 | 英数 | | 雑多 | 英数 |
多くの他言語ユーザーが（無意識に）有している固定観念
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
[ | 1 | , | 3 | , | 4 | , | 5 | ] | . | s | i | z | e | | - | 1 |
括弧 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 括弧 | 雑多 | 英数 | 英数 | 英数 | 英数 | | 雑多 | 英数 |
多くの他言語ユーザーが（無意識に）有している固定観念
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
cf. 日本語は『他字種から平仮名へ移る』以外の字種境界で似たことをやっている��
[ | 1 | , | 3 | , | 4 | , | 5 | ] | . | s | i | z | e | | - | 1 |
括弧 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 括弧 | 雑多 | 英数 | 英数 | 英数 | 英数 | | 雑多 | 英数 |
多くの他言語ユーザーが（無意識に）有している固定観念
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
cf. 日本語は『他字種から平仮名へ移る』以外の字種境界で似たことをやっている�多くの他言語ユーザーが（無意識に）有している固定観念�
[ | 1 | , | 3 | , | 4 | , | 5 | ] | . | s | i | z | e | | - | 1 |
括弧 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 括弧 | 雑多 | 英数 | 英数 | 英数 | 英数 | | 雑多 | 英数 |
多くの他言語ユーザーが（無意識に）有している固定観念
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
cf. 日本語は『他字種から平仮名へ移る』以外の字種境界で似たことをやっている�多くの/他言語/ユーザーが/（/無意識に/）/有している/固定観念�
[ | 1 | , | 3 | , | 4 | , | 5 | ] | . | s | i | z | e | | - | 1 |
括弧 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 括弧 | 雑多 | 英数 | 英数 | 英数 | 英数 | | 雑多 | 英数 |
多くの他言語ユーザーが（無意識に）有している固定観念
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
cf. 日本語は『他字種から平仮名へ移る』以外の字種境界で似たことをやっている�多くの/他言語/ユーザーが/（/無意識に/）/有している/固定観念�逆に、それに反するような交ぜ書き（「まん延」「ひっ迫」など）は嫌われがち
[ | 1 | , | 3 | , | 4 | , | 5 | ] | . | s | i | z | e | | - | 1 |
括弧 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 括弧 | 雑多 | 英数 | 英数 | 英数 | 英数 | | 雑多 | 英数 |
多くの他言語ユーザーが（無意識に）有している固定観念
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
cf. 日本語は『他字種から平仮名へ移る』以外の字種境界で似たことをやっている�多くの/他言語/ユーザーが/（/無意識に/）/有している/固定観念�逆に、それに反するような交ぜ書き（「まん延」「ひっ迫」など）は嫌われがち
[ | 1 | , | 3 | , | 4 | , | 5 | ] | . | s | i | z | e | | - | 1 |
括弧 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 括弧 | 雑多 | 英数 | 英数 | 英数 | 英数 | | 雑多 | 英数 |
多くの他言語ユーザーが（無意識に）有している固定観念
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
cf. 日本語は『他字種から平仮名へ移る』以外の字種境界で似たことをやっている�多くの/他言語/ユーザーが/（/無意識に/）/有している/固定観念�逆に、それに反するような交ぜ書き（「まん延」「ひっ迫」など）は嫌われがち
[ | 1 | , | 3 | , | 4 | , | 5 | ] | . | s | i | z | e | | - | 1 |
括弧 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 括弧 | 雑多 | 英数 | 英数 | 英数 | 英数 | | 雑多 | 英数 |
多くの他言語ユーザーが（無意識に）有している固定観念
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
cf. 日本語は『他字種から平仮名へ移る』以外の字種境界で似たことをやっている�多くの/他言語/ユーザーが/（/無意識に/）/有している/固定観念�逆に、それに反するような交ぜ書き（「まん延」「ひっ迫」など）は嫌われがち
[ | 1 | , | 3 | , | 4 | , | 5 | ] | . | s | i | z | e | | - | 1 |
括弧 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 雑多 | 英数 | 括弧 | 雑多 | 英数 | 英数 | 英数 | 英数 | | 雑多 | 英数 |
Ruby は単に�この流儀を採用しなかった�というだけの話
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
→ のような �simple なルールに従って�プログラミング言語を作れば、�たとえばフォーマッタなどが�作りやすくはなる��
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
→ のような �simple なルールに従って�プログラミング言語を作れば、�たとえばフォーマッタなどが�作りやすくはなる��ルールが simple だと、�そのルールをもとに reason する�（根拠を持って理詰めで推論・判断する）�ことがやりやすいから
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
→ のような �simple なルールに従って�プログラミング言語を作れば、�たとえばフォーマッタなどが�作りやすくはなる��ルールが simple だと、�そのルールをもとに reason する�（根拠を持って理詰めで推論・判断する）�ことがやりやすいから
ただ、この simple なルールを採用しないというのも、�別に wrong と決めつけるべきでは全くない
simple vs. complex は必ずしも good vs. bad ではない
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
→ のような �simple なルールに従って�プログラミング言語を作れば、�たとえばフォーマッタなどが�作りやすくはなる��ルールが simple だと、�そのルールをもとに reason する�（根拠を持って理詰めで推論・判断する）�ことがやりやすいから
ただ、この simple なルールを採用しないというのも、�別に wrong と決めつけるべきでは全くない
simple vs. complex は必ずしも good vs. bad ではない
right vs. wrong
「字種が切り替わる境界のところに� 空白を足しても� 意味が変化することはない」
→ のような �simple なルールに従って�プログラミング言語を作れば、�たとえばフォーマッタなどが�作りやすくはなる��ルールが simple だと、�そのルールをもとに reason する�（根拠を持って理詰めで推論・判断する）�ことがやりやすいから
ただ、この simple なルールを採用しないというのも、�別に wrong と決めつけるべきでは全くない
ただ、この simple なルールを採用しないというのも、�別に wrong と決めつけるべきでは全くない
…というかこの話は皆さんにとって釈迦に説法でしたね
ただ、この simple なルールを採用しないというのも、�別に wrong と決めつけるべきでは全くない
…というかこの話は皆さんにとって釈迦に説法でしたね
ただ、この simple なルールを採用しないというのも、�別に wrong と決めつけるべきでは全くない
…というかこの話は皆さんにとって釈迦に説法でしたね
ただ、この simple なルールを採用しないというのも、�別に wrong と決めつけるべきでは全くない
…というかこの話は皆さんにとって釈迦に説法でしたね
ただ、この simple なルールを採用しないというのも、�別に wrong と決めつけるべきでは全くない
先にオチを：なぜ私はこの発表をしているか
先にオチを：なぜ私はこの発表をしているか
先にオチを：なぜ私はこの発表をしているか
先にオチを：なぜ私はこの発表をしているか
先にオチを：なぜ私はこの発表をしているか
先にオチを：なぜ私はこの発表をしているか
先にオチを：なぜ私はこの発表をしているか
先にオチを：なぜ私はこの発表をしているか
先にオチを：なぜ私はこの発表をしているか
先にオチを：なぜ私はこの発表をしているか
先にオチを：なぜ私はこの発表をしているか
自己紹介
自己紹介：hsjoihs（はすじょい）
@hsjoihs
hsjoihs
@sosoBOTpi
sozysozbot
ﾊﾟｿｺﾝｶﾀｶﾀなど
主に言語
自己紹介：hsjoihs（はすじょい）
実名：佐藤 弘崇 (さとう ひろたか)
経歴など：�・国際言語学オリンピック 2014/2015/2016 日本代表�・Stanford 卒【数学（学士）・物理学（学士）・応用工学物理学（修士）】�・セキュリティ・キャンプ 2022/'23/'24/'25 『Cコンパイラゼミ』講師
@hsjoihs
hsjoihs
@sosoBOTpi
sozysozbot
ﾊﾟｿｺﾝｶﾀｶﾀなど
主に言語
自己紹介：hsjoihs（はすじょい）
実名：佐藤 弘崇 (さとう ひろたか)
経歴など：�・国際言語学オリンピック 2014/2015/2016 日本代表�・Stanford 卒【数学（学士）・物理学（学士）・応用工学物理学（修士）】�・セキュリティ・キャンプ 2022/'23/'24/'25 『Cコンパイラゼミ』講師
所属：株式会社ドワンゴ／ZEN 大学の教員
@hsjoihs
hsjoihs
@sosoBOTpi
sozysozbot
ﾊﾟｿｺﾝｶﾀｶﾀなど
主に言語
<ZEN-univ>
「横断的な学び」を掲げ2025年に開学したオンライン大学
シラバスの科目概要
この科目では、オートマトンをはじめとする「計算機のモデル」のパラダイムと、「言語」という概念を数学的に定式化した「形式言語」という枠組みの 2 つをテーマとして取り上げ、一見距離のあるこれらの 2 つの間の密接な関係と、この 2 つが織りなす「計算」という現象に肉薄するとともに、具体的なプログラミング言語や計算機の実装方法や規格書などを垣間見ることで、普段はとりたてて詳しく追いかける機会の少ない「計算」「計算機」「プログラミング言語」といったものを掘り下げて「脱・神秘化」(demystify) していく。
さらに、正則言語や文脈自由言語などの言語クラスが持つソフトウェアエンジニアリング領域へのきわめて重大な応用を学ぶことで、実践的技術と理論的直感の両方を培う。
シラバスの科目概要
この科目では、オートマトンをはじめとする「計算機のモデル」のパラダイムと、「言語」という概念を数学的に定式化した「形式言語」という枠組みの 2 つをテーマとして取り上げ、一見距離のあるこれらの 2 つの間の密接な関係と、この 2 つが織りなす「計算」という現象に肉薄するとともに、具体的なプログラミング言語や計算機の実装方法や規格書などを垣間見ることで、普段はとりたてて詳しく追いかける機会の少ない「計算」「計算機」「プログラミング言語」といったものを掘り下げて「脱・神秘化」(demystify) していく。
さらに、正則言語や文脈自由言語などの言語クラスが持つソフトウェアエンジニアリング領域へのきわめて重大な応用を学ぶことで、実践的技術と理論的直感の両方を培う。
シラバスの科目概要
この科目では、オートマトンをはじめとする「計算機のモデル」のパラダイムと、「言語」という概念を数学的に定式化した「形式言語」という枠組みの 2 つをテーマとして取り上げ、一見距離のあるこれらの 2 つの間の密接な関係と、この 2 つが織りなす「計算」という現象に肉薄するとともに、具体的なプログラミング言語や計算機の実装方法や規格書などを垣間見ることで、普段はとりたてて詳しく追いかける機会の少ない「計算」「計算機」「プログラミング言語」といったものを掘り下げて「脱・神秘化」(demystify) していく。
さらに、正則言語や文脈自由言語などの言語クラスが持つソフトウェアエンジニアリング領域へのきわめて重大な応用を学ぶことで、実践的技術と理論的直感の両方を培う。
闇を照らす
「正則言語 L₁ と L₂ の� 共通部分 L₁ ∩ L₂ も
正則言語」
↓典型的教材
Introduction to Automata Theory, Languages, and Computation (Hopcroft & Ullman) より引用
「正則言語 L₁ と L₂ の� 共通部分 L₁ ∩ L₂ も
正則言語」
この教材→
↓典型的教材
Introduction to Automata Theory, Languages, and Computation (Hopcroft & Ullman) より引用
「正則表現では�補集合を求めるのは大変だが �DFA だと自明」
↓典型的教材
Introduction to Automata Theory, Languages, and Computation (Hopcroft & Ullman) より引用
「正則表現では�補集合を求めるのは大変だが �DFA だと自明」
この教材→
↓典型的教材
Introduction to Automata Theory, Languages, and Computation (Hopcroft & Ullman) より引用
2023 年 8 月に書き始め、2026 年 5 月についに完成
</ZEN-univ>
授業内で Ruby コミュニティに 2 回言及しました
授業内で Ruby コミュニティに 2 回言及しました
授業内で Ruby コミュニティに 2 回言及しました
授業内で Ruby コミュニティに 2 回言及しました
てなわけで
発表内容①�正規表現エンジンと Pike VM
話す必要のある前提が多い！
話す必要のある前提が多い！
話す必要のある前提が多い！
話す必要のある前提が多い！
話す必要のある前提が多い！
第一章�すごろくと�正則表現の�密接な関係
①：すごろく
①：すごろく
マス目がいくつかあり、マス目が矢印で結ばれている。�スタートに駒を置き、入ってくる文字に応じて矢印をたどって駒を進めていく。
ゴールにぴったりたどり着けるだろうか？
すごろくの具体例
二重丸 = ゴール（文字列を全部読んだときに、ここにいたら勝ち）
"" "1" "00" "10101" → true
"0" "10" "01" "1101" → false
「すごろく」は文字列を二値分類する
"" "1" "00" "10101" → true
"0" "10" "01" "1101" → false
②：すごろくの表現力
能力の限界
有限種類の文字・有限個のマス目での「すごろく」では�あまりややこしいロジックを実装することができない�（有名例：「カッコの開きと閉じが対応しているか？」の判定機は実装不可）
何であれば表現できるか
重要定理：� 「すごろくで表現できるロジック」は、
「選択・連接・繰り返しという基本三演算で構築できるロジック」と等しい
例：先ほどのを選択・連接・繰り返しという基本三演算で書く
"" "1" "00" "10101" → true
"0" "10" "01" "1101" → false
例：先ほどのを選択・連接・繰り返しという基本三演算で書く
"" "1" "00" "10101" → true
"0" "10" "01" "1101" → false
『1または「0の直後に【1の繰り返し】の直後に0」』の繰り返し
③：正則表現
正則表現
「選択・連接・繰り返しという基本三演算で構築したロジック」を書き表す手段�� ↓ のような構造は (A|BC)* と書き表す
演算子とその優先順位
選択：|と書く。優先順位は最弱。
連接：表記しない。「A の後に B、その後に C」を単に ABC と書きたいから。
繰り返し：*と書く。優先順位は最強。
具体例
A または「B の後に C」：A|BC
「A または B」の後に C：(A|B)C
「A または B」が何度でも：(A|B)*
A または 「Bが何度でも」：A|B*
具体例その２
『1または「0の直後に【1の繰り返し】の直後に0」』の繰り返し
具体例その２
『1または「0の直後に【1の繰り返し】の直後に0」』の繰り返し
(1|01*0)*
④：regex�（いわゆる『正規表現』）
VS Code とかに入れるとハイライトされて便利～
正則表現と似ているが、
「選択・連接・繰り返しという基本三演算」のみならず、�ユーザーの利便性のためにあんな機能やこんな機能をバンバン実装していがち
\p{sc=Hiragana} | 文字体系が平仮名である |
{4,} | 4 回以上の繰り返しである |
正則表現と似ているが、
「true か false か」の二値分類のみならず、�パターンに合致する部分文字列とその位置を報告
私はこういう流儀で話します（混乱を最小化したいので）
→
→
あえて曖昧にさせたいときには両方を「正規表現」と呼びます
パターン文字列を与えると、そのパターンに合致する部分文字列とその位置を報告するライブラリ
「選択・連接・繰り返しという基本三演算で構築した二値分類ロジック」を書き表す手段
なんなら Larry Wall も名称を分ける流儀を採用している
[...] what we call "regular expressions", which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines [...] I will, however, generally call them "regexes"��翻訳: 「regular expression」と呼ばれる、本物の regular expression（数学的概念としての正則表現）とはほとんど関係がない代物 [...]。とはいえ、私たちのパターンマッチエンジンで実現できることが広がっていくとともに、この用語（の示す範囲）も広がってきたので、 [...] ただ、私は普通は（こういったパターンマッチエンジンのことは）「regexes」（単数形 regex）と呼ぶことにします
https://www.perl.com/pub/2002/06/04/apo5.html/ より引用。話の本筋に関係のない箇所を意図的に削った。
第二章�歪めて汚す
再掲
→
→
パターン文字列を与えると、そのパターンに合致する部分文字列とその位置を報告するライブラリ
「選択・連接・繰り返しという基本三演算で構築した二値分類ロジック」を書き表す手段
この「部分文字列」が曲者
二値分類「全体が、true か？ false か？」�だけ考えていればよかったときとは�根本的に話が変わってくる
しかしながら regex エンジンの有用性のかなりの部分は�「部分文字列」を locate するというところにある�（特に、文字列置換のタスクにおいては）��よって、無視するわけにはいかない
理論サイドの話をすると：
数学的には、最も綺麗で自然なのは、
「[start, end) を抜き出したときに、それが二値分類で true となるするもの」
を全て返す、とすること��具体例：正則表現「かた*」で文字列「かたたたき」内を検索すると、�「か」「かた」「かたた」「かたたた」の 4 パターンが重なってハイライト
かたたたき
しかしながら
「重なってハイライト」という仕様だと、�現実の人々にとって嬉しくない�（特に、文字列置換のタスクにおいては。）
よって、数学的に最も綺麗で自然なこれを、�どうにかして歪めて汚す必要がある��（私の意見としては、正則表現と regex の最大の差はここにある）
現実の処理系で試してみよう
VS Code では、どこがハイライトされる？
答え
とハイライトされる
「重なり合わないマッチ」を左から探すという前提
結論
regex を使って VS Code とかがハイライトをするときというのは、
となっている��（注：特に | については Perl およびそれ以降の regex が共有している特徴。� ゆえに awk などにおいては成り立たない）
「貪欲マッチ」とかが欲しくなるのも、
「重なってハイライト」を歪めたいから
VS Code では、どこがハイライトされる？
答え
とハイライトされる
第三章�そろそろ本題
まず、「true か false かしかない、易しい世界」の話を
基本三演算でできた再帰的な構造なのだから、�それぞれの演算を「すごろく」で実装して、再帰的に翻訳していけばよい
「選択・連接・繰り返しという基本三演算で構築した二値分類ロジック」を書き表す手段
具体例：(|a*b) はこのような「すごろく」になる
「ε」は空文字列の意味。文字を消費せずに進むことを許す。�水面に落としたインクが広がっていくかのように、�すごろくの駒が「平等に」「分身して」広がっていく
具体例：(|a*b) はこのような「すごろく」になる
「ε」は空文字列の意味。文字を消費せずに進むことを許す。�水面に落としたインクが広がっていくかのように、�すごろくの駒が「平等に」「分身して」広がっていく
具体例：(|a*b) はこのような「すごろく」になる
「ε」は空文字列の意味。文字を消費せずに進むことを許す。�水面に落としたインクが広がっていくかのように、�すごろくの駒が「平等に」「分身して」広がっていく
数学的に綺麗・自然な�「全部探して、重なってハイライト」
便利な定理：
右の 2 種のマスで�正則表現を�翻訳しきることが�できる
思い出すシリーズ：
「分身」ではなく「不平等な選択肢」
すごろくの上を「平等に分身」するのではなく、�盤上に駒はただひとつであり
を にする
「駒はただひとつ」
0: jump -> [1]
1: eat "a" -> 2
2: jump -> [3]
3: jump -> [4, 6]
4: eat "b" -> 5
5: jump -> [4, 6]
6: goal
空文字列には要注意
/()*/ のような「空文字列ループ」があると、当然 VM がハング
文字を一切 eat せずに 1 回ループして同じ行番号に戻ってきてしまうから���「eat していないのに同じ場所に戻ってきた場合に対処」するには、�「eat するまでの間に通過した行番号一覧」を覚えておく
これで治る
ちなみに：空文字列は沼
文字列 a の中をパターン /|a/ で検索すると、
（regex101.com 調べ）
VM のうれしさ：拡張させやすい
VM の悲しさ：素朴にやると実行時間が指数関数的爆発
/(ab|ab)*d/ みたいなパターンを喰わせると、文字列 abababc に対して
「『左・左・左』ならいけるんじゃないだろうか」
「『左・左・右』ならいけるんじゃないだろうか」
「『左・右・左』ならいけるんじゃないだろうか」��となってしまい、実行時間が指数関数的に爆発する��catastrophic backtracking
対処法：「消費した文字数」を深さとする幅優先探索
説明のため、「1 日に文字が 1 文字ずつやってくる」と喩える
ただし、「同じ日付の『やることリスト』に同じ盤面は複数回登録しない」��これで治る（Pike VM などと呼ばれる）
Rust の regex クレートは（他の戦略でできない regex は） Pike VM にフォールバックするらしい�Regex engine internals as a library https://burntsushi.net/regex-internals/ ← おすすめ記事�there exists codepoints in both \w and \s which start with the same leading UTF-8 code units. とかおもろい
Ruby 3.2 で、たいていの regex に対して �catastrophic backtracking が解消した
ただし、以上の話は、「正則表現に不平等な選択肢を入れ「eat 命令とjump 命令」�としたからこそできた話��キャプチャグループの内容にマッチする \1 の類は、�選択・連接・繰り返しという基本三演算で構築した正則表現 で再現することが�不可能であることが数学的に知られている。��よって Ruby 3.2 でも、regex に \1 の類が入っているとこの解消法が適用されない�
皆さんも�regex エンジンを�自作しましょう
（まだ作っていないなら）
発表内容②�あらゆる BNF／文脈自由文法に対処できる、�覚えやすくて理解しやすい最高のパーサー
してますか？
皆さん
パーサー
パーサー大好き！
パーサー大好き！
パーサー大好き！
パーサー大好き！
パーサー大好き！
という人もいれば、
パーサー大好き！
正直パーサー苦手……
という人もいれば、
パーサー大好き！
正直パーサー苦手……
という人もいれば、
パーサー大好き！
正直パーサー苦手……
という人もいれば、
パーサー大好き！
正直パーサー苦手……
という人もいれば、
パーサー大好き！
正直パーサー苦手……
という人も、いることでしょう
という人もいれば、
今回紹介する手法は
なんて素晴らしいんだ！！ 最高じゃないか！（フラグ）���
第一章�BNF／文脈自由文法
文脈自由文法 (context-free grammar)
文脈自由文法 (context-free grammar)
未確定の <開始記号> から始めて、
というゲームを考える。��
文脈自由文法 (context-free grammar)
書き換え規則の例：���
文脈自由文法 (context-free grammar)
書き換え規則の例：�規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1' ��
文脈自由文法 (context-free grammar)
書き換え規則の例：�規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1' ��
文脈自由文法において許される書き換え規則の形は、
�規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1' ��
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
実際にプレイしよう
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
未確定の <開始記号> から始めて、
というゲームを、やってみよう��
スタート地点
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
未確定の <開始記号> から始めて、
というゲームを、やってみよう��
規則Aを適用しよう
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
未確定の <開始記号> から始めて、
というゲームを、やってみよう��
こうなる
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
未確定の<数> <通貨単位> から始めて、
というゲームを、やってみよう��
規則 C を適用しよう
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
未確定の<数> <通貨単位> から始めて、
というゲームを、やってみよう��
こうなる
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
未確定の<数> 'ド' 'ル' から始めて、
というゲームを、やってみよう��
規則 D を適用しよう
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
未確定の<数> 'ド' 'ル' から始めて、
というゲームを、やってみよう��
こうなる
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
'-' <正の数> 'ド' 'ル' から始めて、
というゲームを、やってみよう��
規則 E を適用しよう
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
'-' <正の数> 'ド' 'ル' から始めて、
というゲームを、やってみよう��
こうなる
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
'-' '1' 'ド' 'ル' から始めて、
�
こうなる
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
'-' '1' 'ド' 'ル' から始めて、
これで、全てが「確定」になった。�ゲーム終了�
こうなる
これが、�文脈自由文法
規則A:<開始記号> → <数> <通貨単位>�規則B:<数> → '0'�規則C:<通貨単位> → 'ド' 'ル'�規則D:<数> → '-' <正の数>�規則E:<正の数> → '1'
'-' '1' 'ド' 'ル' から始めて、
これで、全てが「確定」になった。�ゲーム終了�
BNF (Backus-Naur Form)
BNF (Backus-Naur Form)
文脈自由文法の書き換え規則を、左辺の記号ごとにまとめあげたもの。�
BNF (Backus-Naur Form)
文脈自由文法の書き換え規則を、左辺の記号ごとにまとめあげたもの。��それぞれの <ルール名> に対して、置き換え先の候補を列挙する
<数> ::= '0' | '-' <正の数> | '+' <正の数>
<正の数> ::= '1' | '2' | '3'
④：拡張 BNF
【再掲】BNF (Backus-Naur Form)
それぞれの <ルール名> に対して、置き換え先の候補を列挙する
<数> ::= '0' | '-' <正の数> | '+' <正の数>
<正の数> ::= '1' | '2' | '3'
【再掲】BNF (Backus-Naur Form)
それぞれの <ルール名> に対して、置き換え先の候補を列挙する
<数> ::= '0' | '-' <正の数> | '+' <正の数>
<正の数> ::= '1' | '2' | '3'��→ 右辺は、�'字' や <記号> が選択・連接で結びついたもの�であると見なせる
【再掲】BNF (Backus-Naur Form)
「繰り返し」も足せば�正則表現の基本三演算だ！
それぞれの <ルール名> に対して、置き換え先の候補を列挙する
<数> ::= '0' | '-' <正の数> | '+' <正の数>
<正の数> ::= '1' | '2' | '3'��→ 右辺は、�'字' や <記号> が選択・連接で結びついたもの�であると見なせる
ということで、右辺に正則表現を許した「拡張 BNF」
ということで、右辺に正則表現を許した「拡張 BNF」
それぞれの <ルール名> を左辺に置き、�<ルール名> や '字'を選択・連接・繰り返しで結び付けた正則表現を、右辺に置く。��
ということで、右辺に正則表現を許した「拡張 BNF」
それぞれの <ルール名> を左辺に置き、�<ルール名> や '字'を選択・連接・繰り返しで結び付けた正則表現を、右辺に置く。��たとえば、<A> ::= ('I' | <T>)* 'F'というルールがあるなら、�これは<A>を書き換えるときに�【「'I'または<T>」の繰り返しの後に'F'】�と書ける列をひとつ自由に選んで書き換えてよいということ。
ということで、右辺に正則表現を許した「拡張 BNF」
それぞれの <ルール名> を左辺に置き、�<ルール名> や '字'を選択・連接・繰り返しで結び付けた正則表現を、右辺に置く。��たとえば、<A> ::= ('I' | <T>)* 'F'というルールがあるなら、�これは<A>を書き換えるときに�【「'I'または<T>」の繰り返しの後に'F'】�と書ける列をひとつ自由に選んで書き換えてよいということ。
などをしてよい。
「拡張 BNF」の具体例
「拡張 BNF」の具体例
<値> ::= <数値> | <文字列> | <配列>
<数値> ::= '3' | '4' '2'
<文字列> ::= '"' '探' '検' '隊' '"' | '"' 'I' 'T' 'F' '"'
<配列> ::= '[' ']' | '[' <値> (',' <値>)* ']'
「拡張 BNF」の具体例
↑�「繰り返し」
<値> ::= <数値> | <文字列> | <配列>
<数値> ::= '3' | '4' '2'
<文字列> ::= '"' '探' '検' '隊' '"' | '"' 'I' 'T' 'F' '"'
<配列> ::= '[' ']' | '[' <値> (',' <値>)* ']'
定理：拡張 BNF の表現力は、素の BNF と本質的に同じ
定理：拡張 BNF の表現力は、素の BNF と本質的に同じ
雑な証明：
�よって、拡張 BNF で書かれた文法は、素の BNF へと変換できる
第三章�構文解析とは�逆問題である
逆問題
逆問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』
逆問題とは、ある系（物理現象や数学モデル）において、観測や結果（出力）からその原因や内部構造（入力・パラメータ）を推定・復元する問題のことを指す。
逆問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』
逆問題とは、ある系（物理現象や数学モデル）において、観測や結果（出力）からその原因や内部構造（入力・パラメータ）を推定・復元する問題のことを指す。
vs.��
逆問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』
逆問題とは、ある系（物理現象や数学モデル）において、観測や結果（出力）からその原因や内部構造（入力・パラメータ）を推定・復元する問題のことを指す。
vs.��順問題（じゅんもんだい、英: direct problem）（正問題）：�入力や原因が与えられたときに、その結果や応答を計算・予測する問題。
書き換え規則で「書き換え、広げる」が順問題
書き換え規則で「書き換え、広げる」が順問題
<始> ::= <年> <月> <日>�<年> ::= <1桁> <1桁> <1桁> <1桁> �<月> ::= <1桁> | <1桁> <1桁> �<日> ::= <1桁> | <1桁> <1桁> �<1桁> ::= '0'|'2'|'3'|'6'
書き換え規則で「書き換え、広げる」が順問題
<始> ::= <年> <月> <日>�<年> ::= <1桁> <1桁> <1桁> <1桁> �<月> ::= <1桁> | <1桁> <1桁> �<日> ::= <1桁> | <1桁> <1桁> �<1桁> ::= '0'|'2'|'3'|'6'
書き換え規則で「書き換え、広げる」が順問題
<始> ::= <年> <月> <日>�<年> ::= <1桁> <1桁> <1桁> <1桁> �<月> ::= <1桁> | <1桁> <1桁> �<日> ::= <1桁> | <1桁> <1桁> �<1桁> ::= '0'|'2'|'3'|'6'
順問題「書き換えて広げていけば、文字列 '2026320'を作れるなぁ」
逆問題「文字列 '2026320'のどこが<年>・<月>・<日>に相当？」
<始> ::= <年> <月> <日>�<年> ::= <1桁> <1桁> <1桁> <1桁> �<月> ::= <1桁> | <1桁> <1桁> �<日> ::= <1桁> | <1桁> <1桁> �<1桁> ::= '0'|'2'|'3'|'6'
逆問題「文字列 '2026320'のどこが<年>・<月>・<日>に相当？」
<始> ::= <年> <月> <日>�<年> ::= <1桁> <1桁> <1桁> <1桁> �<月> ::= <1桁> | <1桁> <1桁> �<日> ::= <1桁> | <1桁> <1桁> �<1桁> ::= '0'|'2'|'3'|'6'
逆問題「文字列 '2026320'のどこが<年>・<月>・<日>に相当？」
おやっ？
<始> ::= <年> <月> <日>�<年> ::= <1桁> <1桁> <1桁> <1桁> �<月> ::= <1桁> | <1桁> <1桁> �<日> ::= <1桁> | <1桁> <1桁> �<1桁> ::= '0'|'2'|'3'|'6'
この逆問題には解が 2 つある
この逆問題には解が 2 つある
この逆問題には解が 2 つある
この逆問題には解が 2 つある
この逆問題には解が 2 つある
困る
第四章�最も素朴な�パーサーの作り方
まずは簡単な例から
<数> ::= '0' | '-' <正の数> | '+' <正の数>
<正の数> ::= '1' | '2' | '3'
これを図に変換し、各 BNF ルールを関数と見なす
このような図は、railroad diagram と呼ばれる
<数> ::= '0' | '-' <正の数> | '+' <正の数>
<正の数> ::= '1' | '2' | '3'
定理：railroad diagram の表現力は拡張 BNF と全く同じ
定理：railroad diagram の表現力は拡張 BNF と全く同じ
「拡張 BNF で書けるなら、railroad diagram で書ける」：� 選択は線路の分岐、連接は線路の接続、繰り返しは線路のループとせよ��
定理：railroad diagram の表現力は拡張 BNF と全く同じ
「拡張 BNF で書けるなら、railroad diagram で書ける」：� 選択は線路の分岐、連接は線路の接続、繰り返しは線路のループとせよ���「railroad diagram で書けるなら、拡張 BNF で書ける」：� 線路の連なりを「すごろく」として見ることで、� 重要定理『「すごろくで表現できるロジック」は、� 「選択・連接・繰り返しの基本三演算で構築できるロジック」と等しい』� が使えて、右辺を正則表現に変換できるので、これは拡張 BNF になる
関数呼び出しは、このように起こる
関数呼び出しは、このように起こる
関数呼び出しは、このように起こる
関数呼び出しは、このように起こる
素朴パーサーの詳細
素朴パーサーの詳細
例①：「年月日」
先ほどの、困った年月日 BNF で実践してみよう
<始> ::= <年> <月> <日>�<年> ::= <1桁> <1桁> <1桁> <1桁> �<月> ::= <1桁> | <1桁> <1桁> �<日> ::= <1桁> | <1桁> <1桁> �<1桁> ::= '0'|'2'|'3'|'6'
これを図に変換し、各 BNF ルールを関数と見なす
実際に、やってみた
実際に、やってみた
実際に、やってみた
両方の可能性が出力される！！
実際に、やってみた
ただし、ログが長くなりすぎるので
<1桁> ::= '0'|'2'|'3'|'6'
はアドホックに
if (!(c == '0' || c == '2' || c == '3' || c == '6')) {
char msg[64];
snprintf(msg, sizeof msg, "expected digit, got '%c'", c);
die(msg);
}
で実装した��
両方の可能性が出力される！！
実際に、やってみた
ただし、ログが長くなりすぎるので
<1桁> ::= '0'|'2'|'3'|'6'
はアドホックに
if (!(c == '0' || c == '2' || c == '3' || c == '6')) {
char msg[64];
snprintf(msg, sizeof msg, "expected digit, got '%c'", c);
die(msg);
}
で実装した��デバッグログと AST の出力が混じってるけど気にしない
両方の可能性が出力される！！
pstree も見てみよう
pstree がそもそも入ってなくて homebrew で入れたログが残ってるけどまあいいや
例②：左再帰
こういうことをすると、どうなるか
<始> ::= <始> | '2'
実際にやってみた
こうなる
こうなる
プロセス 13897 が�「子プロセスを生やすたびにそれが殺される」�ループが 2000 回ほど発生し、�Resource temporarily unavailable になる
例③：悪意ある爆弾
<始> ::= <始> | <始> | <始>
<始> ::= <始> | <始> | <始>
明確に悪意がある
<始> ::= <始> | <始> | <始>
明確に悪意がある�せっかくなので Claude Code に書かせてみたら、深さガードを勝手に組んだ
お節介 and 便利
お節介 and 便利
シンギュラリティ
お節介 and 便利
シンギュラリティ（爆発的進化）
お節介 and 便利
シンギュラリティ（爆発的進化）（fork 爆弾の爆発を止めてくれる）
お節介 and 便利
シンギュラリティ（爆発的進化）（fork 爆弾の爆発を止めてくれる）
まあ別に MAX_DEPTH=100 にしようと fork: Resource temporarily unavailable になるだけなんですが
終章�not simple �という選択
「railroad diagram が、互いに関数呼び出しをする」
「railroad diagram が、互いに関数呼び出しをする」
この視点というのは、
��
「railroad diagram が、互いに関数呼び出しをする」
この視点というのは、
にもかかわらず、�言語処理系についての伝統的な教科書では�あまり教えられてこなかった。��
「railroad diagram が、互いに関数呼び出しをする」
この視点というのは、
にもかかわらず、�言語処理系についての伝統的な教科書では�あまり教えられてこなかった。��理由のひとつに、�「これを素朴に実装するとfork爆弾発生しまくり」�があるだろう
「railroad diagram が、互いに関数呼び出しをする」
この視点というのは、
にもかかわらず、�言語処理系についての伝統的な教科書では�あまり教えられてこなかった。��理由のひとつに、�「これを素朴に実装するとfork爆弾発生しまくり」�があるだろう
長らくこの概念には標準的な名前すらなく、�2021 年に出た論文
https://link.springer.com/article/10.1007/s10009-021-00634-y で提唱された Systems of Procedural Automata (SPA) という名前が、�Ruby コミュニティの中（だけ）で�流行ってる
伝統的なプログラミング言語処理系の教科書というのは：
伝統的なプログラミング言語処理系の教科書というのは：
伝統的なプログラミング言語処理系の教科書というのは：
伝統的なプログラミング言語処理系の教科書というのは：
伝統的なプログラミング言語処理系の教科書というのは：
Perl の作者 Larry Wall は、そうしなかった
toke.c 内の S_intuit_more 関数を読んでみよう。[] を見た際にそれが
を見極めるための�整数変数 weight を�用意して、それを�増減させる実装。��「曖昧性に遭ったら� 空気を読んで判断」
/* If it is something like 'a-' or '0-', it is more likely to
* be a character class. '!' is the first ASCII graphic, so '!-'
* would be the start of a range of graphics. */
if (! first_time && memCHRs("aA01! ", prev_un_char))
weight += 30;
/* If it is something like '-Z' or '-7' (for octal) or '-9' it
* is more likely to be a character class. '~' is the final ASCII
* graphic, so '-~' would be the end of a range of graphics.
*
* khw: Having [-z] really doesn't imply what the comments above
* indicate, so this should only be tested when '! first_time' */
if (memCHRs("zZ79~", s[1]))
weight += 30;
「人間は、局所的な曖昧性解決は得意だが、�（例えば型情報を利用したオーバーロード解決といった）遠隔的な曖昧性解決が�できるようになるには大学院とか行かなきゃいけない」� — Larry Wall
なぜ Larry Wall はこのような発想に至ったのか
My background is in both computers and linguistics… I put more ideas from linguistics into Perl than is typical in computer science.��... missionary training that my wife and I went through. It was with an outfit called the Summer Institute of Linguistics, which is affiliated with the Wycliffe Bible Translators. Their job is to go out and learn languages that have not been written down before, do a linguistic analysis of the language, come up with a writing system and then translate various things, including the Bible.��言語学のバックグラウンドがあり、�かつ、未記述言語（当然ながら、「どう話すのが正しいか」を定める書籍など無い）をリバエンする�話に慣れ親しんでいた
思い出すシリーズ：
[...] what we call "regular expressions", which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines [...] I will, however, generally call them "regexes"��翻訳: 「regular expression」と呼ばれる、本物の regular expression（数学的概念としての正則表現）とはほとんど関係がない代物 [...]。とはいえ、私たちのパターンマッチエンジンで実現できることが広がっていくとともに、この用語（の示す範囲）も広がってきたので、 [...] ただ、私は普通は（こういったパターンマッチエンジンのことは）「regexes」（単数形 regex）と呼ぶことにします
https://www.perl.com/pub/2002/06/04/apo5.html/ より引用。話の本筋に関係のない箇所を意図的に削った。
数学的にシンプルな「正則表現」の枠を積極的に飛び越え、�シンプルさをかなぐり捨て、�言い表したいことを言える表現力を積み増すことで�regex は育っていった
→
→
パターン文字列を与えると、そのパターンに合致する部分文字列とその位置を報告するライブラリ
「選択・連接・繰り返しという基本三演算で構築した二値分類ロジック」を書き表す手段
Ruby は natural, not simple という設計を採っている
ゆえに、構文解析をする上でも、�「長らく標準的な名前すらついていなかったが� あらゆる BNF／文脈自由文法に対処できる � Systems of Procedural Automata という概念」を用いることで、�表現力が高く complex な Ruby の構文に対して光を照らしていっている
最後になりますが
最後になりますが
出囃子で歌ったように、�
最後になりますが
出囃子で歌ったように、��La idea es compartir, te vas a divertir
分かち合って楽しんでいこう
最後になりますが
出囃子で歌ったように、��La idea es compartir, te vas a divertir
分かち合って楽しんでいこう��30 分枠に収まらなかったネタはいくらでもあるので、�是非話しかけていただければ
ご清聴ありがとうございました