Semantic Rules

Definition. A semantic rule is attached to one grammar production and says how to compute an attribute of a symbol in that production, or how to perform an action.

An attribute is a named value carried by a grammar symbol — written X.attr. For example E.val (the value of E) or digit.lexval (the digit supplied by the lexer).

Two kinds of rule

• Attribute-equation rule — defines an attribute as a function of other attributes. It just states a value.

• Side-effect / action rule — does something observable (print, emit code, update the symbol table) instead of defining a value.

How a rule references symbols

A rule may only mention attributes of symbols in its own production — the head and the body symbols. When a symbol appears more than once, subscripts say which occurrence is meant: the head keeps its plain name and body occurrences get ₁, ₂, …

Without the subscript you could not tell the head E from the body E. Terminal attributes like digit.lexval are not computed by a rule — the lexer supplies them.

Read an attribute-equation rule like a spreadsheet formula: it states what a value is in terms of other values. It does not say when to run — the evaluator works that out.

Our one running example for this whole topic is the desk-calculator grammar with a synthesized attribute val.

(n is the end-of-line marker.) The semantic rules attach a val to every non-terminal:

Six of the seven rules are attribute equations — each defines the val of its head from the vals of its children. The single side-effect rule is print(E.val) on S → E n: it defines no attribute, it just prints the answer.

The input we will translate is:

Every val is synthesized (defined on the head, computed from the children), so we evaluate bottom-up: each rule fires once its children's values exist.

Reading top to bottom: the inner group ( 3 * 5 + 2 ) evaluates to 17 (15 from 3 * 5, then + 2), that group becomes an F worth 17, multiplying by 2 gives 34, and S → E n finally prints it.

Annotated parse tree

The same evaluation shown on the tree, with each node's val filled in:

The root prints 34.

No circular dependencies. A rule b = f(c₁, …, cₖ) means b depends on the cᵢ, so b is computable only after them. If two attributes depended on each other in a loop, no order could compute either. In our example there is no cycle: every val needs only its children's vals, so a single bottom-up pass always works (this all-synthesized form is called S-attributed).

SDD rules are declarative; SDT actions are ordered. The table above is an SDD — each rule states what a val is, not when to compute it. The same translation can be written as an SDT (translation scheme) by placing ordered actions inside the body, e.g. E → E₁ + T { E.val = E₁.val + T.val }, which runs the moment the parser reaches that spot. Same result (prints 34), different placement — see the Translation Schemes topic.

• A semantic rule belongs to one production and either computes an attribute (b = f(c₁, …, cₖ)) or performs an action.
• Two kinds: attribute equations (like E.val = E₁.val + T.val) and side-effect rules (like print(E.val) in S → E n).
• Rules reference only symbols in their own production; subscripts (E₁, T₁) distinguish repeated symbols, and terminal attributes (digit.lexval) come from the lexer.
• Our example's val is synthesized, so it evaluates bottom-up in one pass; the input ( 3 * 5 + 2 ) * 2 n prints 34.
• Rules must have no circular dependency. SDD rules are declarative (positionless); SDT actions are ordered and placed in the body.