Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
ESM Super LT/Comparing LL and LR parse algorithm
Search
Junichi Kobayashi
November 08, 2023
Programming
260
1
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
ESM Super LT/Comparing LL and LR parse algorithm
Junichi Kobayashi
November 08, 2023
Transcript
22 slides
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.
More Decks by Junichi Kobayashi
See All by Junichi Kobayashi
XP をバイブルにする事業部で10年働いた新卒が語りたい『Tidy First?』/ Put your understanding into the code
junk0612
0
110
rage against annotate_predecessor
junk0612
0
300
The Implementations of Advanced LR Parser Algorithm
junk0612
3
2.9k
「今のプロジェクトいろいろ大変なんですよ、app/services とかもあって……」/After Kaigi on Rails 2024 LT Night
junk0612
6
2.9k
LR で JSON パーサーを作る / Coding LR JSON Parser
junk0612
2
2.1k
「ナントカLR」を整理する / Clarifying LR Algorithms
junk0612
1
750
From LALR to IELR: A Lrama's Next Step
junk0612
2
5.4k
RubyConf Taiwan / Understanding Parser Generators surrounding Ruby with Contributing Lrama
junk0612
2
7.3k
LL法とLR法の違いは?調べてみた!-完全版-/Comparing LL and LR parse algorithm -EX Edition-
junk0612
0
2.9k
Other Decks in Programming
See All in Programming
Snowflake Openflow Connector利用の勘所 / 20261024developersio2026tokyo-snowflake-openflow
kasacchiful
PRO
0
340
Claude Code ハーネスDeep Dive – 君はどこまで制御する? -
takateeen_knj
6
5.9k
Goコンパイラを作ってGoをもっと理解する / Build a Go compiler to better understand Go
ikura_hamu
0
130
クラウドエージェントは、 何がそんなに便利なのか / what makes cloud agents so useful
rkaga
5
890
Web3Dライブラリを作ってVue Custom Rendererの仕組みを理解しよう / lets learn vue custom renderer by making 3d library
drumath2237
1
140
あなたはMCPの機能を、まだ知らない。
4geru
1
360
動画プレイヤーはなぜカクつくのか 〜Flutterのレンダリングとネイティブの境界を解剖する〜
naruogram
0
340
コード生成時代のAPI定義を支えるRequest Spec移行
pvcresin
0
190
AIが生成したコードは読むべきか?抽象化設計とコードの品質保証 / abstraction-design-and-quality
minodriven
16
9.2k
仕様駆動開発入門 (何を作るかを先に決めて渡す) | 目指せ Kiro マスター 05
inariku
PRO
2
170
Будущее локальных LLM – Алексей Голобурдин, PythoNN
sobolevn
0
120
どうしても Eloquent でリポジトリパターンをやりたいんだ #phpcon_niigata / phpcon-niigata-2026
shogogg
0
380
Featured
See All Featured
How to make the Groovebox
asonas
2
2.6k
Claude Code どこまでも/ Claude Code Everywhere
nwiizo
68
60k
Become a Pro
speakerdeck
PRO
31
6.4k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
16
2.2k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
28
3.8k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
659
62k
What Being in a Rock Band Can Teach Us About Real World SEO
427marketing
0
1.1k
Designing Experiences People Love
moore
143
24k
Build The Right Thing And Hit Your Dates
maggiecrowley
39
3.5k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
141
35k
Optimising Largest Contentful Paint
csswizardry
37
4k