thwd
thwd

Reputation: 24808

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)?

Upvotes: 4

Views: 950

Answers (1)

rici
rici

Reputation: 241691

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.

Upvotes: 7

Related Questions