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
Let’s write a parser! [SoundCloud HQ edition]
Search
Denis Defreyne
May 17, 2016
Programming
0
210
Let’s write a parser! [SoundCloud HQ edition]
Denis Defreyne
May 17, 2016
Tweet
Share
More Decks by Denis Defreyne
See All by Denis Defreyne
The importance of naming
ddfreyne
0
55
An introduction to fibers
ddfreyne
0
160
Code as data (RubyConfBY 2019 edition)
ddfreyne
0
95
Code as data
ddfreyne
0
140
How to memoize
ddfreyne
0
150
Clean & fast code with enumerators
ddfreyne
0
110
Fibers
ddfreyne
0
440
Let’s create a programming language! [SoundCloud HQ edition]
ddfreyne
0
190
Let’s create a programming language! [RUG::B edition]
ddfreyne
1
210
Other Decks in Programming
See All in Programming
Sidekiqで実現する 長時間非同期処理の中断と再開 / Pausing and Resuming Long-Running Asynchronous Jobs with Sidekiq
hypermkt
6
2.7k
Honoの来た道とこれから
yusukebe
19
3.1k
LLM生成文章の精度評価自動化とプロンプトチューニングの効率化について
layerx
PRO
2
140
外部システム連携先が10を超えるシステムでのアーキテクチャ設計・実装事例
kiwasaki
1
230
Jakarta Concurrencyによる並行処理プログラミングの始め方 (JJUG CCC 2024 Fall)
tnagao7
1
240
ピラミッド、アイスクリームコーン、SMURF: 自動テストの最適バランスを求めて / Pyramid Ice-Cream-Cone and SMURF
twada
PRO
9
1k
offers_20241022_imakiire.pdf
imakurusu
2
370
CSC509 Lecture 09
javiergs
PRO
0
110
リリース8年目のサービスの1800個のERBファイルをViewComponentに移行した方法とその結果
katty0324
5
3.6k
gopls を改造したら開発生産性が高まった
satorunooshie
8
250
Kaigi on Rails 2024 - Rails APIモードのためのシンプルで効果的なCSRF対策 / kaigionrails-2024-csrf
corocn
5
3.4k
Dev ContainersとGitHub Codespacesの素敵な関係
ymd65536
1
130
Featured
See All Featured
The World Runs on Bad Software
bkeepers
PRO
65
11k
Designing on Purpose - Digital PM Summit 2013
jponch
115
6.9k
Become a Pro
speakerdeck
PRO
24
5k
Reflections from 52 weeks, 52 projects
jeffersonlam
346
20k
KATA
mclloyd
29
13k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
47
5k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
228
52k
Fight the Zombie Pattern Library - RWD Summit 2016
marcelosomers
231
17k
4 Signs Your Business is Dying
shpigford
180
21k
The Invisible Side of Design
smashingmag
297
50k
Building Flexible Design Systems
yeseniaperezcruz
327
38k
Speed Design
sergeychernyshev
24
570
Transcript
Let’s write a parser! DENIS DEFREYNE / SOUNDCLOUD, BERLIN /
MAY 17TH, 2016
1. Language 2
I am Denis. 3
But how do you know that I am Denis? 4
But how do you know that I am Denis? I
told you. I wrote it down. You’ve probably seen me before. Etc. 5
But how do you know that I am Denis? You
understand English. 6
Computers are stupid. 7
8 $ git commit --message="Fix bugs"
9 def greet(name) puts "Hello, #{name}" end
10 def greet(name: String): Unit = { println(s"Hello, $name!") }
Text forms a language, but computers don’t know that. 11
2. Parsing 12
Basic idea: 13 Parser objects that are small, composable, and
purely functional.
14 def read(input, pos)
15 def read(input, pos) Success.new(pos + 1) end
16 def read(input, pos) Failure.new(pos) end
17 char("H") Succeeds if the next character is the given
one.
18 char("H").apply("Hello")
18 H e l l o char("H").apply("Hello")
18 H e l l o 0 1 2 3
4 char("H").apply("Hello")
18 H e l l o 0 1 2 3
4 char("H").apply("Hello")
18 H e l l o 0 1 2 3
4 char("H").apply("Hello")
18 H e l l o 0 1 2 3
4 char("H").apply("Hello") Success(pos = 1)
19 char("H").apply("Adiós")
19 A d i ó s 0 1 2 3
4 char("H").apply("Adiós")
19 A d i ó s 0 1 2 3
4 char("H").apply("Adiós")
19 A d i ó s 0 1 2 3
4 char("H").apply("Adiós")
Failure(pos = 0) 19 A d i ó s 0
1 2 3 4 char("H").apply("Adiós")
20 if input[pos] == @char Success.new(pos + 1) else Failure.new(pos)
end
21 seq(a, b) Succeeds if both given parsers succeed in
sequence.
22 seq(char("H"), char("e")).apply("Hello")
H e l l o 22 0 1 2 3
4 seq(char("H"), char("e")).apply("Hello")
H e l l o 22 0 1 2 3
4 seq(char("H"), char("e")).apply("Hello")
H e l l o 22 0 1 2 3
4 seq(char("H"), char("e")).apply("Hello")
H e l l o 22 0 1 2 3
4 seq(char("H"), char("e")).apply("Hello")
H e l l o 22 0 1 2 3
4 seq(char("H"), char("e")).apply("Hello") Success(pos = 2)
23 seq( char("H"), char("e"), char("l"), char("l"), char("o"), )
24 string(s) Succeeds if all characters in the given string
can be read in sequence.
H e l l o 25 0 1 2 3
4 string("Hello").apply("Hello")
H e l l o 25 0 1 2 3
4 string("Hello").apply("Hello")
H e l l o 25 0 1 2 3
4 string("Hello").apply("Hello")
H e l l o 25 0 1 2 3
4 string("Hello").apply("Hello") Success(pos = 5)
26 eof() Succeeds at the end of input; fails otherwise.
H e l l o 27 0 1 2 3
4 seq(string("Hello"), eof).apply("Hello")
H e l l o 27 0 1 2 3
4 seq(string("Hello"), eof).apply("Hello")
H e l l o 27 0 1 2 3
4 seq(string("Hello"), eof).apply("Hello")
H e l l o 27 0 1 2 3
4 seq(string("Hello"), eof).apply("Hello")
H e l l o 27 0 1 2 3
4 seq(string("Hello"), eof).apply("Hello") Success(pos = 5)
28 0 1 2 3 4 5 H e l
l o ! seq(string("Hello"), eof).apply("Hello!")
28 0 1 2 3 4 5 H e l
l o ! seq(string("Hello"), eof).apply("Hello!")
28 0 1 2 3 4 5 H e l
l o ! seq(string("Hello"), eof).apply("Hello!")
28 0 1 2 3 4 5 H e l
l o ! seq(string("Hello"), eof).apply("Hello!")
28 0 1 2 3 4 5 Failure(pos = 5)
H e l l o ! seq(string("Hello"), eof).apply("Hello!")
29 alt(a, b) Succeeds if either of the given parsers
succeed.
A d i ó s 30 0 1 2 3
4 alt(char("H"), char("A")).apply("Adiós")
A d i ó s 30 0 1 2 3
4 alt(char("H"), char("A")).apply("Adiós")
A d i ó s 30 0 1 2 3
4 alt(char("H"), char("A")).apply("Adiós")
A d i ó s 30 0 1 2 3
4 alt(char("H"), char("A")).apply("Adiós") Success(pos = 1)
31 whitespace_char = alt( char(" "), char("\t"), char("\r"), char("\n"), )
32 opt(p) Succeeds always, but only advances if p succeeds.
33 repeat(p) Succeeds always, and attempts to apply p as
often as possible.
34 repeat(whitespace_char)
35 intersperse(a, b) Alternates between a and b., always ending
with a.
36 intersperse(char("a"), char(",")).apply("a,a,b")
a , a , b 36 0 1 2 3
4 intersperse(char("a"), char(",")).apply("a,a,b")
a , a , b 36 0 1 2 3
4 intersperse(char("a"), char(",")).apply("a,a,b")
a , a , b 36 0 1 2 3
4 intersperse(char("a"), char(",")).apply("a,a,b")
a , a , b 36 0 1 2 3
4 intersperse(char("a"), char(",")).apply("a,a,b")
a , a , b 36 0 1 2 3
4 intersperse(char("a"), char(",")).apply("a,a,b") Success(pos = 3)
37 etc.
3. Examples 38
39 720 6 29530
40 digit = alt( *('0'..'9') .map { |c| char(c) }
)
41 digit = char_in('0'..'9')
42 digit = char_in('0'..'9') nat_number = seq(digit, repeat(digit))
43 digit = char_in('0'..'9') nat_number = repeat1(digit)
44 digit = char_in('0'..'9') nat_number = repeat1(digit) .capture
44 digit = char_in('0'..'9') nat_number = repeat1(digit) .capture
Success(pos = 3, data = "720")
45 def read(input, pos)
46 def read(input, pos) Success.new(pos + 1) end
47 def read(input, pos) Success.new(pos + 1, "blahblah") end
48 dec_number = seq( nat_number, char('.'), nat_number, )
49 Horan,Niall,93 Payne,Liam,93 Tomlinson,Louis,91 Styles,Harry,94 Malik,Zayn,93
50 field = repeat(char_not_in(',', "\n")) line = intersperse(field, char(',')) file
= seq( line.intersperse(char("\n")), eof(), )
50 field = repeat(char_not_in(',', "\n")) line = intersperse(field, char(',')) file
= seq( line.intersperse(char("\n")), eof(), )
50 field = repeat(char_not_in(',', "\n")) line = intersperse(field, char(',')) file
= seq( line.intersperse(char("\n")), eof(), )
50 field = repeat(char_not_in(',', "\n")) line = intersperse(field, char(',')) file
= seq( line.intersperse(char("\n")), eof(), )
51 Horan,Niall,93 Payne,Liam,93 Tomlinson,Louis,91 Styles,Harry,94 Malik,Zayn,93
52 [ ["Horan", "Niall", 93], ["Payne", "Liam", 93], ["Tomlinson", "Louis",
91], ["Styles", "Harry", 94], ["Malik", "Zayn", 93], ]
53 add(1, mul(2, 3)) sub(5, 4)
54 lparen = char('(') rparen = char(')') comma = char(',')
55 expr = alt(lazy { funcall }, nat_number)
56 funcall = seq( identifier, lparen, arg_list, rparen, )
57 letter = char_in('a'..'z') identifier = repeat1(letter)
58 arg_list = intersperse( expr, seq(comma, whitespace), )
59 arg_list = opt( intersperse( expr, seq(comma, whitespace), ) )
60
60 expr_list = intersperse(expr, char("\n"))
60 expr_list = intersperse(expr, char("\n")) program = seq(expr_list, eof)
61 add(1, mul(2, 3)) sub(5, 4)
62 Success(pos = 27)
Where’s the data!!! 63
64 funcall = seq( identifier, lparen, arg_list, rparen, )
65 funcall = seq( identifier.capture, lparen, arg_list, rparen, )
66 funcall = seq( identifier.capture, lparen, arg_list, rparen, ).map do
|data| # stuff here end
67 funcall = seq( identifier.capture, lparen, arg_list, rparen, ).map do
|data| FunCall.new(data[0], data[2]) end
68 add(1, mul(2, 3)) sub(5, 4)
69 [ FunCall.new("add", [ 1, FunCall.new("mul", [2, 3]), ]), FunCall.new("sub",
[5, 4]), ]
And that is how you can write a parser. 70
And that is how you can write a parser using
parser combinators. 71
72 ḌPARSE
72 ḌPARSE A GOOD PARSER LIBRARY FOR RUBY
github.com/ddfreyne/d-parse 73
github.com/ddfreyne/d-parse 73
github.com/ddfreyne/d-parse 73
74
74 require 'd-parse'
74 require 'd-parse' module JSONGrammar
74 require 'd-parse' module JSONGrammar extend DParse::DSL
74 require 'd-parse' module JSONGrammar extend DParse::DSL DIGIT = char_in('0'..'9')
NUMBER = repeat1(DIGIT) end
74 require 'd-parse' module JSONGrammar extend DParse::DSL DIGIT = char_in('0'..'9')
NUMBER = repeat1(DIGIT) end res = Grammar::NUMBER.apply('8700')
75
75 case res
75 case res when DParse::Success puts(res.data.inspect)
75 case res when DParse::Success puts(res.data.inspect) when DParse::Failure $stderr.puts res.pretty_message
exit(1) end
76 expected identifier at line 1, column 36 def
reticulate(splines, threshold, ) { ↑
77 github.com/ddfreyne/d-parse
77 github.com/ddfreyne/d-parse PRE- ALPHA! BE AN EARLY ADOPTER!
78 My name is Denis. Ready to parse your questions.
Find me at
[email protected]
, or @denis on Slack.