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
ESM Super LT/Comparing LL and LR parse algorithm
Search
Junichi Kobayashi
November 08, 2023
Programming
1
170
ESM Super LT/Comparing LL and LR parse algorithm
Junichi Kobayashi
November 08, 2023
Tweet
Share
More Decks by Junichi Kobayashi
See All by Junichi Kobayashi
The Implementations of Advanced LR Parser Algorithm
junk0612
3
1.6k
「今のプロジェクトいろいろ大変なんですよ、app/services とかもあって……」/After Kaigi on Rails 2024 LT Night
junk0612
5
2.6k
LR で JSON パーサーを作る / Coding LR JSON Parser
junk0612
2
1.4k
「ナントカLR」を整理する / Clarifying LR Algorithms
junk0612
1
540
From LALR to IELR: A Lrama's Next Step
junk0612
2
4.3k
RubyConf Taiwan / Understanding Parser Generators surrounding Ruby with Contributing Lrama
junk0612
2
6.8k
LL法とLR法の違いは?調べてみた!-完全版-/Comparing LL and LR parse algorithm -EX Edition-
junk0612
0
980
Lrama へのコントリビューションを通して学ぶ Ruby のパーサジェネレータ事情
junk0612
4
7k
ソフトウェア開発とコミュニケーション / Communication in Software Development
junk0612
0
1.3k
Other Decks in Programming
See All in Programming
Cloudflare Workersで進めるリモートMCP活用
syumai
13
1.9k
ワイがおすすめする新潟の食 / 20250530phpconf-niigata-eve
kasacchiful
0
120
知識0からカンファレンスやってみたらこうなった!
syossan27
5
320
コードに語らせよう――自己ドキュメント化が内包する楽しさについて / Let the Code Speak
nrslib
4
520
インターフェース設計のコツとツボ
togishima
2
250
TypeScript エンジニアが Android 開発の世界に飛び込んだ話
yuisakamoto
6
820
CQRS/ESのクラスとシステムフロー ~ RailsでフルスクラッチでCQRSESを組んで みたことから得た学び~
suzukimar
0
180
TypeScript製IaCツールのAWS CDKが様々な言語で実装できる理由 ~他言語変換の仕組み~ / cdk-language-transformation
gotok365
6
340
型安全なDrag and Dropの設計を考える
yudppp
5
630
事業KPIを基に価値の解像度を上げる
nealle
0
180
イベントソーシングとAIの親和性ー物語とLLMに理解できるデータ
tomohisa
1
150
Duke on CRaC with Jakarta EE
ivargrimstad
1
580
Featured
See All Featured
Site-Speed That Sticks
csswizardry
6
570
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
How STYLIGHT went responsive
nonsquared
100
5.6k
The Cult of Friendly URLs
andyhume
78
6.4k
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
32
2.3k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
3.8k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
Documentation Writing (for coders)
carmenintech
71
4.8k
Done Done
chrislema
184
16k
Fontdeck: Realign not Redesign
paulrobertlloyd
84
5.5k
Building Better People: How to give real-time feedback that sticks.
wjessup
368
19k
Speed Design
sergeychernyshev
30
960
Transcript
LL 法と LR 法の違いは? 調べてみた! ESM アジャイル事業部 構文解析器研究部員 小林純一 (@junk0612)
RubyWorld Conference 2023 島根県立産業交流会館「くにびきメッセ」 2023/11/09(Thu.)
• 小林純一 • X / GitHub: @junk0612 • 株式会社永和システムマネジメント アジャイル事業部
◦ RubyxAgile グループ ◦ 構文解析器研究部員 • Lrama コントリビューター ◦ Named References の実装 ◦ 内部パーサーの Racc 化 など 自己紹介
世はまさに 大パーサー時代
LL 法 と LR 法
LL法とLR法 LL法 • トップダウン方式 • 左端導出 • 手書きに適している • 先読みによって構文を推測する
• Prism が採用している LR法 • ボトムアップ方式 • 右端導出 • 手書きには適さない • 決定論的に構文木を構築する • Lrama が生成するパーサーが 採用している
LL法とLR法 LL法 • トップダウン方式 • 左端導出 • 手書きに適している • 先読みによって構文を推測する
• Prism が採用している LR法 • ボトムアップ方式 • 右端導出 • 手書きには適さない • 決定論的に構文木を構築する • Lrama が生成するパーサーが 採用している
例: メソッド定義 method_definition def method_name ( args ) method_body end
method_definition def method_name ( args ) = method_body
method_definition LL法の場合
method_definition def method_name LL法の場合
method_definition def method_name 分岐 • → 引数 • → end-less
メソッド • → メソッド本体 ( = method_body LL法の場合
method_definition def method_name 分岐 • → 引数 • → end-less
メソッド • → メソッド本体 ( = method_body ( LL法の場合
method_definition def method_name ( args ) LL法の場合
method_definition def method_name ( args ) 分岐 • → end-less
メソッド • → メソッド本体 = method_body LL法の場合
method_definition def method_name ( args ) 分岐 • → end-less
メソッド • → メソッド本体 = method_body = LL法の場合
LL法の場合 method_definition def method_name ( args ) = method_body
LR法の場合 def
LR法の場合 def method_name
LR法の場合 def method_name ( args )
LR法の場合 def method_name ( args ) = method_body
LR法の場合 method_definition def method_name ( args ) = method_body
LL法とLR法 LL法 • トップダウン方式 • 左端導出 • 手書きに適している • 先読みによって構文を推測する
• Prism が採用している LR法 • ボトムアップ方式 • 右端導出 • 手書きには適さない • 決定論的に構文木を構築する • Lrama が生成するパーサーが 採用している
Let's parse everything your favorite algorithm.