Eli   Documents Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads

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

Name analysis according to scope rules

Previous Chapter Next Chapter Table of Contents


Environment Module

This module implements a standard contour model for name analysis. The data structure is a tree of scopes, each of which can contain an arbitrary number of definitions. A definition is a binding of an identifier to an object in the definition table (see PDL Reference Manual). For an identifier idn and a scope sc there is at most one binding in sc.

The environment module provides operations for building scope trees, adding definitions to specific scopes, and searching individual scopes or sequences of scopes for the binding of a particular identifier. Inheritance relations can be established between scopes to support object-oriented name analysis.

The module is capable of building multiple trees of scopes in order to model distinct name spaces, such that bindings in one tree do not effect the lookup in another tree.

The module places no constraints on the sequence of construction, definition and lookup operations; there is one exception: an inheritance relation may not be established for a scope that has already been involved in a lookup operation.

The module implements certain lookup operations such that linear search through several scopes is avoided in order to reduce the amortized asymptotic cost of name analysis. This effect on efficiency can be lost if the sequence of those lookup operations arbitrarily often switches the scopes they are applied to.

The modules described in the Name Analysis Library (see Name Analysis of Specification Module Library: Name Analysis) provide solutions for common name analysis tasks based on this environment module. If they are used the interface of this module is available for use in .lido specifications; otherwise the interface is made available by adding $/Name/envmod.specs to the processor specification. In C modules the interface of the environment module is introduced by #include "envmod.h".

Exported types and values

The following types and constant values are provided to represent name analysis data:

Environment
A pointer to a node in the tree of scopes. It is used either to refer to a single scope, or to refer to a scope and all the scopes that are visible from it (i.e. its ancestors in the tree and the scopes that are inherited by each).

NoEnv
A constant of type Environment that represents no environment.

Binding
A pointer to a triple (int idn, Environment sc, DefTableKey key) that represents the binding of the identifier idn in the scope pointed to by sc to the entity key.

NoBinding
A constant of type Binding that represents no binding.

InheritPtr
An opaque type used to traverse inheritance relations.

NoInherit
A constant of type InheritPtr that indicates the end of an inheritance traversal.

Operations to build the scope tree

The following operations are provided for constructing the tree of scopes:

Environment NewEnv ()
A function that creates a new tree consisting of a single, empty scope and returns a reference to that empty scope.

Environment NewScope (Environment env)
A function that creates a new empty scope as a child of the scope pointed to by env and returns a reference to that empty scope.

Operations to establish inheritance

An inheritance relation from scope fromcl to scope tocl means that the scope tocl inherits the bindings of the scope fromcl. The following operations are provided to establish and to check inheritance relations:

int InheritClass (Environment tocl, Environment fromcl)
A function that establishes an inheritance relation from the scope fromcl to the scope tocl if and only if

    tocl and fromcl are different scopes in the same tree of scopes

    the graph of inheritance relations remains acyclic when adding the relation

    the scope tocl has not yet been involved in a lookup for a binding.

InheritClass returns 1 if the inheritance relation could be established; otherwise it returns 0.

int Inheritsfrom (Environment tocl, Environment fromcl)
A function that returns 1 if tocl and fromcl are the same scopes, or if there is a direct or indirect inheritance relation from the scope fromcl to the scope tocl. Otherwise Inheritsfrom returns 0. After a call of Inheritsfrom, no further inheritance relation can be established for tocl or fromcl.

Operations to establish bindings

The following operations are provided to establish a binding within a scope:

Binding BindKey (Environment env, int idn, DefTableKey key)
A function that checks the scope referenced by its env argument for a binding of the identifier specified by its idn argument. If no such binding is found, a binding of the identifier idn to the definition table object specified by key is added to scope env. BindKey returns the value NoBinding if a binding already exists, and returns the new binding otherwise.

int AddIdn (Environment env, int idn, DefTableKey key)
A macro that calls BindKey. AddIdn returns the value 0 if BindKey returns NoBinding, and returns 1 otherwise.

Binding BindKeyInScope (Environment env, int idn, DefTableKey key)
A function that has the same effect as BindKey. BindKeyInScope should be used for efficiency reasons if bindings are established in several different scopes before lookups are performed in them.

Binding BindIdn (Environment env, int idn)
A function that checks the scope referenced by its env argument for a binding of the identifier specified by its idn argument. If no such binding is found, BindIdn obtains a value from NewKey() and binds idn to that value in scope env. BindIdn returns the the binding associated with idn.

DefTableKey DefineIdn (Environment env, int idn)
A macro that calls BindIdn and returns the key of the binding returned by BindIdn.

Binding BindInScope (Environment env, int idn)
A function that has the same effect as BindIdn. BindInScope should be used for efficiency reasons if bindings are established in several different scopes before lookups are performed in them.

