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:

    “A mental disease has swept the planet: banalization.... Presented with the alternative of love or a garbage disposal unit, young people of all countries have chosen the garbage disposal unit.”
    —Ivan Chtcheglov (b. 1934)

    “There are souls that are incurable and lost to the rest of society. Deprive them of one means of folly, they will invent ten thousand others. They will create subtler, wilder methods, methods that are absolutely DESPERATE. Nature herself is fundamentally antisocial, it is only by a usurpation of powers that the organized body of society opposes the natural inclination of humanity.”
    —Antonin Artaud (1896–1948)