Chapter 19 of 33

Syntax-Directed Definitions

By now our parser can take a token stream like 3 * 5 + 4 and decide that it is a valid expression, and even build the parse tree for it. But a parse tree only says how the input is structured. It does not say what the input means: that the expression is worth 19, that x is a float, or what machine instructions should be produced. A compiler needs that meaning to do anything useful.

The simplest idea is to attach the meaning to the grammar itself. Every grammar symbol gets some named values (its attributes), and every production gets small rules that say how to compute those values from the values of neighbouring symbols. That combination is a syntax-directed definition.

A syntax-directed definition (SDD) is a context-free grammar together with attributes attached to its grammar symbols and semantic rules attached to its productions. Each semantic rule computes the value of one attribute from other attributes of symbols in the same production.

In this chapter we will learn the two kinds of attributes (synthesized and inherited), draw annotated parse trees, use dependency graphs to find an evaluation order, and meet the two classes of SDD that compilers actually use: S-attributed and L-attributed. The next chapter, Syntax-Directed Translation Schemes, shows how these definitions are implemented inside real parsers. Every value in this chapter was checked by evaluating the parse trees with a small script.


Attributes and Semantic Rules

An attribute is any piece of information we want to know about a grammar symbol: a number, a type, a string of code, a pointer into the symbol table, a node of a syntax tree. We write it as X.a, meaning "attribute a of symbol X". Terminals get their attributes from the lexical analyzer: a digit token comes with digit.lexval, its numeric value.

Here is the classic first SDD: a desk calculator that computes the value of an arithmetic expression. Every nonterminal has one attribute, val.

Production

Semantic rule

L → E n

L.val = E.val

E → E1 + T

E.val = E1.val + T.val

E → T

E.val = T.val

T → T1 * F

T.val = T1.val × F.val

T → F

T.val = F.val

F → ( E )

F.val = E.val

F → digit

F.val = digit.lexval

Two small notes. The subscript in E1 only tells the two occurrences of E apart inside the same production; it is still the nonterminal E. And n is an end-of-line marker, so L is a whole line typed into the calculator.

Notice that a semantic rule talks only about symbols in its own production. The rule for E → E1 + T cannot look at the whole program; it combines the values of E1 and T that sit directly below it. This locality is what makes SDDs easy to write and easy to implement.


Synthesized and Inherited Attributes

Look at a node N of a parse tree, labelled with nonterminal A. Where can the value of an attribute of A come from? Only from N itself, its children, its parent or its siblings. This gives two kinds of attributes.

A synthesized attribute of A at node N is defined by a semantic rule of the production at N (the production with A as its head). Its value is computed from attribute values of N's children and of N itself.

An inherited attribute of B at node N is defined by a semantic rule of the production at N's parent (where B appears in the body). Its value is computed from attribute values of N's parent, N itself and N's siblings.

The intuition: synthesized information flows up the tree (children tell the parent), inherited information flows down or sideways (the parent or a left sibling tells a child). The calculator above uses only synthesized attributes, because a value is naturally built from the values of its parts.

Point

Synthesized

Inherited

Defined in the production where the symbol is...

the head (left side)

in the body (right side)

Computed from

children (and the node itself)

parent, siblings (and the node itself)

Direction of flow in the tree

Bottom-up

Top-down / left-to-right

Typical uses

Expression values, types of expressions, generated code, syntax-tree nodes

Declared type passed to a list of names, context such as "inside a loop", left operand passed to the rest of an expression

Terminals?

Yes, supplied by the lexer (lexval, entry)

No, terminals never have inherited attributes

Why can terminals have no inherited attributes? Because a terminal's attributes are fixed by the lexical analyzer before parsing even starts; there is no semantic rule in the grammar that defines them.


Annotated Parse Trees

An annotated parse tree is a parse tree that shows the value of each attribute at each node.

For the calculator, take the input 3 * 5 + 4 (we drop the n to keep the picture small). Because every attribute is synthesized, we can fill the values in by a postorder walk: finish all children of a node, then apply the node's rule.

                          E.val = 19
                       /      |      \
              E.val = 15      +       T.val = 4
                  |                       |
              T.val = 15              F.val = 4
             /    |    \                  |
     T.val = 3    *    F.val = 5      digit.lexval = 4
         |                 |
     F.val = 3       digit.lexval = 5
         |
  digit.lexval = 3

