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
6.2k
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
Ruby's Line Breaks
yui_knk
4
4.2k
What is Parser
yui_knk
11
5.2k
Ruby Parser progress report 2024
yui_knk
2
400
最高の構文木の設計 2024年版
yui_knk
9
5.8k
Converting AST
yui_knk
4
350
My favorite script, "dsl.rb"
yui_knk
2
1.2k
Rearchitect Ripper
yui_knk
2
1.2k
The grand strategy of Ruby Parser
yui_knk
7
10k
Declarative parse.y
yui_knk
2
5.6k
Other Decks in Programming
See All in Programming
「ElixirでIoT!!」のこれまでとこれから
takasehideki
0
350
A comprehensive view of refactoring
marabesi
0
110
ReadMoreTextView
fornewid
1
360
UPDATEがシステムを複雑にする? イミュータブルデータモデルのすすめ
shimomura
1
530
Javaに鉄道指向プログラミング (Railway Oriented Pro gramming) のエッセンスを取り入れる/Bringing the Essence of Railway-Oriented Programming to Java
cocet33000
2
540
Team topologies and the microservice architecture: a synergistic relationship
cer
PRO
0
100
実はすごいスピードで進化しているCSS
hayato_yokoyama
0
110
Perlで痩せる
yuukis
1
680
つよそうにふるまい、つよい成果を出すのなら、つよいのかもしれない
irof
1
280
XSLTで作るBrainfuck処理系
makki_d
0
190
プロダクト開発でも使おう 関数のオーバーロード
yoiwamoto
0
150
PT AI без купюр
v0lka
0
230
Featured
See All Featured
The Straight Up "How To Draw Better" Workshop
denniskardys
233
140k
Docker and Python
trallard
44
3.4k
Speed Design
sergeychernyshev
30
990
How to Think Like a Performance Engineer
csswizardry
24
1.7k
Making Projects Easy
brettharned
116
6.2k
"I'm Feeling Lucky" - Building Great Search Experiences for Today's Users (#IAC19)
danielanewman
228
22k
Testing 201, or: Great Expectations
jmmastey
42
7.5k
Agile that works and the tools we love
rasmusluckow
329
21k
The MySQL Ecosystem @ GitHub 2015
samlambert
251
13k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
3.9k
Why You Should Never Use an ORM
jnunemaker
PRO
56
9.4k
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!!