Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
「ナントカLR」を整理する / Clarifying LR Algorithms
Search
Junichi Kobayashi
June 25, 2024
Programming
1
150
「ナントカLR」を整理する / Clarifying LR Algorithms
After RubyKaigi 2024 LR Parser Night w/ Asakusa.rb
Junichi Kobayashi
June 25, 2024
Tweet
Share
More Decks by Junichi Kobayashi
See All by Junichi Kobayashi
From LALR to IELR: A Lrama's Next Step
junk0612
2
2.8k
RubyConf Taiwan / Understanding Parser Generators surrounding Ruby with Contributing Lrama
junk0612
1
3.8k
LL法とLR法の違いは?調べてみた!-完全版-/Comparing LL and LR parse algorithm -EX Edition-
junk0612
0
300
ESM Super LT/Comparing LL and LR parse algorithm
junk0612
1
77
Lrama へのコントリビューションを通して学ぶ Ruby のパーサジェネレータ事情
junk0612
4
3.8k
ソフトウェア開発とコミュニケーション / Communication in Software Development
junk0612
0
1.2k
アジャイルという「マインドセット」 / Mindset named Agile
junk0612
0
850
Rails × パターン / Rails meets Patterns
junk0612
3
2.4k
「アジャイル開発」でハッピーになろう
junk0612
0
140
Other Decks in Programming
See All in Programming
設計の考え方 - インターフェースと腐敗防止層編 #phpconfuk / Interface and Anti Corruption Layer
okashoi
7
1.5k
CSC307 Lecture 04
javiergs
PRO
0
190
dbt v1.8で追加された単体テストを触ってみた
k_data_analyst
2
260
【超難問】絶対に解けないJavaScriptクイズ8選
tomo1227
0
570
CSC307 Lecture 02
javiergs
PRO
0
280
Cloudless Computingの論文紹介
yuukit
1
250
自分好みの TS バンドラを Rust で作れる!Deno の内部ライブラリの活用 – Denoで変わるランタイムの景色 実践事例 Lunch LT
pizzacat83
4
540
IaCにおけるテスト考察 / Tests in IaC
linyows
2
240
俺たちのPHPの型システムはすごいぞっ!
suguruooki
1
210
2024年版 Kotlin サーバーサイドプログラミング実践開発
n_takehata
3
960
30分でわかるつくって、壊して、直して学ぶ Kubernetes入門
aoi1
6
780
Kotlin Collection関数をマスター
masayukisuda
0
2.8k
Featured
See All Featured
How To Stay Up To Date on Web Technology
chriscoyier
784
250k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
353
28k
Fashionably flexible responsive web design (full day workshop)
malarkey
399
65k
Into the Great Unknown - MozCon
thekraken
16
1.2k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
10
3.7k
Making the Leap to Tech Lead
cromwellryan
126
8.7k
KATA
mclloyd
18
12k
Designing for humans not robots
tammielis
247
25k
Product Roadmaps are Hard
iamctodd
PRO
46
10k
Why Our Code Smells
bkeepers
PRO
331
56k
Music & Morning Musume
bryan
42
5.8k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
13
1.4k
Transcript
「ナントカLR」を整理する Junichi Kobayashi (@junk0612) ESM, Inc. LR Parser Night w/
Asakusa.rb ANDPAD Inc. 2024/06/25(Tue.)
Junichi Kobayashi • X / GitHub: @junk0612 • 永和システムマネジメント ◦
Rails エンジニア ◦ 構文解析器研究部員 • 趣味 ◦ パーサー ◦ 音楽ゲーム ◦ ボードゲーム ◦ 俳句
We Are Hiring!! 詳しくは社員まで ☺
大事なことは最初に
「From LALR to IELR」 相関図 Canonical LR 定義に基づく実装 処理能力が高い LALR
現実的なメモリ使用量 最も実用的 IELR 最小 LR の一種 Lrama に実装中 ときどきあるミスが気になる 効率の悪さを直してほしい いいとこ取りを狙う Parser Scannerless Parser 依存 不満 PSLR Lexer 統合のための武器 Lrama が目指すもの
IELR 最小 LR の一種 Lrama に実装中 効率の悪さを直してほしい いいとこ取りを狙う Scannerless Parser
依存 不満 PSLR Lexer 統合のための武器 Lrama が目指すもの Canonical LR 定義に基づく実装 処理能力が高い LALR 現実的なメモリ使用量 最も実用的 「From LALR to IELR」 相関図 ときどきあるミスが気になる Parser Mysterious Conflict
「From LALR to IELR」 相関図 IELR 最小 LR の一種 Lrama
に実装中 ときどきあるミスが気になる いいとこ取りを狙う Scannerless Parser 依存 不満 PSLR Lexer 統合のための武器 Lrama が目指すもの Canonical LR 定義に基づく実装 処理能力が高い LALR 現実的なメモリ使用量 最も実用的 効率の悪さを直してほしい Parser 状態数 (≒メモリ使用量) 5~10倍 (論文より)
「From LALR to IELR」 相関図 ときどきあるミスが気になる 効率の悪さを直してほしい Scannerless Parser 依存
不満 PSLR Lexer 統合のための武器 Lrama が目指すもの Canonical LR 定義に基づく実装 処理能力が高い LALR 現実的なメモリ使用量 最も実用的 IELR 最小 LR の一種 Lrama に実装中 いいとこ取りを狙う Parser どんな入力でも 同じ動作 状態数は ほぼ同じ
「From LALR to IELR」 相関図 Canonical LR 定義に基づく実装 処理能力が高い LALR
現実的なメモリ使用量 最も実用的 IELR 最小 LR の一種 Lrama に実装中 ときどきあるミスが気になる 効率の悪さを直してほしい いいとこ取りを狙う Parser Scannerless Parser 依存 不満 PSLR Lexer 統合のための武器 Lrama が目指すもの
ときどきあるミスが気になる 効率の悪さを直してほしい いいとこ取りを狙う Scannerless Parser 依存 不満 PSLR Lexer 統合のための武器
Lrama が目指すもの 「From LALR to IELR」 相関図 Canonical LR 定義に基づく実装 処理能力が高い LALR 現実的なメモリ使用量 最も実用的 IELR 最小 LR の一種 Lrama に実装中 Parser
Parser State 0 State 1 State 2 State 3 NUM
+ exp State 4 State 5 State 6 * ( exp NUM - … Token Stream Source Code Lexer Grammar File Parser Generator 8, 'B' 4, '-' 1, 'E' 0 LR Parser のイメージモデル
Parser State 0 State 1 State 2 State 3 NUM
+ exp State 4 State 5 State 6 * ( exp NUM - … Token Stream Source Code Lexer Grammar File Parser Generator 8, 'B' 4, '-' 1, 'E' 0 LR Parser のイメージモデル オートマトンを どう作るかの違い
Canonical LR のオートマトン
Canonical LR のオートマトン
LALR のオートマトン
LALR のオートマトン
IELR のオートマトン
「From LALR to IELR」 相関図 Canonical LR 定義に基づく実装 処理能力が高い LALR
現実的なメモリ使用量 最も実用的 IELR 最小 LR の一種 Lrama に実装中 ときどきあるミスが気になる 効率の悪さを直してほしい いいとこ取りを狙う Parser Scannerless Parser 依存 不満 PSLR Lexer 統合のための武器 Lrama が目指すもの
付録: Mysterious Conflict
Mysterious New Conflict
Mysterious Invasive Conflict
Mysterious Mutated Conflict