> On Jun 21, 2021, at 12:19 AM, ben via cctalk <cctalk@classiccmp.org> wrote:
>
> On 2021-06-20 9:01 p.m., Brent Hilpert via cctalk wrote:
>> On 2021-Jun-20, at 7:38 PM, ben via cctech wrote:
>>> On 2021-06-20 8:13 p.m., Toby Thain via cctech wrote:
>>>
>>>> Tried the Shunting Yard algorithm? But watch out, it was invented by a
>>>> quiche eater...
>>>
>>> The problem needs backtracking to generate correct code. Stack or
>>> muilti-register machines don't have this problem with temporaries.
>>> Ben.
>> The parser generates a tree of the algebraic expression, the tree is
>> representative of the evaluation order of the expression, earlier evals
>> lower in the tree, the node at the top is the last evaluated. Then walk the
>> tree from the bottom up to generate code.
>> I think code to do this (efficient compiler code generation) has been done
>> like a gazillion-billion times since 1960.
>
> Computer science people seem to like to brag about how to parse. Walking a
> tree does not solve the tree was built in the wrong order.Parenthesis first
> implies input string re-scanning and text movement.
No, it doesn't. All it requires is a scanner with a stack. Most programming
languages can be parsed without backtracking and with very limited lookahead.
All this was well established in parser theory in the 1970s if not earlier.
But your confusion is not unprecedented; I remember reading a parser (written
in the early 1970s) written by someone who read a text book that actually
claimed the same fallacy. Needless to say the parser was rather messy, though
it somehow managed to get the job done.
The "shunting yard" algorithm is a generalized form of the stack based
expression parsing, applied to whole program parsing. It was created, I
believe, by Dijkstra and Zonneveld for the ALGOL-60 compiler they wrote in
1961, the first ALGOL-60 compiler and, amazingly, an implementation of the full
language (minus the mistakes), even though it ran on a machine with just 4 kW
of memory. For a short description, read Dijkstra's paper describing it, in
English. For a very detailed description, read the Ph.D. thesis of Gauthier
van den Hove, a very impressive work of technical history writing.
The purpose of the shunting yard algorithm is to allow parsing without
backtracking, which is rather important on a machine without enough memory to
store the source text, and one that reads the program source from a paper tape
reader (which, in most of them anyway, does not come with a "reverse" feature).
paul
