S- Attributed Definitions & L- Attributed Definitions

 Before getting into S & L attributed definitions, we need to look on,

1. Synthesized attributes
   
   • A Synthesized attribute is an attribute of the non-terminal on the left-hand side of a production. 
   • Synthesized attributes represent information that is being passed up the parse tree.
   •  The attribute can take value only from its children (Variables in the RHS of the production).
   • The production must have non-terminal as its head.
   • A synthesized attribute at node n is defined only in terms of attribute values at the children of n itself.
   • It can be evaluated during a single bottom-up traversal of parse tree.
   • Synthesized attributes can be contained by both the terminals or non-terminals.
   • Synthesized attribute is used by both S-attributed SDT and L-attributed STD.
     

   For eg. let’s say A -> BC is a production of a grammar, and A’s attribute is dependent on B’s attributes or C’s attributes then it will be synthesized attribute.

2. Inherited attributes
   
   • An attribute of a non terminal on the right-hand side of a production is called an inherited attribute.
   • The attribute can take value either from its parent or from its siblings (variables in the LHS or RHS of the production).
   • The production must have non-terminal as a symbol in its body.
   • A Inherited attribute at node n is defined only in terms of attribute values of n’s parent, n itself, and n’s siblings.
   • It can be evaluated during a single top-down and sideways traversal of parse tree.
   • Inherited attributes can’t be contained by both, It is only contained by non-terminals.
   • Inherited attribute is used by only L-attributed SDT.
     

   For example, let’s say A -> BC is a production of a grammar and B’s attribute is dependent on A’s attributes or C’s attributes then it will be inherited attribute.

   S- Attributed SDT 

   • If an SDT uses only synthesized attributes, it is called as S-attributed SDT.
   • S-attributed SDTs are evaluated in bottom-up parsing, as the values of the parent nodes depend upon the values of the child nodes.
   • Semantic actions are placed in rightmost place of RHS.

    L-attributed SDT

   • If an SDT uses both synthesized attributes and inherited attributes with a restriction that inherited attribute can inherit values from left siblings only, it is called as L-attributed SDT.
   • Attributes in L-attributed SDTs are evaluated by depth-first and left-to-right parsing manner.
   • Semantic actions are placed anywhere in RHS.

    Note – If a definition is S-attributed, then it is also L-attributed but NOT vice-versa