General Information

 o Eli: Translator Construction Made Easy
 o Global Index
 o Frequently Asked Questions

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

Reference Manuals

 o User Interface
 o Eli products and parameters
 o LIDO Reference Manual

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

 Questions, Comments, ....

Tutorial on Type Analysis

Previous Chapter Next Chapter Table of Contents


Functions

We now introduce function declarations to our language. A function is characterized by its signature. Function types are an example of types that have properties which are lists of types, the types of the parameters.

We extend the concrete grammar by productions for function declarations:

Function.con[57]==


Declaration:    FunctionDecl.
FunctionDecl:   'fun' DefIdent Function ';'.
Function:       FunctionHead Block.
FunctionHead:   '(' Parameters ')' TypeDenoter.
Parameters:     [Parameter // ','].
Parameter:      TypeDenoter DefIdent.

This macro is attached to a product file.

Here is an example program that defines some functions. The grammar for function calls and return statements is given below. FunctionExamp[58]==

begin
  var   int i, int j,
        bool b, bool c,
        real r, real s;

  fun f (int x, real y) real
  begin r = x * y; return r;end;

  fun g (real z) void
  begin r = z; return; end;

  s = f (i+1, 3.4);
  g (f (j, s));
  return;
end

This macro is attached to a product file.

A function signature consists of the result type and a list of parameter types. Hence, we use an instance of the LidoList module in order to compose such type lists. (Note: If we had more than one mode of parameter passing, the abstraction of a parameter in the function signature would be a pair: parameter passing mode and parameter type.)

Function.specs[59]==


$/Adt/LidoList.gnrc+instance=DefTableKey+referto=deftbl:inst

This macro is attached to a product file.

The use of the module requires a particular name for the non-existing list element:

Function.head[60]==


#define NoDefTableKey NoKey

This macro is attached to a product file.

A function type is described by two properties, the result type and and the list of parameter types as introduced by the following PDL specifications:

Function.pdl[61]==


ParamTypes:     DefTableKeyList; "DefTableKeyList.h"
ResultType:     DefTableKey [KReset];

This macro is attached to a product file.

We first consider the name analysis aspect of a function declaration. The Function subtree is a range where the parameter definitions are valid. The function Block is nested in that range. Since the DefIdent for parameters are already completely specified for name analysis, we need only:

FunctionScope.lido[62]==


SYMBOL Function INHERITS RangeScope END;

This macro is attached to a product file.

Now we consider a function declaration as a definition of a typed object, and apply the same specification pattern as used for variable declarations. Furthermore, each Parameter is also a TypedDefinition. There is no problem in nesting definitions of a typed objects this way.

FunctionDecl.lido[63]==


SYMBOL FunctionDecl INHERITS TypedDefinition END;

RULE: FunctionDecl ::= 'fun' DefIdent Function ';' COMPUTE
  FunctionDecl.Type = Function.Type;
END;

RULE: Function ::= FunctionHead Block COMPUTE
  Function.Type = FunctionHead.Type;
END;

SYMBOL Parameter INHERITS TypedDefinition END;

RULE: Parameter ::= TypeDenoter DefIdent COMPUTE
  Parameter.Type = TypeDenoter.Type;
  DefIdent.IsVariable = 1;
END;

This macro is attached to a product file.

Now we specify how the type of a function is composed. The FunctionHead, which contains the signature, is treated as a TypeDenotation for a function type. Its ResultType property is obtained from the TypeDenoter of the result type. The ParamTypes property is the list of parameter types. That list is simply composed from the Root and Elem role of the LidoList module instantiated for lists of DefTableKeys.

FunctDeclType.lido[64]==


SYMBOL FunctionHead INHERITS TypeDenotation END;

RULE: FunctionHead ::= '(' Parameters ')' TypeDenoter COMPUTE
  FunctionHead.GotType = 
    ResetParamTypes
      (KResetResultType
         (KResetTypeName (FunctionHead.Type, "function..."),
          TypeDenoter.Type),
       Parameters.DefTableKeyList);
END;

SYMBOL Parameters INHERITS DefTableKeyListRoot END;
SYMBOL Parameter INHERITS DefTableKeyListElem END;

RULE: Parameter ::= TypeDenoter DefIdent COMPUTE
  Parameter.DefTableKeyElem = TypeDenoter.Type;
END;

This macro is attached to a product file.

Function calls are integrated in the expression syntax of our language. We chose a very general form of an Expression to denote the function to be called. That allows us to later expand the language by expressions which yield a function. That feature does not create additional problems for type analysis.

We also introduce return statements into our language.

Call.con[65]==


Expression:     Expression '(' Arguments ')'.
Arguments:      [Argument // ','].
Argument:       Expression.

Statement:      'return' ';'.
Statement:      'return' Expression ';'.

This macro is attached to a product file.

Type analysis for a function call is straight-forward: We access the ResultType from the type of the function Expression; it is the type of the call. The list of parameter types is passed to the Arguments. There it is decomposed into its elements using the list decomposition roles of the LidoList module, DeListRoot and DeListElem. That mechanism also works if in erroneous cases the lengths of the parameter list and the structural argument list are different.

Call.lido[66]==


SYMBOL Arguments INHERITS DefTableKeyDeListRoot END;
RULE: Expression ::= Expression '(' Arguments ')' COMPUTE
  Expression[1].Type = 
        TransDefer (GetResultType (Expression[2].Type, NoKey));

  Arguments.DefTableKeyList = 
        GetParamTypes (Expression[2].Type, NULLDefTableKeyList);
END;

SYMBOL Argument INHERITS DefTableKeyDeListElem END;
RULE: Argument ::= Expression COMPUTE
  Expression.ReqType = Argument.DefTableKeyElem;
END;

This macro is attached to a product file.

The computation of the ReqType attribute above completely captures type checking for each argument. For the function Expression we only have to check whether it really yields a function, the first check below. The other two checks issue messages if the lengths of the lists are different.

CallCheck.lido[67]==


RULE: Expression ::= Expression '(' Arguments ')' COMPUTE
  Expression[2].ReqType = Expression[2].Type;

  IF (EQ (Expression[1].Type, NoKey),
  message (ERROR, "call applied to non function", 0, COORDREF));

  IF (NE (Arguments.DefTableKeyListTail, NULLDefTableKeyList),
  message (ERROR, "arguments missing", 0, COORDREF));
END;

RULE: Argument ::= Expression COMPUTE
  IF (EQ (Argument.DefTableKeyElem, NoDefTableKey),
  message (ERROR, "too many arguments", 0, COORDREF));
END;

This macro is attached to a product file.

A return statement refers to the immediately enclosing function declaration. We have to check that a value of a type compatible to the result type is returned if the latter is not void. A return from the outermost program level is considered as if the program was a void function.

Return.lido[68]==


SYMBOL Program COMPUTE 
  SYNT.Type = KResetResultType (NewKey(), voidType); 
END;

ATTR resType: DefTableKey;

RULE: Statement ::= 'return' ';' COMPUTE
  .resType =
     TransDefer 
       (GetResultType 
          (INCLUDING (FunctionDecl.Type, Program.Type),
           NoKey))
     <- INCLUDING Program.GotType;

  IF (NOT (EqualTypes (.resType, voidType)),
  message (ERROR, "return value required", 0, COORDREF));
END;

RULE: Statement ::= 'return' Expression ';' COMPUTE
  .resType =
     TransDefer 
       (GetResultType 
          (INCLUDING (FunctionDecl.Type, Program.Type),
           NoKey))
     <- INCLUDING Program.GotType;

  IF (EqualTypes (.resType, voidType),
  message (ERROR, "return value not allowed", 0, COORDREF));

  Expression.ReqType = .resType;
END;

This macro is attached to a product file.


Previous Chapter Next Chapter Table of Contents