CODEWITHSUNDEEP
compiler-constructioncompilationgrammarcompiler-optimizationcontext-free-grammar
haolee
haolee

Reputation: 937

What is the difference between LR(1) grammar and operator precedence grammar?

I am learning the "Engineering a Compiler, 2nd Edition". And I have know what is LR(1) grammar,but I can't find operator precedence grammar in this book.

Then I borrowed "Compilers — Principles, Techniques, and Tools" from the library.But I still can't find it.

So I want to know ,what is the difference between the LR(1) grammar and operator precedence grammar.

And if the LR(1) grammar can replace the operator precedence grammar.Thanks!

Upvotes: 3

Views: 2643

Answers (1)

rici
rici

Reputation: 241971

An operator grammar is a context-free grammar in which there are no consecutive non-terminals in any right-hand side. (Intuitively, every production has an operator, as in the grammar for mathematical expressions.)

A operator precedence grammar is an operator grammar in which the parsing automaton can decide whether to shift or reduce based simply on a precedence relationship between the terminal closest to the top of the parsing stack and the lookahead token. Such a precedence relation does not need to be complete, nor transitive, nor antisymmetric.

I'm pretty sure that every operator precedence grammar is LR(1), but the converse is certainly not true. An LR(1) grammar does not have the restriction against consecutive non-terminals, for example, and it is quite possible for the shift/reduce decision in an LR(1) grammar to not be correlated with the uppermost terminal in the parse stack and the lookahead token. Nonetheless, some useful languages can be expressed with an operator precedence grammar.

Like LR-parsing, operator-precedence parsing is a bottom-up technique. It is possibly easier to understand than the LALR algorithm, but it has no other obvious advantage: it is not faster; it is less reliable (in the sense that some implementations will recognize erroneous sentences); and it is harder to verify. Before the LALR algorithm was discovered, however, the size of LR(1) automata (and the limited computing resources available) made operator-precedence parsing seem like a reasonable approach.

These days, you would be much better off using one of the many available parser generators.

Upvotes: 3

Related Questions