Early Programming Books

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