General Information

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

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

Reference Manuals

 o User Interface
 o Eli products and parameters
 o LIDO Reference Manual

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

 Questions, Comments, ....

Type analysis tasks

Previous Chapter Next Chapter Table of Contents


Properties of Types

In general it is necessary to associate properties to types that carry characterizing information which is either used for purposes of type analysis, e.g. to check compatibility of two types or to determine the element type of an array, or for translation purposes, e.g. the size of data objects in the target code. It is an important design issue in type analysis to identify the characterizing properties of types.

In this section four common type classes are used to demonstrate principles of type properties, and their use in type analysis. Solutions for other types may be derived from these by analogy. Here only properties are described that are used in type analysis itself, disregarding properties for the transformation task.

For our solution we use the module for basic type analysis (see Basic Type Analysis) and some modules of the property library (see Property Library of Association of properties to definition).

ArrayType
Array Types
PointerType
Pointer Types
FunctionType
Function Types
ScopeTypes
Types Having Scope Properties

Array types and pointer types are used to demonstrate how new types are introduced by declarations in a program, as opposed to predefined types, and that type properties refer to other types.

Function types are used to demonstrate type properties that are lists of types which are specified using the LidoList module.

Record types are used to demonstrate type properties that are scopes which are specified using modules of the Name library.

Array Types

In this section we use array types to demonstrate how new types are introduced by declarations in a program, as opposed to predefined types. Furthermore it is shown how type properties refer to other types. We assume that an array is described by the type and the number of its elements, like in C. The denotation of an array type shall introduce a new type that is diffierent from any other type, as in Pascal. For ease of our example we do not consider type rules that allow two different array types to be compatible.

The language of our running example is extended by TypeDenoters for arrays and by indexed Variables as specified by the concrete productions:

   TypeDenoter:    ArrayType.
   ArrayType:      TypeDenoter '[' IntNumber ']'.
   Variable:       Variable '[' Expression ']'.
The form chosen for TypeDenoters keeps the grammar simple and orthogonal, but leads to a bit unconventional notation for declaration of array variables and array type names:
   type int[10]   Vector;
   var  Vector    v;
   var  float[5]  a;

   v[6] = 1; a[3] = 2.5;

An array type is described here by two properties introduced by the .pdl specification

   ElemType:       DefTableKey;
   ElemNo:         int;

The rule that any type denoter introduces a new array type is reflected by using the module role TypeDenotation unchanged (see Basic Type Analysis). It provides a computation for ArrayType.Type being a new, unique type key:

   SYMBOL ArrayType INHERITS TypeDenotation END;

   RULE: ArrayType ::= TypeDenoter '[' IntNumber ']' COMPUTE
     ArrayType.GotType =
       ORDER
         (ResetElemType (ArrayType.Type, TypeDenoter.Type),
          ResetElemNo (ArrayType.Type, IntNumber));
   END;

   RULE: TypeDenoter ::= ArrayType COMPUTE
     TypeDenoter.Type = ArrayType.Type;
   END;
Association of the type properties establishes the postcondition ArrayType.GotType. The module roles ensure that the properties are set before accessed.

In the context of an indexed Variable the type is expected to be an array type, as checked in the second computation. The first computation accesses the element type. The call of TransDefer ensures that Type attributes in expression contexts are type keys rather than deferred keys. This is a convention that is introduced by the module roles, and is carried on here.

   RULE: Variable ::= Variable '[' Expression ']' COMPUTE
     Variable[1].Type =
        TransDefer (GetElemType (Variable[2].Type, NoKey));

     IF (EQ (Variable[1].Type, NoKey),
     message (ERROR, "index applied to non array", 0, COORDREF));

     Expression.ReqType = intType;
   END;

Pointer Types

In this section we introduce pointer types to the language of our running example. A type denoted t ! shall be the type of objects that point to objects of type t. Types t ! and s ! shall be equivalent if s and t are equivalent, due to type definitions that simply rename a type. (This rule is similar to that of C, but different from that of Pascal where any ocurrence of a pointer type denoter introduces a new type.)

The concrete grammar of our running example is extended by the productions:

   TypeDenoter:    PointerType.
   PointerType:    TypeDenoter '!'.
   Variable:       Variable '!'.
   Variable:       Variable '&'.
Two new Variable notations are introduced: v ! denotes the object which the value of the pointer variable v points to. v & yields the address of the variable v, it has the type pointer to t if v is a variable of type t.

Due to our equivalence rules all variables in the following example have the equivalent types:

   type int ! IntPtr;
   type IntPtr IP;
   var  IntPtr i, IP j, int ! k;
   ...
   i! = j!;

