Home » forums » LtU Forum

Statically typed Pratt parsers

I recently completed an extensible Pratt parser in C#. I've only managed to find a single mention of a statically typed Pratt parser, pointing to this Ada library. Most implementations I've found are for dynamic languages, ie. Python, JavaScript, Scheme, and of course, Pratt's original implementation was in Lisp.

Is Pratt parsing, aka "top-down operator precedence parsing", really so little used? Or is its use behind the scenes, perhaps in a parser generator or as part of a post-processing phase to resolve operator precedence when using a parser combinator library? Are there any problems to using a typed Pratt parser as compared to parser combinators?

By naasking at 2009-11-16 19:49 | LtU Forum | previous forum topic | next forum topic | other blogs | 15227 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Precedence parsing to be incremental

Interesting.

Semi-related, I've played around with precedence parsing to build incremental parsers for interactive source code editors. This wasn't top down though, as bottom-up naturally allows local modifications to the parse tree to be processed locally without disturbing the rest of the parse tree. Parsing in the live programming version of SuperGlue was done in this way. I didn't try scaling this up for Scala though, there we just memoize parse trees and state in a more conventional recursive descent parser.

At first glance, I'm not sure how Pratt parsing directly relates to incrementality, but its a niche that is not served very well by other parsing technologies and worth looking at.

By Sean McDirmid at Wed, 2009-11-18 02:05 | login or register to post comments

Re: incrementality, that's a

Re: incrementality, that's a good question. A Pratt parser is so simple that it shouldn't be too hard to structure it in a way that you can capture the continuation of each token. Then you can store these continuations in your parse tree, and restart the parse with a new input at an arbitrary point. You can store as many continuations as you want, trading memory for incrementality.

I think it would be possible, although you'd probably want a better language than C#. Perhaps there's an elegant approach I'm missing though.

By naasking at Wed, 2009-11-18 02:59 | login or register to post comments

Lua

IIRC, Lua uses a variant of this technique to parse infix expressions. It's slightly different, though, and as I recall, the rest of the parser is more traditional recursive descent.

By Matt Hellige at Wed, 2009-11-18 04:46 | login or register to post comments

Yes, precedence climbing

Yes, precedence climbing techniques have been known for awhile. This is a good overview of the various known techniques of handling precedence in recursive descent parsers. The author notes that "precedence climbing" is closely related to Pratt's algorithm.

By naasking at Wed, 2009-11-18 15:10 | login or register to post comments

Delphi, FWIW

FWIW the Delphi compiler, written in C with a recursive descent parser has long used a precedence parser similar to Pratt for expressions, though largely hand-inlined with a big switch. The primary advantage is avoiding lots of redundant recursion when precedence is implemented in recursive descent through nesting.

By barrkel at Thu, 2009-11-19 19:17 | login or register to post comments