Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we learn about evaluation orders for syntax-directed definitions. *Dependency graphs* are used to determine an evaluation order for instances of attributes in a parse tree.

### Table of contents.

- Introduction.
- Dependency graphs.
- Ordering the evaluation of attributes.
- S-Attributed Definitions.
- L-Attributed Definitions.
- Semantic rules with controlled side effects.
- Summary.
- References.

## Prerequisites.

## Introduction.

We use *dependency graphs* to determine an evaluation order for an attribute instance when we are given a parse tree.

As we have learned in the prerequisite article, an annotated parse tree shows the values of attributes. The *dependency graph* assists us in computing those values.

In addition to dependency graphs, we also learn about two classes of SDDs namely, *S-Attributed* and *L-Attributed* SDDs.

## Dependency graphs.

We use *dependency graphs* to show the flow of information among attribute instances in a parse tree. An *instance* is an edge from one attribute to another. This means that the computation of the second value is dependent on the first value. These edges are also used to express constraints by semantic rules.

For each node *X* in the parse tree, the dependency graph has a node for each attribute that is associated with *X*.

If the semantic rule associated with production *p* defines the value of a synthesized attribute *A.b* in terms of the value of *X.c*, then the graph is said to have an edge from *X.c* to *A.b*. That is, at every node *N* labeled *A* where production *p* is applied, we create an edge to attribute *b* at *N*, from the attribute *c* at the child of *N* that corresponds to this instance of symbol *X* in the production body.

If a semantic rule that is associated with production *p* defines the value of the inherited attribute *B.c* in terms of the value of *X.a*, then there exists an edge from *X.a* to *B.c*. For each node *N* labeled *B* corresponding to *Bs* occurrence in the production body *p*, we create an edge to attribute *c* at *N* from the attribute *a* at node *M* corresponding to *Xs* occurrence. Note, *M* could be a parent or sibling of *N*.

## Ordering the evaluation of attributes.

The *graph* groups all possible orderings that we can use to evaluate the attributes at various nodes in the tree. If there exists an edge between node *A* and node *B*, the attribute corresponding to *A* is evaluated before *B*.

The allowed evaluation orderings are those of nodes *B1, B2, ..., Bk* such that if there is an edge between *Ai* and *Aj* then *I < j*. These orderings embedded in a directed graph are referred to as a *topological sort* ordering.

A *cycle* cannot exist in a *topological sort*, this is because we cannot evaluate an *SDD* on this parse tree. On the other hand, if no cycles exist then there will be at least one topological sort. This is because if there are no cycles, we can find a node without an edge entering it. If there were no such node, we could proceed from predecessor to predecessor until we came back to a node we had already visited and this would be a cycle. We make this node the first in the ordering, remove it from the graph and repeat on the remaining nodes.

## S-Attributed Definitions.

When we have an SDD(Syntax-directed definition), It is difficult to tell if cycles exist in the dependency graphs of the parse trees. Practically, we use classes of *SDDs* that guarantee an evaluation order since they don't permit cycles in dependency graphs to implement translations.

We conclude with the following statement; An SDD is *S-Attributed* if every attribute is synthesized.

## L-Attributed Definitions.

Between attributes that are associated with the body of a production, graph edges can go from *left* to *right* but not vice versa hence the name *L-attributed*.

Each attribute can be *synthesized* or *inherited*. In case the attribute is inherited its rules are limited. That is if there is a production *A -> X1, X2, ..., Xn* and an inherited attribute *Xi.a* computed by a rule that is associated with this production that only uses;

- Inherited attributes associated with head
*A*. - Either inherited or synthesized attributes associated with occurrences of
*X1, X2, ..., Xi-1*located to the left of*X*. - Inherited/synthesized attributes that are associated with
*X1*itself, only such that there are no cycles in the graph formed by the attributes of*Xi*.

For more information about *L-attributed and S-attributed* definitions and grammar, this article is helpful.

## Semantic rules with controlled side effects.

Even though translations have side effects, using *syntax-directed definitions* enables us to balance between *attribute grammars* and *translation schemes*.

*Attribute grammars* don't have side effects and allow evaluation orders that are consistent with the graph.

Translation schemes impose a *left-right-evaluation* and allow semantic actions to have program fragments.

We can control side effects in *syntax-directed definitions* by;

- Allowing accompanying side effects that do not constrain attribute evaluation. That is, permit side effects when attribute evaluation based on any topological sort of the graph produces a
*correct*translation where*correct*is dependent on the application. - Secondly, we constrain allowed evaluation orders so that the same translation can be produced for any allowed order. Constrains are thought of as implicit edges added to the graph.

## Summary.

If we have a parse tree, we can use a *dependency graph* to show to flow of information among attribute instances.

The difference between an annotated parse tree and a dependency graph is, while the former shows the values of its attributes, the latter assists us in computing those values.

## References.

*Compilers Principles, Techniques, & Tools - Alfred V. Aho Monica S. Lam Ravi Sethi Jeffrey D. Ullman*