The property PointsTo is introduced to describe pointer types:

  PointsTo: DefTableKey [KReset];
(The operation KReset is described below.)

The following computation introduces the notation of pointer types using the module role TypeDenotation. The computation establishes the postcondition as required for TypeDenotations:

   SYMBOL PointerType INHERITS TypeDenotation END;

   RULE: PointerType ::= TypeDenoter '!' COMPUTE
     PointerType.GotType =
       ResetPointsTo (PointerType.Type, TypeDenoter.Type);
   END;

   RULE: TypeDenoter ::= PointerType COMPUTE
      TypeDenoter.Type = PointerType.Type;
   END;

If we do not take further means any two occurrences of a pointer type notation would denote different types. The equivalence rule described above has to be implemented in functions which compare types. Caution has to be taken to avoid non-termination of such functions if applied to recursively defined types. More details can be found in $/Type/Examples/Type.fw.

For the contents operation applied to a Variable we access the PointsTo relation that holds if the Variable really has a pointer type:

   RULE: Variable ::= Variable '!' COMPUTE
     Variable[1].Type =
       TransDefer (GetPointsTo (Variable[2].Type, NoKey));

     IF (EQ (Variable[1].Type, NoKey),
     message (ERROR, "is not a pointer variable", 0, COORDREF));
   END;
The call of TransDefer ensures that Type attributes in expression contexts are type keys rather than deferred keys. A convention that is introduced by the module roles, and carried on here.

The address operator implicitly creates a pointer type that PointsTo the type of the variable. Both properties PointsTo and IsType are set for that new type key.

   RULE: Variable ::= Variable '&' COMPUTE
     Variable[1].Type =
        KResetPointsTo
          (KResetIsType (NewKey (), 1),
           Variable[2].Type);
   END;

The KReset operations set the property and return the first argument. That mechanism is obtained from the module See Some Useful PDL Specifications of Association of properties to definitions, which is automatically instantiated when using the basic type module.

Function Types

Function types are an example for types that have properties which are lists of types, the types of the parameters. They are also used here to demonstrate an application of the LidoList module (see Lists in LIDO Specifications of Abstract data types to be used in specifications).

The type of a function is described by its result type and the list of the types of the parameters. Type analysis of a function call has to check the parameter types of the called function against the corresponding argument types, and has to yield the result type as the type of the call.

