Single-Scan Techniques for the Translation of Arithmetic Expressions into ALGOL 60

ABSTRACT

The first section of the paper contains a brief description of the well-known technique of using a stack, or pushdown store, to re-order the operators of an arithmetic expression, as defined in ALGOL 60, in order to transform the expression into Reverse Polish parenthesis-free form. It is shown that improvements to this Reverse Polish form can be made quite simply, by extending the use of the stack to include information about the operands of the expression. Firstly, information gained from the declarations of the operands can be used to control the generation of real-integer conversion instructions. Secondly, operators whose operands are numerical constants can be computed during translation, using the partially generated Reverse Polish object program as a second stack.

REFERENCES

• 1: HAMBLIN C. L. Translation to and from Polish notation. Comput. J. 5 (Oct. 1962).
• 2: DIJKSTRA, E.W. Recursive programming. Num. Math. 2 (Oct. 1961).
• 3: K. Samelson , F. L. Bauer, Sequential formula translation, Communications of the ACM, v.3 n.2, p.76-83, Feb. 1960 [doi>10.1145/366959.366968]
• 4: DIJKSTRA, E.W. Making a translator for Algol 60. APIC Bull. 7 (May, 1961).
• 5: TAKAHASI, S., NISHINO, H., YosIIHIro, K., AND Fucm, K. System design of the ETL Mk. 6 computer. Proc. IFIP Congress--62, Munich. (North Holland Publ. Co., Amsterdam, Aug. 1962).

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: ALGOL

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

General Terms:
Design, Languages, Performance