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
Monadic Parsing in Python
Search
Oleksii Kachaiev
June 06, 2014
Programming
13
7.2k
Monadic Parsing in Python
Oleksii Kachaiev
June 06, 2014
Tweet
Share
More Decks by Oleksii Kachaiev
See All by Oleksii Kachaiev
Counting HTTP with QUIC & HTTP/3
kachayev
2
260
Talking SQL to Strangers
kachayev
3
550
Counting HTTP: 0.9...3
kachayev
1
77
Managing Data Chaos in The World of Microservices
kachayev
3
650
Deep HTTP Dive Through Aleph & Netty
kachayev
6
3.7k
Keep Your Data Safe With Refined Types
kachayev
4
1.4k
Clojure at Attendify (2nd ed)
kachayev
5
1.6k
Clojure at Attendify
kachayev
4
330
Finagle & Clojure
kachayev
6
1.3k
Other Decks in Programming
See All in Programming
Javaに鉄道指向プログラミング (Railway Oriented Pro gramming) のエッセンスを取り入れる/Bringing the Essence of Railway-Oriented Programming to Java
cocet33000
1
120
Zennの運営完全に理解した #完全に理解したTalk
wadayusuke
1
140
DevTalks 25 - Create your own AI-infused Java apps with ease
kdubois
2
120
Feature Flag 自動お掃除のための TypeScript プログラム変換
azrsh
PRO
4
630
Spring gRPC で始める gRPC 入門 / Introduction to gRPC with Spring gRPC
mackey0225
0
140
ワンバイナリWebサービスのススメ
mackee
10
7.5k
當開發遇上包裝:AI 如何讓產品從想法變成商品
clonn
0
2.6k
TSConfig Solution Style & subpath imports to switch types on a per-file basis
maminami373
1
180
バランスを見極めよう!実装の意味を明示するための型定義 TSKaigi 2025 Day2 (5/24)
whatasoda
2
780
Language Server と喋ろう – TSKaigi 2025
pizzacat83
2
670
コードに語らせよう――自己ドキュメント化が内包する楽しさについて / Let the Code Speak
nrslib
5
1.1k
TypeScript LSP の今までとこれから
quramy
0
110
Featured
See All Featured
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Visualization
eitanlees
146
16k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
10
850
Statistics for Hackers
jakevdp
799
220k
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.8k
Making Projects Easy
brettharned
116
6.2k
The Power of CSS Pseudo Elements
geoffreycrofte
76
5.8k
The Language of Interfaces
destraynor
158
25k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
123
52k
Connecting the Dots Between Site Speed, User Experience & Your Business [WebExpo 2025]
tammyeverts
1
82
Agile that works and the tools we love
rasmusluckow
329
21k
Transcript
Monadic Parsing in Python Alexey Kachayev, 2014
About me • CTO at Attendify.com • Erlang, Clojure, Go,
Haskell • Fn.py library author • CPython & Storm contributor
Find me •@kachayev •github.com/kachayev •kachayev <$> gmail.com
Topic
Will talk •What is "parsing(ers)" •Approaches •Monadic parsing from scratch
•More…
Will talk •Less about theory •Much more about practice
Won’t talk •What "monad" is •Why FP is cool (*)
* you’ll understand it by yourself
Parsing
Definition •Takes grammar •Takes input string (?) •Returns tree (??)
or an error
None
For PL creators only?
Tasks • Processing information from logs • Source code analysing
• DSLs • Protocols & data formats • … and more
Approaches
Production rule S → SS|(S)|()
Grammar block = ["const" ident "=" number {"," ident "="
number} ";"] ["var" ident {"," ident} ";"] {"procedure" ident ";" block ";"} statement ! expression = ["+"|"-"] term {("+"|"-") term} ! term = factor {("*"|"/") factor} ! factor = ident | number | "(" expression ")" ! . . . .
•Top-down / bottom-up •Predictive / Backtracking •LL(k), LALR, LR, CYK
and others In theory
Manually!
@ wikipedia
Manually •Simple to understand •Hard to maintain •Really boring
Can we do better?
What we have •Context-free grammars •Formal theory •Well-defined algorithms •Standard
grammar notation(s)
So…
Parser generator •1. Parse DSL notation •2. Generate parser code
•("any" language)
Parser generator •*PEG* •*Yacc* •ANTLR •… and tens more
Parser generator •Pros •many targeted languages •formalism •performance & optimisations
Parser generator •Cons •another language •bounded in features •"compiled-time" mostly
Can we do better?
Monadic parsers & combinators
Functional Pearls Monadic Parsing in Haskell @Graham Hutton, @Erik Meijer
Parsec MPC library for Haskell
Parsec •Monadic parser combinator(s) •Works even with context- sensitive, infinite
LA grammars •Tens of ports to other langs
None
The Big Idea
Simple type Parser = String → Tree
Compose? type Parser = String → (Tree, String)
Generalize? type Parser a = String → (a, String)
Errors? type Parser a = String → Maybe (a, String)
Or better… type Parser a = String → [(a, String)]
Let’s try…
Snippets: http://goo.gl/leQIEE
None
None
None
None
… and so?
Expressiveness •[] for error •[s1] for single (predictive) •[s1..sN] for
backtracking
First-class citizen
None
Skip anything…
Recognise digit
Combinators
RegExp •and: "abc" •or: "a | b | c" •Kleene
star: "a*"
Derives •a? = "" | a •a+ = aa* •a{2,3}
= aa | aaa
None
None
laziness is cool for this do you need backtracking?
How to use it?
None
None
Cool! but..
ugly ugly not readable
Enhancements •use generators for "laziness" •"combine" function •Scala-style methods •"delay"
method
fn.py Stream
None
[1,2,3,4,5] expr →"[" digit (","digit)* "]"
None
Interesting! but..
Is it enough?
In Haskell
Can I do this in Python?
… hm
Challenge accepted!
In Python
How?
Desugaring…
What?
WAT??? even more like
unit a → Parser a
bind Parser a → (a → Parser b) → Parser
b
lift (a → b) → (a → Parser b)
lifted Parser a → (a → b) → Parser b
WAT??? ok, looks cool, but
None
None
How to use
And even more..
Haskell-style
Do-notation
None
None
(define R 2) (define diameter (lambda (r) (* 2 r)))
None
None
Looks nice!
Mutability kills backtracking :(
And more •errors handling •backtracking control •performance
Links • "funcparselib" http://goo.gl/daidQY • "Monadic parsing in Haskell" http://goo.gl/gygNlM
• "Higher-Order functions for Parsing" http://goo.gl/c8VOIZ • "Parsec" http://goo.gl/bdnDZQ • "Parcon" http://goo.gl/CT06S5 • "Pyparsing" http://goo.gl/gmr2lQ • "You Could Have Invented Monadic Parsing" http://goo.gl/h0rnOQ
Learn Haskell For Great Good
Q/A thanks for your attention,