Removing backward go-to statements from Ada programs: possibilities and problems

ABSTRACT

We here apply a recent mathematical result to the design of a process for removing backward go-to statements from Ada programs. Such statements are often used by programmers whose only reasons to use Ada are contractual. The mathematical result involves directed graphs, such as the flow graphs of programs, and the first step in our algorithm involves constructing the flow graph of an Ada program. In the second step, this flow graph is rearranged according to our mathematical result, which specifies a linear order for every flow graph, together with a structure for it, of loops within loops, in which no loops overlap. In the third step, a new Ada program is produced from the rearranged flow graph. A problem arises here, within the syntax of Ada, which does not allow branching into a sequence of statements. We show how this problem must be addressed, even though addressing it can involve removing existing structure from the Ada program which we are processing.

REFERENCES

• 1: Corrado Böhm , Giuseppe Jacopini, Flow diagrams, turing machines and languages with only two formation rules, Communications of the ACM, v.9 n.5, p.366-371, May 1966 [doi>10.1145/355592.365646]
• 2: Ward Douglas Maurer, The Rearranger - A New Assembler Utility, Proceedings of the 21st IEEE/ACM International Conference on Automated Software Engineering, p.357-358, September 18-22, 2006 [doi>10.1109/ASE.2006.66]
• 3: Ward Douglas Maurer, Generalized structured programs and loop trees, Science of Computer Programming, v.67 n.2-3, p.223-246, July, 2007 [doi>10.1016/j.scico.2007.02.002]
• 4: Oulsnam, G. 1982. Unraveling unstructured programs. The Computer Journal 25, 379--387.
• 5: Sharir, M. 1981. A strong-connectivity algorithm and its applications in data flow analysis. Computers and Mathematics with Applications 7, 67--72.
• 6: Williams, M. H., and Ossher, H. L. 1978. Conversion of unstructured flow diagrams to structured form. The Computer Journal 21, 161--167.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Design, Theory

Keywords:
ada compilers, directed graphs, go-to statements, loop trees