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

Tutorials

 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

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

Type Analysis

Previous Chapter Next Chapter Table of Contents


User-Defined Types

A language that permits user-defined types must provide constructs for the user to denote such types. These constructs are called type denotations. If a programmer writes two type denotations that look the same, it is natural to ask whether they represent the same type. There are two general answers to this question:

Name equivalence
Each type denotation that the programmer writes represents a distinct type.

Structural equivalence
Two type denotations represent the same type if they are constructed in the same way and if corresponding components are the same (see Structural Type Equivalence).
All of the techniques discussed in this document apply independently of the selection of name equivalence or structural equivalence among user-defined types.

A type identifier is a name used in a source language program to refer to a type. It is important to distinguish between the concept of a type and the concept of a type identifier, using different keys to implement them, because a particular type might have zero or more type identifiers referring to it. For example, consider the following snippet of C code:

typedef float time;
typedef float distance;
typedef struct { time t; distance d; } leg;
leg trip[100];
This snippet creates two user-defined types, a structure type and an array (or pointer) type. Moreover, it defines three type identifiers, time, distance, and leg. The first two refer to the language-defined float type, and the third refers to the structure type; the array type is anonymous -- no type identifier refers to it. Seven definition table keys are therefore associated with the types and type identifiers of this snippet; three more are associated with the typed entities t, d, and trip (see Typed Entities).

The Typing module exports computational roles to implement the definition and use of user-defined types:

TypeDenotation
The computational role inherited by a grammar symbol that represents a subtree denoting a type.

TypeDefDefId
The computational role inherited by a grammar symbol that represents a defining occurrence of a type identifier.

TypeDefUseId
The computational role inherited by a grammar symbol that represents an applied occurrence of a type identifier.

Type denotations

Type denotations are language constructs that describe user-defined types. The symbol on the left-hand side of a rule defining a type denotation characterizes the type denoted. It inherits the TypeDenotation role, which provides three attributes:

Type
A DefTableKey-valued attribute representing the type denoted by this subtree. This attribute is set by a module computation that should never be overridden by the user. It should be used in any computation that does not require properties of the type.

TypeKey
A DefTableKey-valued attribute representing the type denoted by this subtree. This attribute is set by a module computation that should never be overridden by the user. It should be used in any computation that accesses properties of the type.

GotType
A void attribute representing the fact that information characterizing a user-defined type has been stored as properties of the key TypeDenotation.Type.
The information stored as properties of the definition table key TypeDenotation.Type cannot be dependent on the results of type analysis (see Dependences for typed entities).

For example, some languages (e.g. Modula-3, Ada) allow a user to define a subrange type that is characterized by its bounds. The bound information may be needed in various contexts where the type is used, and therefore it is reasonable to store that information as properties of the subrange type's key. Suppose, therefore, that Lower and Upper are defined as integer-valued properties. Bound information is independent of any aspect of type analysis:

SYMBOL SubrangeSpec INHERITS TypeDenotation END;
RULE:  SubrangeSpec ::= '[' Number 'TO' Number ']' COMPUTE
  SubrangeSpec.GotType+=
    ORDER(
      ResetLower(SubrangeSpec.Type,atoi(StringTable(Number[1]))),
      ResetUpper(SubrangeSpec.Type,atoi(StringTable(Number[2]))));
END;

Here Number is a non-literal terminal symbol whose value is the digit string appearing in the source text; atoi is the string-to-integer conversion routine from the C library.

Type identifiers

The computational role TypeDefDefId is inherited by a defining occurrence of a type identifier. It provides two attributes:

Type
A DefTableKey value representing the type named by the type identifier. This attribute must be set by a user computation. It should be used in any computation that does not require properties of the type.

TypeKey
A DefTableKey-valued attribute representing the type denoted by this subtree. This attribute is set by a module computation that should never be overridden by the user. It should be used in any computation that accesses properties of the type.

The computational role TypeDefUseId is inherited by an applied occurrence of a type identifier. It provides two attributes:

Type
A DefTableKey value representing the type named by the type identifier. This attribute is set by a module computation that should never be overridden by the user. It should be used in any computation that does not require properties of the type.

TypeKey
A DefTableKey-valued attribute representing the type denoted by this subtree. This attribute is set by a module computation that should never be overridden by the user. It should be used in any computation that accesses properties of the type.

Referring to a type

