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.3k
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
Cursor AI Agentと伴走する アプリケーションの高速リプレイス
daisuketakeda
1
120
実践ArchUnit ~実例による検証パターンの紹介~
ogiwarat
2
280
Bytecode Manipulation 으로 생산성 높이기
bigstark
2
360
[初登壇@jAZUG]アプリ開発者が気になるGoogleCloud/Azure+wasm/wasi
asaringo
0
130
社内での開発コミュニティ活動とモジュラーモノリス標準化事例のご紹介/xPalette and Introduction of Modular monolith standardization
m4maruyama
1
130
コード書くの好きな人向けAIコーディング活用tips #orestudy
77web
3
320
エンジニア向け採用ピッチ資料
inusan
0
140
単体テストの始め方/作り方
toms74209200
0
510
型付きアクターモデルがもたらす分散シミュレーションの未来
piyo7
0
800
エラーって何種類あるの?
kajitack
5
260
ReadMoreTextView
fornewid
1
450
Development of an App for Intuitive AI Learning - Blockly Summit 2025
teba_eleven
0
120
Featured
See All Featured
Testing 201, or: Great Expectations
jmmastey
42
7.5k
A Tale of Four Properties
chriscoyier
159
23k
Building a Scalable Design System with Sketch
lauravandoore
462
33k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
29
1.8k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
How GitHub (no longer) Works
holman
314
140k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
331
22k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
Large-scale JavaScript Application Architecture
addyosmani
512
110k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
233
17k
Balancing Empowerment & Direction
lara
1
340
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!!