VITAL(ID:306/vit001)for Variably Initialized Translator for Algorithmic Languages Semantics language using FSL (Formal Semantics Language). Mondshein, 1967. used for the Lincoln Lab's GSS Places Related languages
References: in [ACM] CACM 9(03) March 1966 includes proceedings of the ACM Programming Languages and Pragmatics Conference, San Dimas, California, August 1965 view details in [ACM] CACM 9(03) March 1966 includes proceedings of the ACM Programming Languages and Pragmatics Conference, San Dimas, California, August 1965 view details in [ACM] CACM 9(03) March 1966 includes proceedings of the ACM Programming Languages and Pragmatics Conference, San Dimas, California, August 1965 view details FSL and its descendents (Feldman [Feld 66]) The problem faced in the original FSL effort was the development of a language for describing the postsyntactic (semantic) processing. An adequate semantic metalanguage should permit the description of the source language to be as natural as possible. It should be readable so that other people can understand the meaning of the source language being defined. It should allow a description which is sufficiently precise and complete to enable efficient automatic compilation. Finally, the metalanguage should not depend on the characteristics of a particular computer. The syntax metalanguage used in FSL is very close to the production language discussed in Section II.B.5. A statement in this syntax language may include a command "EXEC n" which is a call on the semantic statement labeled n. The only other interaction between syntax and semantics is the pairing of syntactic and semantic descriptions in the main stack. The semantic metalanguage, FSL, was the main focus of effort and is discussed in some detail here. The overriding consideration in FSL was machine independence as opposed to object code optimization in the TRANGEN effort discussed below. The plan was to have the metalanguage be machine independent, with the machine dependent aspects of translation handled by a large set of primitives embedded in the compiler kernel. Statements in the metalanguage would be compiled (whence compilercompiler) into machine code made up largely of calls on primitive routines. Some examples should serve to illustrate this approach. Suppose the syntax phase is processing a REAL declaration and calls semantic Routine 1 with the identifier being declared in the second position of the stack (LEFT2). 1: ENTER[SYMB; LEFT2, (STORLOC I DOUBLE), REAL, LEV]; STORLOC e- STORLOC -4- 2 Here a description of the variable is placed in the symbol table, S YMB. The entries for the variable are its name, a tagged address, the word REAL, and the current block level. Finally, STORLOC is increased by two, allocating two cells to the double-precision variable. When an identifier is scanned in an arithmetic statement, semantic Routine 2 is called. 2: IF NOT LEFT1 IS CONSTANT THEN IF SYMB[LEFT1, TYPE] = REAL THEN RIGHT1 e-- SYMB[LEFT1, SEMANTICS] ELSE FA ULT 1 In semantic Routine 2, if the identifier (in LEFT1) is a constant, the routine terminates. If not, the identifier is a variable and must be looked up in the symbol table. The table-lookup is accomplished in FSL through a special table operand of the form (table name) [(operand), (position name)]. This instance of a table operand initiates a search of the table SYMB for an entry (row) whose first column equals the contents of LEFT1. Then the specified position (TYPE) of the matched row is selected and compared with the string construct REAL. If they are the same, the variable was declared to be REAL and all is well. In this case the SEMANTICS (tagged address) of the matched row in SYMB is assigned as the semantics of the real variable. If the variable is not of type REAL or is not in the table at all, the statement FAULT 1 will be executed. This causes the printing of an error message on the listing of the source language program being compiled. Finally, suppose the syntax has recognized an addition which is to be compiled and calls semantic Routine 3. 3: RIGHT2 ~ CODE(LEFT4 "b LEFT2) The code brackets "CODE (" and ")" specify that the statement within them is to be compiled into object code, rather than executed during translation. The execution of this statement will produce a call on a code generating routine which uses the semantic descriptions in the second and fourth positions of the stack to compile a code sequence for addition. The semantic descriptions include the data type, sign, index attributes, and current location of an operand; these, along with the state of the translator, are enough to produce locally good code. The result of an addition is itself an expression, and the syntax is presumed to have put the syntactic symbol, E, into the second position of the stack (cf. line T1 -4- 1, Figure 9, p. 87). The assignment to RIGHT2 will associate the semantics of the result (e.g. DOUBLE, in accumulator) with the syntactic symbol. The FSL system allows almost all constructs to appear inside code brackets (to be done at execution time) or outside code brackets (to be done during translation). The semantic metalanguage, FSL, allows a compiler writer to declare and use a variety of data structures in building a translator. Besides the tables and cells mentioned in the examples, there are stacks, masks, and strings. The system includes a number of auxiliary routines (e.g. format, file manipulation) available at both translation and execution time. The Formula ALGOL compiler was largely written in FSL, and the description [It 66] of that implementation provides a good study of the strengths and weaknesses of FSL. The weaknesses of FSL can be characterized as the lack of several conveniences and a number of basic structural defects. The lack of conveniences, such as index variables, recursive subroutines, assembly language embedding, and debugging aids, are due to its development as a thesis (hit and run) project and have been remedied in later systems. The structural defects result mainly from the attempt to preserve machine independence. An FSL system is useful to the extent that the compiler writer's needs are met by the facilities of the semantic metalangnage. This, in turn, is possible only where there are suitable formalizations of the pertinent, concepts. Thus all the research problems listed in Section IV.C (e.g. data structures, paging, parallelism) are problems in any FSL system. One common misconception is that FSL requires code to be produced immediately when a construct is recognized. One is allowed to defer code generation indefinitely, but the systems now running do not have particularly good facilities for global code optimization or multipass compilers. These problems are being attacked in several current FSL-like projects. There are, however, limits to the level of code optimization which can be achieved in a machine independent way. There is a sense in which any FSL system is predestined to failure: techniques will always be used before they are sufficiently well understood to be formalized. Such a system can still be very helpful, and the search for metalangnage representations should lead to careful study of new techniques. In addition, a particular implementation will normally include informal techniques (e.g. assembly language) for handling constructs not yet formalized. The only other FSL-like system completed to date is VITAL [Mond 67] at the Lincoln Laboratory. VITAL runs in a time sharing environment and differs from FSL mainly in system features. These, along with a number of notational improvements (used in this description), make VITAL much easier to use but are of little theoretical interest. Among the more significant changes is the executable syntactic class name which reduces the size of the syntax table by about one fourth and increases speed. All text is saved in linked blocks of dictionary pointers; this facilitates line editing and reduces recompilation time by about one half. The combined features of persistent storage and compile-time execution aid in the writing of incremental compilers. The user is given considerably more flexibility in register allocation but can choose to abrogate this responsibility as in the original system. A minor but philosophically important change was the addition to the production language of a syntactic (action}, TEST, which depends on a variable set by the semantics. This violates the BNF tradition, but it was found to be necessary for some translators and a great convenience in several others. The FSL systems have undoubtedly been handicapped by being implemented on uncommon machines, the G-20 and the TX-2. To compensate for this there are now three separate implementations for the IBM 360 series in progress. The CABAL group at Carnegie [Fie 67] is designing a system for multipass compilers using a semantic language which is a minimal extension of ALGOL in the direction of FSL. The work under Gries at Stanford [Grie 67b] will also be multipass-oriented but will use a special purpose semantic language. The Lincoln Laboratory effort under J. Curry will probably be quite similar to VITAL. All of these projects may be considered attempts to combine the virtues of FSL with those of TGS, our next subject. in [ACM] CACM 11(02) (February 1968) view details in [ACM] CACM 12(11) (Nov 1969). view details in [ACM] CACM 12(11) (Nov 1969). view details |