A type might be referenced in program text in any of three different ways, each illustrated by a Java or C variable definition:

  1. By writing a keyword, as in int v;

  2. By writing a type identifier, as in t v;

  3. By writing a type denotation, as in struct {int i; float f;} v;

Each of these representations of a type uses its own mechanism for encoding the type. In order to standardize the encoding, a type reference is normally represented in the tree by a distinct symbol having a DefTableKey-valued Type attribute (see Establishing the type of an entity). For example, Type plays that role in this representation for a variable declaration:

RULE: VrblDecl ::= Type VarIdDefs ';' COMPUTE
  VrblDecl.Type=Type.Type;
END;

Here the value of Type.Type represents some type. That attribute must be defined by providing a rule establishing the type represented by a type identifier, a rule establishing each language-defined type represented by a keyword, and a rule establishing each user-defined type represented by a type denotation:

SYMBOL TypIdUse INHERITS TypeDefUseId END;

RULE: Type ::= TypIdUse COMPUTE
  Type.Type=TypIdUse.Type;
END;

RULE: Type ::= 'int' COMPUTE
  Type.Type=intType;
END;

RULE: Type ::= SubrangeSpec COMPUTE
  Type.Type=SubrangeSpec.Type;
END;

The Type attributes discussed in this chapter generally do not give direct access to properties of the type they represent, because many of their values are intermediate in the type analysis computations (see Dependences among types and type identifiers). If it is necessary to access properties of a type at a symbol inheriting TypeDenotation, TypeDefDefId or TypeDefUseId, use the TypeKey attribute. Values of the Type attribute of a symbol inheriting ExpressionSymbol or TypedUseId can be used directly to access type properties.

Operator, function, and method definitions

A user-defined type is often associated with one or more operators. For example, an array type requires an access operator (see Operators with explicit operands). The Expression module provides computational roles and rule computations to define these operators:

OperatorDefs
The computational role inherited by a grammar symbol that represents a context where operators are defined.

OpndTypeListRoot
OpndTypeListElem
Computational roles inherited by grammar symbols that represent operand definition lists.

MonadicOperator
DyadicOperator
ListOperator
Coercible
Rule computations implementing definition contexts.

All operators associated with user-defined types must be added to the database of valid operators before type analysis of expressions can begin. This dependence is made explicit by having the left-hand side symbol of any rule in which operators are defined inherit the OperatorDefs role. One attribute is used to express the dependence:

GotOper
A void attribute indicating that all of the operator definitions in this rule have been carried out. It is set by a module computation that should be overridden by the user.

The OpndTypeListRoot role is inherited by a grammar symbol representing a list of operand types. It has one attribute:

OpndTypeList
A synthesized attribute whose DefTableKeyList value is a list of the operand types in reverse order. It is set by a module computation that should not be overridden by the user.

The OpndTypeListElem role is inherited by a grammar symbol representing a single operand type in a list. It must be a descendant of a node playing the OpndTypeListRoot role, and has one attribute:

Type
A synthesized attribute whose DefTableKey value is set by user computation to represent the operand type.

Operators are actually defined by rule computations. Let `ind', `opr', `rand', `rand1', `rand2', and `rslt' be definition table keys and `rands' be a list of definition table keys.

MonadicOperator(`ind',`opr',`rand',`rslt')
Adds operator `opr'(`rand'):`rslt' to the set named by indication `ind'.

DyadicOperator(`ind',`opr',`rand1',`rand2',`rslt')
Adds operator `opr'(`rand1',`rand2'):`rslt' to the set named by indication `ind'.

