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
180
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.7k
「今のプロジェクトいろいろ大変なんですよ、app/services とかもあって……」/After Kaigi on Rails 2024 LT Night
junk0612
5
2.6k
LR で JSON パーサーを作る / Coding LR JSON Parser
junk0612
2
1.5k
「ナントカLR」を整理する / Clarifying LR Algorithms
junk0612
1
570
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.9k
LL法とLR法の違いは?調べてみた!-完全版-/Comparing LL and LR parse algorithm -EX Edition-
junk0612
0
1.1k
Lrama へのコントリビューションを通して学ぶ Ruby のパーサジェネレータ事情
junk0612
4
7k
ソフトウェア開発とコミュニケーション / Communication in Software Development
junk0612
0
1.3k
Other Decks in Programming
See All in Programming
スタートアップの急成長を支えるプラットフォームエンジニアリングと組織戦略
sutochin26
1
5.8k
#QiitaBash MCPのセキュリティ
ryosukedtomita
1
1.3k
AI時代の『改訂新版 良いコード/悪いコードで学ぶ設計入門』 / ai-good-code-bad-code
minodriven
14
4.6k
AIともっと楽するE2Eテスト
myohei
6
2.6k
Claude Code + Container Use と Cursor で作る ローカル並列開発環境のススメ / ccc local dev
kaelaela
9
5.2k
GitHub Copilot and GitHub Codespaces Hands-on
ymd65536
2
150
AI コーディングエージェントの時代へ:JetBrains が描く開発の未来
masaruhr
1
150
20250628_非エンジニアがバイブコーディングしてみた
ponponmikankan
0
680
XP, Testing and ninja testing
m_seki
3
240
Python型ヒント完全ガイド 初心者でも分かる、現代的で実践的な使い方
mickey_kubo
1
120
Discover Metal 4
rei315
2
130
AI駆動のマルチエージェントによる業務フロー自動化の設計と実践
h_okkah
0
150
Featured
See All Featured
Why Our Code Smells
bkeepers
PRO
336
57k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
130
19k
A designer walks into a library…
pauljervisheath
207
24k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.7k
How GitHub (no longer) Works
holman
314
140k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3.3k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
GraphQLとの向き合い方2022年版
quramy
49
14k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
31
2.4k
The Language of Interfaces
destraynor
158
25k
Become a Pro
speakerdeck
PRO
29
5.4k
Testing 201, or: Great Expectations
jmmastey
43
7.6k
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.