These operations are very similar, but they differ in two aspects:

  • The key for the new binding is given as an argument (BindKey, AddIdn, BindKeyInScope), or a new key is created for the new binding (BindIdn, DefineIdn, BindInScope).

  • Functions that should be preferred for efficiency reasons if several operations on one scope occur in sequence (BindKey, AddIdn, BindIdn, DefineIdn), or if scopes are arbitrarily switched between operations (BindKeyInScope, BindInScope).

DefineIdn and AddIdn are provided for compatibility with previous versions of the environment module.

Operations to find bindings

The following operations are provided to lookup bindings for given identifiers. For ease of understanding they are described here as if the bindings of scopes were traversed in a linear search. In fact the implementation avoids such linear search where possible:

Binding BindingInScope (Environment env, int idn)
A function that checks the scope referenced by its env argument for a binding of the identifier specified by its idn argument. If no binding for idn is found, the scopes that are directly or indirectly inherited by env are searched. During that search, a scope tocl is considered before a scope fromcl if tocl inherits from fromcl. The first binding found is returned; if no binding is found then NoBinding is returned.

DefTableKey KeyInScope (Environment env, int idn)
A macro that calls BindingInScope and returns the key of the binding found. NoKey is returned if no binding is found by BindingInScope.

Binding BindingInEnv (Environment env, int idn)
A function that has the same effect as BindingInScope except that if no binding for idn is found for scope env then the search continues as if BindingInScope was applied successively to ancestors of env in the tree of scopes.

DefTableKey KeyInEnv (Environment env, int idn)
A macro that calls BindingInEnv and returns the key of the binding found. NoKey is returned if no binding is found by BindingInEnv.

These operations are very similar, but they differ in one aspect:

  • Only the scope given as argument and those scopes it inherits from are considered for the lookup (BindingInScope, KeyInScope), or the scope given as argument, its ancestors in the tree of scopes, and those scopes they inherit from are considered for the lookup (BindingInEnv, KeyInEnv).

KeyInScope and KeyInEnv are are provided for compatibility with previous versions of the environment module.

Operations to find additional bindings

The following operations find further bindings that are related in some way to a given one:

Binding OverridesBinding (Binding bind)
A function that yields a hidden binding. Let bind be a binding of identifier idn in a scope e. Then OverridesBinding returns the value that BindingInEnv(e,idn) would have returned if the binding bind had not existed.

Binding NextInhBinding (Environment env, Binding bind)
A function that yields a binding that is also visible due to multiple inheritance relations. Let bind be a binding of identifier idn in a scope e that has been obtained by a call BindingInScope(env, idn), BindingInEnv(env, idn), or NextInhBinding(env, idn), and let tocl be env or its next ancestor that inherits from e. Then NextInhBinding returns a binding of identifier idn, if any, in a scope ep that is inherited by tocl but not by e; otherwise NoBinding is returned.

DefTableKey NextInhKey (Environment env, int idn, DefTableKey key)
A function that has the same effect as NextInhBinding, except that the keys of bindings (instead of the bindings themselves) are supplied and returned.

Operations to examine environments

The following operations are provided to obtain information from environments:

Binding DefinitionsOf(Environment env)
A function that returns the first binding of the scope env. It returns NoBinding if env is NoEnv or if no identifiers are bound in env.

Binding NextDefinition(Binding b)
A function that returns the next binding of the scope EnvOf(b). It returns NoBinding if b is NoBinding or if b is the last binding of EnvOf(b).

int IdnOf(Binding b)
A function that returns the identifier bound by b. It returns NoIdn if b is NoBinding.

DefTableKey KeyOf(Binding b)
A function that returns the key bound by b. It returns NoKey if b is NoBinding.

Environment EnvOf(Binding b)
A function that returns the environment containing b. It returns NoEnv if b is NoBinding.

Environment ParentOf(Environment env)
A function that returns the parent of env in a tree of scopes. It returns NoEnv if env is NoEnv or if env is the root of the tree.

DefTableKey SetKeyOfEnv(Environment env, DefTableKey k)
A function that associates the key k with the scope env. It returns k unless env is NoEnv; in that case it returns NoKey.

DefTableKey KeyOfEnv(Environment env)
A function that returns the key k associated with the scope env by the most recent operation SetKeyOfEnv(env,k). It returns NoKey if env is NoEnv or if SetKeyOfEnv(env,k) has never been executed.

int IsClass(Environment env)
A function that returns 1 if the scope env has been argument of a call of InheritClass; otherwise 0 is returned.

InheritPtr DirectInherits(Environment env)
A function that returns the first direct inheritance relation to env established by a call of InheritClass(env,fromcl). It returns NoInherit if env is NoEnv or if InheritClass(env,fromcl) has never been invoked.

InheritPtr NextInherit(InheritPtr inh)
A function that returns the next direct inheritance relation. It returns NoInherit if inh is NoInherit or if there are no more direct inheritances for the given scope.

Environment EnvOfInherit(InheritPtr inh)
A function that returns the scope fromcl of the inheritance relation inh.


Previous Chapter Next Chapter Table of Contents