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.3k
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
270
Talking SQL to Strangers
kachayev
3
570
Counting HTTP: 0.9...3
kachayev
1
87
Managing Data Chaos in The World of Microservices
kachayev
3
660
Deep HTTP Dive Through Aleph & Netty
kachayev
6
3.8k
Keep Your Data Safe With Refined Types
kachayev
4
1.5k
Clojure at Attendify (2nd ed)
kachayev
5
1.6k
Clojure at Attendify
kachayev
4
350
Finagle & Clojure
kachayev
6
1.3k
Other Decks in Programming
See All in Programming
CSC509 Lecture 05
javiergs
PRO
0
300
テーブル定義書の構造化抽出して、生成AIでDWH分析を試してみた / devio2025tokyo
kasacchiful
0
110
大規模アプリのDIフレームワーク刷新戦略 ~過去最大規模の並行開発を止めずにアプリ全体に導入するまで~
mot_techtalk
1
460
All About Angular's New Signal Forms
manfredsteyer
PRO
0
180
Goで実践するドメイン駆動開発 AIと歩み始めた新規プロダクト開発の現在地
imkaoru
4
850
Domain-centric? Why Hexagonal, Onion, and Clean Architecture Are Answers to the Wrong Question
olivergierke
3
900
Building, Deploying, and Monitoring Ruby Web Applications with Falcon (Kaigi on Rails 2025)
ioquatix
4
2.2k
非同期jobをtransaction内で 呼ぶなよ!絶対に呼ぶなよ!
alstrocrack
0
970
Range on Rails ―「多重範囲型」という新たな選択肢が、複雑ロジックを劇的にシンプルにしたワケ
rizap_tech
0
6.7k
AI Agent 時代的開發者生存指南
eddie
3
1.8k
理論と実務のギャップを超える
eycjur
0
140
Web フロントエンドエンジニアに開かれる AI Agent プロダクト開発 - Vercel AI SDK を観察して AI Agent と仲良くなろう! #FEC余熱NIGHT
izumin5210
3
550
Featured
See All Featured
[RailsConf 2023] Rails as a piece of cake
palkan
57
5.9k
Become a Pro
speakerdeck
PRO
29
5.6k
The Art of Programming - Codeland 2020
erikaheidi
56
14k
Building a Scalable Design System with Sketch
lauravandoore
463
33k
Site-Speed That Sticks
csswizardry
13
910
Code Reviewing Like a Champion
maltzj
526
40k
Rails Girls Zürich Keynote
gr2m
95
14k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
253
22k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
31
2.7k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
140
34k
Evolution of real-time – Irina Nazarova, EuRuKo, 2024
irinanazarova
9
980
GraphQLとの向き合い方2022年版
quramy
49
14k
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,