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
390
「ナントカ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
LR で JSON パーサーを作る / Coding LR JSON Parser
junk0612
2
550
From LALR to IELR: A Lrama's Next Step
junk0612
2
3.6k
RubyConf Taiwan / Understanding Parser Generators surrounding Ruby with Contributing Lrama
junk0612
1
5k
LL法とLR法の違いは?調べてみた!-完全版-/Comparing LL and LR parse algorithm -EX Edition-
junk0612
0
530
ESM Super LT/Comparing LL and LR parse algorithm
junk0612
1
110
Lrama へのコントリビューションを通して学ぶ Ruby のパーサジェネレータ事情
junk0612
4
5.1k
ソフトウェア開発とコミュニケーション / Communication in Software Development
junk0612
0
1.2k
アジャイルという「マインドセット」 / Mindset named Agile
junk0612
0
910
Rails × パターン / Rails meets Patterns
junk0612
3
2.5k
Other Decks in Programming
See All in Programming
Vertical Architectures for Scalable Angular Applications
manfredsteyer
PRO
0
270
Prompt Engineering for Developers @ AWS Community Day Adria 2024
slobodan
0
110
プロジェクト新規参入者のリードタイム短縮の観点から見る、品質の高いコードとアーキテクチャを保つメリット
d_endo
1
880
ピクシブ百科事典のWebフロントエンドパフォーマンス改善
higara
0
170
シールドクラスをはじめよう / Getting Started with Sealed Classes
mackey0225
2
320
破壊せよ!データ破壊駆動で考えるドメインモデリング / data-destroy-driven
minodriven
13
3.6k
Go言語でターミナルフレンドリーなAIコマンド、afaを作った/fukuokago20_afa
monochromegane
2
130
現場で役立つモデリング 超入門
masuda220
PRO
10
2.2k
カスタムしながら理解するGraphQL Connection
yanagii
0
610
Tuning GraphQL on Rails
pyama86
2
670
実践サーバーレスパフォーマンスチューニング ~その実力に迫る~ / Practical Serverless Performance Tuning ~A Close Look at its Power~
seike460
PRO
2
250
Universal Linksの実装方法と陥りがちな罠
kaitokudou
1
210
Featured
See All Featured
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
328
21k
GraphQLとの向き合い方2022年版
quramy
43
13k
Done Done
chrislema
181
16k
Keith and Marios Guide to Fast Websites
keithpitt
408
22k
For a Future-Friendly Web
brad_frost
174
9.4k
10 Git Anti Patterns You Should be Aware of
lemiorhan
653
59k
No one is an island. Learnings from fostering a developers community.
thoeni
19
3k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Put a Button on it: Removing Barriers to Going Fast.
kastner
58
3.5k
The Art of Programming - Codeland 2020
erikaheidi
51
13k
Scaling GitHub
holman
458
140k
Teambox: Starting and Learning
jrom
132
8.7k
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