Eli   Documents
Eli: Translator Construction Made Easy

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 Scope Graphs
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

Array Types

We now add array types to our language. We specify that two array types are structural equivalent if their element types are equivalent, and if the types have the same number of elements. Hence, type equivalence is not only determined by the component types.

Here is an example program that uses arrays, records, and type definitions in combination:

ArrayExamp[63]== 

begin
  var   int k;
  var   int[5] pi, int[5] pj;
  var   record int i, bool b, real[3] r end [2] rv;
  type  bool[4] bt;
  var   bt vbt, bt wbt;
  var   real[6][7] m;
  pi[1] = k;
  vbt = wbt;
  rv[2].b = true;
  rv[1].r[k] = 3.2;
  m[1][k] = 1.0;
end

This macro is attached to a product file.

We extend the grammar by notations for array type denoters and by indexed variables:

Abstract array syntax[64]== 

RULE: TypeDenoter ::= ArrayType END;
RULE: ArrayType   ::= TypeDenoter '[' ArraySize ']' END;
RULE: ArraySize   ::= IntNumber END;

RULE: Variable    ::= Variable '[' Expression ']' END;

This macro is invoked in definition 74.

In this language an array type is described by two properties: the element type and the number of elements: Array type properties[65]== 

ElemType:       DefTableKey;
ElemNo:         int;

This macro is invoked in definition 73.

In the context of a type denotation for an ArrayType the two properties of the type are set together with the TypeName to indicate the array type in the output. The attribute GotTypeProp specifies that these properties are set.

Array type denoter[66]== 

SYMBOL ArrayType INHERITS TypeDenotation END;

RULE: ArrayType ::= TypeDenoter '[' ArraySize ']' COMPUTE
  .GotTypeProp =
     ORDER
       (ResetElemType (ArrayType.Type, TypeDenoter.Type),
        ResetElemNo   (ArrayType.Type, ArraySize.Size),
        ResetTypeName (ArrayType.Type, "array..."),
        ResetTypeLine (ArrayType.Type, LINE));
END;

TERM IntNumber: int;

SYMBOL ArraySize: Size: int;

RULE: ArraySize ::= IntNumber COMPUTE
  ArraySize.Size = IntNumber;
END;

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

This macro is invoked in definition 74.

Finally it is stated that array elements of type void are not allowed. We can not simply compare voidType and the type key, because TypeDenoter.Type not necessarily contains the final element type; it may be related to it. The final type key is obtained by the function FinalType in a state that is characterized by INCLUDING Program.TypeIsSet. Array check element type [67]== 

RULE: ArrayType ::= TypeDenoter '[' ArraySize ']' COMPUTE
  IF (EQ (FinalType (TypeDenoter.Type), voidType),
      message (ERROR, "Wrong element type", 0, COORDREF))
  <- INCLUDING Program.TypeIsSet;
END;

This macro is invoked in definition 74.

Two array types are equivalent if and only if their element types are equivalent and if they have the same number of elements.

In order to state the equivalence with respect to array sizes, we establish a bijective mapping between any array size that occurs in the program and a definition table key. That number mapping is computed by turning an array size into an identifier and then binding that identifier in a scope that serves just this purpose.

Size mapping[68]== 

$/Tech/MakeName.gnrc:inst
$/Name/CScope.gnrc+instance=SizeMap :inst

This macro is invoked in definition 72.

Array size mapping[69]== 

SYMBOL ArraySize INHERITS SizeMapIdDefScope END;

RULE: ArraySize ::= IntNumber COMPUTE
  ArraySize.Sym = IdnNumb (0, IntNumber);
END;

This macro is invoked in definition 74.

The ArraySize.Key serves as the initial set of potential equivalent array types; it is used as the second argument of the RULE computation AddTypeToBlock. The type of the element may contribute to type equivalence of array types. Hence, the third argument of AddTypeToBlock is a singleton list, which is also set as the ComponentTypes property of the array type:

Array type equivalence[70]== 

RULE: ArrayType ::= TypeDenoter '[' ArraySize ']' COMPUTE
  ArrayType.GotType +=
    AddTypeToBlock 
     (ArrayType.Type, ArraySize.Key, 
      VResetComponentTypes 
        (ArrayType.Type, SingleDefTableKeyList (TypeDenoter.Type)))
    <- .GotTypeProp;
END;

This macro is invoked in definition 74.

Type analysis in the context of an indexed variable is specified as a join of three expression subtrees: Variable[1], the left-hand side of the rule is a leaf of an expression tree. PrimaryContext is used to state that its type is the ElemType property of Variable[2].

Variable[2], which yields the array, is considered to be the root of an expression subtree. No requirements are specified. It has to be checked explicitly that its type is an array type.

The subcript expression is a separate expression subtree. It has to be of type int, as specified by its Required attribute.

Indexing[71]== 

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

  IF (EQ (GetElemType (Variable[2].Type, NoKey), NoKey),
    message (ERROR, "Not an array", 0, COORDREF));

  Expression.Required = intType;
END;

This macro is invoked in definition 74.

Array.specs[72]== 

Size mapping[68]

This macro is attached to a product file.

Array.pdl[73]== 

Array type properties[65]

This macro is attached to a product file.

Array.lido[74]== 

 Abstract array syntax[64]
Array type denoter[66]
Array check element type [67]
Array size mapping[69]
Array type equivalence[70]
Indexing[71]

This macro is attached to a product file.

Previous Chapter Next Chapter Table of Contents