Pratt Parsers: Expression Parsing Made Easy
journal.stuffwithstuff.com
Pratt Parsers: Expression Parsing Made Easy
1–10 of 21 posts
Re: Pratt Parsers: Expression Parsing Made Easy
#2I slapped together a crude lexer that works and we’ll just pretend that tokens are raining down from heaven or something.
This perfectly describes all parsing discussions and papers I've read. I love it.
Re: Pratt Parsers: Expression Parsing Made Easy
#3I've also played around with combinatorial parsing using F#'s FParsec (a clone of Haskell's Parsec lib) and I found very pleasant and powerful to work with.
Re: Pratt Parsers: Expression Parsing Made Easy
#4Excited to see how this is integrated with Magpie
Re: Pratt Parsers: Expression Parsing Made Easy
#5A post about... Programming? This isn't the HN I know!
Good post. I need to ruminate on this some more but it might well apply to something I'm working on.
Re: Pratt Parsers: Expression Parsing Made Easy
#6I believe this algorithm is also known as "precedence climbing", and it's the most common way to deal with operator precedence in a recursive-descent parser.
Re: Pratt Parsers: Expression Parsing Made Easy
#7I slapped together a crude lexer that works and we’ll just pretend that tokens are raining down from heaven or something. This perfectly describes all parsing discussions and papers I've read. I love it.
"I have a truly marvelous demonstration of this proposition which this margin is too small to contain."
Re: Pratt Parsers: Expression Parsing Made Easy
#8I believe this algorithm is also known as "precedence climbing", and it's the most common way to deal with operator precedence in a recursive-descent parser.
correct.
the pratt parser is just a way of implementing such a parser.
to be technical, it is a form of left-corner parsing
Re: Pratt Parsers: Expression Parsing Made Easy
#9how to do it in python: http://effbot.org/zone/simple-top-down-parsing.htm
Re: Pratt Parsers: Expression Parsing Made Easy
#10I believe this algorithm is also known as "precedence climbing", and it's the most common way to deal with operator precedence in a recursive-descent parser.
I'd say that having a single production for each precedence level is a more common technique in recursive descent, but it that can be slow because every factor needs to be parsed by recursing through all precedence levels. This technique avoids that, and can parse factors straight away before going into the priority checking loop.
Delphi uses this parsing method for expressions, and is one of the reasons it's so fast at compiling.