CI-67
4. Semantic analysis and transformation
Input: abstract program tree
Tasks: Compiler module:
name analysis environment module
properties of program entities definition module
type analysis, operator identification signature module
transformation tree generator
Output: target tree, intermediate code, target program in case of source-to-source
Standard implementations and generators for compiler modules
Operations of the compiler modules are called at nodes of the abstract program tree
Model: dependent computations in trees
Specification: attribute grammars
generated: tree walking algorithm that calls operations
in specified contexts and in an admissable order
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 67
Objectives:
Tasks and methods of semantic analysis
In the lecture:
Explanation of the
* tasks,
* compiler modules,
* principle of dependent computations in trees.
Suggested reading:
Kastens / Übersetzerbau, Section Introduction of Ch. 5 and 6
--------------------------------------------------------------------------------
CI-68
4.1 Attribute grammars
Attribute grammar (AG) specifies dependent computations in the abstract program tree
declarative: explicit dependencies only; a suitable order of execution is computed
Computations solve the tasks of semantic analysis and transformation
Generator produces a plan for tree walks
that execute calls of the computations,
such that the specified dependencies are obeyed,
computed values are propagated through the tree
Result: attribute evaluator; applicable for any tree specified by the AG
Example: attribute grammar tree with dependent attributes
RULE Decls ::= Decls Decl COMPUTE evaluated Decls
Decls[1].size = size 16
Add (Decls[2].size, Decl.size);
END; Decls 12 Decl 4
RULE Decls ::= Decl COMPUTE size size
Decls.size = Decl.size;
END; Decls Decl
size 4 size 8
RULE Decl ::= Type Name COMPUTE
Decl.size = ...; Decl
END; size 4
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 68
Objectives:
Get an informal idea of attribute grammars
In the lecture:
Explain computations in tree contexts using the example
Suggested reading:
Kastens / Übersetzerbau, Section 5, 5.1
Questions:
Why is it useful NOT to specify an evaluation order explicitly?
--------------------------------------------------------------------------------
CI-69
Basic concepts of attribute grammars
An AG specifies computations in tree:
expressed by computations associated to productions of the abstract syntax
RULE p: Y ::= u COMPUTE f(...); g(...); END;
computations f(...) and g(...) are executed in every tree context of type p
An AG specifies dependencies between computations:
expressed by attributes associated to grammar symbols
RULE p: X ::= u Y v COMPUTE X.b = f(Y.a);
Y.a = g(...);
END; post-condition pre-condition
f(Y.a) uses the result of g(...); hence Y.a=g(...) will be executed before f(Y.a)
dependent computations in adjacent contexts:
RULE r: X ::= v Y w COMPUTE X.b = f(Y.a); END;
RULE p: Y ::= u COMPUTE Y.a = g(...); END;
attributes may specify dependencies without propagating any value:
X.GotType = ResetTypeOf(...);
Y.Type = GetTypeOf(...) <- X.GotType;
ResetTypeOf will be called before GetTypeOf
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 69
Objectives:
Get a basic understanding of AGs
In the lecture:
Explain
* the AG notation,
* dependent computations,
* adjacent contexts in trees
Suggested reading:
Kastens / Übersetzerbau, Section 5, 5.1
Assignments:
* Read and modify examples in Lido notation to introduce AGs
--------------------------------------------------------------------------------
CI-69a
Definition of attribute grammars
An attribute grammar is defined by
a context-free grammar G, (abstract syntax, tree grammar)
for each symbol X of G a set of attributes A(X), written X.a if a element A(X)
for each production (rule) p of G a set of computations of one of the forms
X.a = f ( ... Y.b ... ) or g (... Y.b ... ) where X and Y occur in p
Consistency and completeness of an AG:
Each A(X) is partitioned into two disjoint subsets: AI(X) and AS(X)
AI(X): inherited attributes are computed in rules p where X is on the right-hand side of p
AS(X): synthesized attributes are computed in rules p where X is on the left-hand side of p
Each rule p: X ::= ... Y ... has exactly one computation
for all attributes of AS(X), and
for all attributes of AI(Y), for all symbol occurrences on the right-hand side of p
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 69a
Objectives:
Formal view on AGs
In the lecture:
The completeness and consistency rules are explained using the example of CI-69b
--------------------------------------------------------------------------------
CI-69b
AG Example: Compute expression values
The AG specifies: The value of an expression is computed and printed:
ATTR value: int; SYMBOL Opr: left, right: int;
RULE: Root ::= Expr COMPUTE RULE: Opr ::= quotesingle +quotesingle COMPUTE
printf ("value is \%d\n", Opr.value =
Expr.value); ADD (Opr.left, Opr.right);
END; END;
TERM Number: int; RULE: Opr ::= quotesingle *quotesingle COMPUTE
Opr.value =
RULE: Expr ::= Number COMPUTE MUL (Opr.left, Opr.right);
Expr.value = Number; END;
END;
RULE: Expr ::= Expr Opr Expr
COMPUTE
Expr[1].value = Opr.value;
Opr.left = Expr[2].value;
Opr.right = Expr[3].value;
END;
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 69b
Objectives:
Exercise formal definition
In the lecture:
* Show synthesized, inherited attributes.
* Check consistency and completeness.
Questions:
* Add a computation such that a pair of sets AI(X), AS(X) is no longer disjoint.
* Add a computation such that the AG is inconsistent.
* Which computations can be omitted whithout making the AG incomplete?
* What would the effect be if the order of the three computations on the bottom left of the slide was altered?
--------------------------------------------------------------------------------
CI-70
AG Binary numbers
Attributes: L.v, B.v value
L.lg number of digits in the sequence L
L.s, B.s scaling of B or the least significant digit of L
RULE p1: D ::= L quotesingle .quotesingle L COMPUTE
D.v = ADD (L[1].v, L[2].v);
L[1].s = 0;
L[2].s = NEG (L[2].lg);
END;
RULE p2: L ::= L B COMPUTE
L[1].v = ADD (L[2].v, B.v);
B.s = L[1].s;
L[2].s = ADD (L[1].s, 1);
L[1].lg = ADD (L[2].lg, 1);
END;
RULE p3: L ::= B COMPUTE
L.v = B.v;
B.s = L.s;
L.lg = 1;
END;
RULE p4: B ::= quotesingle 0quotesingle COMPUTE
B.v = 0;
END;
RULE p5: B ::= quotesingle 1quotesingle COMPUTE
B.v = Power2 (B.s);
END;
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 70
Objectives:
A complete example for an AG
In the lecture:
* Explain the task.
* Explain the role of the attributes.
* Explain the computations in tree contexts.
* Show a tree with attributes and dependencies (CI-71)
--------------------------------------------------------------------------------
CI-71
An attributed tree for AG Binary numbers
D
p1 5.25
0
L 3 5 -2
L 2 .25 dependency
p2
p2
1
L 0
B -1 -2
2 4 1 L B
1 0 .25
p2 p5 1 p3 p5 1 attributes:
2 D
1 -1
L B v
1 4 B 0 0
s
p3 0 p4 0 L
p4 lg v
2
B 4 s
B
p5 v
1
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 71
Objectives:
An attributed tree
In the lecture:
* Show a tree with attributes.
* Show tree contexts specified by grammar rules.
* Relate the dependencies to computations.
* Evaluate the attributes.
Questions:
* Some attributes do not have an incoming arc. Why?
* Show that the attribues of each L node can be evaluated in the order lg, s, v.
--------------------------------------------------------------------------------
CI-72
Dependency analysis for AGs
2 disjoint sets of attributes for each symbol X:
AI (X) : inherited (dt. erworben), computed in upper contexts of X
AS (X): synthesized (dt. abgeleitet), computed in lower contexts of X.
upper context of X y
p: Y ::= u X v dependencies
between
attributes
Objective: Partition of
AI (X,1) AI (X,2) attribute sets, such that
u AI (X, i) is computed
AS (X,1) AS (X,2) v
lower context of X context switch before the i-th visit of X
q : X ::= w on tree walk AS (X, i) is computed
during the i-th visit of X
w
Necessary precondition for the existence of such a partition:
No node in any tree has direct or indirect dependencies that contradict the evaluation order of
the sequence of sets: AI (X, 1), AS (X, 1), ..., AI (X, k), AS (X, k)
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 72
Objectives:
Understand the concept of attribute partitions
In the lecture:
Explain the concepts
* sets of synthesized and inherited attributes,
* upper and lower context,
* context switch,
* attribute partitions: sequence of disjoint sets which alternate between synthesized and inherited
Suggested reading:
Kastens / Übersetzerbau, Section 5.2
Assignments:
Construct AGs that are as simple as possible and each exhibits one of the following properties:
* There are some tree that have a dependency cycle, other trees don't.
* The cycles extend over more than one context.
* There is an X that has a partition with k=2 but not with k=1.
* There is no partition, although no tree exists that has a cycle. (caution: difficult puzzle!)
(Exercise 22)
--------------------------------------------------------------------------------
CI-73
Dependency graphs for AG Binary numbers
D v
s
p1 L lg v B s
v
p3 p4
s s
L L s
lg v lg v B v
s
L
p2 lg v
B s
v
s
L p5
B s
lg v v
indirect
dependency
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 73
Objectives:
Represent dependencies
In the lecture:
* graph representation of dependencies that are specified by computations,
* compose the graphs to yield a tree with dependencies,
* explain indirect dependencies
* Use the graphs as an example for partitions (CI-72)
* Use the graphs as an example for LAG(k) algorithm (CI-77)
--------------------------------------------------------------------------------
CI-74
Construction of attribute evaluators
For a given attribute grammar an attribute evaluator is constructed:
* It is applicable to any tree that obeys the abstract syntax specified in the rules of the AG.
* It performs a tree walk and
executes computations when visiting a context for which they are specified.
* The execution order obeys the attribute dependencies.
Pass-oriented strategies for the tree walk: AG class
k times depth-first left-to-right LAG (k)
k times depth-first alternatingly left-to-right / right-to left AAG (k)
once bottom-up SAG
The attribute dependencies of the AG are checked
whether the desired pass-oriented strategy is applicable; see LAG(k) algorithm.
non-pass-oriented strategies:
visit-sequences: OAG
an individual plan for each rule of the abstract syntax
Generator fits the plans to the dependencies.
(c) 2002 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 74
Objectives:
Tree walk strategiees
In the lecture:
* Show the relation between tree walk strategies and attribute dependencies.
Suggested reading:
Kastens / Übersetzerbau, Section 5, 5.1
Questions:
A grammar class is more powerful if it covers AGs with more complex dependencies.
* Arrange the AG classes in a hierarchy according to that property.
--------------------------------------------------------------------------------
CI-75
Visit-sequences
A visit-sequence (dt. Besuchssequenz) vsp for each production of the tree grammar:
p: Xo ::= X1 ... Xi ... Xn
A visit-sequence is a sequence of operations:
arrowdown i, j j-th visit of the i-th subtree
arrowup j j-th return to the ancestor node
evalc execution of a computation c associated to p
Example in the tree: visit-sequences attribute partitions
A guaranty
vsp: ... arrowdown C,1 ...arrowdown B,1 ...arrowdown C,2 ...arrowup 1 correct interleaving:
p: A::= BC AI (X,1) AI (X,2)
B C
AS (X,1) AS (X,2)
D E vsq: ... arrowdown D,1 ... arrowup 1 ... arrowdown E,1 ... arrowup 2
q: C::= DE
Implementation:
one procedure for each section of a visit-sequence upto arrowup
a call with a switch over applicable productions for arrowdown
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 75
Objectives:
Understand the concept of visit-sequences
In the lecture:
Explain
* context switch,
* interleaving of visit-sequences for adjacent contexts,
* partitions are "interfaces" for context switches,
* implementation using procedures and calls
Suggested reading:
Kastens / Übersetzerbau, Section 5.2.2
Assignments:
* Construct a set of visit-sequences for a small tree grammar, such that the tree walk solves a certain task.
* Find the description of the design pattern "Visitor" and relate it to visit-sequences.
Questions:
* Describe visit-sequences which let trees being traversed twice depth-first left-to-right.
--------------------------------------------------------------------------------
CI-76
Visit-sequences for the AG Binary numbers
vsp1: D ::= L quotesingle .quotesingle L
arrowdown L[1],1; L[1].s=0; arrowdown L[1],2; arrowdown L[2],1; L[2].s=NEG(L[2].lg);
arrowdown L[2],2; D.v=ADD(L[1].v, L[2].v); arrowup 1
vsp2: L ::= L B
arrowdown L[2],1; L[1].lg=ADD(L[2].lg,1); arrowup 1
L[2].s=ADD(L[1].s,1); arrowdown L[2],2; B.s=L[1].s; arrowdown B,1; L[1].v=ADD(L[2].v, B.v); arrowup 2
vsp3: L ::= B
L.lg=1; arrowup 1; B.s=L.s; arrowdown B,1; L.v=B.v; arrowup 2
vsp4: B ::= quotesingle 0quotesingle
B.v=0; arrowup 1
vsp5: B ::= quotesingle 1quotesingle
B.v=Power2(B.s); arrowup 1
Implementation:
Procedure vs for each section of a vsp to a arrowup i
a call with a switch over alternative rules for arrowdown X,i
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 76
Objectives:
Example for visit-sequences (CI-75)
In the lecture:
* Show tree walk
Questions:
* Check that adjacent visit-sequences interleave correctly.
* Check that all dependencies between computations are obeyed.
* Write procedures that implement these visit-sequences.
--------------------------------------------------------------------------------
CI-76a
Tree walk for AG Binary numbers
D
p1 5.25
0
L 3 5 -2
L 2 .25
p2 tree walk
p2
1
L 0
B -1 -2
2 4 1 L B
1 0 .25
p2 p5 1 p3 p5 1 attributes:
2 D
1 -1
L B v
1 4 B 0 0
s
p3 0 p4 0 L
p4 lg v
2
B 4 s
B
p5 v
1
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 76a
Objectives:
See a concrete tree walk
In the lecture:
Show that the visit-sequences of CI-76 produce this tree walk for the tree of CI-71.
--------------------------------------------------------------------------------
CI-77
LAG (k) condition and algorithm
An AG is a LAG(k), if: For each symbol X there is an attribute partition A (X,1), ..., A (X, k),
such that the attributes in A (X, i) can be computed in the i-th depth-first left-to-right pass.
Necessary and sufficient condition over dependency graphs - expressed graphically:
A dependency A dependency
from right to left b a a b at one symbol
X Y X on the right-hand
element side
A(X,j) A(Y,i) A(X,i) A(X,j)
element j > i i < j
Algorithm: computes A (1), ..., A (k), if the AG is LAG(k), for i = 1, 2, ...
A (i) := all attributes that are not yet assigned
remove attributes from A(i) as long as the following rules are applicable:
* remove X.b, if there is a context where it depends on an attribute of A (i) according to the
pattern given above,
element * remove Z.c, if it depends on a removed attribute
Finally: all attributes are assigned to a passes i = 1, ..., k the AG is LAG(k)
all attributes are removed from A(i) the AG is not LAG(k) for any k
element
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 77
Objectives:
Understand the LAG condition
In the lecture:
* Explain the LAG(k) condition,
* motivate it by depth-first left-to-right tree walks,
* explain the algorithm using the example of CI-73.
Suggested reading:
Kastens / Übersetzerbau, Section 5.2.3
Assignments:
* Check LAG(k) condition for AGs (Exercise 20)
Questions:
* At the end of each iteration of the i-loop one of three conditions hold. Formulate them.
--------------------------------------------------------------------------------
CI-78
Generators for attribute grammars
LIGA University of Paderborn OAG
FNC-2 INRIA ANCAG (Oberklasse von OAG)
Synthesizer Generator Cornell University OAG, inkrementell
CoCo Universität Linz LAG(1)
Properties of the generator LIGA
* integrated in the Eli system, cooperates with other Eli tools
* high level specification language Lido
* modular and reusable AG components
* object-oriented constructs usable for abstraction of computational patterns
* computations are calls of functions implemented outside the AG
* side-effect computations can be controlled by dependencies
* notations for remote attribute access
* visit-sequence controlled attribute evaluators, implemented in C
* attribute storage optimization
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 78
Objectives:
See what generators can do
In the lecture:
* Explain the generators
* Explain properties of LIGA
Suggested reading:
Kastens / Übersetzerbau, Section 5.4
--------------------------------------------------------------------------------
CI-78a
State attributes without values
RULE: Root ::= Expr COMPUTE
Expr.print = "yes"; The attributes print
printf ("\n") <- Expr.printed; and printed do not
END; have a value
RULE: Expr ::= Number COMPUTE They just describe pre-
Expr.printed = and post-conditions of
printf ("\%d ", Number) <- Expr.print; computations:
END; Expr.print:
RULE: Opr ::= quotesingle +quotesingle COMPUTE postfix output has
Opr.printed = printf ("+ ") <- Opr.print; been done up to
END; not including this
RULE: Opr ::= quotesingle *quotesingle COMPUTE node
Opr.printed = printf ("* ") <- Opr.print; Expr.printed:
END; postfix output has
RULE: Expr ::= Expr Opr Expr COMPUTE been done up to
Expr[2].print = Expr[1].print; including this node
Expr[3].print = Expr[2].printed;
Opr.print = Expr[3].printed;
Expr[1].printed = Opr.printed;
END;
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 78a
Objectives:
Understand state attributes
In the lecture:
Explain
* attributes without values,
* representing only dependencies between computations.
Questions:
How would the output look like if we had omitted the state attributes and their dependencies?
--------------------------------------------------------------------------------
CI-78b
Dependency pattern CHAIN
CHAIN print: VOID; A CHAIN specifies a
left-to-right depth-first
RULE: Root ::= Expr COMPUTE dependency through a
CHAINSTART HEAD.print = "yes"; subtree.
printf ("\n ") <- TAIL.print;
END; Trivial computations of
the form X.a = Y.b in the
RULE: Expr ::= Number COMPUTE CHAIN order can be
Expr.print = omitted. They are added
printf ("\%d ", Number) <- Expr.print; as needed.
END;
RULE: Opr ::= quotesingle +quotesingle COMPUTE
Opr.post = printf ("+") <- Opr.pre;
END;
RULE: Expr ::= Expr Opr Expr COMPUTE
Opr.pre = Expr[3].print;
Expr[1].print = Opr.post;
END;
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 78b
Objectives:
See LIDO construct CHAIN
In the lecture:
* Explain the CHAIN pattern.
* Compare the example with CI-78a
--------------------------------------------------------------------------------
CI-78c
Dependency pattern INCLUDING
ATTR depth: int; An attribute at the root of
a subtree is used from
RULE: Root ::= Block COMPUTE within the subtree.
Block.depth = 0;
END; Propagation through the
contexts in between is
RULE: Statement ::= Block COMPUTE omitted.
Block.depth =
ADD (INCLUDING Block.depth, 1);
END;
TERM Ident: int;
RULE: Definition ::= `definequotesingle Ident COMPUTE
printf ("\%s defined on depth \%d\n ",
StringTable (Ident),
INCLUDING Block.depth);
END;
INCLUDING Block.depth
accesses the depth attribut of the next upper node of
type Block.
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 78c
Objectives:
See LIDO construct INCLUDING
In the lecture:
Explain the use of the INCLUDING construct.
--------------------------------------------------------------------------------
CI-78d
Dependency pattern CONSTITUENTS
RULE: Block ::= quotesingle {quotesingle Sequence quotesingle }quotesingle COMPUTE A computation accesses
Block.DefDone = attributes from the
subtree below its context.
CONSTITUENTS Definition.DefDone;
END; Propagation through the
RULE: Definition ::= quotesingle Definequotesingle Ident COMPUTE contexts in between is
Definition.DefDone = omitted.
printf ("\%s defined in line \%d\n",
StringTable(Ident), LINE);
END; The shown combination
RULE: Usage ::= quotesingle usequotesingle Ident COMPUTE with INCLUDING is a
printf ("\%s used in line \%d\n ", common dependency
pattern.
StringTable(Ident), LINE),
<- INCLUDING BLOCK.DefDone;
END;
CONSTITUENTS Definition.DefDone accesses the
DefDone attributes of all Definition nodes in the
subtree below this context
(c) 2001 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Lecture Compiler I WS 2001/2002 / Slide 78d
Objectives:
See LIDO construct CONSTITUENTS
In the lecture:
Explain the use of the CONSTITUENTS construct.
--------------------------------------------------------------------------------