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, ....

Type analysis tasks

Previous Chapter Next Chapter Table of Contents


Operator Identification

Operator identification is a subtask of type analysis for any language that has overloaded operators, i.e. a source operator symbol like + may denote one of several target operations, e.g. integer addition or floating point addition or boolean disjunction. The distinction is made using the types of the operands. (The Ada-like case where the expected result type is also used is not supported here.)

The Operator module allows compact descriptions of the characteristics of each operator. It is required that types of operands and expressions are represented by DefTableKeys which are PDL known keys. The module also supports transformation of operators. Target operators are also represented by PDL known keys which may have properties associated that describe their translation.

This module replaces the AdaptOil module of previous library versions, and covers all its functionality. It uses the current version of the Oil tool which supports operators and types being represented by DefTableKeys.

The Operator module is instantiated with a referto parameter that gives the name of the file containing the operator descriptions

   $/Type/Operator.gnrc +referto=(FILENAME):inst
If this instantiation is contained in a .specs file and if the description file, say Oper.d is contained in the same directory, it may read
   $/Type/Operator.gnrc +referto=(Oper.d):inst
If the .specs and Oper.d are contained in a .fw specification, the same line can be used.

The file contains a sequence of macro calls that describe source operators and target operators. The module provides computational roles for binary and unary operators (BinTgtOpr and UnTgtOpr) which perform operator identification. Their use is described below.

The macros that describe the operators have the following forms:

SrcOpr (Token, ConSymbol, TreeSymbol, SrcKey)
A source operator is described. Token is a literal terminal that denotes the operator in the concrete grammar. The operator's precedence is specified by the concrete grammar nonterminal ConSymbol, that collects a set of operators having the same precedence. In the tree grammar the operator (and all others of the ConSymbol set) is represented by a TreeSymbol. SrcKey is the name of a DefTableKey which represents this operator uniquely. It is automatically introduced as a PDL known key.

TgtOpr (SrcKey, TgtKey, Signature, KeyInit)
A target operator TgtKey is described. It is uniquely represented by the DefTableKey TgtKey, which is automatically introduced as a PDL known key. The operator is one of several overloaded meanings for the source operator SrcKey. Its signature is specified by Signature, using the notation of the Oil tool. The types occurring in the Signature are names of DefTableKeys. Properties may be associated to TgtKey to be used for further analysis and translation tasks. They can be initialized by KeyInit which is a possibly empty PropertyValueList in PDL notation. (If more than one property is initialized, the macro name comma has to be used as a separator instead of the , token.)

The following restrictions must be obeyed: Every SrcKey must occur only once in a SrcOpr description. Every TgtKey must occur only once in a TgtOpr description.

The computational role BinTgtOpr is to be inherited by a grammar symbol that represents a binary operator and that is mentioned as a TreeSymbol in a SrcOpr description. Two attributes named LType and RType have to be set to the type of the left and of the right operand respectively. Attributes ResType, LTType, and RTType are computed representing the result type of the identified target operator and its operand types. An attribute TgtKey is computed representing the target operator by the key specified in the TgtOpr description.

The same holds for the computational role UnTgtOpr, with the exception that only the RType attribute has to be set.

The computational role ChkOpr provides a check whether a valid target operator is identified for the given types, and issues a message otherwise. It can be inherited by binary or unary operator symbols.

The use of this module is demonstrated by adding expressions with binary and unary operators to the language of our running example. In the concrete grammar an expression hierarchy defines precedences and associativity of operator sets:

   Expression:     Expression AddOpr Factor / Factor.
   Factor:         Factor MulOpr Operand / Operand.
   Operand:        MonOpr Operand.
   Operand:        '(' Expression ')'.
Here UnOprs have highest precedence and AddOpr have lowest. The operators of the three sets are not specified here. They are introduced by SrcOpr descriptions contained in the file the module is instantiated with, e.g.
   SrcOpr ('+', AddOpr, BinOpr, AddKey)
   SrcOpr ('*', MulOpr, BinOpr, MulKey)
   SrcOpr ('-', MonOpr, UnOpr,  NegKey)

The module adds a production for every source operator to the concrete grammar, e.g.

   AddOpr: '+'.
It states that AddOpr and MulOpr are to be represented by a BinOpr node in the tree, and it adds an attribute computations for each operator context to the tree, e.g.
   RULE: BinOpr ::= '+' COMPUTE BinOpr.OprSym = AddKey; END;

The following target operator descriptions (also contained in the file the module is instantiated with) overload those operators with operations on integral numbers and boolean values:

  TgtOpr (AddKey, iAddKey, (intType,intType):intType,    TgtStr={"+"})
  TgtOpr (AddKey, bOrKey,  (boolType,boolType):boolType, TgtStr={"||"})
  TgtOpr (MulKey, iMulKey, (intType,intType):intType,    TgtStr={"*"})
  TgtOpr (MulKey, bAndKey, (boolType,boolType):boolType, TgtStr={"&&"})
  TgtOpr (NegKey, iNegKey, (intType):intType,            TgtStr={"-"}) 
  TgtOpr (NegKey, bNotKey, (boolType):boolType,          TgtStr={"!"}) 
From these descriptions the module generates the necessary .oil specifications, e.g
  INDICATION AddKey: iAddKey;
  OPER iAddKey (intType,intType):intType;
and the necessary .pdl specifications, e.g
  iAddKey -> TgtStr={"+"};
The properties that are initialized in the target operator description, here TgtStr have to be defined in the user's specification.

We then can use the computational roles BinTgtOpr, UnTgtOpr, and ChkOpr to solve the overloading resolution task. We only have to assign the types of the operands to attributes of the operator symbol, and use the types of the signature of the identified target operator correspondingly:

   SYMBOL Expression: Type, ReqType: DefTableKey;

   SYMBOL BinOpr INHERITS BinTgtOpr, ChkOpr END;
   RULE: Expression ::= Expression BinOpr Expression COMPUTE
     BinOpr.LType = Expression[2].Type;
     BinOpr.RType = Expression[3].Type;
     Expression[1].Type = BinOpr.ResType;
     Expression[2].ReqType = BinOpr.LTType;
     Expression[3].ReqType = BinOpr.RTType;
   END;

   SYMBOL UnOpr INHERITS UnTgtOpr, ChkOpr END;
   RULE: Expression ::= UnOpr Expression COMPUTE
     UnOpr.RType = Expression[2].Type;
     Expression[1].Type = UnOpr.ResType;
     Expression[2].ReqType = UnOpr.RTType;
   END;

The operator descriptions of the target operators in our example associate a property TgtStr to be used for a translation to C:

   RULE: Expression ::= Expression BinOpr Expression COMPUTE
     Expression[1].CCode =
        PTGBinOpr (Expression[2].CCode,
                   GetTgtStr (BinOpr.TgtKey, "??"),
                   Expression[3].CCode);
   END;

   RULE: Expression ::= UnOpr Expression COMPUTE
     Expression[1].CCode =
        PTGUnOpr (GetTgtStr (UnOpr.TgtKey, "??"),
                  Expression[2].CCode);
   END;

To complete the above example we need a .pdl specification of the TgtStr property

   TgtStr:  CharPtr; "Strings.h"

and suitable .ptg patterns for the translation of expressions:

   BinOpr: "(" $1 ")" $2 string "(" $3 ")"
   UnOpr:  $1 string "(" $2 ")"


Previous Chapter Next Chapter Table of Contents