A final solution to the Dangling else of ALGOL 60 and related languages

ABSTRACT

The dangling else problem consists of a class of potential ambiguities in ALGOL-like conditional statements whose basic form is “if B1 then if B2 then S1 else S2” where B1 and B2 are Boolean expressions and S1 and S2 are basic statements. The difficulty lies in whether to attach the else to the first if or to the second one. Existing solutions to the problem are either ambiguous or unnecessarily restrictive. Let S and S1 be statements. We define S to be closed if “S else S1” is not a statement, and to be open if “S else S1” is a statement. Thus an unconditional statement is a closed statement. Open and closed conditional statements are defined by syntax equations in such a way as to preserve openness and closure. In each case, an else must always be preceded by a closed statement. It is shown that the syntax equations are unambiguous, and that any change in the statement types required within the syntax equations would lead to either ambiguity or unnecessary restriction.

REFERENCES

• 1: ARDEN, B., GALLER, B., AND GRAHAM, R. The MAD Manual. U. of Michigan Press, Ann Arbor, Mich., 1965.
• 2: Walter H. Burkhardt, Letters to the editor: syntax and generalization of ALGOL 60, Communications of the ACM, v.8 n.5, p.261, May 1965 [doi>10.1145/364914.364925]
• 3: COBOL-1961: revised specifications for a common business oriented language. Publ. 0-598941, U.S. Government Printing Office, Washington, D.C., 1961.
• 4: Robert W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM (JACM), v.10 n.3, p.316-333, July 1963 [doi>10.1145/321172.321179]
• 5: PL/I: Language specifications. Form C26-6571-2, IBM Programming Systems Publications, Poughkeepsie, N.Y., Jan. 1966.
• 6: Arthur F. Kaupe, Jr., A note on the dangling else ALGOL 60, Communications of the ACM, v.6 n.8, p.460, Aug. 1963 [doi>10.1145/366707.367585]
• 7: J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
• 8: Peter Naur , J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger, Report on the algorithmic language ALGOL 60, Communications of the ACM, v.3 n.5, p.299-314, May 1960 [doi>10.1145/367236.367262]
• 9: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL, and its formal definition: Part II, Communications of the ACM, v.9 n.2, p.89-99, Feb. 1966 [doi>10.1145/365170.365202]
• 10: Christopher J. Shaw, A specification of JOVIAL, Communications of the ACM, v.6 n.12, p.721-736, December 1963 [doi>10.1145/763973.763978]