Syntax Directed Translation Scheme (SDT)

What is SDT?
                     SDT stands for Syntax Directed Translation. SDT is combination of Grammar with Semantic Rules (Translation Rules).

e.g. 
S->AB {S.val=A.val+B.val}
A->a {A.val=a.lval}
B->b {B.val=b.lval}
                     This is Syntax Directed Translation (SDT). Here S->AB is grammar production while {S.val=A.val+B.val} is semantic rule or translation rule.


What are Synthesized attributes and Inherited attributes?

Synthesized attributes:
                      Attributes of Parent whose value is dependent on the attribute values of children are called as Synthesized attributes.

e.g. S->AB {S.val=A.val+B.val}
                     Here attribute value of val of parent S is computed from attribute values of children A and B. Hence, val is Synthesized attribute.

Inherited attributes: 
                      Attributes of Children whose value is dependent on attribute values of Parent and Siblings are called as Inherited attributes. 

e.g. S->AB {A.val=S.val, B.val=S.val+A.val} 
                      Attribute value of children are dependent on attribute values of Parent and Sibling. Hence, here val is Inherited attribute.

What are S- attributed grammar & L-attributed grammar?

S-attributed Grammar/SDT:
                      Grammar which has only synthesized attributes are called s-attributed grammar/SDT.

e.g. 
S->AB {S.val=A.val+B.val}
A->a {A.val=a.lval}
B->b {B.val=b.lval}

                     This grammar consists of only Synthesized attributes. Hence, it is S-attributed Grammar.


L-attributed grammar:
                    Grammar which has 
1. synthesized attributes and/or
2. inherited attributes where attribute value of any child is dependent on attribute value of parent and/or attribute value of LEFT sibling only
                    is called L-attributed grammar.

e.g. 
1.
S->AB {S.val=A.val+B.val, A.val=S.val, B.val=S.val-A.val}
A->a {A.val=a.lval}
B->b {B.val=b.lval}

                This grammar consists of Synthesized attributes and Inherited attributes with Children's attribute value dependent on attribute value of Parent & Left Sibling. Hence it is L-attributed grammar. 

2. 
S->AB {S.val=A.val+B.val, A.val=S.val-B.val}
A->a {A.val=a.lval}
B->b {B.val=b.lval}

                As in this grammar, A.val is dependent of attribute value of left sibling B, this is not L attributed grammar. 

Important Note / Example

3.
S->AB {S.val=A.val+B.val}
A->a {A.val=a.lval}
B->b {B.val=b.lval}
                This grammar is both S-attributed grammar and L-attributed grammar. 


4. 
S->AB {S.val=A.val+B.val, A.val=S.val-B.val}
A->a {A.val=a.lval}
B->b {B.val=b.lval}
                 This grammar is neither S-attributed nor L-attributed grammar.