6 ms·

Pratt Parsers: Expression Parsing Made Easy

89 points by jashkenas 16y ago

scott_s 16y ago
I 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.
- ShirtlessRod 16y ago
  "I have a truly marvelous demonstration of this proposition which this margin is too small to contain."
statictype 16y ago
I'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.
amadiver 16y ago
Excited to see how this is integrated with Magpie
cletus 16y ago
A 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.
ssp 16y ago
I 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.
- _tef 16y ago
  correct. the pratt parser is just a way of implementing such a parser. to be technical, it is a form of left-corner parsing
- barrkel 16y ago
  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.
  - scottdw2 16y ago
    I don't actually know if Delphi is fast or not, I'll take your word on it. However, I'd be skeptical that the parser is one of the main reasons for its fast compile times. In my experience, parsing is really a tiny amount of compilation time. The VB.NET compiler, for example, uses the same parsing technique, and it is ... "not fast" at compiling. It spends most of its time binding symbols.
    - barrkel 16y ago
      Delphi's parser binds symbols and types the tree as it parses. The only thing left to do after parsing is code generation, which is only a couple of passes over the tree. The parser (or more accurately, the lexer) is the bit of the compiler which ultimately limits its performance, because it needs to see every character of the source. The compiler can never be faster than linear in the length of its input. Metrics on the Delphi compiler actually show that string hashing is the hottest piece of code, and that's already optimized about as far as it can go.
      - scottdw2 16y ago
        Which means its fast because of the way it binds symbols, not because of the way it parses infix expressions. One thing to consider is that such a design hurts the usability of the language. It's a lot easier to not have to worry about forward declarations and "module" interfaces. I don't know Delphi, but I imagine what you describe relies on something like the "unit" construct from Turbo Pascal.
ms4720 16y ago
how to do it in python: http://effbot.org/zone/simple-top-down-parsing.htm http://effbot.org/zone/simple-top-down-parsing.htm
- beagle3 16y ago
  Unfortunately I can only upvote once. Way, way more complete than the post linked article.
  - ms4720 16y ago
    not a problem
- silentbicycle 16y ago
  Crockford has an article about it (http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html) in _Beautiful Code_, and there's a copy of the Pratt paper that escaped the clutches of the ACM's paywall at http://hall.org.ua/halls/wizzard/pdf/Vaughan.Pratt.TDOP.pdf http://hall.org.ua/halls/wizzard/pdf/Vaughan.Pratt.TDOP.pdf . Spread it around!
eliben 16y ago
Uhm, I wrote this a while ago: http://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/ http://eli.thegreenplace.net/2010/01/02/top-down-operator-pr... [sorry for the plug, but I think my tutorial is more comprehensive in terms of explaining how the thing actually works]
- silentbicycle 16y ago
  I agree - I find your post is clearer than the original paper, Crockford's explanation, and Lundh's Python post. It helps that you start with just addition and multiplication, then add more functionality after explaining the basics.
- munificent 16y ago
  That post is excellent! Somehow I didn't find that when I was looking to learn more about TDOP. The only change I made from yours and Pratt's is that I split out the nud and led parsers completely. It seemed weird to me to lump them together just because they share a token when they aren't semantically related. For example, the "(" token handles grouping in prefix position and function calls in infix, and those don't have anything to do with each other, so I split out PrefixParselets and InfixParselets into entirely separate dictionaries.
fholm 16y ago
I love Pratt parsers (or Top Down Operator Precedence parsers rather), I recently re-wrote the IronJS lexer and parser by hand (from using one generated by ANTLR) using the techniques described in this blog post and saw some pretty hefty performance increments http://ironjs.wordpress.com/2011/03/19/new-lexer-and-parser-in-ironjs/ http://ironjs.wordpress.com/2011/03/19/new-lexer-and-parser-... Edit, I also have a generalized version that can take pretty much any input and any output (F#) here: https://github.com/fholm/Vaughan https://github.com/fholm/Vaughan

