• Skip to main content
  • Skip to primary sidebar
  • Skip to secondary sidebar
  • Skip to footer

Computer Notes

Library
    • Computer Fundamental
    • Computer Memory
    • DBMS Tutorial
    • Operating System
    • Computer Networking
    • C Programming
    • C++ Programming
    • Java Programming
    • C# Programming
    • SQL Tutorial
    • Management Tutorial
    • Computer Graphics
    • Compiler Design
    • Style Sheet
    • JavaScript Tutorial
    • Html Tutorial
    • Wordpress Tutorial
    • Python Tutorial
    • PHP Tutorial
    • JSP Tutorial
    • AngularJS Tutorial
    • Data Structures
    • E Commerce Tutorial
    • Visual Basic
    • Structs2 Tutorial
    • Digital Electronics
    • Internet Terms
    • Servlet Tutorial
    • Software Engineering
    • Interviews Questions
    • Basic Terms
    • Troubleshooting
Menu

Header Right

Home » Compiler » Syntax Directed Definition (SDD) and Types of Syntax Directed Definitions
Next →
← Prev

Syntax Directed Definition (SDD) and Types of Syntax Directed Definitions

By Dinesh Thakur

Syntax directed definition specifies the values of attributes by associating semantic rules with the grammar productions.

It is a context free grammar with attributes and rules together which are associated with grammar symbols and productions respectively.

The process of syntax directed translation is two-fold:

• Construction of syntax tree and

• Computing values of attributes at each node by visiting the nodes of syntax tree.

Semantic actions

Semantic actions are fragments of code which are embedded within production bodies by syntax directed translation.

They are usually enclosed within curly braces ({ }).

It can occur anywhere in a production but usually at the end of production.

(eg.)

                                            E—> E1 + T {print ‘+’}

Types of translation

 

• L-attributed translation

o It performs translation during parsing itself.

o No need of explicit tree construction.

o L represents ‘left to right’.

 

• S-attributed translation

o It is performed in connection with bottom up parsing.

o ‘S’ represents synthesized.

We’ll be covering the following topics in this tutorial:

  • Types of attributes
  • Types of Syntax Directed Definitions

Types of attributes

• Inherited attributes

   o It is defined by the semantic rule associated with the production at the parent of node.

   o Attributes values are confined to the parent of node, its siblings and by itself.

   o The non-terminal concerned must be in the body of the production.

• Synthesized attributes

   o It is defined by the semantic rule associated with the production at the node.

   o Attributes values are confined to the children of node and by itself.

   o The non terminal concerned must be in the head of production.

   o Terminals have synthesized attributes which are the lexical values (denoted by lexval) generated by the lexical analyzer.

                      Syntax directed definition of simple desk calculator

 

Production

Semantic rules

L —> En

L.val = E.val

E —> E1+ T

E.val = E1.val+ T.val

E —> T

E.val = T.val

T—> T1*F

T.val = Ti.val x F.val

T —> F

T.val = F.val

F —> (E)

F.val = E.val

F —> digit

F.val = digit.lexval

                        

                             Syntax-directed definition-inherited attributes

 

Production

Semantic Rules

D —>TL

L.inh = T.type

T —> int

T.type =integer

T —> float

T.type = float

L —> L1, id

L1.inh = L.inh

addType (id.entry, Linh)

L —> id

addType (id.entry, L.inh)

 

 

 

 

 

 

 

 

 

 

 

• Symbol T is associated with a synthesized attribute type.

• Symbol L is associated with an inherited attribute inh,

Types of Syntax Directed Definitions

S-attributed Definitions

Syntax directed definition that involves only synthesized attributes is called S-attributed. Attribute values for the non-terminal at the head is computed from the attribute values of the symbols at the body of the production.

The attributes of a S-attributed SDD can be evaluated in bottom up order of nodes of the parse tree. i.e., by performing post order traversal of the parse tree and evaluating the attributes at a node when the traversal leaves that node for the last time.

 

Production

Semantic rules

L —> En

L.val = E.val

E —> E1+ T

E.val = E1.val+ T.val

E —> T

E.val = T.val

T—> T1*F

T.val = Ti.val x F.val

T —> F

T.val = F.val

F —> (E)

F.val = E.val

F —> digit

F.val = digit.lexval

L-attributed Definitions

The syntax directed definition in which the edges of dependency graph for the attributes in production body, can go from left to right and not from right to left is called L-attributed definitions. Attributes of L-attributed definitions may either be synthesized or inherited.

If the attributes are inherited, it must be computed from:

• Inherited attribute associated with the production head.

• Either by inherited or synthesized attribute associated with the production located to the left of the attribute which is being computed.

• Either by inherited or synthesized attribute associated with the attribute under consideration in such a way that no cycles can be formed by it in dependency graph.

Production

Semantic Rules

T —> FT’

T ‘.inh = F.val

T ‘ —> *FT1’

T’1.inh =T’.inh x F.val

In production 1, the inherited attribute T’ is computed from the value of F which is to its left. In production 2, the inherited attributed Tl’ is computed from T’. inh associated with its head and the value of F which appears to its left in the production. i.e., for computing inherited attribute it must either use from the above or from the left information of SDD.

You’ll also like:

  1. What is Parser (Syntax analysis)? Error Handling and Recovery in Syntax Analyzer
  2. What is protocol? and its types – Definition
  3. Software Design Documentation (SDD)
  4. What is Operating System and its types? Definition
  5. Error Handling and Error Recovery In Syntax Analyzer
Next →
← Prev
Like/Subscribe us for latest updates     

About Dinesh Thakur
Dinesh ThakurDinesh Thakur holds an B.C.A, MCDBA, MCSD certifications. Dinesh authors the hugely popular Computer Notes blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps.

Dinesh Thakur is a Freelance Writer who helps different clients from all over the globe. Dinesh has written over 500+ blogs, 30+ eBooks, and 10000+ Posts for all types of clients.


For any type of query or something that you think is missing, please feel free to Contact us.


Primary Sidebar

Compiler Design

Compiler Design

  • CD - Translators
  • CD - Compiler Phases
  • CD - Input Buffering
  • CD - Lexical Analysis
  • CD - Regular Expression
  • CD - LR Parsers
  • CD - Parse Tree
  • CD - Parsing Type
  • CD - Lex
  • CD - Syntax Directed Definition
  • CD - Compiler Construction tools
  • CD - Regular Expression
  • CD - Context Free Grammars
  • CD - Syntax Analysis
  • CD - Grouping of Phases
  • CD - Language Processing System
  • CD - Derivations
  • CD - Error Handling

Other Links

  • Compiler Design - PDF Version

Footer

Basic Course

  • Computer Fundamental
  • Computer Networking
  • Operating System
  • Database System
  • Computer Graphics
  • Management System
  • Software Engineering
  • Digital Electronics
  • Electronic Commerce
  • Compiler Design
  • Troubleshooting

Programming

  • Java Programming
  • Structured Query (SQL)
  • C Programming
  • C++ Programming
  • Visual Basic
  • Data Structures
  • Struts 2
  • Java Servlet
  • C# Programming
  • Basic Terms
  • Interviews

World Wide Web

  • Internet
  • Java Script
  • HTML Language
  • Cascading Style Sheet
  • Java Server Pages
  • Wordpress
  • PHP
  • Python Tutorial
  • AngularJS
  • Troubleshooting

 About Us |  Contact Us |  FAQ

Dinesh Thakur is a Technology Columinist and founder of Computer Notes.

Copyright © 2023. All Rights Reserved.