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

Record Types

We introduce record types to our language in order to demonstrate how composed user defined types are specified. A record type is described by a sequence of field declarations which have the same semantics as ObjDecls used in variable declarations. A notation for variables is added that allows to select a component from a variable.

Here is an example program that defines and uses a record variable named rv:

RecordExamp[47]== 

begin
  var   record int i, bool b, real r end rv;
  var   int j, bool c, real s;
  j = rv.i;
  c = rv.b;
  s = rv.r;
end

This macro is attached to a product file.

The following productions describe record types and component selections:

Abstract record syntax[48]== 

RULE: TypeDenoter ::= RecordType END;
RULE: RecordType  ::='record' ObjDecls 'end' END;

RULE: Variable    ::= Variable '.' SelectIdent END;
RULE: SelectIdent ::= Ident END;

This macro is invoked in definition 62.

An abstraction of a record type is the sequence of component definitions, each consisting of a type and a name. A RecordType describes such a type abstraction. It inherits the module role TypeDenotation:

Type denoter[49]== 

SYMBOL RecordType INHERITS TypeDenotation END;

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

RULE: RecordType ::= 'record' ObjDecls 'end' COMPUTE
  .GotTypeProp =
    ORDER (
      ResetTypeName (RecordType.Type, "record..."),
      ResetTypeLine (RecordType.Type, LINE));

END;

This macro is invoked in definition 62.

The last computation above sets the properties TypeName and TypeLine of the created type for the facility of printing type information we have introduced above. The attribute GotTypeProp represents that state. It is used in another instance of this RULE context below, where further properties are associated to the type.

The construct for component selection, e.g. rv.i, demonstrate a typical situation where type ananlysis and name analysis depend on each other: The type of the variable rv has a property, which is a scope; it is used to lookup a binding for the selector i. Hence we instantiate the name analysis module ScopeProp, which supports scopes as properties. It is adapted to the needs of type analysis by the module TypeDep: Scope property module[50]== 

$/Name/ScopeProp.gnrc:inst
$/Type/TypeDep.gnrc:inst

This macro is invoked in definition 60.

The role ExportRange of the ScopeProp module specifies the RecordType to be a range that may export its bindings to be lookedup outside of that range, e.g. in component selections. Its scope of component definitions is associated to the ScopeKey. The ScopeKey is specified to be the type key created by the role TypeDenotation: Range[51]== 

SYMBOL RecordType INHERITS ExportRange COMPUTE
  SYNT.ScopeKey = SYNT.Type;
END;

This macro is invoked in definition 62.

Type Equivalence

As record types have non-trivial abstractions, the question arises under which circumstances two record types are the same. Consider the following examples: RecordEqual[52]== 

begin
  var   record int i, bool b, real r end va;
  var   record int i, bool b, real r end vc;
  var   record int j, bool k, real l end vd;
  va = vc;
  va = vd;
end

This macro is attached to a product file.

Typing rules of the language have to state which of the variables va, vc, and vd have the same type, and which of the assignments are correct. Languages usually apply one of two different typing rules:

The first rule states that every occurrence of a description of a record type (or of any other compound type) introduces a type different from all other types, even from those that are equally notated. Under this rule all three variables have different types. This rule is called name equivalence, because every type description gets a name - explicitly or implicitly, as in this example -and types are distingushed by their names.

The second rule states that two types are equal if their abstractions are equal; i.e. the sequences of components coincide elementwise in the types and names of components. In the above example va and vc have the same types. This rule is called structural equivalence.

In case of structural equivalence the type rules of the language may define precisely, which type properties belong to the abstraction that is used to determine type equivalence. For example, the rule could state that the types of the record components belong to the abstraction, and the names of the components do not belong to it. In that case all four variables of the above example would have the same type.

The type analysis library provides a module StructEquiv that extends the Typing module, such that any of these these variants of equivalence rules can be supported: Struct equiv module[53]== 

$/Type/StructEquiv.fw

This macro is invoked in definition 60.

In this language stuctural equivalence is specified, such that for record types only the sequence of types, but not the names of components are relevant for structural type equivalence.

