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.