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

Tutorial on Type Analysis

Previous Chapter Next Chapter Table of Contents


Pointer Types

In this chapter we introduce pointer types to our language. The notation t ! denotes a type for values that point to values of type t.

A new Variable notation is introduced: In v ! the dereferencing operator ! is applied to the variable v, which must have a pointer type. The result of the operation is the value that v points to.

A pointer value of type t ! is created by execution of a generator new t, where t is a type denotation.

Here is an example program that uses these pointer constructs in different contexts:

PointerExamp[114]==

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 = new int;
  pi! = 1;
  pi = pj;
  pi! = pj!;
  rv!.b = true;
  rv!.r! = 3.2;
  l.next!.x = 1;
  l.next = nil;
end
This macro is attached to a product file.

The following productions are added to the grammar:

Abstract pointer syntax[115]==

RULE: TypeDenoter ::= PointerType END;
RULE: PointerType ::= TypeDenoter '!' END;

RULE: Variable    ::= Variable '!' END;
RULE: Expression  ::= 'nil' END;
RULE: Expression  ::= Generator END;
RULE: Generator   ::= 'new' TypeDenoter END;
This macro is invoked in definition 125.

There are two constructs which introduce a pointer type. The first one is a denoter for a pointer type. Two monadic operators are created for each pointer type: One is applied to a pointer and yields the value pointed to, the other yields the reference of an entity instead of its value. The dereferencing operators of all pointer types are overloaded on the indication DerefOpr, correspondingly all operators that prevent dereferencing are overloaded on the indication RefOpr. We also introduce an artificial type for the nil symbol: Pointer operators[116]==

DerefOpr;
RefOpr;
NilOpr;
nilType -> IsType = {1};
This macro is invoked in definition 124.

Creating these pairs of operators for a pointer type establishes the condition PointerType.GotOper, which is a precondition for operator identification. Furthermore, we state that the type of the nil symbol is coercible to each pointer type.

Pointer type denotation[117]==

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

SYMBOL PointerType INHERITS TypeDenotation, OperatorDefs END;

RULE: PointerType ::= TypeDenoter '!' COMPUTE
  PointerType.GotOper +=
    ORDER 
      (Coercible (NilOpr, nilType, PointerType.Type),
       MonadicOperator
         (DerefOpr, NewKey(), PointerType.Type, TypeDenoter.Type),
       MonadicOperator
         (RefOpr, NewKey(), TypeDenoter.Type, PointerType.Type));
END;

RULE: Expression  ::= 'nil' COMPUTE
  PrimaryContext (Expression, nilType);
END;
This macro is invoked in definition 125.

A generator also introduces a pointer type. The TypeDenoter states which is the type pointed to. Generators may occur as operand in expressions:

Generator[118]==

SYMBOL Generator INHERITS TypeDenotation, OperatorDefs END;

RULE: Generator ::= 'new' TypeDenoter COMPUTE
  Generator.GotOper +=
    ORDER (
    MonadicOperator
       (DerefOpr, NewKey(), Generator.Type, TypeDenoter.Type),
    MonadicOperator
       (RefOpr, NewKey(), TypeDenoter.Type, Generator.Type));
END;

RULE: Expression ::= Generator COMPUTE
  PrimaryContext (Expression, Generator.Type);
END;
This macro is invoked in definition 125.

Types t !, s ! and the types created by new t and new s are all considered to be equivalent in our language, if the types s and t are equivalent, with respect to renaming and to equivalence rules for the particular type categories.

We use the facilities of the StructEquiv module to specify such structural type equivalence for pointer types. In particular two conditions are specified for types a and b to be equivalent: Both have to be of the kind PointerClass, and their sequences of component types have to be elementwise equivalent, in this case the single type pointed to: EqualPtrTypes.lido[119]==

RULE: PointerType ::= TypeDenoter '!' COMPUTE
  PointerType.GotType =
    AddTypeToBlock
      (PointerType.Type, PointerClass,
       VResetComponentTypes 
         (PointerType.Type, SingleDefTableKeyList (TypeDenoter.Type)))
  <- .moreTypeProperies;
END;

RULE: Generator ::= 'new' TypeDenoter COMPUTE
  Generator.GotType =
    AddTypeToBlock
      (Generator.Type, PointerClass,
       VResetComponentTypes 
         (Generator.Type, SingleDefTableKeyList (TypeDenoter.Type)))
  <- .moreTypeProperies;
END;
This macro is attached to a product file.

The PointerClass is a unique key used to distinguish this kind of types from other kinds, e.g. array types:

Pointer type equality[120]==

PointerClass;
This macro is invoked in definition 124.

Pointer types are to be treated especially when types are checked for equivalence: On the one hand, a type is allowed to be recursively defined if the recursion goes through a pointer component, for example in type record int i, rec! p end rec;. That is why we associate the property AllowRecurType to the pointer type, together with the properties defining the output for types.

Pointer types allow recursion[121]==

RULE: PointerType ::= TypeDenoter '!' COMPUTE
  .moreTypeProperies =
    ORDER
      (ResetTypeName (PointerType.Type, "pointer..."),
       ResetTypeLine (PointerType.Type, LINE),
       ResetAllowRecurType (PointerType.Type, 1));
END;

RULE: Generator ::= 'new' TypeDenoter COMPUTE
  .moreTypeProperies =
    ORDER
      (ResetTypeName (Generator.Type, "pointer..."),
       ResetTypeLine (Generator.Type, LINE),
       ResetAllowRecurType (Generator.Type, 1));
END;
This macro is invoked in definition 125.

On the other hand, we have to check that pointer types are not defined directly recursively, or indirectly recursively s.t. only pointer types are involved:

  type p1! p1;
  type p2! p3;
  type p3! p2;
In the example above all three type are pairwise equivalent.

Recursion check for pointer types[122]==

RULE: PointerType ::= TypeDenoter '!' COMPUTE
  IF (EQ (FinalType (PointerType.Type), FinalType (TypeDenoter.Type)),
    message (ERROR, "Recursively defined pointer type", 
             0, COORDREF))
    <- INCLUDING Program.TypeIsSet;
END;
This macro is invoked in definition 125.

For the dereferencing operation applied to a Variable we specify that in the following context a suitable operator that overloads the DerefOpr indication is applicable:

Pointer variable[123]==

RULE: Variable ::= Variable '!' COMPUTE
  MonadicContext (Variable[1], , Variable[2]);
  Indication (DerefOpr);

  IF(BadOperator,
    message(ERROR,"Dereferencing not allowed", 0, COORDREF));
END;
This macro is invoked in definition 125.

Pointer.pdl[124]==

Pointer type equality[120]
Pointer operators[116]
This macro is attached to a product file.

Pointer.lido[125]==

Abstract pointer syntax[115]
Pointer type denotation[117]
Generator[118]
Pointer types allow recursion[121]
Recursion check for pointer types[122]
Pointer variable[123]
This macro is attached to a product file.

Pointer.con[126]==

Concrete pointer syntax[143]
This macro is attached to a product file.


Previous Chapter Next Chapter Table of Contents