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:

    “If you have abandoned one faith, do not abandon all faith. There is always an alternative to the faith we lose. Or is it the same faith under another mask?”
    —Graham Greene (1904–1991)

    “The methods by which a trade union can alone act, are necessarily destructive; its organization is necessarily tyrannical.”
    —Henry George (1839–1897)