ListOperator(`ind',`opr',`rands',`rslt')
Adds operator `opr'(t1,...,tn):`rslt' to the set named by indication `ind'. Here t1,...,tn are the values obtained from `rands'.

Coercible(`opr',`rand',`rslt')
Adds coercion `opr'(`rand'):`rslt' to the coercions in the database.

The actual value of `opr' is often irrelevant in these computations, because the designer does not ask which operator was selected from the given indication. The Expression module provides the known key NoOprName for use in these situations.

Consider a type denotation for one-dimensional arrays. Assume that a subscript must be of the language-defined integer type, and that each new array type overloads the standard array indexing indication indexInd with the indexing operator for that array (see Operators with explicit operands). The operator name is uninteresting:

SYMBOL ArraySpec INHERITS TypeDenotation, OperatorDefs END;

RULE: ArraySpec ::= Type '[' ']' COMPUTE
  ArraySpec.GotOper+=
    DyadicOperator(
      indexInd,
      NoOprName,
      ArraySpec.Type,
      intType,Type.Type);
END;

Another approach defines the Accessor property of the array type to be an indication with a singleton operator set (see Operators with explicit operands):

ATTR Indic: DefTableKey;

SYMBOL IndexTypes INHERITS OpndTypeListRoot END;

RULE: ArraySpec ::= Type '[' IndexTypes ']' COMPUTE
  .Indic=NewKey();
  ArraySpec.GotType+=ResetAccessor(ArraySpec.Type,.Indic);
  ArraySpec.GotOper+=
    ListOperator(
      .Indic,
      NoOprName,
      IndexTypes.OpndTypeList,
      Type[1].Type);
END;

Functions and methods are simply operators with operand lists. These operators overload the indication that is the function or method name. In many cases, of course, a singleton operator set will be associated with a function or method name. The operator name may or may not be interesting, depending on how the designer chooses to interpret the results of type analysis.

Java method definitions overload the method identifier:

SYMBOL MethodHeader INHERITS OperatorDefs     END;
SYMBOL Formals      INHERITS OpndTypeListRoot END;

RULE: MethodHeader ::= Type MethIdDef '(' Formals ')' COMPUTE
  MethodHeader.GotOper+=
    ListOperator(
      MethIdDef.Key,
      NoOprName,
      Formals.OpndTypeList,
      Type.Type);
END;
The corresponding method call uses the method identifier as the operator symbol in a list context. Its indication is its Key attribute, as in the declaration:

SYMBOL MethIdUse INHERITS OperatorSymbol COMPUTE
  SYNT.Indic=THIS.Key;
END;
SYMBOL Arguments INHERITS OpndExprListRoot END; 

RULE: Expr ::= Expr '.' MethIdUse '(' Arguments ')' COMPUTE
  ListContext(Expr[1],MethIdUse,Arguments);
END;

Every value in a C enumeration is coercible to an integer:

SYMBOL enum_specifier INHERITS TypeDenotation, OperatorSymbol END;

RULE: enum_specifier ::= 'enum' '{' enumerator_list '}'
  enum_specifier.GotOper+=
    Coercible(NoOprName,enum_specifier.Type,intType);
END;

Reducing specification size

A user type definition often requires definition of a number of operators, based on the relationship between the new type and its components. Although all of those operations can be defined using the techniques of the previous section, it may be simpler to define a "template" for the particular type constructor and then instantiate that template at each corresponding type denotation.

The necessary information can be captured in an OIL class (see Class definition of Oil Reference Manual). For example, a set type in Pascal implies operators for union, intersection, membership, and comparison:

CLASS setType(baseType) BEGIN
  OPER
    setop(setType,setType): setType;
    setmember(baseType,setType): boolType;
    setrel(setType,setType): boolType;
  COERCION
    (emptyType): setType;
END;

INDICATION
  plus: setop;
  minus: setop;
  star: setop;
  in: setmember;
  equal: setrel;
  lsgt: setrel;
  lessequal: setrel;
  greaterequal: setrel;
Within the class definition, the class name (setType in this example) represents the type being defined. The parameters of the class (e.g. baseType) represent the related types. Thus a set requires a set member operation that takes a value of the base type and a value of the set type, returning a Boolean. Notice that the designer chose to use the same operator for union, intersection, and difference because all of these operators have the same signature and distinguishing them is irrelevant for type analysis.

Let `cl' be an OIL class name, and `typ', `arg1', `arg2', `arg3' be definition table keys representing types. Each of the following rule computations instantiates an OIL class with a specific number of parameters:

InstClass0(c,typ)
InstClass1(c,typ,arg1)
InstClass2(c,typ,arg1,arg2)
InstClass3(c,typ,arg1,arg2,arg3)
Create the operators defined by OIL class `cl' for type `typ'. Types `arg1', `arg2', and `arg3' are the parameters of the instantiation:

A class instantiation creates operators, so it should have the GotOper attribute as a postcondition:

SYMBOL TypeDenoter INHERITS TypeDenotation, OperatorDefs END;

RULE: TypeDenoter ::= 'set' 'of' type COMPUTE
  TypeDenoter.GotOper+=InstClass1(setType,TypeDenoter.Type,type.Type);
END;


Previous Chapter Next Chapter Table of Contents