The use of transition matrices in a recursive-descent compiler

ABSTRACT

Transition matrices are a well-known tool for the construction of bottom-up compilers. This paper discusses the use of transition matrices in the recursive-descent compiler for the structured assembly language PL/85. In this compiler, a transition matrix (TM) is a self-contained module which can recursively invoke other TMs. TM invocation and exit and state transitions are handled by a microcoded interpreter. It is shown that our use of TMs made the compiler easy to implement and maintain, considerably reduced the space requirements for the parser, and resulted in a reliable, efficient and flexible compiler with good error handling capabilities.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 3: Melvin E. Conway, Design of a separable transition-diagram compiler, Communications of the ACM, v.6 n.7, p.396-408, July 1963 [doi>10.1145/366663.366704]
• 4: Richard W. Conway , Thomas R. Wilcox, Design and Implementation of a Diagnostic Compiler for PL/I, Cornell University, Ithaca, NY, 1971
• 5: David Gries, Use of transition matrices in compiling, Communications of the ACM, v.11 n.1, p.26-34, Jan. 1968 [doi>10.1145/362851.362872]
• 6: David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
• 7: Interdata Users Manual, Publication Number 29-261R03, July 1974.
• 8: Donald E. Knuth, Structured Programming with go to Statements, ACM Computing Surveys (CSUR), v.6 n.4, p.261-301, Dec. 1974 [doi>10.1145/356635.356640]
• 9: Naur, P. Control Record Driven Processing. In: Structured Programming, Infotech State of the Art Report, 1976, 309-322.
• 10: S. Ron Oliver , Nell D. Jones, Program control via transition matrices—a novel application of micro-programming, Proceedings of the ACM SIGMINI/SIGPLAN interface meeting on Programming systems in the small processor environment, p.70-77, March 04-06, 1976, New Orleans, Louisiana, United States
• 11: Pleban, U.F. Design and Implementation of the Structured Assembly Language PL/85. Technical Report TR-76-6, Department of Computer Science, University of Kansas, March 1976.
• 12: Pleban, U.F., Jones, N.D., Klein, W.P., and Muchnick, S.S. PL/85 Users Manual (Second Edition). Technical Report TR-77-1, Department of Computer Science, University of Kansas, February 1977.
• 13: Niklaus Wirth, PL360, a Programming Language for the 360 Computers, Journal of the ACM (JACM), v.15 n.1, p.37-74, Jan. 1968 [doi>10.1145/321439.321442]
• 14: Woods, W.A. An Experimental Parsing System for Transition Network Grammars. In: Rustin, R.(Ed.) Natural Language Processing. Algorithmics Press, 1973.
• 15: Charles T. Zahn, Structured control in programming languages, ACM SIGPLAN Notices, v.10 n.7, July 1975 [doi>10.1145/987305.987308]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.1 Requirements/Specifications
          Subjects: Tools
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Languages