Eli   Documents

General Information

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

Tutorials

 o Quick Reference Card
 o Guide For new Eli Users
 o Release Notes of Eli
 o Tutorial on Name Analysis
 o Tutorial on Scope Graphs
 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

Libraries

 o Eli library routines
 o Specification Module Library

Translation Tasks

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

Tools

 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

Administration

 o System Administration Guide

Mail Home

Oil Reference Manual

Previous Chapter Next Chapter Table of Contents


OIL's Support Library

The library functions are grouped according to classes of functions. Within each class a C definition of the function is presented, followed by a brief description of the semantics of the function.

The next section describes the five C types used and defined by the library. These types are defined entirely by the functions in OIL's library.

The follow-on section describes operator identification using set of possible types which is the most general identification method supported by OIL.

Should a call to an OIL function for operator identification or coercion sequence construction fail, special values are returned. Functions are supplied to test for these special values allowing production of error messages for these error cases.

Besides operator identification using set of possible types, there is also a simpler identification algorithm which is strictly bottom up. It is useful when the full power of OIL is not necessary and the efficiency of a one pass algorithm can be utilized.

Looking at an operator's type signature is fundamental to propagating the constraints of an operator's type signature out from the node it labels. OIL supplies a function to examine any given operator's function signature,

Coercion sequences are fundamental to most uses of OIL and constructing and examining coercion sequences is critical to examining them for code generation purposes.

Creating instances of specified classes. OIL's CLASS construct allows for easy support of most type constructors. OIL allows a type constructor to be specified and then instantiated to create a type which conforms to the specification of the CLASS.

Names are an enumeration of the identifiers in the specification for easy comparisons. When a class is instantiated all its operators have new unique signatures based on the created type, but the names of corresponding operators are the same as those used in the specification of the class operator.

Construction of types, operators, identifications and classes can be performed by the library functions. Thus should a particular application need to build and define a unique class, coercion or any OIL object it can be done during the compilation using these functions.

Library Types

The semantics of the functions are described in terms of the basic types understood by OIL.
tOilType
This type is associated with the identifiers defined as (type) in the OIL specification and represents type denotations. It is used to define function signatures for operators and thus the coercion graph.

tOilOp
This type is associated with the identifiers defined as (operator) in the OIL specification. An element of this type can have associated with it either a function signature or a list of identifiable operators. All coercions are operators.

tOilTypeSet
Is a private type of the OIL library functions which represents a set of type denotations and represents the set of possible types concept.

tOilClass
This type is associated with identifiers defined as (class) in the OIL specification and identifies the set of operators and coercions defined for that class. It is used as the handle for instantiating a class. The instantiation operation creates a new object of type: tOilType and adds new instances of the operators and coercions defined for the class.

tOilCoercionSeq
This type represents a sequence of coercion operators which will transform a value of one type into a desired type. The coercions sequence may be empty or of an arbitrary length. Each element in a coercion sequence is a coercion operator.

There is one other type which is important for use of the ADT and that is the name of a class, type or operator. A name is represented as a definition table key (see The Definition Table Module of Definition Table) and each identifier in the OIL specification has a unique name associated with it. This allows a class operator to be treated the same regardless of its arguments. But since the argument signature of an instantiated class operator will refer to the types used to instantiate the class, the type specific information can be referenced as needed.

Set of Possible Types

The functions OilIdResultTS* identify the set of possible result types given the operator indication (oi) and the set of possible result types (ats*) for each operand.

The set of types (tOilTypeSet) returned describes the the union of the result types of any of the operators which can be identified by (oi) with any combination of argument types selected by the argument type sets, (at*.) Also in this set are types which can be reached from identified operators by means of a coercion sequence.

tOilTypeSet OilIdResultTS1( oi:tOilOp, ats:tOilTypeSet );
tOilTypeSet OilIdResultTS2( oi:tOilOp, ats1,ats2:tOilTypeSet );
tOilTypeSet OilIdResultTS3( oi:tOilOp, ats1,ats2,ats3:tOilTypeSet );

The functions OilIdOpTS* identify an operator given the operator indication (oi), the result type (rt) and the sets of possible argument types (ats*.)

tOilOp OilIdOpTS1( rt:tOilType, oi:tOilOp, ats:tOilTypeSet );
tOilOp OilIdOpTS2( rt:tOilType, oi:tOilOp, ats1,ats2:tOilTypeSet );
tOilOp OilIdOpTS3( rt:tOilType, oi:tOilOp, ats1,ats2,ats3:tOilTypeSet );

