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 English is spoken in heaven ... God undoubtedly employs Cranmer as his speechwriter. The angels of the lesser ministries probably use the language of the New English Bible and the Alternative Service Book for internal memos.”
    —Charles, Prince Of Wales (b. 1948)

    “Crime is terribly revealing. Try and vary your methods as you will, your tastes, your habits, your attitude of mind, and your soul is revealed by your actions.”
    —Agatha Christie (1891–1976)