Read it from the bottom: F.val = 3 and F.val = 5 come from the lexer, T.val = 3 × 5 = 15 by T → T1 * F, then E.val = 15 by E → T, and finally the root gets 15 + 4 = 19. The grammar made * sit deeper in the tree than +, so the multiplication was done first. The meaning follows the shape of the tree, and the shape follows the grammar. Keep this in mind for the solved problems later.


An SDD with an Inherited Attribute

Inherited attributes are needed when information comes from the context of a construct rather than from inside it. The standard example is a C-style declaration such as float id1, id2, id3. The type is written once, at the left, but every identifier in the list must be told about it.

Production

Semantic rules

D → T L

L.inh = T.type

T → int

T.type = integer

T → float

T.type = float

L → L1 , id

L1.inh = L.inh
addType(id.entry, L.inh)

L → id

addType(id.entry, L.inh)

T.type is synthesized (it comes up from the keyword). L.inh is inherited: in D → T L, the type is handed from the left sibling T to L, and in L → L1 , id it is passed down from L to L1. Each L node then calls addType, which records the type of one identifier in the symbol table (see the Symbol Table chapter).

                    D
                 /     \
     T.type = float ──→ L.inh = float              addType(id3, float)
          |            /    |    \
        float   L.inh = float  ,   id3             addType(id2, float)
                 /    |    \
        L.inh = float ,    id2
              |                                    addType(id1, float)
             id1

The arrow from T to L is the inherited flow: information moved sideways to a sibling, then downwards along the chain of L nodes. A purely synthesized design is possible here too, but it would force us to write a less natural grammar (for example D → D , id | T id). Inherited attributes let the grammar keep its natural shape.

The calls to addType are side effects: they do not define an attribute, they change the symbol table. An SDD with no side effects at all is sometimes called an attribute grammar. Side effects are allowed in SDDs as long as the order in which they happen does not change the result; here each call updates a different identifier, so any order is fine.


Dependency Graphs and Evaluation Order

With only synthesized attributes, postorder always works. Once inherited attributes appear, we need a way to decide which attribute can be computed first. That is the job of the dependency graph.

A dependency graph for a parse tree has one node for each attribute instance in the tree, and an edge from attribute X.a to attribute Y.b whenever the semantic rule that defines Y.b uses X.a. Any topological sort of this graph is a valid evaluation order.

To see a real example, we use the expression grammar after left recursion has been removed (as in the LL(1) Parsing chapter). Removing left recursion broke T → T * F into two productions, so the left operand of * is no longer in the same production as the right operand. An inherited attribute carries it across.

Production

Semantic rules

T → F T'

T'.inh = F.val
T.val = T'.syn

T' → * F T1'

T1'.inh = T'.inh × F.val
T'.syn = T1'.syn

T' → ε

T'.syn = T'.inh

F → digit

F.val = digit.lexval

Think of T'.inh as "the value of everything to my left so far" and T'.syn as "the final answer once I have finished". The ε-production is where the running value turns into the answer and starts travelling back up.

Annotated parse tree for 3 * 5, with every attribute instance numbered:

                 T   (9) val = 15
               /   \
    (3) F.val = 3    T'   (5) inh = 3,  (8) syn = 15
         |         /  |  \
 (1) digit = 3    *   F    T1'   (6) inh = 15,  (7) syn = 15
                      |      |
          (4) F.val = 5      ε
                      |
            (2) digit = 5

The edges of the dependency graph, one for each use of an attribute in a rule:

(1) digit.lexval = 3  ──→  (3) F.val          F → digit
(2) digit.lexval = 5  ──→  (4) F.val          F → digit
(3) F.val             ──→  (5) T'.inh         T → F T'
(5) T'.inh            ──→  (6) T1'.inh        T' → * F T1'
(4) F.val             ──→  (6) T1'.inh        T' → * F T1'
(6) T1'.inh           ──→  (7) T1'.syn        T' → ε
(7) T1'.syn           ──→  (8) T'.syn         T' → * F T1'
(8) T'.syn            ──→  (9) T.val          T → F T'

