Table of contents

Introduction

Syntax Directed Definition

2.1.

Inherited and Synthesised Attribute

2.2.

Evaluation of an SDD at Node of the Parse Tree

2.3.

How to Construct Annotated Parse Tree?

Features of Syntax Directed Definition

Types of Syntax Directed Definitions

4.1.

S-attributed Translation

4.2.

L-attributed Translation

Types of attributes

5.1.

Inherited attributes

5.2.

Synthesized attributes

Frequently Asked Questions

6.1.

What is meant by syntax directed definition?

6.2.

What are the two types of syntax directed definition?

6.3.

What is meant by syntax directed definition in compiler design?

Conclusion

Last Updated: Mar 27, 2024

Medium

Syntax Directed Definition (SDD)

Author Divyansh Vinod

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

By connecting semantic rules to grammar productions, syntax-directed definition determines the values of attributes. It resembles an abstract specification in certain ways.

SDT (syntax-directed translation) adds 'semantics rules' or actions to CFG products. As a result, we may refer to the grammar that has been augmented as attributed grammar.

The 'syntax analysis phase' and the 'semantic analysis phase' are intertwined in syntax-directed translation. To begin the syntax-directed translation, you must first create a 'parse tree.' Following that, apply the production's semantic rules. And then assess the property at the parse tree's nodes.

An annotated parse tree is a parse tree that has the evaluated attribute value. 'L-attributed translations' and 'S-attributed translations' are the two types of syntax-directed translation.

Syntax Directed Definition

A CFG with attributes and rules is called a syntax-directed definition (SDD). The properties are linked to the grammar symbols in an extended CFG (i.e. nodes of the parse tree). The rules are associated with grammar production.

A grammar symbol's attribute can now be integers, types, table references, or a string. Let us go through two kinds of qualities in more detail:

Inherited and Synthesised Attribute

For a non-terminal symbol (node) N, we can declare the value of a synthesized attribute:

The attribute value of children.
The total attribute values of N.

For a non-terminal symbol (node) N, we can declare the value of an inherited attribute:

N's parent's attribute values.
N's Siblings' attribute values.
Total attribute values of N.

Evaluation of an SDD at Node of the Parse Tree

To determine the value of attributes at nodes in a parse tree, do the following:

We must first construct a parse tree.
Then we must use SDD rules to assess the values of all the nodes in the parse tree's attributes.
An annotated parse tree is formed via this improvised parse tree.

How to Construct Annotated Parse Tree?

As the name implies, the annotated parse tree displays the value(s) of all node attribute(s). So, before we analyze a node's attribute value, we must first evaluate all the elements that determine its value.

To evaluate a node's synthesized attribute, we must parse the tree from the bottom up. Its value is determined by the value of the child attributes of the concerned node and the node itself.
To determine a node's inherited attribute, we must parse the tree from the top down. Its value is determined by its parent, siblings, and the node itself.
Synthesized and inherited attributes may coexist at some nodes in a parse tree. In this scenario, we're not sure if there is even a single order in which the nodes' characteristics may be evaluated.

A dependency tree can even determine the order in which the characteristics are examined

Features of Syntax Directed Definition

Features of Syntax Directed Definition are the following:

An abstract statement of this kind is called Syntax Directed Definition (SDD).
It is a context-free grammar with attributes and rules that are jointly linked to productions and grammar symbols, respectively.
The symbols used in grammar are connected to attributes. The production of grammar is connected to rules.
Definitions that are S-attributed and L-attributed are the two categories of Syntax Directed Definitions.

Types of Syntax Directed Definitions

S-attributed translation and L-attributed translation are two types of syntax-directed translation.

S-attributed Translation

If the node's attributes are synthesised attributes, the SDD is S-attributed. For evaluation of an S-attributed SDD, the nodes of the parse tree can be traversed in any bottom-up sequence.

The characteristics in S-attributed SDD are evaluated via postorder traversal. When the traverser crosses node N for the last time in postorder traversal, node N is evaluated.

L-attributed Translation

If the attributes of nodes are synthesized or inherited, an SDD is L-attributed. The parse tree can now be traversed exclusively from left to right. This is because L stands for left-to-right traversal in 'L-attributed translation.'

Start analyzing the L-attributed SDD in the following order:

The inherited attribute's value.
The value of synthesizing attributes.

Types of attributes

For non-terminals, we have the following two characteristics. Attributes that are synthetic and inherited.

Inherited attributes

The semantic rule connected to the production at the parent of the node defines inherited attributes. Values for attributes are limited to a node's parent, siblings, and self. The production's body must contain the concerned non-terminal. A semantic rule connected to the production at the parent of N defines an inherited attribute for a nonterminal B at a parse-tree node N. An example of inherited attributes is following:

S --> TUV { U.in = S.in, U.type = T.type }

Synthesized attributes

The semantic rule related to the production at the node defines the synthesised attributes. Values for attributes are only applicable to a node's children and to that node alone. The non-terminal in question needs to be in charge of production. The lexical values (designated by lexval) produced by the lexical analyzer are the synthesised properties of terminals. A semantic rule connected to the production at the parse-tree node N defines a synthesised attribute for a nonterminal A there. An example of synthesized attributes are following:

S --> S₁ + T { S.val = S₁.val + T.val}

The values in this were derived by S.val from S1.val and T.val.

Frequently Asked Questions

What is meant by syntax directed definition?

Syntax-directed definition establishes the values of attributes by linking semantic principles to grammar outputs. A syntax-directed definition is a CFG with attributes and rules. In an extended CFG, the properties are connected to the grammar symbols (i.e. nodes of the parse tree).

What are the two types of syntax directed definition?

Syntax-directed definitions come in two different varieties. The two types of Syntax Directed Definitions are S-attributed and L-attributed Definitions. L-attributed translation translates while the parsing is being done. Additionally, bottom-up parsing is combined with S-attributed translation.

What is meant by syntax directed definition in compiler design?

It is a context-free grammar with rules and attributes that are linked to products and symbols, respectively. By connecting semantic rules to the grammar productions, syntax-directed definition determines the values of attributes. It is an abstract specification.

Conclusion

In this article, we have extensively discussed syntax-directed translation, various syntax-directed translation schemes, and the applications of syntax-directed translation.

We hope that this blog has helped you enhance your knowledge regarding Syntax Directed Translation. If you want to learn more, check out our articles on Code Studio.