GSS-3.1 3. Visiting Trees Overview Computations in structure trees may serve any suitable purpose, e.g. * compute or check properties of language constructs, e. g. types, values * determine or check relations in larger contexts, e.g. definition - use * construct data structure or target text Formal model for specification: attribute grammars (AGs) Generator Liga transforms a specification of computations in the structure tree (an AG written in the specification language Lido) into a tree walking attribute evaluator that executes the specified computations for each given tree in a suitable order. (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 301 Objectives: Introduction to computations in trees In the lecture: * Purpose of computations, * reminder on attribute grammars, * task of the generator. -------------------------------------------------------------------------------- GSS-3.1a Computations in Tree Contexts Specified by AGs Abstract syntax is augmented by: Attributes associated to nonterminals: e.g. Expr.Value Expr.Type Block.depth used to store values at tree nodes, representing a property of the construct, propagate values through the tree, specify dependences between computations Computations associated to productions (RULEs) or to nonterminals (SYMBOL): Compute attribute values using other attribute values of the particular context (RULE or SYMBOL), or cause effects, e.g. store values in a definition table, check a condition and issue a message, produce output Each attribute of every node is computed exactly once. Each computation is executed exactly once for every node of the RULE it is specified for. The order of the computation execution is determined by the generator. It obeys the specified dependences. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 301a Objectives: Fundamentals of AGs In the lecture: * Attributes and computations related to abstract syntax, * evaluation model. -------------------------------------------------------------------------------- GSS-3.2 Dependent Computations SYMBOL Expr, Opr: value: int SYNT; typed attributes of symbols SYMBOL Opr: left, right: int INH; TERM Number: int; terminal symbol has int value RULE: Root ::= Expr COMPUTE printf ("value is \%d\n", Expr.value); SYNThesized attributes are END; computed in lower contexts, INHerited attributes in upper c.. RULE: Expr ::= Number COMPUTE Expr.value = Number; SYNT or INH usually need not END; be specified. RULE: Expr ::= Expr Opr Expr COMPUTE Expr[1].value = Opr.value; Generator determines the Opr.left = Expr[2].value; order of computations Opr.right = Expr[3].value; consistent with dependences. END; RULE: Opr ::= quotesingle +quotesingle COMPUTE Opr.value = ADD (Opr.left, Opr.right); Example: END; RULE: Opr ::= quotesingle -quotesingle COMPUTE Computation and output of Opr.value = SUB (Opr.left, Opr.right); an expression's value END; (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 302 Objectives: Introduction of Lido notation In the lecture: Explain the notation along the example: * typed attributes, * computations with side effect (print), * attribute computations, * execution order determined by dependences, * SYNT and INH attributes. -------------------------------------------------------------------------------- GSS-3.3 An Attributed Structure Tree Root Expr Attribute value 9 dependence Expr 5 4 Expr value 5 Opr left value right value 4 9 + Expr 8 3 Expr Number value Opr left value right 8 value 4 3 5 Number - Number 8 3 (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 303 Objectives: Attribute values and dependences In the lecture: Explain * RULE contexts, * Computations in RULE contexts, * Computations depend on attributes, * a suitable tree walk. -------------------------------------------------------------------------------- GSS-3.4 Pre- and Postconditions of Computations RULE: Root ::= Expr COMPUTE Attributes print and printed Expr.print = "yes"; don't have values (type VOID) printf ("n") <- Expr.printed; END; They describe states being pre- and postconditions of RULE: Expr ::= Number COMPUTE computations Expr.printed = printf ("\%d ", Number) <-Expr.print; Expr.print: END; Postfix output up to this node is RULE: Expr ::= Expr Opr Expr COMPUTE completed. Expr[2].print = Expr[1].print; Expr[3].print = Expr[2].printed; Expr.printed: Opr.print = Expr[3].printed; Postfix output up to and Expr[1].printed = Opr.printed; including this node is END; completed. RULE: Opr ::= quotesingle +quotesingle COMPUTE Opr.printed = printf ("+ ") <- Opr.print; Example: END; Expression is printed in postfix form (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 304 Objectives: Specification of execution order In the lecture: Explain: * postfix output, * meaning and use of attributes print and printed -------------------------------------------------------------------------------- GSS-3.4a Pattern: Dependences Left-to-Right Depth-First Through the Tree CHAIN print: VOID; CHAIN specifies left-to-right depth-first dependence. RULE: Root ::= Expr COMPUTE CHAINSTART HEAD.print = "yes"; CHAINSTART in the root printf ("n") <- TAIL.print; context of the CHAIN END; (initialized with an irrelevant value) RULE: Expr ::= Number COMPUTE Expr.print = Computations are inserted printf ("\%d ", Number) <-Expr.print; between pre- and END; postconditions of the CHAIN RULE: Expr ::= Expr Opr Expr COMPUTE CHAIN order can be Expr[3].print = Expr[2].print; overridden. Opr.print = Expr[3].print; Expr[1].print = Opr.print; Omitted CHAIN computations END; are added automatically RULE: Opr ::= quotesingle +quotesingle COMPUTE Opr.print = printf ("+ ") <- Opr.print; Example: END; Output an expression in postfix form (cf. GSS-3.4) (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 304a Objectives: Learn to use the CHAIN construct In the lecture: * Explain the meaning, * show typical applications. Questions: Describe how a CHAIN construct can be substituted by adding further attributes and computations. -------------------------------------------------------------------------------- GSS-3.4b Pattern: Dependences Left-to-Right Depth-First Through the Tree Root CHAINSTART added CHAIN HEAD TAIL dependences Expr p(...) CHAIN pre- and postcondition overriding a CHAIN dependence Expr Opr Expr printf(...) Expr Expr Opr Expr printf(...) printf(...) Expr Expr printf(...) printf(...) (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 304b Objectives: Learn to use the CHAIN construct In the lecture: * Explain the meaning by a pair of attributes at every symbol the CHAIN passes through - one INH and one SYNT -------------------------------------------------------------------------------- GSS-3.5 Pattern: Combine Attribute Values of a Subtree Specification CONSTITUENTS Usage.Count WITH (int, ADD, IDENTICAL, ZERO) UsageCount Other UsageCount UsageCount CONSTITUENTS combines certain attributes of a subtree, here Usage.Count WITH (int, ADD, IDENTICAL, ZERO) Meaning: type binary unary constant function function, function for applied to optional every attribute subtrees (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 305 Objectives: Understand CONSTITUENTS In the lecture: * Explain combining values. * The binary function mus be associative. * The konstant function must be neutral w.r.t the binary function. 2-stelligen sein. Questions: How can you express the effect of that constituents by explicit computations? -------------------------------------------------------------------------------- GSS-3.6 Pattern: Use an Attribute of a Remote Ancestor Node SYMBOL Block: depth: int INH; Example: RULE: Root ::= Block COMPUTE Compute nesting depth of blocks Block.depth = 0; END; RULE: Block ::= '(' Sequence ')' END; RULE: Sequence LISTOF Definition / Statement END; INCLUDING Block.depth refers to ... the depth attribute of the next ancestor node (towards the root) that RULE: Statement ::= Block COMPUTE has type Block Block.depth = ADD (INCLUDING Block.depth, 1); END; TERM Ident: int; The INCLUDING attribute is automatically propagated through RULE: Definition ::= quotesingle definequotesingle Ident the contexts between its definition in COMPUTE an ancestor node and its use in an printf("\%s defined on depth \%d\n", INCLUDING construct. StringTable (Ident), INCLUDING Block.depth); END; (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 306 Objectives: Learn to use INCLUDING constructs In the lecture: * Explain the meaning, * show typical applications. Questions: Describe how an INCLUDING construct can be substituted by adding further attributes and computations. -------------------------------------------------------------------------------- GSS-3.6a Example for INCLUDING in a Tree Root depth =Block Sequence Statement Definition Statement INCLUDING Block.depth depth = INCLUDING Block.depth INCLUDING Block.depth depth = Block Block Sequence Sequence Definition Statement Definition INCLUDING Block.depth INCLUDING Block.depth (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 306a Objectives: Understand INCLUDING constructs In the lecture: * Explain the meaning, -------------------------------------------------------------------------------- GSS-3.7 Pattern: Combine Preconditions of Subtree Nodes SYMBOL Block: DefDone: VOID; Example: RULE: Root ::= Block END; Output all definitions before all uses RULE: Block ::= '(' Sequence ')' COMPUTE Block.DefDone = CONSTITUENTS Definition.DefDone; The attributes DefDone do not have END; values - they specify preconditions for some computations ... RULE: Definition ::= quotesingle definequotesingle Ident This CONSTITUENTS construct does COMPUTE not need a WITH clause, because it Definition.DefDone = does not propagate values printf("\%s defined in line \%d\n", StringTable (Ident), LINE); END; Typical combination of a RULE: Statement ::= quotesingle usequotesingle Ident CONSTITUENTS construct and an COMPUTE INCLUDING construct: printf("\%s used in line \%d\n", Specify the order side-effects are to StringTable (Ident), LINE) occur in. <- INCLUDING Block.DefDone; END; (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 307 Objectives: Learn to use a common pattern for remote access In the lecture: * Explain the pattern, * show typical applications -------------------------------------------------------------------------------- GSS-3.9 Computations Associated to Symbols Computations may be associated to symbols; then they are executed for every occurrence of the symbol in a production. SYMBOL Expr COMPUTE printf ("expression value \%d in line \%d\n", THIS.value, LINE); END; Symbol computations may contain INCLUDING, CONSTITUENTS, and CHAIN constructs: SYMBOL Block COMPUTE printf ("\%d uses occurred\n", CONSTITUENTS Usage.Count WITH (int, ADD, IDENTICAL, ZERO); END; SYNT.a resp. INH.a indicates that the computation belongs to the lower resp. upper context of the symbol: SYMBOL Block COMPUTE INH.depth = ADD (INCLUDING Block.depth); END; Computations in RULE contexts override computations for the same attribute in SYMBOL context, e.g. for begin of recursions, defaults, or exceptions: RULE: Root ::= Block COMPUTE Block.depth = 0; END; (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 309 Objectives: Understand SYMBOL computations In the lecture: Explain SYMBOL computations using the examples of the slide. * THIS, SYNT, INH in computations stand for the containing symbol. * In SYMBOL computations attributes of a RULE context can not be used. -------------------------------------------------------------------------------- GSS-3.10 Reuse of Computations CLASS SYMBOL IdOcc: Sym: int; Computations are associated to CLASS SYMBOL IdOcc COMPUTE CLASS symbols, which do not SYNT.Sym = TERM; occur in the abstract syntax. END; SYMBOL DefVarIdent INHERITS IdOcc END; SYMBOL DefTypeIdent INHERITS IdOcc END; INHERITS binds CLASS symbols SYMBOL UseVarIdent INHERITS IdOcc END; to tree symbols of the abstract SYMBOL UseTypeIdent INHERITS IdOcc END; syntax. CLASS SYMBOL CheckDefined COMPUTE IF (EQ (THIS.Key, NoKey), message ( ERROR, "identifier is not defined", 0, COORDREF); END; SYMBOL UseVarIdent INHERITS IdOcc, CheckDefined END; SYMBOL UseTypeIdent INHERITS IdOcc, CheckDefinedEND; (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 310 Objectives: learn to reuse symbol computations In the lecture: * Explain the notation and the examples. -------------------------------------------------------------------------------- GSS-3.10a Reuse of Pairs of SYMBOL Roles CLASS SYMBOL OccRoot COMPUTE CLASS symbols in cooperating CHAINSTART HEAD.Occurs = 0; roles, e.g. count occurrences of a SYNT.TotalOccs = TAIL.Occurs; language construct (OccElem) in a END; subtree (OccRoot) CLASS SYMBOL OccElem COMPUTE SYNT.OccNo = THIS.Occurs; Restriction: THIS.Occurs = ADD (SYNT.OccNo, 1); Every OccElem-node must be in an END; OccRoot-subtree. Reused in pairs: SYMBOL Block INHERITS OccRoot END; Block - Definition and SYMBOL Definition INHERITS OccElem END; Statement - Usage SYMBOL Statement INHERITS OccRoot END; must obey the restriction. SYMBOL Usage INHERITS OccElem END; Library modules are used in this way (see Ch. 6) (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 310a Objectives: Understand related symbol roles In the lecture: * Explain the restriction. * Refer to the library of specifications. -------------------------------------------------------------------------------- GSS-3.11 Design Rules for Computations in Trees 1.Decompose the task into subtasks, that are small enough to be solved each by only a few of the specification patterns explained below.d Develop a .lido fragment for each subtask and explain it in the surrounding .fw text. 2.Elaborate the central aspect of the subtask and map it onto one of the following cases: A. The aspect is described in a natural way by properties of some related program constructs, e.g. types of expressions, nesting depth of blocks, translation of the statements of a block. B. The aspect is described in a natural way by properties of some program entities, e.g. relative addresses of variabes, use of variables before their definition. Develop the computations as described for A or B. 3.Step 2 may exhibit that further aspects of the subtask need to be solved (attributes may be used, for which the computations are not yet designed). Repeat step 2 for these aspects. (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 311 Objectives: Guidelines for systematic design In the lecture: Explained using examples. (Case B is provided in Ch. 6) -------------------------------------------------------------------------------- GSS-3.12 A: Compute Properties of Program Constructs Determine the type of values, which describe the property. Introduce attributes of that type for all symbols, which represent the program constructs. Check which of the following cases fits best for the computation of that property: A1: Each lower context determines the property in a different way: Then develop RULE computations for all lower contexts. A2: As A1; but upper context. A3: The property can be determined independently of RULE contexts, by using only attributes of the symbol or attributes that are accessed via INCLUDING, CONSTI- TUENT(S), CHAIN: Then develop a lower (SYNT) SYMBOL computation. A4: As A3; but there are a few exceptions, where either lower of upper (not both) RULE contexts determine the property in a different way: Then develop a upper (INH) or a lower (SYNT) SYMBOL computation and override it in the deviating RULE contexts. A5: As A4; but for recursive symbols: The begin of the recursion is considered to be the exception of A4, e.g. nesting depth of Blocks. If none of the cases fits, the design of the property is to be reconsiderd; it may be too complex, and may need further refinement. (c) 2013 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Lecture Generating Software from Specifications WS 2013/14 / Slide 312 Objectives: Rule for designing computations. In the lecture: The cases are explained using examples --------------------------------------------------------------------------------