The numbering 1, 2, ..., 9 is already a topological order: every edge goes from a smaller number to a larger one. So one valid evaluation order is 1, 2, 3, 4, 5, 6, 7, 8, 9. Another valid one is 1, 3, 5, 2, 4, 6, 7, 8, 9. Both give T.val = 15. In general a dependency graph has many topological orders, and an exam answer may list any of them.

Circular SDDs

If the dependency graph has a cycle, there is no topological order, and the attributes cannot be evaluated at all. For example:

A → B      A.s = B.i
           B.i = A.s + 1

To compute B.i we need A.s, and to compute A.s we need B.i. An SDD like this is circular. Checking whether some parse tree of a general SDD can have a cycle is possible but takes exponential time in the worst case, so compilers do not try. Instead they restrict themselves to two classes of SDD that are guaranteed to be acyclic and that come with a simple evaluation order.


S-Attributed SDDs

An SDD is S-attributed if every attribute is synthesized.

The desk calculator is S-attributed. Every edge in its dependency graph points from a child to its parent, so a postorder traversal always works:

postorder(N):
    for each child C of N, from left to right:
        postorder(C)
    evaluate the attributes of N

Postorder is exactly the order in which an LR (bottom-up) parser performs reductions. So an S-attributed SDD can be evaluated during bottom-up parsing without building a tree: whenever the parser reduces by a production, it applies that production's rules. This is why S-attributed definitions fit Yacc and Bison so naturally (see Yacc & Bison).


L-Attributed SDDs

