Eli   Documents Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads

General Information

 o Eli: Translator Construction Made Easy
 o Global Index
 o Frequently Asked Questions
 o Typical Eli Usage Errors


 o Quick Reference Card
 o Guide For new Eli Users
 o Release Notes of Eli
 o Tutorial on Name Analysis
 o Tutorial on Type Analysis
 o Typical Eli Usage Errors

Reference Manuals

 o User Interface
 o Eli products and parameters
 o LIDO Reference Manual
 o Typical Eli Usage Errors


 o Eli library routines
 o Specification Module Library

Translation Tasks

 o Lexical analysis specification
 o Syntactic Analysis Manual
 o Computation in Trees


 o LIGA Control Language
 o Debugging Information for LIDO
 o Graphical ORder TOol

 o FunnelWeb User's Manual

 o Pattern-based Text Generator
 o Property Definition Language
 o Operator Identification Language
 o Tree Grammar Specification Language
 o Command Line Processing
 o COLA Options Reference Manual

 o Generating Unparsing Code

 o Monitoring a Processor's Execution


 o System Administration Guide

Mail Home

Definition Table

Previous Chapter Next Chapter Table of Contents

Definition Table Design Criteria

There are many properties that might be of interest to a compiler. A Pascal compiler needs to know the type and value of a constant. More information is needed for a variable: its type, the static nesting level of the procedure containing its declaration, and where it is located in the target machine's memory. The compiler designer must decide how to represent this information.

The first task in definition table design is to select the set of entities to be represented by definition table keys. Then a set of properties must be defined to carry the information associated with the entities. There is no need to specify relationships between properties and entities: a value of any property may be associated with any entity.

Criteria for selecting entities

Identifier definitions must be represented by definition table keys if the normal environment module is used. Whether there are other entities that should be represented by definition table keys depends on the particular translation problem.

Entities that are invariably created by an identifier declaration can be represented by the definition table key bound to that declaration. If an entity may be created without being bound to an identifier, however, then it must be represented by a distinct definition table key. For example, the following Pascal variable declaration defines an identifier and creates a variable bound to that identifier, but also creates a type that is not bound to any identifier:

var I: 1..10;

A Pascal compiler could use one key for the definition of I and the variable, since Pascal variables are created only in conjunction with identifier declarations. It must use a separate key for the subrange type, however, since types can be created without declaring any identifier.

Distinct definition table keys should be used for generated entities that are "similar" to user-defined entities. For example, Pascal labels are created only in conjunction with label definitions; a user-defined label entity can therefore be represented by the definition table key requested by the environment module to represent the label definition. A Pascal compiler will probably create labels in the course of translating statements like if, case and while. These labels should also be represented by definition table keys (obtained from NewKey) to maintain compatibility with user-defined labels. This compatibility is important because of the semantics common to generated and user-defined labels. If it is necessary to distinguish the two, that is easily done via a Boolean property.

Criteria for grouping data values

Each definition table key provides access to information about an entity. The information is embodied in a set of properties. How should those properties be defined?

One possibility is to define a single property to carry all of the information associated with a particular definition table entry. That property would be a structure, with distinct fields to hold the distinct items of information. There is a subtle problem with this approach: Because the items of information associated with an entity are determined at different times by different modules, fields of the structure will be undefined for various periods during its lifetime. If, through an oversight in the design, the compiler accesses one of these undefined fields, then it may very well crash. Such errors are often extremely difficult to diagnose, and the compiler development time is thus increased unnecessarily.

A better approach is to group related information that is obtained at a particular point in the compilation as a single property, and to leave unrelated information or information that is obtained at several different points as separate properties. When a property value is set, that value is complete (if any information was not available at the time, it would have been treated as a separate property), and any query must supply a consistent default value to be returned in case the desired property is not available.

In general, it is better to err on the side of too many properties than too few. Each definition table key is actually implemented as a pointer to a list, with the properties being elements of that list. The list element consists of a code identifying the property and a block of storage large enough to hold a value of the property's type. The length of the list for a particular definition table key is the number of values that have actually been associated with that definition table key. If no update operation is performed for a particular property on an entity, nothing is stored for that property. A valid value is guaranteed to be returned from a query operation because of the default argument supplied to the query call. A default value for a property can be simulated by always using the same value every time the query operation is used for that property.

When properties are combined, the number of list entries may be reduced. (This is not always the case, because two distinct properties only require one list element if one of these properties has its default value.) If the number of list entries is reduced, the time to access properties is reduced. Normally, however, property lists are short and the time to access properties is an insignificant fraction of the total processing time. Thus there is usually little payoff in access time from combining properties.

Previous Chapter Next Chapter Table of Contents