Early Programming Books

[Paul Koning]

> On Jun 21, 2021, at 12:19 AM, ben via cctalk <cctalk at 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