Syntax-Directed Definitions for Expression Evaluation

From Syntax to Semantics: The Role of SDT

The output of the parsing phase is a parse tree, which represents the grammatical structure of the source code. Syntax-Directed Translation is a method for decorating this parse tree with semantic information. We do this by associating attributes with grammar symbols and defining semantic rules for each production.

• An attribute is a piece of data associated with a grammar symbol. For example, a non-terminal E (for expression) might have an attribute val to store its numerical value. A symbol T (for type) might have an attribute type storing int or float.
• A semantic rule is a rule associated with a production that specifies how to compute the attributes of the symbols in that production.

A Syntax-Directed Definition (SDD) is a context-free grammar augmented with such attributes and semantic rules. It's a high-level, declarative specification of the semantics. This is what we'll focus on.

Synthesized Attributes: Passing Information Up the Tree

The most straightforward type of attribute is a synthesized attribute. The value of a synthesized attribute for a non-terminal on the left-hand side (LHS) of a production is computed from the attributes of the symbols on the right-hand side (RHS).

Think of it as information flowing upwards in the parse tree, from the leaves (terminals) towards the root. A parent node computes its value based on the values of its children.

A classic use for synthesized attributes is evaluating an arithmetic expression. Consider this simple grammar:
E → E₁ + T | T
T → T₁ * F | F
F → (E) | digit

We can define a synthesized attribute val for each non-terminal. The semantic rules would look like this:

Here, digit.lexval is the numerical value of the token provided by the lexical analyzer.

An SDD that uses only synthesized attributes is called an S-Attributed Definition. These are convenient because they can be evaluated during bottom-up parsing (like SLR parsing from our last lesson). When the parser performs a reduction for a production A → α, it can immediately compute the synthesized attributes of A using the values from α that are already on the parsing stack.

To get a formal understanding of attributes and S-attributed definitions, please watch the following video.

Inherited Attributes: Passing Information Down and Across

Synthesized attributes are powerful but insufficient for all tasks. Sometimes, the meaning of a symbol depends on its context. For example, in a declaration like int x, y, z;, the type of x, y, and z is int, which is determined by the int token appearing at the beginning of the statement. To handle this, we need information to flow downwards from the parent declaration node to the identifier nodes.

This is achieved using inherited attributes. The value of an inherited attribute for a symbol on the RHS of a production is computed using attribute values of the LHS non-terminal or symbols to its left on the RHS.

Let's look at the grammar for declarations:
D → T L
L → L₁, id | id
T → int | float

We can use an inherited attribute in for the non-terminal L to pass the type down.

In the rule D → T L, L inherits its type from T. In L → L₁, id, the list L₁ to the left inherits the type from the parent L. This allows the type information to propagate throughout the entire list of identifiers.

L-Attributed Definitions: The Best of Both Worlds

An SDD that uses both synthesized and inherited attributes is powerful, but we need some rules to ensure the attributes can be evaluated efficiently (e.g., in one pass). This leads to the definition of an L-Attributed Definition.

In an L-Attributed SDD, for any production A → X₁X₂...Xn, an inherited attribute for a symbol Xj on the RHS can only depend on:

1. The inherited attributes of the parent A.
2. The attributes (synthesized or inherited) of the symbols to its left, X₁, X₂, ..., Xj-₁.

Synthesized attributes can be computed from any attributes of the children or the parent's inherited attributes. S-Attributed definitions are a special case of L-Attributed definitions.

This "left-to-right" dependency allows attributes to be evaluated in a single depth-first traversal of the parse tree.

Core Application: Evaluating Expressions with an LL-Friendly Grammar

Now let's apply these concepts to a core GATE problem: evaluating an expression using a grammar that has been made suitable for top-down parsing by eliminating left recursion. This requires a combination of synthesized and inherited attributes, making it a perfect example of an L-Attributed SDD.

Consider this grammar for expressions involving + and *:
E → T E'
E' → + T E'₁ | ε
T → F T'
T' → * F T'₁ | ε
F → (E) | num

Let's evaluate the expression 3 * 5 + 2. The parse tree structure forces 3 * 5 to be evaluated first within the T non-terminal, and then the result is passed to E' to handle the + 2.

To make this work, E' needs to inherit the result of T. Similarly, T' needs to inherit the result of F.

Here is the complete L-Attributed SDD:

Let's trace the evaluation of 3 * 5 + 2 on the parse tree. The attributes are computed during a depth-first traversal.

An annotated parse tree for 3 * 5 + 2. Arrows show the flow of inherited (down) and synthesized (up) attribute values.

1. Innermost T evaluation (for 3 * 5):

   • The F for 3 computes F.val = 3.
   • In T → F T', this value is passed down: T'.inh = 3.
   • T' expands to * F T'₁. The F for 5 has F.val = 5.
   • The rule for T' → * F T'₁ computes the inherited value for the next T'₁: T'₁.inh = T'.inh * F.val = 3 * 5 = 15.
   • T'₁ produces ε. Its rule is T'₁.syn = T'₁.inh, so T'₁.syn = 15.
   • This value is synthesized up. For T' → * F T'₁, T'.syn = T'₁.syn = 15.
   • This is synthesized up again. For T → F T', T.val = T'.syn = 15. We have now computed 3 * 5.

2. Outermost E evaluation (for 15 + 2):

   • In E → T E', the T from step 1 has T.val = 15. This is passed down: E'.inh = 15.
   • E' expands to + T E'₁. The T for 2 computes T.val = 2.
   • The rule for E' → + T E'₁ computes the next inherited value: E'₁.inh = E'.inh + T.val = 15 + 2 = 17.
   • E'₁ produces ε. Its rule sets E'₁.syn = E'₁.inh = 17.
   • This value is synthesized up. For E' → + T E'₁, E'.syn = E'₁.syn = 17.
   • Finally, for E → T E', E.val = E'.syn = 17.

The root of the tree now has the final value, 17. This example perfectly encapsulates how inherited attributes pass context down and to the right, while synthesized attributes consolidate results and pass them up.

Conclusion

In this lesson, we bridged the gap between syntactic structure and semantic meaning. You learned that Syntax-Directed Translation uses attributes and rules to compute values and other properties alongside the parsing process.

Here are your key takeaways:

• Syntax-Directed Definitions (SDDs) augment a grammar with attributes and semantic rules.
• Synthesized attributes transfer information up the parse tree (from children to parent) and are ideal for bottom-up parsers. SDDs with only these are S-Attributed.
• Inherited attributes transfer information down or sideways (from parent or left siblings) and are essential for capturing context.
• L-Attributed Definitions are a powerful class of SDDs using both attribute types, with a left-to-right dependency rule that allows for efficient single-pass evaluation.
• Evaluating expressions with LL-friendly grammars is a classic problem that demonstrates the interplay of both inherited and synthesized attributes.

In our next lesson, we will discuss Runtime Environments. You'll see how the concepts from today are used in practice, for example, by using an SDT to gather information about variables and functions and store it in a symbol table, a fundamental component of the runtime system.