Operator-precedence parser: Difference between revisions

Revision as of 21:39, 5 June 2006

Revision as of 20:00, 11 July 2006

Line 77:

1 is returned.

== Alternatives to Dijkstra's Algorithm ==

There are alternative ways to apply operator precedence rules which do not involve the Shunting Yard algorithm. One is to build a tree of the original expression, then apply tree rewrite rules to it. Another is the algorithm used in the early FORTRAN I compiler, which is to first fully parenthesise the expression by a trivial macro replacement — inserting a number of parentheses around each operator, such that they lead to the correct precedence when parsed with a 'flat' grammar. (A hack which takes longer to explain properly than to write code for - see below!)

[[Category:Parsing algorithms]]

<pre>

#include <stdio.h>

char *intable[] = { NULL, "^", "*", "/", "+", "-", "" };

char *outtable[] = { "))))\n", ")^(", "))*((", "))/((", ")))+(((", ")))-(((", "((((" };

int main(int argc, char **argv)

{

int i, tab;

for (argv[i=0]=""; i <= argc; i++) {

for (tab = 0; tab < (sizeof(outtable)/sizeof(char *)); tab += 1) {

if ((!argv[i]) || (tab && !strcmp(argv[i], intable[tab]))) {

printf("%s", outtable[tab]); break;

} else if (tab && !*intable[tab]) printf("%s", argv[i]);

}

}

}

</pre>

Invoke it as: <pre>

$ cc -o parenthesise parenthesise.c

$ ./parenthesise a \* b + c ^ d / e

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

</pre>

==External links==

* [http://www.gtoal.com/software/OperatorPrecedence Tree-based operator precedence]

* [http://www.gtoal.com/software/OperatorPrecedenceHack Adding parentheses.] (This is the [http://polaris.cs.uiuc.edu/publications/c1070.pdf FORTRAN I algorithm] as attested to by Knuth - see page 72.)