The following computation in the RULE context of a record type denotation specifies which properties of a record type are considered for the check whether two types are equivalent. Here we state two rules:

First, a record type can only be equivalent to a type that is a record type, too. For that purpose we introduce a key RecordClass that identifies the category of record types: Type class[54]== 

RecordClass;

This macro is invoked in definition 61.

The rule computation AddTypeToBlock below associates every record type to that initial set RecordClass. The equivalence check will then partition it as far as necessary into subsets of record types which are equivalent.

Second, two record types s and t are equivalent if the types of their fields are pairwise equivalent in the given order. For that purpose a list of component types is computed ObjDecls.OpndTypeList using roles of the LidoList module and given as the third argument of AddTypeToBlock.

Beyond type equivalence, our language requires further checks on type structures. So, the list of component types is also associated as a property ComponentTypes to the type key by a function VResetComponentTypes that yields the property value as its result: Component type property[55]== 

ComponentTypes: DefTableKeyList [VReset]; "DefTableKeyList.h"

This macro is invoked in definition 61.

PropLib module[56]== 

$/Prop/PropLib.fw

This macro is invoked in definition 60.

The attribute RecordType.GotType states that all properties of the record type are associated to its key. Hence, a dependence on the attribute GotTypeProp computed above is added here. Type equality computation[57]== 

RULE: RecordType ::= 'record' ObjDecls 'end' COMPUTE
  RecordType.GotType +=
      AddTypeToBlock
         (RecordType.Type, RecordClass, 
          VResetComponentTypes (RecordType.Type, ObjDecls.OpndTypeList))
      <- .GotTypeProp;
END;

SYMBOL ObjDecls INHERITS OpndTypeListRoot END;
SYMBOL ObjDecl INHERITS OpndTypeListElem END;

SYMBOL ObjDecl COMPUTE
  SYNT.DefTableKeyElem = SYNT.Type;
END;

This macro is invoked in definition 62.

Qualified Names

A record component selection of the form Variable.SelectIdent is considered as a qualified name: The SelectIdent is an applied occurrence of an identifier that is qualified by the Variable preceeding the dot. Its type is expected to have a scope property that has a binding for that identifier.

Variable.SelectIdent is a leaf of an expression tree. Its type is determined by the type of SelectIdent, as specified using the PrimaryContext computation. Selection expression[58]== 

RULE: Variable ::= Variable '.' SelectIdent COMPUTE
  PrimaryContext (Variable[1], SelectIdent.Type);
END;

This macro is invoked in definition 62.

SelectIdent combines roles of name analysis and type analysis: It is a qualified identifier use (QualIdUse). The role requires that the attribute SelectIdent.ScopeKey is computed. A module computation accesses the (Scope property from it, stores it in SelectIdent.Scope and searches a binding for the identifier; the role ChkQualIdUse gives a message if the scope exists, but no binding is found. A user computation is required to check whether the type has a scope property.

The roles TypedUseId, ChkTypedUseId, and PrtType determine, check, and output the type of the SelectIdent.

Selection types[59]== 

SYMBOL SelectIdent INHERITS 
        QualIdUse, ChkQualIdUse, IdentOcc,
        TypedUseId, ChkTypedUseId, PrtType
END;

RULE: Variable ::= Variable '.' SelectIdent COMPUTE
  SelectIdent.ScopeKey = Variable[2].Type;

  IF (EQ (SelectIdent.Scope, NoEnv),
  message (ERROR, "selection applied to non record type", 
           0, COORDREF));
END;

This macro is invoked in definition 62.

Record.specs[60]== 

Scope property module[50]
Struct equiv module[53]
PropLib module[56]

This macro is attached to a product file.

Record.pdl[61]== 

Type class[54]
Component type property[55]

This macro is attached to a product file.

Record.lido[62]== 

Abstract record syntax[48]
Type denoter[49]
Range[51]
Type equality computation[57]
Selection expression[58]
Selection types[59]

This macro is attached to a product file.

Previous Chapter Next Chapter Table of Contents