Eli   Documents
Eli: Translator Construction Made Easy

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

Next Chapter Table of Contents

Introduction

OIL deals with three primary concepts: operators, types and indications. The operators which OIL refers to are strongly typed functions. The types which are named in an OIL specification are referred to as `primitive types' but there are also `constructed types' which are created at compile time. Indications are a name given to a list of operators which may be identified by an appearance of an indication in an expression.

Although operators, types and indications are primary terms in discussing OIL and operator identification, the rest of this chapter is devoted to explanations of:

Operator identification::
A review of operator identification by example.
Coercions::
Coercions allow the compiler to use a value of one type where another is specified.
Sets of possible types::
The set of all the types which an expression might return.
Classes::
A set of operators and coercions which can be instantiated for a newly created constructed type.
Names::
An enumeration associated with each operator, type and class identifier.

Operator identification

Anyone familiar with compiler construction is familiar with operator identification but may not necessarily know it by that name. Thus operator identification is introduced by an example.

In Pascal the expression x+y can have a number of meanings or it may be invalid. For it to be valid x and y must refer to type values which allow the identification of a well typed operator associated with +. The operator identified might be integer addition, real addition or set union. The operator identified is determined by the types associated with x and y and be formulated like:

  • x and y are both integer then integer addition

  • x and y are sets with the same element type then set union

  • one of x and y is real and the other is real or integer then real addition

  • otherwise x+y is undefined or an error

The + in x+y is called the indication and x and y are the operands. The process of operator identification chooses a strongly typed operator associated with the indication and has a type signature which matches the types of the operands. This is a simplification but it does capture the essentials of operator identification.

The operation of `matching' the operand type with the type signature is really the relation `is coercible to', see Coercions.

Coercions

A coercion is a distinguished operator which the compiler may insert in an expression to make operator identification possible. In the previous section the Pascal expression x+y could identify a real expression if x's type was real but y's type was integer. OIL allows this to be specified using a coercion from integer to real. Thus whenever an integer is supplied but a real is required the compiler may apply the coercion to the integer argument and thus have only real arguments to identify real addition with.

If there is a coercion from type A to type B then type A is said to be `coercible to' type B.

A coercion sequence is any number of coercions applied in sequence. In OIL a coercion sequence is used as if it were a single coercion. Thus if type A is coercible to type B and type B is coercible to type C then there is a coercion sequence from type A to type C. The elements in the sequence are the coercion operators in the order they need to be applied to satisfy the type constraint. Thus using a coercion sequence type A may match and argument of type C.

Coercion sequences lead to a revised definition of `coercible to'. If there is a coercion sequence from type A to type B then type A is said to be `coercible to' type B. Note that since a coercion sequence may be empty every type is coercible to itself.

Sets of possible types

Each type has an associated set of possible types. A type B is in the set of possible types for type A if A is coercible to B.

Likewise an expression may have a set of possible types. Take x+y as an example. The set of possible types associated with the expression would include the result type of any operator which can be identified by + and an element from the set of possible types for x and an element from the set of possible types for y.

Note that the set of possible types is a transitive closure of the relation `is coercible to'. When a new coercion is created then the transitive closure of every type may need to be updated. But in practice this is not the case and most coercions have no impact on the set of possible types for most types.

Classes

Formally OIL's classes are parametric abstract types. But they may be most easily comprehended as a procedure which takes some types as an argument and creates a new type and adds a set of operators and coercions into an existing type schema. The net effect being that the new operators may now be identified and the set of possible types for some types may be increased.

Consider the subrange type constructor in Pascal. It creates a coercion from the subrange to the base type.

Names for operators, types and classes

You will want associate semantics to the identifiers in your OIL specification. Names allow a convenient way of doing that. All types, classes and operators have names associated with them. The name is represented as a definition table key (see The Definition Table Module of Definition Table) and can be referenced in your attribute grammar by the identifier used in the OIL specification.

The name associated with an ADT type, class or operator is accessed by using the unary functions: OilTypeName, OilClassName and OilOpName.

Next Chapter Table of Contents