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! [RUG::B edition]
Search
Denis Defreyne
May 12, 2016
Programming
3
220
Let’s write a parser! [RUG::B edition]
Denis Defreyne
May 12, 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
Streams APIとTCPフロー制御 / Web Streams API and TCP flow control
tasshi
1
310
[PyCon Korea 2024 Keynote] 커뮤니티와 파이썬, 그리고 우리
beomi
0
110
Pinia Colada が実現するスマートな非同期処理
naokihaba
2
160
レガシーな Android アプリのリアーキテクチャ戦略
oidy
1
170
Jakarta Concurrencyによる並行処理プログラミングの始め方 (JJUG CCC 2024 Fall)
tnagao7
1
240
外部システム連携先が10を超えるシステムでのアーキテクチャ設計・実装事例
kiwasaki
1
230
macOS でできる リアルタイム動画像処理
biacco42
7
2k
Identifying User Idenity
moro
6
8k
Webの技術スタックで マルチプラットフォームアプリ開発を可能にするElixirDesktopの紹介
thehaigo
2
930
カスタムしながら理解するGraphQL Connection
yanagii
1
1.2k
Snowflake x dbtで作るセキュアでアジャイルなデータ基盤
tsoshiro
2
440
Generative AI Use Cases JP (略称:GenU)奮闘記
hideg
0
160
Featured
See All Featured
Thoughts on Productivity
jonyablonski
67
4.3k
Code Reviewing Like a Champion
maltzj
519
39k
Art, The Web, and Tiny UX
lynnandtonic
296
20k
A better future with KSS
kneath
238
17k
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
Imperfection Machines: The Place of Print at Facebook
scottboms
264
13k
The Cult of Friendly URLs
andyhume
78
6k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
7
150
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
25
1.8k
Done Done
chrislema
181
16k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
246
1.3M
Understanding Cognitive Biases in Performance Measurement
bluesmoon
26
1.4k
Transcript
Let’s write a parser! DENIS DEFREYNE / RUG˸˸B / MAY
12TH, 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. Tobi introduced me. You might have 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
Text forms a language, but computers don’t know that. 10
2. Parsing 11
Basic idea: 12 Parser objects that are small, composable, and
purely functional.
13 def read(input, pos)
14 def read(input, pos) Success.new(pos + 1) end
15 def read(input, pos) Failure.new(pos) end
16 char("H") Succeeds if the next character is the given
one.
17 char("H").apply("Hello")
17 H e l l o char("H").apply("Hello")
17 H e l l o 0 1 2 3
4 char("H").apply("Hello")
17 H e l l o 0 1 2 3
4 char("H").apply("Hello")
17 H e l l o 0 1 2 3
4 char("H").apply("Hello")
17 H e l l o 0 1 2 3
4 char("H").apply("Hello") Success(position = 1)
18 char("H").apply("Adiós")
18 A d i ó s 0 1 2 3
4 char("H").apply("Adiós")
18 A d i ó s 0 1 2 3
4 char("H").apply("Adiós")
18 A d i ó s 0 1 2 3
4 char("H").apply("Adiós")
Failure(position = 0) 18 A d i ó s 0
1 2 3 4 char("H").apply("Adiós")
19 if input[pos] == @char Success.new(pos + 1) else Failure.new(pos)
end
20 seq(a, b) Succeeds if both given parsers succeed in
sequence.
21 seq(char("H"), char("e")).apply("Hello")
H e l l o 21 0 1 2 3
4 seq(char("H"), char("e")).apply("Hello")
H e l l o 21 0 1 2 3
4 seq(char("H"), char("e")).apply("Hello")
H e l l o 21 0 1 2 3
4 seq(char("H"), char("e")).apply("Hello")
H e l l o 21 0 1 2 3
4 seq(char("H"), char("e")).apply("Hello")
H e l l o 21 0 1 2 3
4 seq(char("H"), char("e")).apply("Hello") Success(position = 2)
22 seq( char("H"), char("e"), char("l"), char("l"), char("o"), )
23 string(s) Succeeds if all characters in the given string
can be read in sequence.
H e l l o 24 0 1 2 3
4 string("Hello").apply("Hello")
H e l l o 24 0 1 2 3
4 string("Hello").apply("Hello")
H e l l o 24 0 1 2 3
4 string("Hello").apply("Hello")
H e l l o 24 0 1 2 3
4 string("Hello").apply("Hello") Success(position = 5)
25 eof() Succeeds at the end of input; fails otherwise.
H e l l o 26 0 1 2 3
4 seq(string("Hello"), eof).apply("Hello")
H e l l o 26 0 1 2 3
4 seq(string("Hello"), eof).apply("Hello")
H e l l o 26 0 1 2 3
4 seq(string("Hello"), eof).apply("Hello")
H e l l o 26 0 1 2 3
4 seq(string("Hello"), eof).apply("Hello")
H e l l o 26 0 1 2 3
4 seq(string("Hello"), eof).apply("Hello") Success(position = 5)
27 0 1 2 3 4 5 H e l
l o ! seq(string("Hello"), eof).apply("Hello!")
27 0 1 2 3 4 5 H e l
l o ! seq(string("Hello"), eof).apply("Hello!")
27 0 1 2 3 4 5 H e l
l o ! seq(string("Hello"), eof).apply("Hello!")
27 0 1 2 3 4 5 H e l
l o ! seq(string("Hello"), eof).apply("Hello!")
27 0 1 2 3 4 5 Failure(position = 5)
H e l l o ! seq(string("Hello"), eof).apply("Hello!")
28 alt(a, b) Succeeds if either of the given parsers
succeed.
A d i ó s 29 0 1 2 3
4 alt(char("H"), char("A")).apply("Adiós")
A d i ó s 29 0 1 2 3
4 alt(char("H"), char("A")).apply("Adiós")
A d i ó s 29 0 1 2 3
4 alt(char("H"), char("A")).apply("Adiós")
A d i ó s 29 0 1 2 3
4 alt(char("H"), char("A")).apply("Adiós") Success(position = 1)
30 whitespace_char = alt(char(" "), char("\t"))
31 optional(p) Succeeds always, but only advances if p succeeds.
32 repeat(p) Succeeds always, and attempts to apply p as
often as possible.
33 repeat(whitespace_char)
34 intersperse(a, b) Alternates between a and b., always ending
with a.
35 intersperse(char("a"), char(",")).apply("a,a,b")
a , a , b 35 0 1 2 3
4 intersperse(char("a"), char(",")).apply("a,a,b")
a , a , b 35 0 1 2 3
4 intersperse(char("a"), char(",")).apply("a,a,b")
a , a , b 35 0 1 2 3
4 intersperse(char("a"), char(",")).apply("a,a,b")
a , a , b 35 0 1 2 3
4 intersperse(char("a"), char(",")).apply("a,a,b")
a , a , b 35 0 1 2 3
4 intersperse(char("a"), char(",")).apply("a,a,b") Success(position = 3)
36 etc.
37 720 6 29530
38 digit = alt( *('0'..'9') .map { |c| char(c)
} )
39 digit = char_in('0'..'9')
40 nat_number = seq(digit, repeat(digit))
41 nat_number = repeat1(digit)
42 nat_number = repeat1(digit) .capture
42 nat_number = repeat1(digit) .capture Success(position = 3, data =
"123")
43 nat_number = repeat1(digit) .capture .map(&:to_i)
43 nat_number = repeat1(digit) .capture .map(&:to_i) Success(position = 3, data
= 123)
44 def read(input, pos)
45 def read(input, pos) Success.new(pos + 1) end
46 def read(input, pos) Success.new(pos + 1, "blahblah") end
47 first,last,age Denis,Defreyne,29
48
48 field = repeat(char_not(',', "\n")).capture
48 field = repeat(char_not(',', "\n")).capture line = field.intersperse(char(','))
48 field = repeat(char_not(',', "\n")).capture line = field.intersperse(char(',')) file =
seq( line.intersperse(char("\n")), end_of_input, )
49 [ ["first_name", "last_name", "age"], ["Denis", "Defreyne", "29"], ]
50 add(1, mul(2, 3)) mul(2, 3)
51 lparen = char('(') rparen = char(')') comma = char(',')
52 expr = alt(lazy { funcall }, nat_number)
53 funcall = seq( identifier, lparen, arglist, rparen, )
54 letter = char_in('a'..'z') identifier = repeat1(letter).capture
55
55 arglist = seq(expr, arglist_tail)
55 arglist = seq(expr, arglist_tail) arglist_tail = repeat(seq(comma, whitespace, expr))
56
56 expr_list = expr.intersperse(char("\n"))
56 expr_list = expr.intersperse(char("\n")) program = seq(expr_list, eof)
57 [ ["add", 1, ["mul", 2, 3]], ["mul", 2, 3],
]
And that is how you can write a parser. 58
github.com/ddfreyne/d-parse 59
github.com/ddfreyne/d-parse 59
github.com/ddfreyne/d-parse 59
60 My name is Denis Defreyne. Ready to parse your
questions. Find me at
[email protected]
, or @ddfreyne on Twitter.