This is one version of http://www.gtoal.com/software/OperatorPrecedence from your personal cache.
The page may have changed since that time. Click here for the current page.
Since this page is stored on your computer, publicly linking to this page will not work.

Google may not be affiliated with the authors of this page nor responsible for its content. This page may be protected by copyright.

OperatorPrecedence - Software Development
  OperatorPrecedence UserPreferences
 
HelpContents FindPage Diffs Info Edit Subscribe XML Print View

I'm not going to describe the most common methods of implementing operator precedence, because they're well known and well documented. What I'm going to describe here is a method of implementing operator precedence that is not very well known, but is remarkably easy to implement and efficient to run.

One form of grammar for expressions implicitly embeds the precedence in the grammar itself:

  <expr>    ::= <expr> '+' <term>
                | <term>;
  <term>    ::= <term> '*' <factor>
                | <factor>;
  <factor>  ::= <factor> '^' <element>
                | <element>;
  <element> ::= '(' <expr> ')'
                | <number>;
  <number>  ::= <digit> { <digit> };
  <digit>   ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

Out first win comes from using a much simpler grammar with no operator precedence coded in. However this style of grammar means that the operator precedence must be determined after parsing. A grammar in this style might look like this:

  <expr>    ::= <number> {<op> <number>}
                | '(' <expr> ')';
  <op>      ::= '+' | '-' | '*' | '/' |'^';
  <number>  ::= <digit> { <digit> };
  <digit>   ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

This grammar will generate very lop-sided parse trees. For example the parse tree for the expression "i = 2 + 3 * 4 - 5 / 6" will look like:

    //              =
    //             / \
    //            /   '+'
    //           /   / \
    //          /   /   '*'
    //         /   /   / \
    //        /   /   /   '-'
    //       /   /   /   / \
    //      /   /   /   /   '/'
    //     /   /   /   /   / \
    //    i   2   3   4   5   6

The fully parenthesised version of the statement above would be "i=(2+(3*4)-(5/6))" and the parse tree should be:


    //              =
    //             / \
    //            /   '+'
    //           /   / \
    //          /   /   '-'
    //         /   /   / \
    //        /   /   /   \
    //       /   /   /     '/'
    //      /   /   '*'   / \
    //     /   /   / \   5   6
    //    i   2   3   4

Well, when you look at the diagrams like that, it's intuitively obvious that there is probably some way to map from 'before' to 'after' using some sort of graph-rewriting operation.

Well, let's simplify the example and handle the trivial case: "a*b+c"

    //        '*'
    //       / \
    //      /   '+'
    //     /   / \
    //    a   b   c

This rewrites to:

    //         '+'
    //        / \
    //       /   \
    //      '*'   c
    //     / \
    //    a   b

If we assume this is the total problem, then the algorithm is simply a string rewrite:

(X op (Y op Z)) -> ((X op Y) op Z)

or if you prefer it in terms of code,

void reorder(TRIP root)
{
   int orig_opsym, orig_left, orig_right;
   while ((binop(opsym(root)))
          && (binop(opsym(rightchild(root))))
          && (prio[opsym(rightchild(root))] < prio[opsym(root)])) {
     orig_opsym = opsym(root);
     orig_left = leftchild(root);
     orig_right = rightchild(root);

     opsym(root) = opsym(orig_right);
     leftchild(root) = orig_right;
     rightchild(root) = rightchild(orig_right);

     opsym(orig_right) = orig_opsym;
     rightchild(orig_right) = leftchild(orig_right);
     leftchild(orig_right) = orig_left;

   }
}

The question is, when should we apply this transformation to a tree node?

Simple: when the priority of the operator on the right hand branch is less than the priority of the parent operator.

If we do this in the context of a large tree, we should apply it at each node repeatedly until the operator on the right is not of a lower priority (that's what the while in the code above does). The function above is not the whole story - it applies to one node only. I must admit my first guess as to when to invoke the node rotation function was wrong, and although I did eventually get it working, it was somewhat by trial and error - so I am not documenting the details of that here yet. I'll leave it as the traditional "exercise to the reader"... My own solution took advantage of the fact that the rotate operation is idempotent and can be called repeatedly without harm on the same node, so I pretty much called it at every opportunity, including no doubt several places where it wasn't necessary. (I'll document it properly once I've simplified my code and understand the correct way to do it better)

Note that we treat parenthesised expressions as a simple term when handling the top level, and we treat the contents of the parenthesised expression as an expression in its own right to be prioritised separately.

Having an explicit node for parentheses is useful for stopping accidental undoing of explicit precedence given by the user. However a 'no-op' node is not normally allowed in an AST so after applying the operator precedence algorithm, these protective nodes should be elided.

This algorithm is not well documented on the net; I've only found one reference to it, at [WWW]comp.compilers, plus [WWW]followups. I think it deserves to be better known.

(Another algorithm which also deserves to be better known is this OperatorPrecedenceHack, when you happen to have an application that can be easily adapted to take advantage of it - which is not often the case, unfortunately.)

PythonPowered