Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
Monadic Parsing in Python
Search
Oleksii Kachaiev
June 06, 2014
Programming
19k
13
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
Monadic Parsing in Python
Oleksii Kachaiev
June 06, 2014
Transcript
99 slides
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,
More Decks by Oleksii Kachaiev
See All by Oleksii Kachaiev
Counting HTTP with QUIC & HTTP/3
kachayev
2
340
Talking SQL to Strangers
kachayev
3
660
Counting HTTP: 0.9...3
kachayev
1
150
Managing Data Chaos in The World of Microservices
kachayev
3
750
Deep HTTP Dive Through Aleph & Netty
kachayev
6
4.1k
Keep Your Data Safe With Refined Types
kachayev
4
1.6k
Clojure at Attendify (2nd ed)
kachayev
5
1.7k
Clojure at Attendify
kachayev
4
410
Finagle & Clojure
kachayev
6
1.4k
Other Decks in Programming
See All in Programming
AI時代のIaC入門 〜なぜインフラをコードで管理したいのか?〜 / Introduction to IaC in the AI Era
akihisaikeda
6
1.5k
作れるエンジニアから、価値を届けるエンジニアへ
ryunakayama
1
310
Secure Your Coding Agent Like It’s Malware (v1.5) 🇬🇧 @Code.talks 2026
richargh
0
180
将来の標準フォーマッター?ktfmtを深堀る
t45k
0
220
AI駆動開発4年目の現在地(『あなたはFDEになるべきか?』イベント資料)
kumaiu
0
660
どうしても Eloquent でリポジトリパターンをやりたいんだ #phpcon_niigata / phpcon-niigata-2026
shogogg
0
620
自宅サーバはどこまで再現できるのか - Proxmox VE上のVM環境をIaCとバックアップで戻してみた
youto
0
430
baseline으로 마이그레이션, 리팩토링 안전하게 맡기기
fornewid
1
1k
学びを記事・スライド・Xへ高速展開する― AI-assisted Learning Loopで回すコンテンツ生成術
ochtum
0
210
Getting Started with Vibe Coding
miccheng
0
240
AI時代のシニアエンジニアとは
yosuke_furukawa
PRO
15
12k
React Native経験者が Flutterを30⽇間触って驚いたこと
3saito
0
200
Featured
See All Featured
Why Our Code Smells
bkeepers
PRO
340
58k
Why Your Marketing Sucks and What You Can Do About It - Sophie Logan
marketingsoph
0
470
Are puppies a ranking factor?
jonoalderson
2
4.2k
Reality Check: Gamification 10 Years Later
codingconduct
0
2.4k
The SEO identity crisis: Don't let AI make you average
varn
0
630
Jess Joyce - The Pitfalls of Following Frameworks
techseoconnect
PRO
1
480
What's in a price? How to price your products and services
michaelherold
247
13k
Agile Actions for Facilitating Distributed Teams - ADO2019
mkilby
0
350
HDC tutorial
michielstock
2
1k
[RailsConf 2023] Rails as a piece of cake
palkan
59
7.2k
Designing for humans not robots
tammielis
254
26k
From Legacy to Launchpad: Building Startup-Ready Communities
dugsong
0
380