Suppose that an operator indication can identify only a single operator, but it is used in an inappropriate context for that operator. Functions OilIdOpTS* will return an invalid operator in that case. In many situations, however, it is preferable to return the one possible operator and report errors in the context. The function OilNoOverload is used in these situations.

tOilOp OilNoOverload( oi:tOilOp, OilIdOpTS*( ... ));

The function OilTypeToSet constructs a set of types from a given type denotation. The set of types returned contains t and all the type denotations which can be reached from t by any sequence of coercion operators.

tOilTypeSet OilTypeToSet( t:tOilType );

The function OilSelectTypeFromTS selects a type from a given set of types. The type selected is the type which is both in the set ts and can be coerced to all the types in the set.

tOilType OilSelectTypeFromTS( ts:tOilTypeSet );

The following equation is true for any type t:

OilSelectTypeFromTS( OilTypeToSet( t ) ) = t

The function OilBalance selects a type which can be coerced to all the elements which sets ts1 and ts2 have in common. This operation corresponds with function of type balancing in typed expression analysis from compiler and programming language theory.

tOilType OilBalance( ts1,ts2:tOilTypeSet );

The following is true for all type sets ts1 and ts2:
OilBalance( ts1,ts2 ) = OilSelectTypeFromTS( ts1 AND ts2 )

One other important operation on sets is a test for set membership. This operation is performed on a type set by the function OilSetIncludes, which returns true if the set s includes the type t.

int OilSetIncludes( s:tOilTypeSet, t:tOilType );

OilSetIncludes will be the usual mechanism for testing if a expression can be coerced to a particular type. The expression's set of possible types is calculated and OilSetIncludes is used to check if the type in question is in the set of possible types.

Validating operator identification

The function OilIsValidOp validates that a given value denotes a valid operator. Since any operator identification operation will return some operator indication, we need to validate that the operator identified was not the catchall illegal operator.

int OilIsValidOp( op: tOilOp );

Simpler operator identification

The function OilIdOp* can identify the operator associated with the indication (oi) which has an argument type to which (at) can be coerced. In general these are less powerful than the `set of result type' operators, but for simple languages they are both faster and easier to use. You can probably use these if you can identify the correct operator from the the types of the operands alone without regard to the context.

tOilOp OilIdOp1( oi: tOilOp, at: tOilType );
tOilOp OilIdOp2( oi: tOilOp, at1,at2: tOilType );
tOilOp OilIdOp3( oi: tOilOp, at1,at2,at3: tOilType );

Looking at an operator's type signature

The function OilGetArgType allows us to get the type of the n'th argument (arg) of an operator(op.) The 0'th argument returns the result type from the function signature.

tOilType OilGetArgType( op:tOilOp, arg:int );

Coercion sequences

The function OilCoerce allows us to construct a sequence of coercion operators from type t1 to t2. The first operator in the sequence (see OilHeadCS below) will have a result type of t2. The last operator in the sequence will have a source type of t1. OilCoerce will always return a coercion sequence. But if there is no valid coercion sequence between the types then the catchall error coercion sequence is produced.

tOilCoercionSeq OilCoerce(  t1,t2:tOilType );

These operations on coercion sequences (tOilCoercionSeq) allow us to step through a coercion sequence and perform an action for each operator in the sequence.

The function OilEmptyCS will test a coercion sequence to see if it is empty. The result will be true is the argument is empty and false otherwise.

The function OilHeadCS returns the first operator in the sequence. The operator returned by OilHeadCS will have been defined by a coercion statement. Or it will be the error operator in the case of an error coercion sequence.

The function OilTailCS returns the rest of the sequence once the first operator in the sequence is removed.

int OilEmptyCS( cs: tOilCoercionSeq );
tOilOp OilHeadCS( cs: tOilCoercionSeq );
tOilCoercionSeq OilTailCS( cs: tOilCoercionSeq );

The function OilIsValidCS allows us to validate a coercion sequence. It is crucial to detect invalid typing for a subexpression since every call to OilCoerce will return a coercion sequence and we need to know if the sequence returned was the catchall error coercion.

int OilIsValidCS( cs: tOilCoercionSeq );

Instantiate Classes

When a class is instantiated a new type is created and the set of operators and coercions defined for that class are created using the created class and the types indicated by the parameters to build the actual function signatures for the created operators. The `is coercible to' relation is enhanced by all the coercions defined by the instantiation.

Classes can be instantiated by calling one of the functions:

tOilType OilClassInst0( c:tOilClass, n:DefTableKey );
tOilType OilClassInst1( c:tOilClass, n:DefTableKey, at:tOilType );
tOilType OilClassInst2( c:tOilClass, n:DefTableKey, at1,at2:tOilType );