S-attributed SDDs cannot express everything comfortably (the declaration and T' examples above needed inherited attributes). L-attributed SDDs allow inherited attributes, but only in a controlled way: information may flow down and from left to right, never from right to left.

An SDD is L-attributed if each attribute is either synthesized, or inherited with this restriction: in a production A → X1 X2 ... Xn, a rule defining an inherited attribute Xi.a may use only (1) inherited attributes of the head A, (2) any attributes of X1, ..., Xi−1 (the symbols to the left of Xi), and (3) attributes of Xi itself, provided no cycle is formed through them.

Why exactly these sources? Imagine walking the tree depth-first, left to right. When we arrive at Xi, we have already finished X1 to Xi−1, and we came from A, whose inherited attributes were computed before we entered A. Everything Xi is allowed to use is already known at the moment we reach it. What is forbidden:

  • Synthesized attributes of the head A. A.s is computed only after all of A's children are finished, including Xi, so using it for Xi creates a cycle risk.

  • Any attribute of a symbol to the right (Xi+1, ..., Xn), which has not been visited yet.

Because of this restriction, an L-attributed SDD can always be evaluated in a single depth-first, left-to-right traversal: compute a node's inherited attributes just before visiting it, and its synthesized attributes just after finishing it. This is the order of a top-down (LL or recursive-descent) parser, which is why L-attributed SDDs pair so well with top-down parsing. Our T' grammar is L-attributed, and the declaration SDD is too.

The Relationship

   ┌──────────────────────────── all SDDs ─────────────────────────────┐
   │                                                                    │
   │      ┌──────────── L-attributed ─────────────┐                     │
   │      │                                       │    (some are        │
   │      │      ┌──── S-attributed ────┐         │     circular)       │
   │      │      │                      │         │                     │
   │      │      └──────────────────────┘         │                     │
   │      └───────────────────────────────────────┘                     │
   └────────────────────────────────────────────────────────────────────┘

Every S-attributed SDD is L-attributed, because the restriction applies only to inherited attributes, and an S-attributed SDD has none. The reverse is false: the T' SDD is L-attributed but not S-attributed.

Property

S-attributed

L-attributed

Attributes allowed

Synthesized only

Synthesized + restricted inherited

Evaluation order

Postorder (bottom-up)

Depth-first, left to right

Natural parser

LR parsers (Yacc/Bison)

LL / recursive descent (also LR with extra tricks)

Can be circular?

No

No

Example

Desk calculator

T → F T' with inh/syn; declarations


SDDs with Side Effects: Building Syntax Trees

One of the most important uses of an SDD inside a real compiler is to build a syntax tree (abstract syntax tree), which later phases work on. Each node of a syntax tree is an operator with its operands as children; punctuation and chain productions like E → T disappear.

We use two helper functions: new Leaf(op, val) creates a leaf, and new Node(op, c1, c2) creates an interior node. The attribute node holds a pointer to the tree built so far.

Production

Semantic rule

E → E1 + T

E.node = new Node('+', E1.node, T.node)

E → E1 − T

E.node = new Node('−', E1.node, T.node)

E → T

E.node = T.node

T → T1 * F

T.node = new Node('*', T1.node, F.node)

T → F

T.node = F.node

F → ( E )

F.node = E.node

F → id

F.node = new Leaf(id, id.entry)

F → num

F.node = new Leaf(num, num.val)

This SDD is S-attributed. For the input a + b * 3, a bottom-up evaluation creates the nodes in this order:

p1 = new Leaf(id, entry for a)
p2 = new Leaf(id, entry for b)
p3 = new Leaf(num, 3)
p4 = new Node('*', p2, p3)
p5 = new Node('+', p1, p4)          ← E.node at the root

Resulting syntax tree:
          +
        /   \
       a     *
            / \
           b   3

Compare this with the parse tree for the same input, which would have about a dozen nodes for E, T, F and the tokens. The syntax tree keeps only what matters for meaning. Intermediate Code & Three-Address Code shows how such trees are turned into instructions.


Solved Problems

Problem 1: The Grammar Decides, Not the Symbol

Consider this SDD, where the operator symbols have been given unusual meanings:

E → E1 * T     { E.val = E1.val + T.val }
E → T          { E.val = T.val }
T → T1 + F     { T.val = T1.val × F.val }
T → F          { T.val = F.val }
F → num        { F.val = num.lexval }

Evaluate 2 + 3 * 4 + 5.

Solution. Ignore what the symbols normally mean and look only at the grammar. + is generated by T, which is lower in the tree than E, so + has higher precedence and is applied first. Both productions are left recursive, so both operators are left associative. The parse groups the input as:

(2 + 3) * (4 + 5)

T for "2 + 3" : 2 × 3 = 6        ('+' means multiply)
T for "4 + 5" : 4 × 5 = 20
E             : 6 + 20 = 26      ('*' means add)

Answer: 26. The common wrong answers come from evaluating with ordinary meanings (2 + 12 + 5 = 19) or from applying the new meanings with ordinary precedence (2 × (3 + 4) × 5 = 70). A longer input, 4 + 1 * 2 + 3 + 1 * 5, groups as (4+1) * (2+3+1) * 5 and evaluates to 4 + 6 + 5 = 15.

Problem 2: Value of a Binary Number

Write an SDD that computes the decimal value of an unsigned binary numeral, using the grammar N → L, L → L B | B, B → 0 | 1. Show the annotated tree for 1101.

Solution. Reading left to right, each new bit doubles the value seen so far and adds itself, which is just like reading a decimal number digit by digit.

N → L        { N.val = L.val }
L → L1 B     { L.val = 2 × L1.val + B.val }
L → B        { L.val = B.val }
B → 0        { B.val = 0 }
B → 1        { B.val = 1 }
                         N.val = 13
                             |
                         L.val = 13
                        /          \
                  L.val = 6       B.val = 1
                 /         \          |
            L.val = 3    B.val = 0    1
           /         \       |
      L.val = 1   B.val = 1  0
          |           |
      B.val = 1       1
          |
          1

L.val values, bottom to top:  1,   2×1 + 1 = 3,   2×3 + 0 = 6,   2×6 + 1 = 13

The value is 13, and the SDD is S-attributed. (If the grammar were right recursive, L → B L, the simple doubling rule would no longer work, because the leftmost bit would be processed last. You would then need extra attributes, such as the length of the remaining list, to know each bit's weight.)

Problem 3: Classify the SDDs

For each production with rules, say whether the SDD is S-attributed, L-attributed or neither. Attributes ending in s are synthesized and those ending in i are inherited.

#

Production and rules

Answer

Reason

a

A → B C { A.s = B.s + C.s }

S-attributed (so also L)

Only synthesized attributes

b

A → B C { B.i = A.i; C.i = B.s; A.s = C.s }

L-attributed, not S

B.i uses the head's inherited attribute; C.i uses its left sibling B

c

A → B C { B.i = C.s; A.s = B.s }

Neither

B.i uses C, a symbol to its right

d

A → B C { C.i = A.s; A.s = B.s }

Neither

C.i uses the head's synthesized attribute

e

A → B C { C.i = A.i + B.s; A.s = C.s }

L-attributed, not S

C.i uses the head's inherited attribute and its left sibling

Note that (d) is not circular here (A.s depends only on B), but it still violates the L-attributed rule. "Not L-attributed" does not automatically mean "circular". It means the simple left-to-right evaluation order is not guaranteed to work.


Common Mistakes

  • Evaluating with the usual meaning of an operator symbol. Precedence and associativity come from the grammar, and the meaning comes from the semantic rule.

  • Saying a terminal has an inherited attribute. Terminal attributes come from the lexer and are synthesized.

  • Thinking "inherited" means "from the parent only". Inherited attributes may also come from siblings (left siblings, in the L-attributed case).

  • Allowing Xi.inh to use A.syn in an L-attributed SDD. Only the head's inherited attributes are allowed.

  • Believing every L-attributed SDD is S-attributed. It is the other way round.

  • Forgetting that an SDD is a specification, not a program. It says what each attribute equals, not when to compute it. The order comes from the dependency graph (and, in practice, from the parser, as the next chapter shows).


Interview and Exam Questions

Q1. What is the difference between a synthesized and an inherited attribute?

A synthesized attribute of a node is computed from the attributes of its children (and itself), using a rule of the production at that node. An inherited attribute is computed from the attributes of the node's parent, siblings and itself, using a rule of the parent's production.

Q2. Why is every S-attributed SDD also L-attributed?

The L-attributed restriction only limits inherited attributes. An S-attributed SDD has no inherited attributes, so it satisfies the restriction trivially.

Q3. In what order can the attributes of an S-attributed SDD be evaluated, and which parser does that match?

Postorder (children before parent). That is the order in which a bottom-up LR parser performs reductions, so the rules can be applied at each reduction.

Q4. What is a dependency graph used for?

It records which attribute instances each attribute depends on. Any topological sort of it is a valid evaluation order; a cycle means the attributes cannot be evaluated.

Q5. In A → P Q R, which attributes may a rule for Q.i use if the SDD is to be L-attributed?

A's inherited attributes, any attribute of P, and Q's own attributes (as long as no cycle forms). It may not use A's synthesized attributes or anything of R.

Q6. With E → E * T { E.val = E.val − T.val } | T and T → T + F { T.val = T.val / F.val } | F and F → num, what is the value of 8 * 12 + 3 * 4?

+ has higher precedence (it is lower in the grammar), so the input groups as 8 * (12 + 3) * 4. T for 12 + 3 is 12 / 3 = 4. Then E is computed left to right: 8 − 4 = 4, then 4 − 4 = 0. The answer is 0.

Q7. Why do we need inherited attributes at all?

Some information depends on the context of a construct, not on its parts: the declared type of a list of identifiers, or the left operand of an operator after left recursion has been removed. Inherited attributes carry that context down or across the tree without forcing an unnatural grammar.


Summary

  • An SDD = grammar + attributes on symbols + semantic rules on productions. Each rule uses only symbols of its own production.

  • Synthesized attributes flow up from children; inherited attributes flow down from the parent or across from siblings. Terminals have only synthesized attributes.

  • An annotated parse tree shows attribute values at each node; a dependency graph shows which attribute needs which, and a topological sort gives the evaluation order. Cycles make an SDD unevaluable.

  • S-attributed: only synthesized; evaluate in postorder, ideal for bottom-up parsing.

  • L-attributed: inherited attributes may use only the head's inherited attributes and symbols to the left; evaluate in one depth-first left-to-right pass, ideal for top-down parsing. Every S-attributed SDD is L-attributed.

  • SDDs can have side effects, such as entering types into the symbol table or building syntax-tree nodes.

An SDD says what to compute. In the next chapter, Syntax-Directed Translation Schemes, we embed the computation into the grammar as actions, decide exactly when each action runs, and plug it into LR and recursive-descent parsers.