General Information

	Eli: Translator Construction Made Easy
	Global Index
	Frequently Asked Questions
	Typical Eli Usage Errors

Tutorials

	Quick Reference Card
	Guide For new Eli Users
	Release Notes of Eli
	Tutorial on Name Analysis
	Tutorial on Scope Graphs
	Tutorial on Type Analysis
	Typical Eli Usage Errors

Reference Manuals

	User Interface
	Eli products and parameters
	LIDO Reference Manual
	Typical Eli Usage Errors

Libraries

	Eli library routines
	Specification Module Library

Translation Tasks

	Lexical analysis specification
	Syntactic Analysis Manual
	Computation in Trees

Tools

	LIGA Control Language
	Debugging Information for LIDO
	Graphical ORder TOol

FunnelWeb User's Manual

	Pattern-based Text Generator
	Property Definition Language
	Operator Identification Language
	Tree Grammar Specification Language
	Command Line Processing
	COLA Options Reference Manual

Generating Unparsing Code

Monitoring a Processor's Execution

Administration

System Administration Guide

Tutorial on Type Analysis

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;

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.