Certifications of algorithms 117 and 118 magic square (odd and even orders)2

The proof of the non-existence of a phrase structure grammar for ALGOL 60 by Robert W. Floyd [Comm. ACM 5 (Sept. 1962)] depends on the assumption that a syntactically correct ALGOL program must be a block. The concept of “program” is defined ambiguously in the ALGOL Report, as pointed out by Naur [1], but it is generally accepted that a program is defined as a self-contained statement. If this definition is taken, Floyd's proof becomes incomplete in that it ignores the fact that the following are syntactically correct ALGOL programs: begin; end begin end &lpargt;dummy statement⦔

View this article in the ACM Digital Library.