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
LALR parser generatorの作り方
Search
yui-knk
January 20, 2024
Programming
6
5.3k
LALR parser generatorの作り方
BuriKaigi 2024
https://burikaigi.dev/
yui-knk
January 20, 2024
Tweet
Share
More Decks by yui-knk
See All by yui-knk
What is Parser
yui_knk
10
5k
Ruby Parser progress report 2024
yui_knk
2
330
最高の構文木の設計 2024年版
yui_knk
8
4.5k
Converting AST
yui_knk
4
300
My favorite script, "dsl.rb"
yui_knk
2
990
Rearchitect Ripper
yui_knk
2
990
The grand strategy of Ruby Parser
yui_knk
7
8.8k
Declarative parse.y
yui_knk
2
4.8k
Ruby Parser progress report
yui_knk
2
7.4k
Other Decks in Programming
See All in Programming
富山発の個人開発サービスで日本中の学校の業務を改善した話
krpk1900
4
370
Honoとフロントエンドの 型安全性について
yodaka
4
280
2024年のWebフロントエンドのふりかえりと2025年
sakito
1
230
プログラミング言語学習のススメ / why-do-i-learn-programming-language
yashi8484
0
120
CloudNativePGがCNCF Sandboxプロジェクトになったぞ! 〜CloudNativePGの仕組みの紹介〜
nnaka2992
0
220
社内フレームワークとその依存性解決 / in-house framework and its dependency management
vvakame
1
550
Pythonでもちょっとリッチな見た目のアプリを設計してみる
ueponx
1
490
Grafana Cloudとソラカメ
devoc
0
140
Kanzawa.rbのLT大会を支える技術の裏側を変更する Ruby on Rails + Litestream 編
muryoimpl
0
220
動作確認やテストで漏れがちな観点3選
starfish719
6
1k
iOSエンジニアから始める visionOS アプリ開発
nao_randd
3
120
第3回 Snowflake 中部ユーザ会- dbt × Snowflake ハンズオン
hoto17296
4
360
Featured
See All Featured
Building an army of robots
kneath
302
45k
GitHub's CSS Performance
jonrohan
1030
460k
Music & Morning Musume
bryan
46
6.3k
Optimising Largest Contentful Paint
csswizardry
34
3.1k
Producing Creativity
orderedlist
PRO
343
39k
Writing Fast Ruby
sferik
628
61k
A designer walks into a library…
pauljervisheath
205
24k
Art, The Web, and Tiny UX
lynnandtonic
298
20k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
132
33k
A Tale of Four Properties
chriscoyier
158
23k
RailsConf 2023
tenderlove
29
1k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
8
270
Transcript
LALR parser generatorͷ࡞Γํ January 20, 2024 BuriKaigi 2024 @yui-knk Yuichiro
Kaneko
About me • Yuichiro Kaneko • yui-knk (GitHub) / spikeolaf
(Twitter) • Treasure Data • Engineering Manager of Applications Backend • The author of ruby/lrama LALR parser generator • CRuby committer, mainly develop parser related features
PR: We are hiring!! • https://www.treasuredata.com/company/jobs/
Parserͱ ͍ͧ͘ɺ͍ͧ͘ࢁ
Parserͷׂ • ೖྗ͞ΕͨจࣈྻʹߏΛ༩͑Δ Class Method Method Assignment @name Call Name
capitalize
Lexerͷׂ • ॲཧܥ(ruby)͔ΒΈΔͱͨͩͷόΠτྻ • ·ͣจࣈྻΛదͳ୯ҐͰ۠Δඞཁ͕͋Δ • Ruby͞·͟·ͳEncodingΛαϙʔτ͍ͯ͠Δ 636c61737320477265657465720a2020646566 20696e697469616c697a65286e616d65290a20 202020406e616d65203d206e616d652e636170
6974616c697a650a2020656e640a0a2020646 5662073616c7574650a2020202070757473202 248656c6c6f20237b406e616d657d21220a202 0656e640a656e640a class Greeter def
ParserͱLexer • Lexer͕tokenΛΓग़͠ɺParser͕ߏԽ͢Δ Class Method Method Assignm @name Call Name
capitaliz class Greeter def Lexer Parser
͍·RubyͰParser͕͍ https://twitter.com/OssVision/status/1735433960191299602
͍·RubyͰParser͕͍ • Bison͕ਏ͍ • BisonͷversionڥʹΑͬͯҟͳΔ • ෳͷBisonͷversionΛαϙʔτ͢ΔͨΊʹɺ৽͍͠ػೳ͕͑ͳ͍ • RubyͷparserෳࡶͰɺϝϯςφϯεੑ͕Β͘ࢹ͞Ε͖ͯͨ •
Language Server Protocolͷ಄ • RubyͰRBS(ܕ)RubyCop(੩తղੳث)ͱ͍ͬͨπʔϧ͕׆ൃʹ։ൃ ͞Ε͍ͯΔ • ͦͷ݁ՌɺϢʔβʔͷೖྗதͷϓϩάϥϜͱ͍͏ෆશͳೖྗΛύʔε͢ Δඞཁ͕Ͱ͖ͯͨ (ΤϥʔτϨϥϯτͳύʔαʔ) • ͜ΕΒΛղܾ͢ΔͨΊʹParserʹେنͳվળΛ͍Ε͍ͯΔ
Parserͷ࡞Γํ • खॻ͖parser • Parser GeneratorΛར༻ͯ͠ੜ͢Δ • Ruby Ͱͪ͜Βͷํ๏Λ࠾༻͍ͯ͠Δ •
Yacc, Bison, ANTLR ͳͲ • Lramaparser generator
Parser Generator • ઃఆϑΝΠϧΛͱʹparserΛੜ͢Δπʔϧ • RubyͰGNU BisonΛ͍··Ͱ͖ͬͯͨ • Ruby 3.3ͰBisonΛLramaʹஔ͖͑ͨ
• https://github.com/ruby/lrama ઃఆϑΝΠϧ parse.c Bison Lrama
ઃఆϑΝΠϧͷྫ • BNFͰจ๏Λهड़͢Δ • ͱͯΘ͔Γ͍͢
Parser Generatorͷར • จ๏͕ཧղ͍͢͠ • จ๏ఆٛͱύʔαʔͷ࣮ʹဃ͕ͳ͍ • จ๏ͷมߋʹରͯ͠ϑΟʔυόοΫΛಘΔ͜ͱ͕Ͱ͖Δ • ίϯϐϡʔλαΠΤϯεͷཧʹج͍͍ͮͯΔ
• ΤϥʔτϨϥϯτͳύʔαʔΛจ๏ఆ͔ٛΒࣗಈੜͰ͖Δ
LR parser͍͍ͧ • Bisonʹ͍Ζ͍Ζͱػೳ͕ෆ͍ͯ͠ΔͷͰ • RubyͰLrama LR parser generatorΛ࣮ͯ͠ •
RubyͰLramaΛ͏Α͏ʹ͢Δ͘Β͍ʹਪ͍ͯ͠Δ
Parser Generatorͷ ࡞Γํ ࢁʹண͍ͨʂ
ΞʔΩςΫνϟ • Frontend, Backend, Code Generator͔ΒͳΔ ઃఆϑΝΠϧ Parser Frontend Backend
Code Generator Parser Generator
Frontend • LexerͱParserΛ༻͍ͯઃఆϑΝΠϧΛ෦తͳσʔλߏʹม͢Δ • σʔλߏͷओRule ઃఆϑΝΠϧ ෦දݱ
Action • Actionͷ෦ղੳ͢Δඞཁ͕͋Δ • $$ͳͲͷಛघͳมͰtokenͷҐஔใʹΞΫηεͰ͖Δ • จ๏ϑΝΠϧͱผͷLexerΛ༻ҙ͢Δͷ͕Α͍ • มCodeੜ࣌ʹparser internalͳมʹஔ͖͑Δ
Backend • Rule͔ΒState MachineΛੜ͢Δ • ߏจղੳදͱ͍͏ͷཁ͢ΔʹΦʔτϚτϯ ߏจղੳද
• ֤RuleΛΦʔτϚτϯʹม͢Δ • શͯͷΦʔτϚτϯΛ߹ͨ͠ͷ͕ߏจղੳද LR parserstackΛͬͨDAF class A body end
def m1 body end class B body end
LALRҎ֎ͷΞϧΰϦζϜ • ߏจղੳͷͨΊͷΦʔτϚτϯͷ࡞Γํ͍Ζ͍Ζ͋Δ • LR(0), SLR(1), LALR(1), LR(1), IELR(1) ͳͲͷΞϧΰϦζϜ͕͋Δ
• ղੳՄೳͳݴޠඞཁͳϝϞϦ͕ͦΕͧΕҟͳΔ • Rule͔ΒΦʔτϚτϯΛ࡞ΔͷͰɺΞϧΰϦζϜͷબ͕จ๏ϑΝΠϧͷ γϯλοΫεͱಠཱ͍ͯ͠Δ
ߴͳLook-Aheadू߹ͷܭࢉ • LALR(1)Λ࣮͢Δͱ͖ʹʹͳΔͷ͕ɺޮతʹLook-Aheadू߹Λ ܭࢉ͢Δ͜ͱ • “Ef fi cient Computation of
LALR(1) Look-Ahead Sets” ͱ͍͏จͷΞ ϧΰϦζϜΛ༻͢ΔͱΑ͍ • https://dl.acm.org/doi/pdf/10.1145/69622.357187
Code Generator • State MachineΛλʔήοτͷݴޠʹ߹Θͤ ࣮ͯ͢Δ • tableΛࠓͷstateͱtokenͰݕࡧͯ࣍͠ʹΔ ͖͜ͱΛܾΊΔ •
shift, reduce, accept, error
TemplateʹΛຒΊࠐΉ • ࣮ࡍʹΔ͜ͱඞཁͳมΛཧͯ͠templateʹຒΊࠐΉ࡞ۀ • LramaͩͱERB, Bisonͩͱm4 • ERBҒେ
εύʔε(ૄ)ͳߏจղੳද • ॎ͕ঢ়ଶɺԣ͕τʔΫϯͷछྨͱ͍͏େ͖ͳςʔϒϧ • ઌ΄Ͳͷྫͩͱ70/238Ϛε͔͍ͬͯ͠ͳ͍ (29%͘Β͍)
εύʔε(ૄ)ͳߏจղੳද • ޓ͍ҧ͍ʹͯ͠1ͭͷྻʹ·ͱΊΔ • ίϯύΫτσʔλߏͰΑ͘ͳΒͳ͍ͩΖ͏͔?
ΞʔΩςΫνϟʔ • RuleͱState Machine͕ͦΕͧΕͷίϯϙʔωϯτؒͷΠϯλʔϑΣΠε ઃఆϑΝΠϧ ύʔαʔ Frontend Backend Code
Generator Rule State Machine
Parser GeneratorΛ ֦ு͢Δ ͔ʹඒຯͦ͠͏…
Named References • TokenͷͳͲʹΞΫηε͢Δͱ͖ʹ$1, $2Ͱͳ͘ɺ$cpath, $bodyͱ ໊લͰΞΫηεͰ͖Δ • Lexerͷ࣮͚ͩͰ࣮ݱͰ͖ΔͷͰFrontend͚ͩͷมߋͰ࣮ݱͰ͖ͨ
Parameterizing Rules • ෳճͷ܁Γฦ͠ͱ͍͏ͷจ๏ఆ্ٛΑ͘ग़ ͯ͘Δ • ॻ͖ํͷύλʔϯ͕ܾ·͍ͬͯΔͷͰ͋Εɺͦ ΕΛநԽͯ͠ॻ͖͍ͨ • LramaͰ࣮ͣΈ
Parameterizing Rules • ઃఆϑΝΠϧ͔ΒRuleͷσʔλߏΛͭ͘Δͱ͖ʹల։͢Δ͚ͩͳͷͰɺ Frontend͚ͩͷมߋͰ࣮ݱͰ͖Δ
%after-shift • RipperͷΑ͏ͳ໘ന͍ػೳΛ࣮͠Α͏ͱ͢ΔͱShift͢Δॠؒ Reduce͢ΔॠؒʹcallbackΛ͜͞͠Έͨ͘ͳΔ • Frontendͷparser/lexerͱCode GeneratorͷtemplateΛ͍͡ΕͰ͖ Δ
·ͱΊ ͦΖͦΖᲳ͕৯͍ͨ…
·ͱΊ • LR parser͍͍ͧ • LR parser generator3ͭͷίϯϙʔωϯτ͔ΒͳΓɺݴޠॲཧܥʹߏ͕ࣅ ͍ͯΔ •
ׂ͞Ε͍ͯΔͨΊػೳՃͷࡍʹඞཁͳίϯϙʔωϯτ͚ͩΛมߋ͢Ε͍͍ • Lrama parser generatorΨϯΨϯ։ൃத • ͔Ͷ͜ʹ͖ͬͰRubyͷparserͷ։ൃঢ়گΛ·ͱΊ͍ͯΔ • https://yui-knk.hatenablog.com/ • ruby-jpͱ͍͏slackͷ #lr-parser νϟωϧʹීஈ͍Δ
RubyKaigi 2024
Thank you!!