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, ....

Tutorial on Type Analysis

Previous Chapter Next Chapter Table of Contents


Pointer Types

In this section we introduce pointer types to our language. A type denoted t ! shall be the type of objects that points to objects of type t.

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.

The following concrete productions are added:

Pointer.con[48]==


TypeDenoter:    PointerType.
PointerType:    TypeDenoter '!'.
Variable:       Variable '!'.
Variable:       Variable '&'.

This macro is attached to a product file.

Here is an example program that uses these pointer constructs in different contexts: PointerExamp[49]==

begin
  var   int k;
  var   int! pi, int! pj;
  var   record int i, bool b, real! r end! rv;
  type  record int x, t! next end t;
  var   t l;
  pi = k&;
  pi! = 1;
  pi = pj;
  pi! = pj!;
  rv!.b = true;
  rv!.r! = 3.2;
  l.next!.x = 1;
end

This macro is attached to a product file.

The property PointsTo is introduced to describe pointer types.

Pointer.pdl[50]==


PointsTo: DefTableKey [KReset];

This macro is attached to a product file.

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 occurrence of a pointer type denoter introduces a new type.)

As discussed in the section where we introduced record types, we specify a TypeDenoter such that a new type representation is created. The EqualTypes function is augmented below by rules that implement the desired equivalence of two types that stem from different occurrences of TypeDenoters.

PointerType.lido[51]==


SYMBOL PointerType INHERITS TypeDenotation END;

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

RULE: PointerType ::= TypeDenoter '!' COMPUTE
  PointerType.GotType =
    ResetTypeName 
      (KResetPointsTo (PointerType.Type, TypeDenoter.Type),
       "pointer...");

  IF (RecursivePtrType (PointerType.Type, PointerType.Type),
  message (ERROR, "recursive pointer type", 0, COORDREF))
  <- INCLUDING Program.GotType;
END;

This macro is attached to a product file.

The last computation checks that the pointer type denoted here does not refer to itself via pointer relations only. Note: Although a message is given in such erroneous cases, functions that operate on types must be coded such that they can deal with such types.

We now state how pointer types are checked for equivalence. Our language requires that two pointer type notations shall be considered to be equal types if the types they point to are equal. Such cases where different type keys may represent equal types are not yet captured by the initial frame of the EqualTypes function. Instead, it has an insertion point EqualTypes.h where code fragments can be inserted, each fragment checking an equivalence rule for a certain kind of types.

Here, the following .phi fragment is applicable if the type t1 is a pointer type. Equivalence holds only if t2 is a pointer type, too, and the types they point to are equal. Furthermore, we have to make sure that the recursion terminates even in erroneous cases where one of the types is defined to point to itself.

Pointer.EqualTypes.phi[52]==


{ /* pointer types: */
  DefTableKey tr1, tr2;
  tr1 = TransDefer (GetPointsTo (t1, NoKey));
  if (tr1 != NoKey) 
  { /* tr1 is a pointer type: */
        tr2 = TransDefer (GetPointsTo (t2, NoKey));
        if (tr2 == NoKey)
                return 0; /* tr2 is not a pointer type */
        if (RecursivePtrType (tr1, tr1) || 
            RecursivePtrType (tr2, tr2))
                return 0; /* recursive pointer type */
        return EqualTypes (tr1, tr2);
  }
}/* end pointer types */

This macro is attached to a product file.

The .phi technique is also used to insert the definition of the function RecursivePtrType and its interface declaration:

Pointer.TypeFct.phi[53]==


#ifdef PROTO_OK
int RecursivePtrType (DefTableKey orig, DefTableKey chk)
#else
int RecursivePtrType (orig, chk) DefTableKey orig, chk;
#endif
/* 1 is returned if the type chk directly or indirectly
   points to orig; 0 is returned otherwise.
*/
{ chk = TransDefer (GetPointsTo (chk, NoKey));
  if (chk == NoKey) return 0;
  if (chk == orig)  return 1;
  return RecursivePtrType (orig, chk);
}

This macro is attached to a product file.

Pointer.TypeFctHdr.phi[54]==


extern int RecursivePtrType ELI_ARG((DefTableKey orig, DefTableKey chk));

This macro is attached to a product file.

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

PointerVar.lido[55]==


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;

This macro is attached to a product file.

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.

AddressVar.lido[56]==


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

This macro is attached to a product file.


Previous Chapter Next Chapter Table of Contents