Syntax Directed Translation

SYNTAX DIRECTED TRANSLATION (SDT)

The CFG with semantic actions is called as SDT or the translation rules placed in RHS side of production.
Example:  
                    S---->AB               {print(*)}
                    A----->a                 {print(1)}
                    B------>S                {print(2)}

SDT can be constructed
  (i) to store the information in symbol table
  (ii) to verify the variable declaration
  (iii) to construct DAG
  (iv) to perform type checking, type conversion , type evaluation.
  (v) to evaluate algebraic expression etc.
A parse tree which shows attributes at each and every node is called as ANNOTATED/DECORATED parse tree.

Type of Attributes

1. Synthesized attribute: Attribute whose value is evaluated in terms of attribute value of it's children.
2. Inherited attribute: Attribute whose value is evaluated in terms of attribute values of siblings or parent.

Syntax Directed Definition (SDD)

1. S-attributed SDD:
     (i) Uses "only synthesized attributes"
     (ii) Semantic actions can be placed at right end of the rule
     (iii) Follows bottom up approach
           A---->BC { A.i = f( B.i  or C.i )
2. L-attributed SDD:
       (i) SDT in which attributes are synthesized or restricted to inherit either from 'parent' or 'left sibling'.
       (ii) Follows DFS and top down approach

Example: 
                          A---->BCD     {  C.i = f( A.i  or  B.i )} or
                                                  { D.i = f( A.i or B.i  or C.i)} or
                                                  { B.i = f(A.i)}

Every S-attributed SDT is L-attributed SDT.
Every L-attributed SDT need not be S-attributed SDT.
SDT follows depth first search notation.