TOSI: A tree oriented string interpreter for the design and implementation of semantics

In an ideal translator writing system (TWS) each of the components (such as lexical scanners, parsers and code generators) is modularized so that given a component’s input and output specifications, it is possible to replace it by some other which is able to produce the correct output for any input to the original component. For example, if a TWS is used to write a translator and it is desired that a right parse for a source language program be produced, then the translator produced should work correctly whether the parser component used is based on simple precedence methods, LR(k) methods or on Earley’s general context-free parsing algorithm.3* 5* l3 Some components produced by TWSs have been successfully modularized (for example, lexical scanners, parsers and lookup routines)’l but until now the semantic components have not. In this paper we shall describe a tree oriented string interpreter (TOSI), one of whose applications is as a set of semantic modules for translators produced by a TWS. (TOSI has other applications which we shall describe in the fourth section.) TOSI was developed as a generalization of earlier work on a syntax directed translator1 and a syntax directed macroprocessor (SDMP).2 For the syntax directed macroprocessor, Strachey’s General Purpose Macrogenerator ( GPM),g a very powerful and simple string processor, was modified to traverse trees and to interpret strings attached to tree nodes. (The original GPM interpreted a string from a single, fixed input stream.) In the SDMP, the modified GPM performs the ‘semantic’ phase of translation. Semantics are specified by attaching to each production of a context-free grammar, and therefore to each branch node of a derivation tree, a set of strings. When interpreted by the modified GPM, these strings control the evaluation of system and user-defined macros as well as the traversal of some source language input derivation tree. The output of such an interpretive traversal constitutes the target language translation. Implicit in the SDMP is the concept that the semantic phase of translation is implementable as an independent module. The modified GPM needs to know only the node structure of the tree it is traversing and how to access the sets of strings attached to the nodes. (The modified GPM was combined with an implementation of the syntax directed analyser of Abramsonl to produce a usable, but not totally modular, translation system.) TOSI, based on a more flexible string processor than the GPM and conceived as a tool for use in a fully modular TWS, is tree structure independent (actually graph structure independent). TOSI has primitives for tree traversal and for selection of strings from tree