General Information

	Eli: Translator Construction Made Easy
	Global Index
	Frequently Asked Questions
	Typical Eli Usage Errors

Tutorials

	Quick Reference Card
	Guide For new Eli Users
	Release Notes of Eli
	Tutorial on Name Analysis
	Tutorial on Scope Graphs
	Tutorial on Type Analysis
	Typical Eli Usage Errors

Reference Manuals

	User Interface
	Eli products and parameters
	LIDO Reference Manual
	Typical Eli Usage Errors

Libraries

	Eli library routines
	Specification Module Library

Translation Tasks

	Lexical analysis specification
	Syntactic Analysis Manual
	Computation in Trees

Tools

	LIGA Control Language
	Debugging Information for LIDO
	Graphical ORder TOol

FunnelWeb User's Manual

	Pattern-based Text Generator
	Property Definition Language
	Operator Identification Language
	Tree Grammar Specification Language
	Command Line Processing
	COLA Options Reference Manual

Generating Unparsing Code

Monitoring a Processor's Execution

Administration

System Administration Guide

Type Analysis

Program-Dependent Property Computation

There are language constructs which need to set a property of an entity that depends on a property of another entity. If the order of accessing and setting the properties depends on the particular program, those operations can not be specified by dependent computations in trees, rather a program dependent mechanism is needed. An example for such a construct is a variable declaration of the form

    like a b;

The variable b is declared to have the same type as the variable a has. A program may have arbitrary long chains of such type references, which may occur in any order. This module provides a worklist algorithm to solve such problems: Tree computations create worklist tasks, which try to access and set certain properties as described by call-back functions, and store them on the worklist. They are re-executed in sweeps through the worklist until no futher task can be completed.

The module is instantiated by

$/Type/PropertyWorklist.gnrc+instance=`prefix':inst

If the instance parameter is given, the prefix is added to every name exported by that instantiation, e.g. prefixTaskFct. In the following we write *TaskFct to indicate that such a prefix will be added to that name. Several instances of the module with different prefixes may be used, if several worklists are needed,

The module provides the roles *RootWorklist and *WLPropertyTask:

*WLPropertyTask is the central task which creates a worklist task. The attribute SYNT.*TaskFct has to be set to a pointer to a function which performs the computation of the worklist task for this context. (Different functions may be chosen in different *WLPropertyTask contexts.) The values of the following attributes are available when the function is called during sweeps through the worklist:

INH.*PropKeyA and SYNT.*PropKeyB are keys of type DefTableKey and have the default NoKey. SYNT.*WLDepOnTaskA and SYNT.*WLDepOnTaskB are pointers of type PropertyTaskPtr which may be set to point to other worklist task; the default is NULLPropertyTaskPtr.

The attribute SYNT.*WLTask provides a pointer which identifies the created worklist task. Its value may be propagated to some other *WLPropertyTask context, the task of which depends on information from this task.

Each function used as a *TaskFct in a *WLPropertyTask context has to be declared in a C module where PropertyWL.h is included in the .h and .c file.

All these function declarations have the following signature:

void WLCallBackSetType (PropertyTaskPtr this)

In the body of the function the values of the four attributes, e.g. INH.*PropKeyA, can be accessed via the parameter, e.g. this->PropKeyA. Furthermore, the coordinates of the creation context are available by this->coord of type CoordPtr.

In case of the above example with the like construct one could use this->PropKeyA for the key of the variable, the type of which is to be set, and this->PropKeyB for the variable which provides the type. The worklist algorithm while sweeping through the list of tasks re-calls the function for each task until its this->done is set. In this example, the function would execute

  DefTableKey tp = GetTypeOf (this->PropKeyB, NoKey);
  if (tp == NoKey) return;
  ResetTypeOf (this->PropKeyA, tp);
  this->done = 1; return;

Between the start of the worklist algorithm and its completion, no computations in tree contexts are executed. Hence, there are only two ways to propagate information from one worklist task to another: either via setting and accessing properties of this->PropKeyA or this->PropKeyB, or by accessing the data components of another task via this->WLDepOnTaskA or this->WLDepOnTaskB, e.g. GetTypeOf (this->WLDepOnTaskA->PropKeyA, NoKey).

This feature can be used to substitute the attribute value propagation between related *WLPropertyTask contexts. Binding of qualified names like a.b.c is a typical example: Assume that the TypeOf property of variable identifiers is determined by worklist tasks, e.g. because of the presence of like constructs. Then the task for binding the qualified identifier c depends on the result of the task for the qualifier a.b. That relation can be established in the task creation context using the attribute *WLDepOnTaskA, such that the function call for the worklist task can access the TypeOf property.

The attribute *RootWorklist.*WLSolved indicates that the worklist algorithm has terminated. Any computation which accesses properties computed by worklist tasks have to depend on it. The worklist algorithm terminates, when a sweep through the list did not complete any task. Some tasks may still be unsolved, e.g. because of missing settings of properties or cyclic dependences between tasks. The attribute *RootWorklist.*WLOpenTasks gives the number tasks that remained unsolved. In the creation context of a task it can be checked whether this particular task completed, using

PTRSELECT (THIS.*WLTask, done) <- INCLUDING *RootWorklist.*WLSolved

The accumulating attribute *RootWorklist.*WLReadyToSolve contributes to the precondition for starting the worklist algorithm. It has to be used if some worklist tasks are created without notification by the *WLPropertyTask role. The function which creates a worklist task has the following signature:

PropertyTaskPtr CreatePropertyTask
        (PropWLPtr wl,
         DefTableKey PropKeyA, DefTableKey PropKeyB,
	 PropertyTaskPtr WLDepOnTaskA, PropertyTaskPtr WLDepOnTaskB,
	 WLTaskFctType TaskFct,
         CoordPtr coord);

The first parameter is the reference to the list of worklist tasks, it is obtained from the attribute INCLUDING *RootWorklist.*Worklist; the meaning of the other parameters can be deduced from their names. It is possible and may be useful in certain cases to call CreatePropertyTask from inside a worklist function; then care must be taken to guarantee termination. If the CreatePropertyTask is called in a C module, PropertyWL.h is to be included.