We extend the concrete grammar of our running example by productions for function declarations and calls:

   Declaration:    FunctionDecl.
   FunctionDecl:   'fun' DefIdent Function ';'.
   Function:       FunctionHead Block.
   FunctionHead:   '(' Parameters ')' TypeDenoter.
   Parameters:     [Parameter // ','].
   Parameter:      TypeDenoter Ident.
   Expression:     Expression '(' Arguments ')'.
   Arguments:      [Argument // ','].
   Argument:       Expression.

In the context of a function declaration the list of parameter types is composed and associated as a property of the function type. In the context of a function call that property is accessed, the list is decomposed, and its elements - the formal parameter types - are compared with the types of the arguments.

In order to describe lists of parameter types we instantiate the LidoList module for the element type DefTableKey as described in (See Lists in LIDO Specifications of Abstract data types to be used in specifications,):

   $/Adt/LidoList.gnrc+instance=DefTableKey+referto=deftbl:inst

A function type is described by two properties, the result type and and the list of parameter types as introduced by the following PDL specifications:

   ParamTypes:     DefTableKeyList; "DefTableKeyList.h"
   ResultType:     DefTableKey;
where the DefTableKeyList type and the file defining it is obtained from the module instance.

Several module roles are to be combined in the contexts of function declarations: The Function is a RangeScope where the parameters are bound. The FunctionDecl is a TypedDefinition for the function identifier. The FunctionHead is a TypeDenotation describing the signature of the function. The Parameter is a TypedDefinition.

  SYMBOL Function INHERITS RangeScope END;

  SYMBOL FunctionDecl INHERITS TypedDefinition END;
  RULE: FunctionDecl ::= 'fun' DefIdent Function ';' COMPUTE
    FunctionDecl.Type = Function.Type;
  END;

  SYMBOL FunctionHead INHERITS TypeDenotation END;
  RULE: FunctionHead ::= '(' Parameters ')' TypeDenoter COMPUTE
    FunctionHead.GotType =
      ORDER
        (ResetResultType (FunctionHead.Type, TypeDenoter.Type),
         ResetParamTypes (FunctionHead.Type,
                          Parameters.DefTableKeyList));
  END;
  SYMBOL Parameter INHERITS TypedDefinition END;
Language rules that determine when the types of two functions are equal have to be implemented in the functions for type comparison. An example can be found in $/Type/Examples/Type.fw.

The parameter type list is composed using the list construction roles of the LidoList module:

   SYMBOL Parameters INHERITS DefTableKeyListRoot END;
   SYMBOL Parameter  INHERITS DefTableKeyListElem END;
   RULE: Parameter ::= TypeDenoter DefIdent COMPUTE
     Parameter.DefTableKeyElem = TypeDenoter.Type;
   END;

In the context of a call the type of the Expression is expected to be a function type. The parameter type list is decomposed using the list decomposition roles of the LidoList module, and checked for missing arguments:

   SYMBOL Arguments INHERITS DefTableKeyDeListRoot END;
   RULE:  Expression ::= Expression '(' Arguments ')' COMPUTE
     Arguments.DefTableKeyList =
        GetParamTypes (Expression[2].Type, NULLDefTableKeyList);

     Expression[1].Type = 
        TransDefer (GetResultType (Expression[2].Type, NoKey));

     IF (EQ (Expression[1].Type, NoKey),
     message (ERROR, "call applied to non function", 0, COORDREF));

     Expression[2].ReqType = Expression[2].Type;

     IF (NE (Arguments.DefTableKeyListTail, NULLDefTableKeyList),
     message (ERROR, "arguments missing", 0, COORDREF));
   END;
The type of each formal parameter is obtained from the decomposed list and stated to be the required type of the actual argument:
   SYMBOL Argument INHERITS DefTableKeyDeListElem END;
   RULE:  Argument ::= Expression COMPUTE
     Expression.ReqType = Argument.DefTableKeyElem;

     IF (EQ (Argument.DefTableKeyElem, NoDefTableKey),
     message (ERROR, "too many arguments", 0, COORDREF));
END;

To obey the naming requirements of the LidoList module we have to define the name NoDefTableKey for missing list elements in a .head specification:

   #define NoDefTableKey NoKey

Types Having Scope Properties

In this section we demonstrate types that have a property which is a scope, i.e. a set of object definitions. Examples for such types are records as in Pascal or C, or classes as in object-oriented languages. This task of type analysis is closely related to the name analysis task: The value of such a property is the scope of a certain range, e.g. the definitions of record components, or the members of a class. Variables of such a type may be used in component or member selections, again, a name analysis task.

In See Scopes Being Properties of Objects of Name analysis according to scope rules, it is shown how scopes are used as properties of defined entities. Here we extend that concept towards typed objects using record types as an example.

A notation for record types is introduced into our language:

   type record int a; bool b; end r;
   var r rv, int i;
   rv.a = 1;
   i = rv.a;
Here, a record type r is defined, a variable vr of that type is declared, and component selections are used.

The concrete grammar is extended by productions for record type notations and for component selections:

  TypeDenoter:    RecordType.
  RecordType:     'record' ObjDecls 'end'.
  Variable:       Variable '.' SelectIdent.
  SelectIdent:    Ident.

We use an instance of the See Scope Properties Algol-like of Name analysis according to scope rules, module. The name analysis role RangeScopeProp specifies the record type to be a range. Its scope of component definitions is associated to the ScopeKey. The ScopeKey is specified to be the type key created by the role TypeDenotation. The default for the GotType attribute need not be overridden, because the AlgScopeProp module takes care for setting the scope property before using it:

  SYMBOL RecordType INHERITS TypeDenotation, RangeScopeProp 
  COMPUTE
    SYNT.ScopeKey = SYNT.Type;
  END;

  RULE: TypeDenoter ::= RecordType COMPUTE
    TypeDenoter.Type = RecordType.Type;
  END;

The selection identifier is bound in a scope that is obtained from a scope property. Hence, it has the same computational roles as specified for the QualIdent of the scope operator :: in (see Scope Properties Algol-like of Name analysis according to scope rules), i.e. IdUseScopeProp, ChkIdUse, and IdentOcc. For type analysis it has additionally the roles for an applied identifier occurrence of a typed object.

   SYMBOL SelectIdent INHERITS
        IdUseScopeProp, ChkIdUse, IdentOcc,
        TypedUseId, ChkTypedUseId
   END;

   RULE:  Variable ::= Variable '.' SelectIdent COMPUTE
     SelectIdent.Scope = GetScope (Variable[2].Type, NoEnv)
        <- INCLUDING RootScope.GotScopeProp;

     Variable[1].Type = SelectIdent.Type;

     IF (EQ (SelectIdent.Scope, NoEnv),
     message (ERROR, "selection applied to non record type",
              0, COORDREF));
   END;
Here the scope property for the selection is obtained from the type of the selected variable. The precondition ensures that the scope properties have been set.


Previous Chapter Next Chapter Table of Contents