Eli   Documents

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

Abstract data types to be used in specifications

Next Chapter Table of Contents


Lists in LIDO Specifications

Several language implementation tasks are solved using linear lists constructed of data elements which are computed at certain tree nodes, e.g. a the list of parameter types that is part of the type of a function. Such lists reflect a left-to-right depth-first order of the corresponding tree nodes. Similarly such lists are decomposed in other contexts, e.g. to check the types of the arguments of a function call. This module provides .lido specifications for such patterns of linear list usage. The module uses functions of the linear list module List. Any assignable C type may be chosen as type of the list elements.

This module is instantiated by

   $/Adt/LidoList.gnrc+instance=TYPE +referto=HDR :inst
where TYPE is the name of the element type and HDR.h is a file that defines the element type, e.g.
   $/Adt/LidoList.gnrc+instance=DefTableKey +referto=deftbl :inst
If the element type is predefined in C the referto parameter is omitted, e.g.
   $/Adt/LidoList.gnrc+instance=int :inst

The module provides two groups of computational roles, TYPEListRoot, PreTYPEListElem, PostTYPEListElem, TYPEListElem, for construction of a list from attribute values at tree nodes, and TYPEDeListRoot, PreTYPEDeListElem, PostTYPEDeListElem, TYPEDeListElem for distribution of a list over attributes of tree nodes. For each of the two cases there is one role that characterizes the root of the subtree where the list construction or distribution is applied, and three roles for nodes that are related to list elements. These three roles affect the order of list elements differently in cases where the related tree nodes may occur recursively (see below).

For construction of a list TYPEListRoot is associated to a grammar symbol that contains all occurrences of the roles for its list elements in its subtree. If TYPEListRoot occurs recursively in the tree, its lists are collected separately. The resulting list of type TYPEList is obtained by the attribute TYPEListRoot.TYPEList.

A user's computation has to provide the list element values of type TYPE by attributes named TYPEElem at the symbols which have one of the three element roles. One of the three roles should be chosen depending on the desired order of the elements in cases where the list element symbol occurs recursively in the tree:

If the role PreTYPEListElem is used the elements are taken in pre-order; i.e. the attribute value of a node occurs in the list prior to those of nodes in its subtrees.

If the role PostTYPEListElem is used the elements are taken in post-order; i.e. the attribute value of a node occurs in the list after those of nodes in its subtrees.

If the role TYPEListElem is used no elements are taken from subtrees of an element node.

There are situations where not all tree nodes that have the role TYPEListElem shall contribute an element to the list. A condition attribute TYPEListElem.TYPETakeIt of type int can be computed such that it is false (0) if this tree node shall not contribute to the list. The value of the attribute TYPEListElem.TYPEElem is irrelevant in that case. If the condition attribute TYPEListElem.TYPETakeIt is true the value of the attribute TYPEListElem.TYPEElem is taken as an element of the list. A default computation sets TakeIt to true (1). It becomes effective if it is not overridden as described above.

TYPEFilterListElem is outdated. Its task should be achieved using the attribute TYPETakeIt. TYPEFilterListElem may be used instead of TYPEListElem. Then the value TYPEFilterListElem.TYPEElem will only be inserted into the list if a call of the function TYPEFilter yields non-null when given TYPEFilterListElem.TYPEElem as argument. The function TYPEFilter has to be defined if the role TYPEFilterListElem is used.

For decomposition of a list TYPEDeListRoot is associated to a grammar symbol, and a computation has to be provided such that the attribute TYPEDeListRoot.TYPEList gets a list value. That list value is decomposed such that each occurrence of grammar symbols having one of the element roles for decomposition (see below) get a list element value. The list element values are obtained by attributes named TYPEElem. If the list is shorter than the number of the element nodes in the subtree the attributes of the remaining nodes get the value NoTYPE. TYPEDeListRoot.TYPEListTail is the list of remaining elements which are not associated to element nodes in the subtree, if any.

One of the three element roles for list decomposition should be chosen depending on the desired order of the elements in cases where the list element symbol occurs recursively in the tree:

If the role PreTYPEDeListElem is used the list elements are associated to TYPEElem attributes of nodes in pre-order, i.e. the attribute of a node gets an element of the list which occurs before those elements in the list that are distributed at the subtrees of the node.

If the role PostTYPEDeListElem is used the list elements are associated to TYPEElem attributes of nodes in post-order, i.e. the attribute of a node gets an element of the list which occurs after those elements in the list that are distributed at the subtrees of the node.

If the role TYPEDeListElem is used no elements are distributed to subtrees of an element node.

A condition attribute TYPETakeIt of type int is computed to true (1) by default. It determines whether an element of the list is taken at this node. That computation may be overridden by a nontrivial computation if such a condition is desired.

If list decomposition is used the name NoTYPE has to be defined suitably in a user's specification, e.g. in HDR.h.

Both TYPEListRoot and TYPEDeListRoot may be recursively nested without affecting each other.

An example for the use of this module in type analysis is given in (see Function Types of Functions as typed entities): In the context of a function declaration the list of parameter types is composed and associated as a property of the function type. In the context of a function call that property is accessed, the list is decomposed, and its elements - the formal parameter types - are compared with the types of the arguments.


Next Chapter Table of Contents