Attribute Grammar

Question

Can someone explain these terms clearly these terms with examples?

• Attribute Grammar
• Synthesized attributes
• Inherited attributes
• L and S Attributes

Answer 1

Attribute Grammer:

• An attribute grammar is a context-free grammar that has been extended to provide context- sensitive information by appending attributes to some of its nonterminals.
• Each distinct symbol in the grammar has associated with it a finite, possibly empty, set of attributes.

        • Each attribute has a domain of possible values.
        • An attribute may be assigned values from its domain during parsing.
        • Attributes can be evaluated in assignments or conditions.

Classes of Attribute:
    1. Syntheized attributes
    2. Inherited attributes

Syntheized attributes: 
    1. Value is computed from values of Children's attribute.
    2. Evaluted during Bottom Up parsing
    3. S-attributed grammer contains only syntheized attributes.

Inherited attributes:
    1. Value is computed/inherited from either Parent or siblings.
    2. Evaluted by transversing parse tree from Left to Right, Top to bottom parsing.
    3. L-attributed grammer contains Inherited attributes.

S-attribute Grammers:
    1. Syntheized attributes 
    2. Semantic actions placed only to the right end of productions. (offers less flexibility)
    3. Bottom up parsing

    Examples:
        1. $A → BCD$
           $then, A.S → f(B.S,C.S,D.S)$ ==> value of A deriving from children's attribute only.
        2.  $Expr → Expr + Term\\  Expr → Term\\ Term → Term * Factor\\ Term → Factor\\ Factor → "(" Expr ")"\\ Factor → integer$

        Both grammers use only Syntheized values, therfore they are S-attribute grammers.

L-attribute Grammers:
        1. Syntheized and Inherited (parent and Left siblings only) attributes 
        2. Semantic actions placed anywhere productions.
            (offers more flexibility)
        3. Left to Right, Bottom Up parsing

 Examples:

            1.$A → xyz; then, { y.S = A.S; y.S = x.S;}$
                   Above grammer is L-attribute because, y dervies its value only from parent and siblings to the left.
            But,
                $A → xyz; then, { y.S = A.S; y.S = z.S;}$
                   In contrast to above grammar, here y evaluates its value from 'z', which is right sibling of 'y'. therfore, it's not a L-attributed grammer.