Compiler Design

Syntax Directed Definitions (SDD)

A Syntax Directed Definition (SDD) is a generalization of a context-free grammar in which each grammar symbol has a set of attributes, and each production has a set of semantic rules for computing attribute values.

An SDD is a pure specification — it defines what values the attributes should have, but does not specify how or in what order those values are computed. It behaves like a declarative mathematical definition.

Formal Definition

An SDD consists of:

A Context-Free Grammar (CFG).
For each grammar symbol X, a set of attributes A(X).
For each production A → α, a set of semantic rules of the form b := f(c_1, c_2, ..., c_k) where:
- b is a synthesized attribute of A, or
- b is an inherited attribute of one of the grammar symbols in α.

SDD for Type Checking of Expressions

A common application of SDDs is performing type checking on expressions. In this grammar, we define a synthesized attribute .type which propagates the type of subexpressions upwards, flagging type_error if compatibility checks fail.

Production	Semantic Rule for `.type`
E → E_1 + E_2	E.type = (E_1.type == int && E_2.type == int) ? int : type_error
E → E_1 * E_2	E.type = (E_1.type == int && E_2.type == int) ? int : type_error
E → E_1 and E_2	E.type = (E_1.type == bool && E_2.type == bool) ? bool : type_error
E → E_1 < E_2	E.type = (E_1.type == E_2.type) ? bool : type_error
E → id	E.type = lookup(id.name).type (retrieve from Symbol Table)
E → num	E.type = int
E → true	E.type = bool
E → false	E.type = bool

Error Propagation in SDDs

If any subexpression results in a type_error, that error propagates upward. For instance, in the expression true + 5:

The compiler evaluates true to have type bool.
The compiler evaluates 5 to have type int.
For production E → E_1 + E_2, it checks if both operands have type int. Since one is bool, the expression evaluates to type_error.
The parent expression inherits this error state, preventing downstream code generation.

Worked Example: Expression Evaluation Syntax Directed Translation (SDT)