INTRODUCTION

This paper contains the documentation of the complete Attributed Abstract Program Tree (AAPT) evaluator generator. In [Faase88] a formal description of the AAPT formalism is given. For a good understanding of the documentation knowledge of the formal description is essential. Many references to this formal description are included in the documentation.

The evaluator generator is implemented using VAX-PASCAL. This is an extension of standard PASCAL, which allows modular programming methods. We have tried to apply a modular approach as much as possible. This has resulted in a large number of modules. Many of these modules can be used in other compiler generators as well. Some of the modules have already been used in other programs. Two of these modules are described in [Faase89].

1 Organisation of the documentation

Each of the modules is described separately, and can be treated as independent documents. These documents contain (generally speaking) the following elements: description of the functionality, description of procedures and functions defined in the module, remarks on the usages of these procedures and functions, remarks on the implementation, description of the interface with other modules, and the source listing. Each document has references to the formal description [Faase88] and other documents.

In this section we give a short description of each module, explaining its position and role within the whole program. The grouping of the modules in the following subsections is determined by the sequential and the hierarchical ordering of the modules. The main program can be divided into five passes. The modules that belong to a given pass are grouped together into a subsection.

1.1 General modules

In this subsection we describe the main program module and three other modules which are used by many of the other modules.

1.1.1 The main program module (main)

This module contains the main program. It also contains a description of how the five passes are connected, and in which order they are executed.

1.1.2 The binary identifier tree module (bintree)

This module contains all the data structures used for storing the information read from the input file and also information derived from the input file. It contains procedures to add new identifiers to the tree and to retrieve information about these identifiers. Besides this, the module also provides procedures which are used for suppressing error messages and a procedure which returns statistical information about the binary identifier tree.

1.1.3 The listing generator module (listing)

This module provides a number of procedures to generate a neat listing. Each of the pages of the listing has a header. The module contains procedures to control the beginning and end of the printing process in the listing. It also contains a left margin mechanism for indentation. The printing is not character oriented, but word oriented.

The module also contains two procedures that can be used for echoing entire lines from the input, and for printing error markings under these lines at the correct position.

1.1.4 The global definitions module (definitions)

This module contains global definitions. These include some global type definitions, and the definitions of the variables which represent the options.

1.2 First pass: scanning and parsing the input

In this subsection we present the modules that are used by the first pass of the main program.

1.2.1 The parser module (parser)

This module contains the parser of the input grammar. All of the type checking and some other semantic checks are done by this module.

1.2.2 The scanner module (scanner)

This module contains the scanner. The scanner reads the input file and returns the symbols it has recognized, together with their representation. The scanner scans one symbol at a time in the input file on request from the parser.

1.2.3 The error handler module (errors)

This module contains the error handler that is responsible for generating error messages during the first pass. (During other passes, errors are reported by the procedures that perform the tests, and thus do not use this module.)

1.3 Second pass: semantical checks

In this subsection we present the modules that are used by the second pass of the main program.

1.3.1 The second pass module (pass2)

This module contains the testing procedures of the first part of the second pass, which are concerned with testing the grammar and calculating the attributes.

1.3.2 The transforming attribute assignments module (trans)

This module contains the procedure that transforms the attribute assignments and performs the remaining semantical checks of the attribute assignments and expressions.

The main reason for the transformation is to check whether all attributes are correctly defined by means of the attribute assignments.

The transformed attribute assignments are used during the (fifth) code generation pass.

1.4 Third pass: generating dependencies

In this subsection we present the module that is used by the third pass of the main program.

1.4.1 The dependency graph generation module (depend)

This module contains the procedures that derive the dependency graph from the given attribute assignments. The graph itself is built by calling procedures of the Simple Multi-Pass Module (see next subsection).

This module also contains the function that tests whether the given grammar is flat implementable (see formal description [Faase88] section 2.9).

1.5 Fourth pass: the simple multi-pass algorithm

In this subsection we present the module that is used by the fourth pass of the main program.

1.5.1 The simple multi-pass module (allsmp)

This module implements the Simple Multi-Pass (SMP) algorithm as described in the formal description. The dependency graph is used to find a partition of the attributes over a number of passes, if a solution exists.

1.6 Fifth pass: program generation

In this subsection we present the modules that are used by the fifth pass of the main program.

1.6.1 The program generation module (genera)

This module contains the procedure that generates all the PASCAL code for the attribute evaluator.

1.6.2 The construction of one-pass relations module
(onepassrel)

In the generation process a number of relations are calculated. These relations are used to determine whether in a certain context an attribute occurrence is implemented as stored in the representation of the abstract program tree, or as a parameter of a tree walking and attribute evaluating procedure.

1.6.3 The type generation module (gtypes)

This module contains the procedures that generate the typing used to represent the abstract program tree that is used by the generated attribute evaluator.

1.6.4 The assignment generation module (gass)

This module contains the procedures to generate the tree traversing and attribute evaluating procedures of the generated attribute evaluator. A set of tree traversing procedures is generated for each pass.

1.6.5 The primitive generation module (genpro)

This module provides a number of procedures that are used to generate the actual PASCAL program code. Roughly speaking, each PASCAL program consists of keywords, symbols, identifiers and comments. This module provides means to generate these quantities in a simple and efficient way.

The module also provides an abstraction mechanism for the representation of different kinds of identifiers used in the generated program.

1.7 Auxiliaries

In this last subsection we present some modules which could not be put under the headings of the previous subsections.

1.7.1 The print binary identifier tree (printtree)

This module contains a procedure that prints the complete contents of the binary identifier tree in alphabetic order of the identifiers.

1.7.2 The performance module (perform)

This module contains a number of procedures used to perform statistical analysis. The analysis can be divided into three groups:

• time analysis, to measure the cpu time used for a certain task,
• counting analysis, to count the number of calls to a procedure, and
• binary identifier tree statistics, to give some statistics about the binary tree.

1.7.3 The open files module (openfiles)

This module contains procedures to open files for reading and writing, with file names given by the user. the existence of a file is checked before it is opened for reading.

1.7.3 The screen management module (screen)

The objectives of the screen management module are to display to the user the scanning/parsing and generation process, and to help him correct errors in the input file.

1.7.4 The primitive terminal interface module (vt100)

This module provides an interface for a vt100 terminal which implements the escape sequences for controlling the special features of this terminal.

2 Notation remarks

Throughout this documentation several conventions are used. First of all an abbreviated reference mechanism is used. In the documentation many references are made to the formal description [Faase88]. All these references only consist of a (sub)section number between square brackets.

A great number of cross references between the modules exist. Each cross reference consist of a mnemonic and a (sub)section number between square brackets. These mnemonics are found below the title and in the page number of the description of each module. They are also given in the previous section, in which the modules are briefly explained.

References to formal identifiers of the formal description are given between quotes using the italic courier font. For example: "node types".

References to constants, types, variables, procedures and functions used in the program are given using the italic courier font, and the underscore symbol is replaced by a space (for sake of increased readability). For example: tnode kind.

3 Conclusions

The program described in this documentation has gone through several development stages. During documentation, several errors in the program where found, which shows that writing documentation is a way of checking the correctness of a program. This is especially true after a program has gone through several development stages.

Having completed the exercise of documentation, we feel that many of the program constructions used should be rewritten. Some constructions, for example, were found to be obsolete. Within the documentation pointers can be found which indicate how constructions could be improved.

References