Home > Archive > Compilers > August 2005 > Re: Implementing a stack-based interpreter
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Re: Implementing a stack-based interpreter
|
|
| Tomasz Kowaltowski 2005-08-07, 5:02 pm |
| "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>:
> BTW, does anybody know the author of the infix to reverse Polish notation
> conversion algorithm? I failed to find any references, so far.
I recall vaguely a description of the first Fortran compiler which
translated infix expressions into code which must have been equivalent
to reverse Polish (postfix) notation. The original method was quite
complicated introducing extra parentheses around each operator
according to its priority and then doing the translation. It required
thus two passes over the expression.
The simple stack based one pass algorithm seems to appear in many texts
on data structures. Probably it was reinvented by many authors.
-- Tomasz Kowaltowski
[Forward Polish notation was invented in 1920, RPN in the 1950s, so I
wouldn't be surprised if infix to Polish algorithms were invented in
the 1920s. -John]
| |
| Hans Aberg 2005-08-10, 5:07 pm |
| John Levine <johnl@iecc.com> wrote:
> [Forward Polish notation was invented in 1920, RPN in the 1950s, so I
> wouldn't be surprised if infix to Polish algorithms were invented in
> the 1920s. -John]
The very point with Polish notation is that infix expressions can be
translated into them, because then one can use it to simplify proofs in
metamathematics. That's why, simplification of proofs, that Church used it
in his lambda calculus. So I guess Jan Lukasiewicz made that algorithm at
the same time he introduced the prefix notation. Also see_
_ http://en.wikipedia.org/wiki/Polish_notation
_ http://en.wikipedia.org/wiki/RPN
The latter page says that Charles Hamblin made the RPN algorithm.
--
Hans Aberg
|
|
|
|
|