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

LIDO - Reference Manual

Previous Chapter Next Chapter Table of Contents


Remote Attribute Access

Remote access constructs are used to relate computations that belong to distant contexts in the tree, rather than those of adjacent contexts. The INCLUDING construct accesses attributes of symbols that are further up in the tree (i. e. closer to the root). The CONSTITUENT(S) construct accesses attributes of symbols that are further down in the tree (i. e. closer to the leaves). The CHAIN construct relates computations in a left-to-right depth-first order within subtrees.

These constructs may propagate values or simply specify dependencies between computations.

Remote access constructs are used to abstract from the particular tree structure between related computations. Computational patterns can be specified independent of the particular grammar using remote access in combination with symbol computations and CLASS symbols. Reusable specification modules are based on that technique.

INCLUDING

The INCLUDING-construct accesses an attribute of a symbol that is on the path towards the tree root. Hence, several computations in a subtree may depend on an attribute at the subtree root.

Syntax

    RemoteAccess ::= 'INCLUDING' RemAttrList
    RemAttrList  ::=  RemAttr | '(' RemAttrs ')'
    RemAttrs     ::=  RemAttr ',' RemAttrs '|' RemAttr
    RemAttr      ::=  SymbName '.' AttrName



Examples

    INCLUDING Range.Env
    INCLUDING (Block.Scope, Root.Env)

The RemAttrList specifies the set of attributes referred to by the INCLUDING construct, called the referred set. On evaluation it accesses an attribute of the first symbol on the path to the root which is in that set.

An INCLUDING in a rule computation accesses an attribute of a symbol above the current context, even if the left-hand side symbol is in the RemAttrList.

An INCLUDING in a symbol computation accesses an attribute of a symbol above the current one, even if the current one is in the RemAttrList.

An attribute of a CLASS symbol C.a in the RemAttrList contributes attributes X.a to the referred set for all TREE symbols X by which C is inherited.

An INCLUDING in a VOID context does not cause a value to be propagated; it just states a dependency.

Restrictions

The referred set may not be empty, unless the computation which contains it is not part of or inherited by any rule context.

The tree grammar must guarantee that in every tree there is at least one of the symbols of the referred set above the context of the INCLUDING.

The referred set must not contain different attributes of the same symbol.

The types of the attributes in the referred set must be equal, unless INCLUDING is in a VOID context.

CONSTITUENT(S)

The CONSTITUENTS-construct accesses attributes of symbols that are in the subtree of the current context. Hence, it may depend on several computations in the subtree. If values are to be propagated they are combined by user defined functions.

The CONSTITUENT-construct accesses a single attribute instance of a symbol that is in the subtree of the current context.

Syntax

    RemoteAccess ::= [ SymbolRef ] 'CONSTITUENT' 
                     RemAttrList [ ShieldClause ]
                   | [ SymbolRef ] 'CONSTITUENTS' 
                     RemAttrList [ ShieldClause ] [ WithClause ]
    ShieldClause ::= 'SHIELD' SymbNameList
    SymbNameList ::= SymbName | '(' SymbNames ')' | '(' ')'
    WithClause   ::= 'WITH' '(' TypeName ',' CombFctName ',' 
                                SingleFctName ',' NullFctName ')'












Examples

    CONSTITUENT Declarator.type
    Declarations CONSTITUENTS DefIdent.GotType
    CONSTITUENTS Range.GotLocKeys SHIELD Range
    CONSTITUENTS Stmt.code SHIELD Stmt
       WITH (PTGNode, PTGSeq, IDENTICAL, PTGNull)

The RemAttrList specifies the set of attributes referred to by the CONSTITUENT(S) construct, called the referred set. On evaluation it accesses all instances of attributes of that set which are in a certain range of the subtree of the current context. That range is determined by its root node, which itself does not belong to the range, and by the set of shield symbols. The tree nodes below a shield symbol are excluded from that range.

In a rule computation the root of the tree range is the node corresponding to the left-hand side of the production. The optional SymbolRef may restrict the root of the tree range to a node corresponding to a symbol of the right-hand side of the production.

