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
Rubyで書くParser (自力かライブラリか、それが問題だ)
Search
やきとりい
November 25, 2017
Programming
3
1.8k
Rubyで書くParser (自力かライブラリか、それが問題だ)
2017.Nov 福岡Ruby会議02 でのセッション資料です。Parser書いたら楽しいよというお話。
やきとりい
November 25, 2017
Tweet
Share
More Decks by やきとりい
See All by やきとりい
Reading and improving Pattern Matching in Ruby
yotii23
0
130
10年前のRails Girls Japanむかしばなしとわたし #rggjp #rgjp10th
yotii23
3
400
Rubyから広がるプログラミング入門教育〜小学校高学年向けプログラミング入門書『ユウと魔法のプログラミング・ノート』執筆から学んだこと〜
yotii23
2
730
質問を”聴く”技術
yotii23
21
12k
ダイバシティな絵本のご紹介
yotii23
0
2.9k
翻訳で橋をかける
yotii23
5
780
「わたし」をふくんで世界は広がる #DevFestWomen
yotii23
2
1.3k
30冊超のプログラミング教育本を読んだわたしの考えるさいきょうのこどもむけプログラミング本の選び方#meetup_kb
yotii23
2
1.6k
株式会社万葉会社説明 #tokyogirlsrb
yotii23
4
18k
Other Decks in Programming
See All in Programming
TypeScriptのパフォーマンス改善
yajihum
14
5.1k
Productivity is Messing Around and Having Fun
hollycummins
1
180
欠陥を早期に発見するための Software Engineer in Test とその重要性 / What is Software Engineer in Test and How they works
orgachem
PRO
17
2.4k
AmperとFleetを使ったAndroidアプリ
yoppie
0
300
Namespace, What and Why
tagomoris
3
680
GoでParserを書く
karupanerura
3
350
Let's learn code review
riofujimon
2
640
An adventure of Happy Eyeballs
coe401_
1
150
JavaScript Closure
asoluka
0
2k
Open standards for building event-driven applications in the cloud
meteatamel
0
230
Try creating your own orderedmap
kazamori
1
280
Revisiting the Hotwire Landscape after Turbo 8 @ RailsConf 2024, Detroit
marcoroth
3
610
Featured
See All Featured
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
188
16k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
660
120k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
245
20k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
26
2.3k
Making Projects Easy
brettharned
109
5.5k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
358
22k
Fontdeck: Realign not Redesign
paulrobertlloyd
76
4.9k
Building Flexible Design Systems
yeseniaperezcruz
320
37k
Adopting Sorbet at Scale
ufuk
69
8.6k
Unsuck your backbone
ammeep
664
57k
Intergalactic Javascript Robots from Outer Space
tanoku
266
26k
Embracing the Ebb and Flow
colly
80
4.2k
Transcript
RUBYͰॻ͘PARSER (ࣗྗ͔ϥΠϒϥϦ͔ɺͦΕ͕ͩʣ 2017.Nov ԬRubyձٞ02 ௗҪઇ
ௗҪઇ ࣗݾհ w גࣜձࣾສ༿ۈ w 3BJMTΞϓϦέʔγϣϯΤϯδχΞ w 3BJMT(JSMT5PLZPOEΦʔΨφΠβʔ w ༁ॻʹ
w ʰϓϩάϥϛϯά&MJYJSʱ %BWF5IPNBTɺΦʔϜࣾ ాߞҰͱڞ༁ w ʰϧϏΟͷ΅͏͚ΜʱγϦʔζ ϦϯμɾϦΧεஶɹᠳӭࣾ
ௗҪઇ ࣗݾհ ੜ·ΕԬ ౦۠ശ࡚খֶߍ ஜࢵঁֶԂதֶߍ ஜࢵঁֶԂߴֶߍ => େֶ͔Β౦ژ ͍ͭͷؒʹ͔ϓϩάϥϚʹ 2012ԬRubyձٞ01
LT 2015 RailsGirls Fukuoka ίʔν Ԭ ظ ؒ
None
RUBY Ͱॻ͘PARSER ͘͡ • ͳͥParserΛॻ͘͜ͱʹͳͬͨͷ͔ • ઃܭ • ParserΉ͔͍ͣ͠ʂ •
Treetop ͱ͍͏ gem • ͦΕͰָ͍ࣗ͠࡞ParserʢͨͿΜΊͨ΄͏͕͍͍ʣ
ͳͥPARSERΛॻ͘͜ͱʹͳͬͨͷ͔ ͦΕͪΐͬͱͨ͠ग़དྷ৺ͩͬͨ
RUBYʹELIXIRʢ̍ Έ͍ͨͳ ύλʔϯϚονϯάʢ2 ΄͍͠… 1 Elixir: Erlang VM্Ͱಈ͘ϓϩάϥϛϯάݴޠ 2 ύλʔϯϚονϯάɿElixirʹ͋Δ͔͍͍ͬ͜ػೳ
=~ ͰϚονͤͯ͞ύλʔϯมͱ͍͍ͯͨ͠ RUBYͰॻ͖͍ͨύλʔϯϚον
=== ͰϚον͍ͤͨ͞ʢCASEจॻ͖͍ͨʣ RUBYͰॻ͖͍ͨύλʔϯϚον
͜Εʢ̍ ͕ಈ͘ͱ આಘྗ͕͋ΔΜ͡Όͳ͍͔…ʢ2 1 ࠷ॳ༷͚ͩເݟͯͨ 2 ݁ہઆಘྗ͕͔͋ͬͨෆ໌
ͬͯΈͨ ʢRUBY KAIGI YOUTUBE HTTPS://WWW.YOUTUBE.COM/WATCH? V=1M4IPJH0K0E&INDEX=19&T=6S&LIST=PL
RUBYΠϯλϓϦλͷCͷίʔυͷࠩ͜Ε͚ͩ ͬͯΈͨ compile.c parse.y
ʢಈ͚ྑ͠ɺύϑΥʔϚϯεͳͲߟ͑ͳ͍ͷͱ͢Δʣ ઃܭ Ruby script Parse Compile Ruby byte code Evaluator
ʢಈ͚ྑ͠ɺύϑΥʔϚϯεͳͲߟ͑ͳ͍ͷͱ͢Δʣ ઃܭ Ruby script Parse Compile Ruby byte code PatternMatching
%p([a, ‘bc’]) =~ [3, ‘bc’] “[a, ‘bc’]” มϦετ[“a”] มͷఆٛ Evaluator pattern_match obj Parse pattern Binding ΛͱΔͨΊʹ͝ʹΐΔ ASTߏங Ϛον͢Δ͔νΣοΫ มೖ RubyͷClass
ʢಈ͚ྑ͠ɺύϑΥʔϚϯεͳͲߟ͑ͳ͍ͷͱ͢Δʣ ઃܭ Ruby script Parse Compile Ruby byte code PatternMatching
%p([a, ‘bc’]) =~ [3, ‘bc’] “[a, ‘bc’]” มϦετ[“a”] มͷఆٛ Evaluator pattern_match obj Parse pattern Binding ΛͱΔͨΊʹ͝ʹΐΔ RubyͷClass ࠓͷίί‼︎ ASTߏங Ϛον͢Δ͔νΣοΫ มೖ
ʢPATTERN MATCHING ΫϥεͷʣPARSERͷΔ͜ͱ ྫ͑ `%p ([a, ‘bc’])`ͱ͍͏ύλʔϯ͕ࢦఆ͞Εͨ߹ɺ “[a, ‘bc’]” ͱ͍͏จࣈྻΛड͚औͬͯ…
• छྨ:ʮྻʯͰ͋Δ • ཁૉͷҰ൪͕มaͰ͋Δ • ཁૉͷೋ൪͕จࣈྻ ͷ ‘bc’ Ͱ͋Δ • ඞཁͳύλʔϯมͷϦετɿ[a]Ͱ͋Δ ͜ͱΛղੳͯ͠ɺߏʹ͢Δ
%p([a, ‘bc’]) =~ [3, ‘bc’] PARSEͷྲྀΕ “[a, `bc`]” [ ͱ
a ͱ , ͱ `bc` ͱ ] Tokenize จࣈྻ Tokens AST ASTߏங String Node (‘bc’) Array Node Variable Node (a) 1 AST࡞Δͱ͖ʹࠓճύλʔϯมϦετ࡞Δ
PARSEͷྲྀΕ “{status: 200, users: [a, b] }” { ͱ status:
ͱ 200 ͱ , ͱ users: ͱ [ ͱ aͱ , ͱ b ͱ ] ͱ } Tokenize จࣈྻ Tokens ASTߏங %p({status: 200, users: [a, b] }) =~ {status: 200, users: [1, 3] } AST Variable Node (b) val:Array Node Variable Node (a) Hash Node val: Integer Node (200) key: Symbol Node (:status) key: Symbol Node (:users)
࠷ऴతʹཉ͍͠ͷAST %p({status: 200, users: [a, b] }) =~ {status: 200,
users: [1, 3] } AST Variable Node (b) val:Array Node Variable Node (a) Hash Node val: Integer Node (200) key: Symbole Node (:status) key: Symbole Node (:users) {status: 200, users: [a, b] } ɹASTΛḷͬͯɺͱύλʔϯͱϚον͢Δ͔ΛௐΔ Ϛονର ͦͦhash? key ͕ status: ͷ val 200? key ͕users: ͷ val ྻʁ ྻͷཁૉ2? ྻͷཁૉͷ1൪Λมaʹ֨ೲ͠Αʔ ྻͷཁૉͷ2൪Λมbʹ֨ೲ͠Αʔ
Ή͔͔ͣͬͨ͠ ʢͱ͘ʹTOKENIZE ʣ
Tokenize “[a, `bc`]” [ ͱ a ͱ , ͱ `bc`
ͱ ] Tokenize จࣈྻ Tokens Tokens Token ͷλΠϓΛݟͯɺʮ͓ͬྻͷ։͖ه߸͕དྷ͔ͨΒɺ͜ͷޙྻ͕ด͡ Δ·ͰྻͷதͩͳʯΈ͍ͨʹASTΛ࡞ͬͯΏ͘ λΠϓ [ ྻͷ։͖ه߸ a ม , ΧϯϚ `bc` จࣈྻɹ ] ྻͷด͡ه߸
ͬͨͷStringScanner#scan Tokenize • StringScanner#scan • จࣈྻΛ಄͔ΒεΩϟϯͯ͠ɺਖ਼نදݱʹϚονͨ͠ΒϚον෦ Λฦͯͦ͠ͷޙΖ·ͰindexΛ͢͢ΊΔ “[a, `bc`]” [
a , `bc` ] ਖ਼نදݱ λΠϓ /\[/ ྻͷ։͖ ه߸ /[a-z_][a-z0-9_]*/ ม /,/ ΧϯϚ /'.*?'/ จࣈྻɹ /\]/ ྻͷด͡ ه߸ “a, `bc`]” “`bc`]” “]” “[a, `bc`]” จࣈྻ Tokens Scan
ίϛοτ࣌ʹ ྫɿεϖʔε͕2ͭҎ্ʹͳΔͱࣦഊ͢Δόά “[a, `bc`]” “[a, `bc`]”
ͯ͠ͳ͍ʢ͕ΜΔʣ ྫɿࣗ͘͝વʹ{} Λলུͯ͠͏͔͝ͳ͍ϋογϡ %p({ user: 1, from: ‘Fukuoka’}) %p( user:
1, from: ‘Fukuoka’ )
TOKENIZEʹҰͷਖ਼نදݱηοτ͔͠దԠͰ͖ͳ͍ ྫɿ͋ΔλΠϓͷTOKENIZEಠࣗϧʔϧͳͲ͕ѻ͍͑ͯͳ͍ “Name is #{user.name}”
• %p( [x, :y, { "array" => [5, v] }]
) ͘Β͍·ͰParseͰ͖ΔΑ͏ʹͳͬͨ • ࣗྗͰҰ͔ΒParserΛॻ͘ͷ͔ͳΓߝΓ • ֦ுੑʹݶք͋ΔʢΘͨ͠ʹʣ
PARSERΛॻ͍ͯΈΔͱ… • ࠓ·Ͱࣗ͘͝વʹಡΈॻ͖͍ͯͨ͠`[1, 2, 3]` `{status: 200, users: [1, 2]
}`ͳͲ͕ɺ ಥવʮ͜Ε͔Βղऍ͞ΕΔʢ·ͩҙຯΛ࣋ͨͳ͍ʣจࣈྻʯͱ ͯ͠ͷલʹݱΕΔ • εϖʔεɺΧϯϚɺͯ͢ʹҙຯ͕͋Δ • Rubyຊମͷparse͍͢͝ • ਓؒͷ͍͢͝
·͞ʹʮ͏Ұɺ RUBYͱग़ձ͏ʯମݧ
https://github.com/cjheath/treetop ͱ͜ΖͰTreetopͱ͍͏gem͕͋Γ·͢ • PEGϕʔεͷಠࣗͷهड़ํࣜͰਖ਼نදݱͳͲΛͬͯจ๏ϧʔϧΛఆ ٛ͢Δ.treetopϑΝΠϧΛͭ͘Δ • ttίϚϯυʹͦͷϑΝΠϧΛ͢ͱɺͦΕΛݩʹrubyͷparserϑΝΠ ϧΛ࡞ͬͯ͘ΕΔ • ੜ͞ΕͨrubyϑΝΠϧΛrequire
͢Δ͜ͱͰɺsyntaxnode, ͍ΘΏ ΔASTΛߏங͢ΔParserΛ͏͜ͱ͕Ͱ͖Δ • ϧʔϧͷωετͷهड़༰қ
࠷ॳ͔ΒTREETOPΛ ͑ྑ͔ͬͨͷͰ…
ࣗ࡞PARSERͱTREETOPൺֱද ࣗ࡞ Treetop هड़ͷચ࿅ ϧʔϧͷωετ όάͷग़ʹ͘͞ Rubyͱग़ձ͑Δ
ʢෛ͚੯͠Έ͚ͩͰͳ͍ʣ ͦΕͰָ͍ࣗ͠࡞PARSER • ͦͦ࡞Γ࢝Ίͨஈ֊ͰʮParserʯͱ͍͏ͷ͕΅ΜΓ͔͠ཧ ղͰ͖ͯͳ͔ͬͨ • ͜ͷஈ֊ͰTreetopΛͬͯɺநෛ͚͍ͯ͜͠ͳͤͳ͔ͬͨ ͷͰͳ͍͔ • ͍·͍ํ͕Θ͔Βͳͯ͘Treetopͷੜͨ͠Ruby
ParserΛಡΉͱ ؾ͕࣋ͪΘ͔Δ • ࣗͷίʔυ͕શ෦จࣈྻʹݟ͑ΔମݧϓϥΠεϨε • ंྠͷ࠶ൃ໌Ͱ͍͍ɺंྠ͕৺ͷதʹΈཱͯΒΕΔͷେࣄ
ˎ͋ΔఔҎ্ෳࡶͳ͜ͱΛ ͠Α͏ͱ͢Δͱߦ͖٧·Δɺ ͦΖͦΖΓ͑Δͷ͕٢ˎ
ԿͰ RUBYʹग़ձ͍͖ͬͯ·͠ΐ͏ɺ ͋Γ͕ͱ͏͍͟͝·ͨ͠ɻ