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
77
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
「ナントカLR」を整理する / Clarifying LR Algorithms
junk0612
1
160
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
Lrama へのコントリビューションを通して学ぶ Ruby のパーサジェネレータ事情
junk0612
4
3.9k
ソフトウェア開発とコミュニケーション / 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
Kotlin Script 활용하기
kciter
0
150
エンジニアが開発生産性を上げるためにやる最初の一歩
ktchiroyah
0
130
GoogleI/O2024 LT報告会資料
shinsukefujita1126
1
210
Fat Controller は悪か? ~光のFat Controller・闇のガリController~
stwile
1
300
CSC307 Lecture 04
javiergs
PRO
0
210
BigQueryとDataformとTROCCO®による事業グロース
nihemak
0
290
Kotlin Collection関数をマスター
masayukisuda
0
3.1k
ビルドツールとはなにか?からはじめるGradle超入門 / JJUG CCC 2024 Spring
nhayato
1
180
JJUG CCC 2024 Spring自動アップグレードを夢見て、Amazon Q Developer使ってみた
toricky6
2
190
ゼロから始める型安全なGraphQL開発
shachi_daikon55
0
180
データサイエンスやデータエンジニアリングの求人サイトの個人開発
billyio
0
670
What's new in Xcode 16 ダイジェスト
enomotok
0
220
Featured
See All Featured
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
34
6.2k
The Illustrated Children's Guide to Kubernetes
chrisshort
35
47k
What's new in Ruby 2.0
geeforr
338
31k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
34
9k
Java REST API Framework Comparison - PWX 2021
mraible
PRO
19
7.1k
A better future with KSS
kneath
231
17k
How To Stay Up To Date on Web Technology
chriscoyier
784
250k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
143
43k
Keith and Marios Guide to Fast Websites
keithpitt
408
22k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
119
18k
Making the Leap to Tech Lead
cromwellryan
126
8.7k
Optimizing for Happiness
mojombo
372
69k
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.