In a (lower or upper) symbol computation the root of the tree range is the node corresponding to that symbol.

If the optional ShieldClause is given it specifies the set of shielded symbols. If an empty ShieldClause is given, no symbols are shielded from the tree range. If the ShieldClause is omitted then the root symbol of the tree range (as described above) is shielded from the range.

An attribute of a CLASS symbol C.a in the RemAttrList contributes attributes X.a to the referred set for all TREE symbols X to which C is inherited.

A CLASS symbol C in the ShieldClause contributes symbols X to the set of shielded symbols for all TREE symbols X to which C is inherited.

A CONSTITUENT(S) in a VOID context simply states a dependency and does not cause a value to be propagated.

For a CONSTITUENTS that is not in VOID context a WithClause specifies how the values of the accessed attribute instances are combined into one value.

The given TypeName specifies the type of the result and of intermediate values.

The CombFctName specifies a function (or macro) that is applied to two values of the given type and yields one value of that type.

The SingleFctName specifies a function (or macro) that is applied to each accessed attribute instance and yields a value of the given type.

The NullFctName specifies a function (or macro) that has no argument and yields an intermediate value. It is called for every node in the tree range that could have referred attribute instances below it according to the tree grammar, but for the particular tree it has none. Hence, the result of this function should be neutral with respect to the combine function.

It is guaranteed that the combine function is applied to intermediate values according to a post-order projection of the accessed tree nodes. It is left open in which associative order that function combines intermediate values.

The referred set of a CONSTITUENTS may be empty if no attributes of the RemAttrList are reachable in the subtree or if CLASS symbols in the RemAttrList are not inherited to any TREE symbol. In that case a VOID CONSTITUENTS is ignored, and a value CONSTITUENTS results in a call of the NullFctName.

Restrictions

A SymbolRef must denote a right-hand side symbol of the production. It must not be specified in symbol computations.

A CONSTITUENTS in a value context must have a WithClause.

For a CONSTITUENT the tree grammar must guarantee that the accessed attribute instance is uniquely determined for every tree.

The RemAttrs must have the same type if the CONSTITUENT(S) is in value context.

CHAIN

Chains relate computations in left-to-right depth-first order within certain subtrees. A chain may propagate values or just specify dependencies in that order. Only effective computations, that compute a new chain value or a new post-condition need to be specified. They are automatically linked in the described order.

The basic idea is captured by the following diagram representing the way of a chain through the tree context of a rule graphically:

        RULE: LhsSym ::= RhsSym1 RhsSym2 END;

                 |                ^
                 v                |
                 u     LhsSym     d
                /                  ^
               /                    \
              /        _____         \
             /         |   |          \
            v          |   v           \
            d  RhsSym1 u   d  RhsSym2   u
            |          ^   |            ^
            |          |   |            |
            ------------   --------------
The arcs represent the path of the chain through this context, coming in from the upper context of LhsSym, going through the two subtrees, and leaving to the upper context. That chain propagation is established automatically if the chain is not used in this context. Usually, some of the three arcs inside the the context may be specified by explicit computations that use and define the chain at a certain symbol occurrence. The u and d in the graphic stand for usable and definable chain accesses respectively.

Chain accesses are denoted like attribute accesses with a ChainName instead of an attribute name.

Syntax

    ChainSpec     ::= 'CHAIN' ChainNames ':' TypeName

    Computation   ::= 'CHAINSTART' Attribute '=' Expression Terminator

    Attribute     ::= SymbolRef '.' ChainName


Examples

    CHAIN cnt : int
    RULE: Block ::= '{' Decls Stmts '}' COMPUTE
      CHAINSTART Stmts.cnt = 0;
      printf ("Block has %d statements\n", Stmts.cnt);
    END;
    RULE: Stmt ::= Var '=' Expr ';' COMPUTE
      Stmt.cnt = ADD (Stmt.cnt, 1);
    END;

    CHAIN codeseq: PTGNode;
    SYMBOL Block COMPUTE
      CHAINSTART HEAD.codeseq = PTGNULL;
      SYNT.transl = TAIL.codeseq;
    END;
    SYMBOL Stmt COMPUTE
      THIS.codeseq = PTGSeq (THIS.codeseq, THIS.transl);
    END;

