Search code examples
parsingcontext-free-grammarpratt-parser

What kind of parser is a pratt parser?


I'm implementing pratt's top down operator precedence parser and I'd like to know in which formal category it falls into - is it LR(1)?


Solution

  • Pratt parser are not LR parsers. And they're not exactly LL parsers either. In fact, Pratt parsers are generally hand-coded in some general purpose programming language; the technique is not based on an abstraction like push-down finite state automata. This makes it somewhat more difficult to prove assertions about a given Pratt parser, such as that it recognizes a particular formal language.

    In general, Pratt parsers can easily be designed to recognize a language if the grammar is an operator precedence grammar, so they can be considered to be a dual of operator precedence parsing, even though operator precedence parsing is bottom-up and Pratt parsers are nominally top-down. Tracing a Pratt parser and the transitions of an operator precedence parser for the same language will show the similarity.

    So I suppose that it might be possible to come up with a formalism for Pratt parsers, but as far as I know, none exists.