A Method for the Syntax Directed Design of Multiprograms

A method of program design is described which leads naturally to the expression of a program as a pipeline network of simple processes. Starting from the problem statement the valid inputs and outputs are specified by grammars, which can be combined to define the requisite translation. A notation for translation grammars is described informally which allows a translation to take into account semantic as well as syntactic information. Terminal symbols may be attributed by data types and may be qualified by Boolean expressions. The notation is capable of direct compilation but in this paper we show how it may be used to derive a program in a conventional high level language such as Pascal or Cobol. It is shown that more complex problems can be solved by simple pipeline structures of simple translations. Provided that nonbacktracking grammars are used to specify translations, the pipeline structure is well-suited to concurrent execution on a multiprocessor. The method is illustrated by examples from data processing.