A CHAIN specification introduces the name and the type of a chain. Any attribute notation using a ChainName denotes a chain access.

A chain states a precondition and a postcondition for each symbol node on the chain. The precondition is set by the upper context of the symbol, the postcondition by its lower context. They can be understood as an implicitly introduced pair of attributes, an inherited one for the precondition and a synthesized one for the postcondition.

A computation is allocated on the chain if it depends on the chain and its result contributes to the chain. Such computations are automatically linked in left-to-right depth-first order. A computation is only linked in chain order if it defines the chain and depends directly or indirectly on it. A computation that only accesses the chain without defining it is not necessarily executed in chain order.

A computation that defines a chain without directly or indirectly accessing it breaks the chain, i. e. the execution order of subsequent chain computations is independent of those prior to this computation.

There may be several instances of a chain that have the same name and type. Each instance is identified by a context that contains a CHAINSTART computation for that chain. Chain references in subtrees of such a CHAINSTART context belong to that instance, unless they belong to a nested instance of CHAINSTART context deeper in the tree. Different instances of a chain are not related to each other, regardless of whether they are nested or separate. However, they may be explicitly connected by computations. The structure of the tree grammar must ensure that there is a CHAINSTART context above any computation that refers to the chain.

A CHAINSTART computation defines the initial value of a chain. The chain is started at the symbol specified as the destination of the CHAINSTART computation. It must be the leftmost of the right-hand side symbols which the chain is to be passed through. HEAD.c may be used for a chain c to denote the leftmost symbol of the right-hand side, in symbol computations as well as in rule computations.

A computation may refer to a chain c by one of the following notations: X.c in rule computations, THIS.c, SYNT.c, INH.c in symbol computations, HEAD.c, and TAIL.c in both rule and symbol computations.

The notations X.c and THIS.c have different meanings depending on their occurrence in a defining position of an attribute computation or in an applied position within an expression:

In rule computations the following holds: If X is the left-hand side symbol of the production, then an applied occurrence X.c denotes the chain's precondition at X; a defining occurrence X.c denotes the chain's postcondition at X. If X is a right-hand side symbol of the production, then a defining occurrence X.c denotes the chain's precondition at X; an applied occurrence X.c denotes the chain's postcondition at X.

In symbol contexts only lower computations may access or define a chain. An applied occurrence of THIS.c denotes the chain's precondition of that symbol; INH.c may be used instead. A defining occurrence of THIS.c denotes the chain's postcondition of that symbol; SYNT.c may be used instead.

The notation HEAD.c can be used to define the chain's precondition of the leftmost subtree. The notation TAIL.c can be used to access the chain's postcondition of the rightmost subtree. These notations can be used in symbol computations and in rule computations. If used in a rule computation that rule must have at least one subtree.

If HEAD.c, TAIL.c, or CHAINSTART is used in a symbol computation that is inherited by a rule which has no subtree, they have the same effect as if there was a subtree which passes the chain dependency and the chain value, if any, unchanged.

In the following example a chain c is used in symbol computations. They state that the functions Prefix and Suffix are called on the chain for every Expression context. The Prefix call is applied to the incoming chain and specifies the chain precondition for the leftmost subtree of Expression. The Suffix call is applied to the result of the rightmost subtree and specifies the chain postcondition of this Expression:

    SYMBOL Expression COMPUTE
        HEAD.c = Prefix (THIS.c);
        THIS.c = Suffix (TAIL.c);
    END;

Restrictions

Every ChainName must be different from any attribute name and any AttrName.

The tree grammar must guarantee that each access of a chain is in a subtree of a CHAINSTART context for that chain. Furthermore that subtree may not be to the left of the symbol where the CHAINSTART initiates the chain.

None of THIS.c, SYNT.c, INH.c, TAIL.c may be used in upper symbol computations.

HEAD.c must not be used in applied positions.

TAIL.c must not be used in defining positions.

Chains can not be accessed in INCLUDING or CONSTITUENT(S) constructs.


Previous Chapter Next Chapter Table of Contents