Search code examples
parsingcompiler-constructionabstract-syntax-treesemantic-analysis

Can an attribute be synthesized and inherited at the same time?


I have read that synthesized and inherited attributes are disjoint sets. However I have difficulty deducing that from the definitions, which points to my lack of understanding of these definitions.

Assume that I have a production S -> E + E. If I assign define my attributes in the following way:

S -> E1 + E2

E1.side = left
E2.side = right

E1.position = 1
E2.position = E1.position + 2

Then side attribute of E uses attributes from neither parent and sibling, nor children nodes. So is it an inherited attribute, or synthesized? Why is that so? And why it doesn't fit the other category?

Also would it anything be different for position attribute?


Solution

  • In Knuth's original formulation (and it's worth reading his paper, which is quite readable), a synthetic attribute is one applied to the non-terminal on the left-hand side of a production, while an inherited attribute is one applied to a symbol (not necessarily a non-terminal) on the right-hand side of a production. The function which defines the attribute can use the attributes of any other symbol in the production.

    As is usual, the assumption is made that the start symbol never appears on the right-hand side of a production; this is not a restriction, since it is easy to extend the grammar with a production S' -> S which defines a new start symbol. With that assumption, it's evident that the start symbol has no inherited attributes (since it never appears on the right-hand side of a production), and a terminal has no synthetic attributes (since it never appears on the left-hand side of a production.)

    Moreover, the formula for a synthetic attribute can only use attributes of symbols on the right-hand side of a production, because no attribute formula can use attributes of the symbol whose attribute is being computed. However, this is not the definition of "synthetic attribute" (although it is often presented as one); rather, it is a consequence of the definition. On the other hand, inherited attribute computations may use the attributes of the symbol on the left-hand side, but they are not required to. They might be constants, as in your case, or they might only use other right-hand side symbols.

    In all cases, attributes are supposed to be free of side effects; the attribute grammar model is functional in the sense that it does not rely on execution order (other than data dependencies). An attribute could not be set twice because that would violate order independence (the attribute can only have one value, not different values at different times). So inherited and synthetic attributes are disjoint sets; every attribute is either applied to a symbol when it's on the left-hand side of a production (synthetic) or a symbol on the right-hand side (inherited).

    And to answer the specific question you raise, both of your attributes are inherited because they apply to symbols on the right-hand side of a production.