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:

    “Our mother gives us our earliest lessons in love—and its partner, hate. Our father—our “second other”Melaborates on them. Offering us an alternative to the mother-baby relationship . . . presenting a masculine model which can supplement and contrast with the feminine. And providing us with further and perhaps quite different meanings of lovable and loving and being loved.”
    —Judith Viorst (20th century)

    “All good conversation, manners, and action, come from a spontaneity which forgets usages, and makes the moment great. Nature hates calculators; her methods are saltatory and impulsive.”
    —Ralph Waldo Emerson (1803–1882)