Evaluation Order for SDD's - Naukri Code 360

Q: What is an S-Attributed SDD?

The SDD whose every attribute is synthesized is known as an S-attributed SDD.

Q: What is the principle behind L-Attributed SDD?

The principle behind L-Attributed SDD is that dependency-graph edges can go from left to right, but not from right to left, between the characteristics associated with a production body.

Introduction

"Dependency graphs" are a valuable tool for deciding the order in which attribute instances in a parse tree should be evaluated. While an annotated parse tree provides the values of attributes, a dependency graph teaches us how to compute those values.

We define two basic classes of SDDs in this blog, in addition to dependency graphs: "S-attributed" and the more generic "L-attributed" SDDs. Most translations seen in practice may be written to correspond to the requirements of at least one of these classes.

Also read About, Specifications of Tokens in Compiler Design ,Lexical Analysis in Compiler Design

Dependency Graphs

A dependency graph shows how information flows between attribute instances in a parse tree; an edge from one attribute instance to another indicates that the value of the first is required to compute the value of the second. The semantic rules imply constraints, which are expressed by edges.

Ordering the Evaluation of Attributes

The dependency graph describes the numerous ways in which the properties at the various nodes of a parse tree can be evaluated. If there happens to be an edge from node M to node N in the dependency graph, the attribute corresponding to M must be assessed before the attribute corresponding to N. As a result, the only valid evaluation orders are those with nodes N₁, N₂, and N₃,...N_kis such that if there is a dependency graph edge from N_i to N_j, then i<j. A topological sort of graph is an ordering that embeds a directed graph into a linear order.

There are no topological sorts if the graph contains a cycle; that is, there is no way to assess the SDD on this parse tree. However, even if there are no cycles, there is always at least one topological sort. To illustrate why we can quickly discover a node with no edge entering because there are no cycles. If there was no such node, we might go from predecessor to predecessor until we reached a node we'd seen before, resulting in a cycle. Remove the node from the dependency network, make it the first in the topological order, and continue with the other nodes.

Also See, Symbol Table Operations

S-Attributed Definitions

It is pretty challenging to determine whether any parse trees exist with cycles in their dependency networks given an SDD. Since they do not allow dependency graphs with cycles, translations can be implemented using classes of SDDs that guarantee an evaluation order. Furthermore, the two types discussed in this section can be used in conjunction with top-down or bottom-up parsing.

The following is the definition of the first class:

If every attribute of an SDD is synthesized, it is S-attributed.

We can assess an SDD's attributes in any bottom-up order of the parse tree nodes when it is S-attributed. When doing a postorder traversal of the parse tree and evaluating the attributes at node N when the traversal leaves N the last time, it is generally straightforward to evaluate the attributes.

Since a bottom-up parse corresponds to a postorder traversal, S-attributed definitions can be implemented during bottom-up parsing. In particular, the order in which an LR parser reduces a production body to its head is known as postorder.

L-Attributed Definitions

L-attributed definitions are the second type of SDD. The principle behind this class is that dependency-graph edges can go from left to right, but not from right to left, between the characteristics associated with a production body (hence "L-attributed"). To be more specific, each attribute must be one of the following:

Synthesized or inherited, but with the following restrictions: Assume that there is a production A→X ₁, X ₂,..., X _n and that there is an inherited attribute X _i. A computed by a rule connected with this production.
Aspects of the head A that are inherited.
Attributes related to the occurrences of symbols X ₁, X ₂,..., X_i-1 positioned to the left of X _I are either inherited or synthesized.
This occurrence of X_i is related to inherited or synthesized characteristics, but only so that there will be no cycles in a dependency graph generated by the attributes of this X _i.

Semantic Rules with Controlled Side Effects

In practice, side effects occur: a desk calculator may print a result; a code generator may enter the identifier type into a symbol table. We achieve a balance between attribute grammars and translation systems with SDDs. Attribute grammars have no negative consequences and allow for any evaluation order that is consistent with the dependency graph. Left-to-right evaluation is imposed by translation systems, which enables semantic actions to comprise any program fragment.

The following methods will be used to control side effects in SDDs:

Allow for unintentional side effects that do not affect attribute evaluation. Allow side effects when attribute evaluation based on any topological sort of the dependency network results in a "correct" translation, where "correct" is determined by the application.
Limit the evaluation orders that can be used so that each order that can be utilized produces the exact translation. The constraints might be viewed as hidden edges in the dependency graph.

Frequently Asked Questions

What does a dependency graph represent?

A dependency graph shows how information flows between attribute instances in a parse tree.

What is an S-Attributed SDD?

The SDD whose every attribute is synthesized is known as an S-attributed SDD.

What is the principle behind L-Attributed SDD?

The principle behind L-Attributed SDD is that dependency-graph edges can go from left to right, but not from right to left, between the characteristics associated with a production body.

Conclusion

In this article, we have extensively discussed evaluation order for SDDs, dependency graphs, s-attributed definitions and l-attributed definitions.

We hope that this blog has helped you enhance your knowledge regarding Evaluation Order for SDDs. If you want to learn more, check out our articles on Code Studio.