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

Next Chapter Table of Contents

Kernel Language

We start with a very simple kernel language where a Program is a Block consisting of Declarations for variables, assignment Statements, and trivial Expressions. Other forms of Declarations and Expressions are added to the grammar when the type analysis task is further refined.

Here is a simple example program:

SimpleExamp[1]== 

begin
  var   int i, int j,
        bool b, bool c,
        int r, int s;
  i = 1;
  b = true;
  r = 3;
  j = i;
  c = b;
  s = r;
end

This macro is attached to a product file.

Structure and notation of the kernel language is specified here by its abstract syntax.

Abstract Kernel syntax[2]== 

RULE: Program      ::=    Block END;
RULE: Block        ::=    'begin' Declarations Statements 'end' END;
RULE: Declarations LISTOF Declaration END;
RULE: Statements   LISTOF Statement END;

RULE: Declaration  ::=    'var' ObjDecls ';' END;
RULE: ObjDecls     LISTOF ObjDecl  END;
RULE: ObjDecl      ::=    TypeDenoter DefIdent END;
RULE: TypeDenoter  ::=    'int' END;
RULE: TypeDenoter  ::=    'bool' END;
RULE: TypeDenoter  ::=    'void' END;

RULE: Statement    ::=    Variable '=' Expression ';' END;
RULE: Statement    ::=    Expression ';' END;

RULE: Expression   ::=    Variable END;
RULE: Expression   ::=    IntNumber END;
RULE: Expression   ::=    'true' END;
RULE: Expression   ::=    'false' END;

RULE: Variable     ::=    UseIdent END;

RULE: DefIdent     ::=    Ident END;
RULE: UseIdent     ::=    Ident END;

This macro is invoked in definition 16.

Concrete syntax rules corresponding to the LISTOF constructs above, specifications of the notations of identifiers, literals, and comments are given in the appendix.

Basic Scope Rules

The basic task of name analysis is consistent renaming. For each identifier occurrence a Key attribute is computed such that it identifies a program entity uniquely. Keys are used to associate properties to program entities and to retrieve those properties in different contexts. The symbols DefIdent, UseIdent distinguish defining and used identifier occurrences.

The scope rules of a language determine how identifier occurrences are bound to program entities. We specify Algol-like scope rules for our language. The basic Algol-like scope rule reads:

A definition of an identifier a is valid in the whole smallest range that encloses that definition, except inner ranges that contain another definition of a.

Hence, a definition in an outer range is hidden by a definition of the same identifier in an inner range for the whole inner range. Identifiers may be applied before they are defined.

We instantiate a library module that provides computations according to this scope rule:

Basic scope module[3]== 

$/Name/AlgScope.gnrc:inst

This macro is invoked in definition 14.

The use of that module requires that every identifier occurrence has the attribute Sym representing the identifier encoding. Hence we specify a computational role IdentOcc that provides that attribute, and will be inherited by any identifier occurrence.

The computational roles RangeScope, IdDefScope, and IdUseEnv are associated to the corresponding symbols of our grammar:

Kernel scope rules[4]== 

TERM Ident: int;
ATTR Sym: int;
CLASS SYMBOL IdentOcc COMPUTE SYNT.Sym = TERM; END;

SYMBOL Block    INHERITS RangeScope END;
SYMBOL DefIdent INHERITS IdDefScope, IdentOcc END;
SYMBOL UseIdent INHERITS IdUseEnv, IdentOcc END;

This macro is invoked in definition 16.

Erroneous programs may violate the scope rules in two different situations:

  • A particular applied identifier occurrence has no valid defining identifier occurrence.

  • There are more than one defining identifier occurrences for the same identifier in a range.

Such situations shall be indicated by error messages. Furthermore, we want every defining occurrence of a multiply defined identifier be marked by a message.

For that purpose we use the following two library modules:

Message support[5]== 

$/Tech/Strings.specs
$/Prop/OccCnt.gnrc:inst

This macro is invoked in definition 14.

The Strings module provides a function that concatenates a string and an identifier, to be used for error messages related to identifiers.

The OccCnt module provides computations that count how often an entity identified by a Key attribute occurs in certain contexts, in our case in a defining context.

The check for existence of a definition is directly obtained from the module role ChkIdUse. For the second check we specify a computational role ChkUnique in order to reuse it for several grammar symbols. If an entity occurs more than once in the ChkUnique context it is multiply defined.

Scope checks[6]== 

SYMBOL UseIdent INHERITS ChkIdUse END;
SYMBOL DefIdent INHERITS ChkUnique END;