Constraints:

The number of parameters defined for the class must match the number of types supplied as arguments.

Name Functions

Each type, operator and class has a name associated with it. There is a function for retrieving the name associated with a specific type during attribution:

DefTableKey OilTypeName( t:tOilType );
DefTableKey OilOpName( op:tOilOp );
DefTableKey OilClassName( c:tOilClass );

If the identifier MyType is a type in a specification then the C symbol MyType will have the value of OilTypeName(MyType).

Compile Time

The OIL library has all of the necessary functions for the construction of OIL entities during the execution of the generated compiler. This capability allows the changing of the OIL schema in more detailed ways than simply instantiating an already specified class. The different capabilities for modifying the schema are:

Type Constructor
A new type may be constructed without using Classes.
Operator Constructor
A new operator may be explicitly constructed with a given signature(remember operators are use to represent indications also.)
Signature Constructor
An argument signature for an operator can be constructed from types.
Coercion Constructor
A properly constructed operator can be declared to be a coercion.
Identification Constructor
Any operator can be defined to `indicate' any other operator.
Class Constructor
Can be built from class operators and coercions.

Types

In addition to class instantiation, a new type may be constructed with the function OilNewType. Its only argument is the name to be associated with the new type.
tOilType OilNewType( id:DefTableKey );

Operators

Constructing a new operator is a two step process, first a new argument signature must be constructed and then a new operator with that signature can be constructed using the function OilNewOp. Besides the argument signature, OilNewOp requires the name of the new operator(id), and the cost of the new operator(cost.)
tOilOp OilNewOp(id:DefTableKey,sig:tOilArgSig,cost:int);

Argument Signatures

Argument signatures are built in two steps: an empty signature is constructed with OilNewArgSig and then a type is pushed onto the front of the signature using OilAddArgSig.
tOilArgSig OilNewArgSig(dummy:int);
tOilArgSig OilAddArgSig( arg:tOilType, sig:tOilArgSig );
Note that by convention, the last type pushed onto the signature is the result type of the created operator.

Coercions

Any operator with an argument signature of length 2 can be a coercion by simply applying OilAddCoercion on it.
int OilAddCoercion( op:tOilOp );

Constraints

A check is not made that the signature is of length 2.

Identifications

A relationship between an operator indication (ind) and an operator (op) is established by simply supplying them to the OilAddIdentification function. OilAddIdentification returns the value of op.
tOilOp OilAddIdentification( ind, op:tOilOp );

Constraints

A check is not made regarding the redundancy of the new identification with respect to the existing schema. You can have ambiguity of which operator is identified by any given indication and operand signature. OIL will choose the most recently declared, least cost identification.

Classes

Classes are very complex entities and are constructed in stages. First an empty class in created using OilNewClass. The argument id specifies the name of the class and the argument argNum specifies how many parameters the class has.
tOilClass OilNewClass(id:DefTableKey,argNum:int);

To an existing class(c) we can add an operator with a given class signature(sig) and given cost(cost) with the function OilAddClassOp.

tOilClassOp OilAddClassOp(id:DefTableKey,sig:tOilClassArgSig,cost:int, c:tOilClass);

With a class operator we can create an identification of an instantiated class operator(op) by an existing operator(ind) with the function OilAddClassOpId.

int OilAddClassOpId(ind:tOilOp,op:tOilClassOp);

The function OilAddClassCoercion is used to define an existing class operator(op) to be a coercion.

int OilAddClassCoercion(op:tOilClassOp);

Building a class argument signature is similar to constructing a simple argument signature but it is complicated by the fact that a class argument needs to be described in terms of a parameter binding. A class argument's parameter binding determines the value of the parameter when the class is instantiated. Like simple signatures we first build an empty class signature and then push arguments onto it. An empty class signature is created with OilNewClassSigArg and an argument description is added with OilAddClassSigArg.

tOilClassArgSig OilNewClassSigArg(dummy:int);

tOilClassArgSig OilAddClassSigArg(
			    td:tOilClassSigArgDesc,
			    st:tOilType,
			    pi:int,
			    cs:tOilClassArgSig
			  );

The extra arguments to OilAddClassSigArg describe the possible bindings which will instantiate the class signature.
td
Can be eClassRef to indicate that a reference to the created type replaces this argument, eParamRef to indicate that one of the parameters to the class instantiation will replace this argument or eSpecTypeRef to indicate that a specific type will replace this argument.
st
Specifies which explicit type will replace this argument.
pi
Selects which parameter of the class instantiation will replace this argument.


Previous Chapter Next Chapter Table of Contents