LL法とLR法の違いは？調べてみた！-完全版-/Comparing LL and LR parse algorithm -EX Edition-

1. LL 法と LR 法の違いは？ 調べてみた！ 完全版 ESM アジャイル事業部 構文解析器研究部員 小林純一 (@junk0612) Fukuoka.rb #333 Ninja Talk 大会 オンライン 2023/11/29(Wed.)
2. Fukuoka.rb 333回目 おめでとう ございます
3. Fukuoka.rb 333回目 おめでとう ございます • RubyWorld Conference 2023 で行われたスポンサートーク 「ESM スーパーライトニングトークス」の 私が担当した部分の再演・増補改訂版です • 半分も終わらないうちに時間が来てしまったので 面白いところまでたどり着けませんでした • この内容を 80 秒で話そうとしたのが良くなかった (反省) ◦ いや、終わらないだろうとは思ってたんですけど…… この発表は
4. LL 法と LR 法の違いは？ 調べてみた！ 完全版 ESM アジャイル事業部 構文解析器研究部員 小林純一 (@junk0612) Fukuoka.rb #333 Ninja Talk 大会 オンライン 2023/11/29(Wed.)
5. • 小林純一 • X / GitHub: @junk0612 • 株式会社永和システムマネジメント アジャイル事業部 ◦ RubyxAgile グループ ◦ 構文解析器研究部員 • Lrama コントリビューター ◦ Named References の実装 ◦ 内部パーサーの Racc 化 など 自己紹介
9. 世はまさに 大パーサー時代
10. LL 法 と LR 法
11. LL法とLR法 LL法 • トップダウン方式 • 左端導出 • 手書きに適している • 先読みによって構文を推測する • Prism が採用している LR法 • ボトムアップ方式 • 右端導出 • 手書きには適さない • 決定論的に構文木を構築する • Lrama が生成するパーサーが 採用している
12. LL法とLR法 LL法 • トップダウン方式 • 左端導出 • 手書きに適している • 先読みによって構文を推測する • Prism が採用している LR法 • ボトムアップ方式 • 右端導出 • 手書きには適さない • 決定論的に構文木を構築する • Lrama が生成するパーサーが 採用している
13. 例: メソッド定義 method_definition def method_name ( args ) method_body end method_definition def method_name ( args ) = method_body
14. Fukuoka.rb 333回目 おめでとう ございます • パーサーは自分が今どこを読んでいるかを知っている • 今読んでいるルールにおいて次に何が来るはずかは 文法ファイルからわかる • 次のトークンを先読みし、何であったかによって処理を分岐する ◦ 分岐の決定に必要なトークンの先読み数が k のとき LL(k) と表記する • 来るはずのないトークンが来たら文法エラーとする LL 法の基本的な考え方
15. method_definition LL法の場合
16. method_definition def method_name LL法の場合
17. method_definition def method_name 分岐 • → 引数 • → end-less メソッド • → メソッド本体 ( = method_body LL法の場合
18. method_definition def method_name 分岐 • → 引数 • → end-less メソッド • → メソッド本体 ( = method_body ( LL法の場合
19. method_definition def method_name ( args ) LL法の場合
20. method_definition def method_name ( args ) 分岐 • → end-less メソッド • → メソッド本体 = method_body LL法の場合
21. method_definition def method_name ( args ) 分岐 • → end-less メソッド • → メソッド本体 = method_body = LL法の場合
22. LL法の場合 method_definition def method_name ( args ) = method_body
23. Fukuoka.rb 333回目 おめでとう ございます • パーサーは自分が何を読んできたかを知っている • 読んできたトークンがどういう並びになったら 上位のトークンに置換可能かは、文法ファイルからわかる • トークンを読み進んでいき、置換可能なトークンが一意になったら置換す ることを繰り返す • 現在の並びで置換可能なトークンがなくなったら文法エラーとする LR 法の基本的な考え方
24. LR法の場合 def
25. LR法の場合 def method_name
26. LR法の場合 def method_name ( args )
27. LR法の場合 def method_name ( args ) = method_body
28. LR法の場合 method_definition def method_name ( args ) = method_body
29. LL法とLR法 LL法 • トップダウン方式 • 左端導出 • 手書きに適している • 先読みによって構文を推測する • Prism が採用している LR法 • ボトムアップ方式 • 右端導出 • 手書きには適さない • 決定論的に構文木を構築する • Lrama が生成するパーサーが 採用している
30. Let's parse everything your favorite algorithm.