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
2.1k
Rubyで書くParser (自力かライブラリか、それが問題だ)
2017.Nov 福岡Ruby会議02 でのセッション資料です。Parser書いたら楽しいよというお話。
やきとりい
November 25, 2017
Tweet
Share
More Decks by やきとりい
See All by やきとりい
社会の中のわたしの技術 ─ 自分の地図の描き方 #wttjp
yotii23
0
830
Rubyと自由とAIと
yotii23
6
2.7k
Railsの勉強のすすめかた
yotii23
0
150
株式会社万葉「自分ごと」としての産休・育休(持続的エンジニア人生のための組織戦略) #enechange_meetup
yotii23
4
750
Reading and improving Pattern Matching in Ruby
yotii23
0
280
10年前のRails Girls Japanむかしばなしとわたし #rggjp #rgjp10th
yotii23
3
560
Rubyから広がるプログラミング入門教育〜小学校高学年向けプログラミング入門書『ユウと魔法のプログラミング・ノート』執筆から学んだこと〜
yotii23
2
920
質問を”聴く”技術
yotii23
23
14k
ダイバシティな絵本のご紹介
yotii23
0
3.1k
Other Decks in Programming
See All in Programming
AIでLINEスタンプを作ってみた
eycjur
1
230
ProxyによるWindow間RPC機構の構築
syumai
3
1.2k
基礎から学ぶ大画面対応(Learning Large-Screen Support from the Ground Up)
tomoya0x00
0
490
デザイナーが Androidエンジニアに 挑戦してみた
874wokiite
0
470
Vue・React マルチプロダクト開発を支える Vite
andpad
0
110
概念モデル→論理モデルで気をつけていること
sunnyone
2
190
Performance for Conversion! 分散トレーシングでボトルネックを 特定せよ
inetand
0
160
はじめてのMaterial3 Expressive
ym223
2
440
🔨 小さなビルドシステムを作る
momeemt
4
680
プロパティベーステストによるUIテスト: LLMによるプロパティ定義生成でエッジケースを捉える
tetta_pdnt
0
330
@Environment(\.keyPath)那么好我不允许你们不知道! / atEnvironment keyPath is so good and you should know it!
lovee
0
120
AIと私たちの学習の変化を考える - Claude Codeの学習モードを例に
azukiazusa1
10
4.1k
Featured
See All Featured
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.4k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
112
20k
Documentation Writing (for coders)
carmenintech
74
5k
A Tale of Four Properties
chriscoyier
160
23k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
131
19k
Building Adaptive Systems
keathley
43
2.7k
The Art of Programming - Codeland 2020
erikaheidi
56
13k
What’s in a name? Adding method to the madness
productmarketing
PRO
23
3.7k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
48
9.7k
How STYLIGHT went responsive
nonsquared
100
5.8k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
162
15k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
333
22k
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ʹग़ձ͍͖ͬͯ·͠ΐ͏ɺ ͋Γ͕ͱ͏͍͟͝·ͨ͠ɻ