SYMBOL ChkUnique INHERITS Count, TotalCnt COMPUTE
  IF (GT (THIS.TotalCnt, 1),
  message (ERROR, 
           CatStrInd ("identifier is multiply defined: ", 
                      THIS.Sym),
           0, COORDREF));
END;

This macro is invoked in definition 16.

Types in the Kernel Language

We use the modules Typing to support type analysis. As we are going to specify structural equivalence for some kinds of type, we also instantiate the module StructEquiv. Type analysis module[7]== 

$/Type/Typing.gnrc:inst
$/Type/StructEquiv.fw

This macro is invoked in definition 14.

So, we have to adopt the modules' strategy for representing types:

Types are represented by DefTableKeys. Such a key is created for each program construct which denotes a particular type. The unknown type is represented by NoKey.

The kernel language has only language defined types: int, bool, and void. Each of them is represented by a known key. Here we introduce only the key for the type void, as the other types occur in operator specification, and are introduced there: Language defined type keys[8]== 

voidType -> IsType = {1};

This macro is invoked in definition 15.

All type keys have a property IsType, which distinguishes them from keys representing entities other than types. Usually the property IsType is not set or accessed by user specifications. Module roles ensure that they are properly used.

The following computations set the Type attributes of the constructs that denote languge defined types: Language defined types[9]== 

RULE: TypeDenoter ::= 'int'  COMPUTE TypeDenoter.Type = intType;  END;
RULE: TypeDenoter ::= 'bool' COMPUTE TypeDenoter.Type = boolType; END;
RULE: TypeDenoter ::= 'void' COMPUTE TypeDenoter.Type = voidType; END;

This macro is invoked in definition 16.

Further forms of TypeDenoters for user defined types are specified in subsequent sections.

We now consider a variable declaration as an example for a language construct that defines a typed entity. In our language a variable declaration may define several variables. An ObjDecl states the type and the name for each of them.

The pair of module roles TypedDefinition and TypedDefId supports the pattern of declaring typed entities: ObjDecl has the role TypedDefinition, i.e. a construct that specifies the types of all TypedDefIds in its subtree. The attribute ObjDecl.Type has to be set appropriately:

Declarations[10]== 

SYMBOL ObjDecl INHERITS TypedDefinition END;
SYMBOL DefIdent INHERITS TypedDefId END;

ATTR Type: DefTableKey;

RULE: ObjDecl ::= TypeDenoter DefIdent COMPUTE
  ObjDecl.Type = TypeDenoter.Type;
END;

This macro is invoked in definition 16.

The module roles TypedUseId classifies a used name of a typed entity, and causes the attribute TypedUseId.Type to be set to the type defined for that entity. The corresponding check role issues messages if that classification is violated:

Typed identifiers[11]== 

SYMBOL UseIdent INHERITS TypedUseId, ChkTypedUseId END;

This macro is invoked in definition 16.

In order to report some results of the type analysis we associate two properties to every type key: a string value TypeName and the number of the line where the type is introduced. (The latter will become more significant when user defined types are defined for the language.)

Output properties[12]== 

TypeName: CharPtr; "Strings.h"
TypeLine: int;

intType ->  TypeName = {"int"};
boolType -> TypeName = {"bool"};
voidType -> TypeName = {"void"};

intType ->  TypeLine = {0};
boolType -> TypeLine = {0};
voidType -> TypeLine = {0};

This macro is invoked in definition 15.

For every used identifier the name and the defining line of its type is printed: Kernel output[13]== 

SYMBOL UseIdent INHERITS PrtType END;

SYMBOL PrtType COMPUTE
  printf ("line %d Type %s defined in line %d\n", LINE,
          GetTypeName (THIS.Type, "no type name"),
          GetTypeLine (THIS.Type, 0))
  <- INCLUDING  Program.TypeIsSet;
END;

This macro is invoked in definition 16.

Kernel.specs[14]== 

Basic scope module[3]
Message support[5]
Type analysis module[7]

This macro is attached to a product file.

Kernel.pdl[15]== 

Language defined type keys[8]
Output properties[12]

This macro is attached to a product file.

Kernel.lido[16]== 

Abstract Kernel syntax[2]
Kernel scope rules[4]
Scope checks[6]
Language defined types[9]
Declarations[10]
Typed identifiers[11]
Kernel output[13]

This macro is attached to a product file.

Kernel.gla[17]== 

Token notation[137]

This macro is attached to a product file.

Kernel.con[18]== 

Concrete Kernel syntax[135]

This macro is attached to a product file.

Oprand.sym[19]== 

Expression mapping[136]

This macro is attached to a product file.

Next Chapter Table of Contents