I am aware of what is ambiguity, and why is it necessary to eliminate ambiguity in compilers in a certain context, but how can we allow ambiguity for operator precedence parser? Say I have a set of operations like a-b-c now if we operate it with two different parse trees, say one like (a-b)-c and other like a-(b-c) there meaning changes.. So how can we allow ambiguous grammar in operator precedence parser? shouldn't it be the opposite?

  • 1
    $\begingroup$ An operator precedence parser knows how to resolve this ambiguity, in this case by associating subtraction to the left. $\endgroup$ – Yuval Filmus Jun 11 '19 at 14:25
  • $\begingroup$ Thanks again.. :) $\endgroup$ – Turing101 Jun 11 '19 at 14:26
  • 1
    $\begingroup$ "Precedence" includes information about "rank" AND associativity (left or right) of the operation $\endgroup$ – Bulat Jun 11 '19 at 14:47

An operator precedence parser usually has no ambiguity at all. However, the evaluation order is not determined by the parse tree, but by the operator precedences and associativities.

As a practical example, the Swift language doesn't define operator precedence or associativity in the language. It doesn't even define operators, except that the scanner knows which sequences of letters could be operators. The actual operators and precedence / associativity are define by the programmer, or as part of the standard library. As a result, a+b*c>d/e produces a parse tree that just consists of the five operands and four potential operators. The parse is unique, but doesn't tell how the expression should be evaluated.

The next phase checks that all the four potential operators are indeed operators. Then the priorities and associativity of the operators, as defined by the programmer or standard library, are examined. * and / have highest priority, + has lower, and > has even lower priority. If you had a-b-c, then the two operators have the same precedence, and both are left-associative, so the order is also clear. If you had two or more consecutive operators with same priority and different associativity, or with no associativity, that would be an error.

You couldn't define a grammar to handle operators, because their precedence and associativity are not even known when you start compiling.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.