89 points by jashkenas 16y ago

I 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.

ShirtlessRod 16y ago
"I have a truly marvelous demonstration of this proposition which this margin is too small to contain."

statictype 16y ago

I'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.

amadiver 16y ago

Excited to see how this is integrated with Magpie

cletus 16y ago

A 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.

ssp 16y ago

I 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.

_tef 16y ago
correct. the pratt parser is just a way of implementing such a parser. to be technical, it is a form of left-corner parsing
barrkel 16y ago
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.
- scottdw2 16y ago
  I don't actually know if Delphi is fast or not, I'll take your word on it. However, I'd be skeptical that the parser is one of the main reasons for its fast compile times. In my experience, parsing is really a tiny amount of compilation time. The VB.NET compiler, for example, uses the same parsing technique, and it is ... "not fast" at compiling. It spends most of its time binding symbols.
  - barrkel 16y ago
    Delphi's parser binds symbols and types the tree as it parses. The only thing left to do after parsing is code generation, which is only a couple of passes over the tree. The parser (or more accurately, the lexer) is the bit of the compiler which ultimately limits its performance, because it needs to see every character of the source. The compiler can never be faster than linear in the length of its input. Metrics on the Delphi compiler actually show that string hashing is the hottest piece of code, and that's already optimized about as far as it can go.
    - scottdw2 16y ago
      Which means its fast because of the way it binds symbols, not because of the way it parses infix expressions. One thing to consider is that such a design hurts the usability of the language. It's a lot easier to not have to worry about forward declarations and "module" interfaces. I don't know Delphi, but I imagine what you describe relies on something like the "unit" construct from Turbo Pascal.

ms4720 16y ago

how to do it in python: http://effbot.org/zone/simple-top-down-parsing.htm http://effbot.org/zone/simple-top-down-parsing.htm

beagle3 16y ago
Unfortunately I can only upvote once. Way, way more complete than the post linked article.
- ms4720 16y ago
  not a problem
silentbicycle 16y ago
Crockford has an article about it (http://javascript.crockford.com/tdop/tdop.html http://javascript.crockford.com/tdop/tdop.html) in _Beautiful Code_, and there's a copy of the Pratt paper that escaped the clutches of the ACM's paywall at http://hall.org.ua/halls/wizzard/pdf/Vaughan.Pratt.TDOP.pdf http://hall.org.ua/halls/wizzard/pdf/Vaughan.Pratt.TDOP.pdf . Spread it around!

eliben 16y ago

Uhm, I wrote this a while ago: http://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/ http://eli.thegreenplace.net/2010/01/02/top-down-operator-pr... [sorry for the plug, but I think my tutorial is more comprehensive in terms of explaining how the thing actually works]

silentbicycle 16y ago
I agree - I find your post is clearer than the original paper, Crockford's explanation, and Lundh's Python post. It helps that you start with just addition and multiplication, then add more functionality after explaining the basics.
munificent 16y ago
That post is excellent! Somehow I didn't find that when I was looking to learn more about TDOP. The only change I made from yours and Pratt's is that I split out the nud and led parsers completely. It seemed weird to me to lump them together just because they share a token when they aren't semantically related. For example, the "(" token handles grouping in prefix position and function calls in infix, and those don't have anything to do with each other, so I split out PrefixParselets and InfixParselets into entirely separate dictionaries.

fholm 16y ago

I love Pratt parsers (or Top Down Operator Precedence parsers rather), I recently re-wrote the IronJS lexer and parser by hand (from using one generated by ANTLR) using the techniques described in this blog post and saw some pretty hefty performance increments http://ironjs.wordpress.com/2011/03/19/new-lexer-and-parser-in-ironjs/ http://ironjs.wordpress.com/2011/03/19/new-lexer-and-parser-... Edit, I also have a generalized version that can take pretty much any input and any output (F#) here: https://github.com/fholm/Vaughan https://github.com/fholm/Vaughan