Operator-precedence Parser - Alternative Methods

Alternative Methods

There are other ways to apply operator precedence rules. One is to build a tree of the original expression and then apply tree rewrite rules to it.

Such trees do not necessarily need to be implemented using data structures conventionally used for trees. Instead, tokens can be stored in flat structures, such as tables, by simultaneously building a priority list which states what elements to process in which order.

Another approach is to first fully parenthesize the expression, inserting a number of parentheses around each operator, such that they lead to the correct precedence even when parsed with a linear, left-to-right parser. This algorithm was used in the early FORTRAN I compiler.

Example code of a simple C application that handles parenthesisation of basic math operators (+, -, *, /, ^ and parentheses):

#include int main(int argc, char *argv){ int i; printf("(((("); for(i=1;i!=argc;i++){ if(argv && !argv){ switch(*argv){ case '(': printf("(((("); continue; case ')': printf("))))"); continue; case '^': printf(")^("); continue; case '*': printf("))*(("); continue; case '/': printf("))/(("); continue; case '+': if (i == 1 || strchr("(^*/+-", *argv)) printf("+"); else printf(")))+((("); continue; case '-': if (i == 1 || strchr("(^*/+-", *argv)) printf("-"); else printf(")))-((("); continue; } } printf("%s", argv); } printf("))))\n"); return 0; }

For example, when compiled and invoked from the command line with parameters

a * b + c ^ d / e

it produces

((((a))*((b)))+(((c)^(d))/((e))))

as output on the console.

A limitation to this strategy is that unary operators must all have higher precedence than infix operators. The "negative" operator in the above code has a higher precedence than exponentiation. Running the program with this input

- a ^ 2

produces this output

((((-a)^(2))))

which is probably not what is intended.

Read more about this topic:  Operator-precedence Parser

Famous quotes containing the words alternative and/or methods:

    “No alternative to the
    one-man path.”
    —Denise Levertov (b. 1923)

    “We are lonesome animals. We spend all our life trying to be less lonesome. One of our ancient methods is to tell a story begging the listener to say—and to feel—”Yes, that’s the way it is, or at least that’s the way I feel it. You’re not as alone as you thought.””
    —John Steinbeck (1902–1968)