What are synthesized attributes in the context of creating an abstract syntax tree?

Question

Compilers parse source code and build an abstract syntax tree. The functions used to construct an abstract syntax tree return pointers which constitute synthesized attributes. What are they and how do they differ from inherited attributes.?

edit: I don't know if this can help, but I originally heard of these terms in a French context: Attributs synthétisés, attributs hérités.

Answer 1

Attributes are additional values associated with something of central interest. In the case of ASTs, you can think of them as pairs (attribute_name, attribute_value) associated with each AST node, where the attribute name corresponds to some interesting fact-type, and the attribute value corresponds to the actual state of that fact (e.g., "(constants_in_subtree_count,12)").

Inherited and synthesized are terms for describing how the attribute values are computed for each AST node, usually associated with the grammar rule that produces the AST node using its children.

Synthesized attributes are those whose value is computed from attribute values from children nodes, and are being passed up the tree. Often, values of synthesized attributes are combined to produce an attribute for the parent node. If an AST node has two children, each of which have their own attributes (constants_in_subtree_count,5) and (constants_in_subtree_count,7), then by passing those attributes up, the parent can compute his corresponding attribute (constants_in_subtree_count,12).

Inherited attributes are those passed from the parent down to the child. If the root of a function AST "knows" the function return type is (return_type,integer) as an attribute, it can pass the return type to the children of the function root, e.g. to the function body. Someplace deep down in that tree is an actual return statement; if it receives the inherited attribute (return_type,X), it can check that the result it is computing is the correct type.

In practice, you want to be able to define arbitrary sets of attributes for nodes, and pass them up and down the tree for the multiple purposes required to process ASTs (building symbol tables, constructing control flow graphs, doing type checking, computing metrics, ...). An attribute grammar generator is a kind of parser generator that will take grammar rules, sets of attribute definitions, and rules about how to compute synthesized and inherited attributes for the nodes involved in each rule, and generates both a parser and an AST walker that computes all the attributes.

The value of this idea is it provides an organizing principle supported by automation, that can be used to compute many interesting things about ASTs in a regular way. Otherwise you get to code all that stuff using ad hoc code.

Our DMS Software Reengineering Toolkit is an AST manipulation system (actually source-to-source program transformations) that heavily uses parallel attribute evaluation to compute all kinds of useful analyses over ASTs: conventional metrics, symbol tables, type checks (like the return type check I described above), control and data flow extraction from code, as well as other not-so-easily described but useful results computed over subtrees ("list of side effecting assignments in this expression"). Why parallel? Well, attribute computations in subtrees are essentially independent, so the parallelism is already there, and when you deal with really big trees performance matters. DMS often deals with thousands of compilation units, each producing a (possibly big) AST.