Syntax-directed definitions: synthesized and inherited attributes

Why it exists

A parser only says whether a sentence fits the grammar. A compiler needs more: the value of an expression, the type of a name, the code for a statement. Syntax-directed translation attaches this computation to the grammar: every grammar symbol gets attributes (a value, a type, a code string, a location) and every production gets rules that say how to compute the attributes from each other. The computation is then driven by the structure of the parse tree. A definition that only describes what to compute, without saying in which order or with which parser, is a syntax-directed definition (SDD).

Prerequisites

You need parse trees and a parsing method (LR parsing); the examples use the layered expression grammar.

Precise definitions

Attribute. A named value attached to a grammar symbol, for example E.val, T.type, id.name. Every node of a parse tree labelled by that symbol has its own copy (an attribute instance).

Semantic rule. A rule attached to a production that defines an attribute of one of the symbols of that production in terms of attributes of the symbols of the same production: E.val = E1.val + T.val. When a symbol occurs twice in a production the occurrences are distinguished by subscripts (E → E1 + T), the one on the left of the arrow keeping the plain name.

Syntax-directed definition (SDD). A context-free grammar together with attributes and semantic rules. In the form used for GATE the rules have no side effects (they are functions); an SDD with side effects, such as printing, is better called a translation scheme (next pages).

Synthesized attribute. An attribute of a nonterminal $A$ at a node $N$ that is defined by a rule of the production at $N$, in terms of attributes of $N$'s children (and possibly of $N$ itself). Information flows up the tree. Attributes of tokens (num.lexval, id.name) are synthesized: they are supplied by the lexical analyser.

Inherited attribute. An attribute of a nonterminal $B$ at a node $N$ that is defined by a rule of the production at the parent of $N$, in terms of attributes of the parent, of $N$ itself and of $N$'s siblings. Information flows down and sideways. Inherited attributes are convenient when the structure of the parse tree does not match the structure of the program: for example the type in a declaration int a, b, c is in the tree on the left of the list, while the names that need it are in the tree below the list.

Recognising the kind. Look at the rule: if the attribute defined is of the symbol on the left of the production, it is synthesized; if it is of a symbol on the right, it is inherited. (A symbol can have both kinds.) The start symbol has no inherited attributes, unless given initial values.

Annotated parse tree. A parse tree with the values of all attributes written at its nodes. Evaluating an SDD for a sentence means building its parse tree and then filling in the attributes.

Dependency graph. Draw a node for every attribute instance of the parse tree and, for every rule, an edge from each attribute it uses to the attribute it defines. An order in which the attributes can be evaluated is a topological order of this graph; it exists exactly if the graph has no cycle. A definition that can produce a cyclic dependency graph for some sentence is circular and is not well defined: for $A \to B$ with the rules B.i = A.s and A.s = B.i each attribute waits for the other.

Side-effect-free, S-attributed and L-attributed. The two important restricted forms, S-attributed (only synthesized attributes) and L-attributed (inherited attributes limited to depend on the left), are the subject of evaluation orders.

How it works

First a definition with synthesized attributes only, the desk calculator. Each production computes val from the children:

The animation builds the parse tree of 3 * 5 + 4 with a real parser, then evaluates one attribute per step in a topological order. Nodes whose attributes are still unknown are dashed; the one just evaluated is shaded. Every value is computed from values that already exist, from the leaves up, and the root gets 19.

Now an inherited attribute. In the declaration int a, b, c the grammar is $D \to T\ L$, $T \to \text{int} \mid \text{float}$, $L \to L_1 , \text{id} \mid \text{id}$, with T.type synthesized, L.in inherited ($D \to T L$: L.in = T.type; $L \to L_1 , \text{id}$: L1.in = L.in and id.type = L.in; $L \to \text{id}$: id.type = L.in). The type is created at the top and must travel down to the identifiers, so the evaluation order is top-down here.

Worked examples

Cheat box

Traps and GATE patterns

Connections

SDDs are evaluated on the trees built by the parsers of LL(1) parsing and LR parsing. The restricted classes and the evaluation order are on S-attributed and L-attributed definitions; executing actions during parsing is translation schemes. The main application is the generation of intermediate code (code and temporaries are attributes). Types attached to names are kept in the symbol table described in phases of a compiler.

PYQs

Consider the following two syntax-directed
definitions SDD1 and SDD2 for type declarations.

SDD1
Grammar
(G1)
Semantic Rules
D→TV
D.type = T.type
V.type = T.type
T→ int
T.type = int
T→ float
T.type = float
V→V1 id
V1.type = V.type
put(id.entry,V.type)
V→ id
put(id.entry,V.type)

SDD2
Grammar
(G2)
Semantic Rules
D→D1 id
D.type = D1.type
put(id.entry, D1.type )
D→T id
D.type = T.type
put(id.entry, T.type )
T→ int
T.type = int
T→ float
T.type = float

D is the start symbol, and int, float and id are the
three terminals. The non-terminal V1 is the same as
V and the non-terminal D1 is the same as D. Here,
the subscript is used to differentiate the grammar
symbols on the two sides of a production. The
function put updates the symbol table with the type
information for an identifier.

Let P and Q be the languages specified by grammars
G1 and G2, respectively.

Which of the following statements is/are true?

Consider the following syntax-directed definition
(SDD)

S → D H T U { S.val = D.val + H.val + T.val + U.val; }

D → "M" D1         { D.val = 5 + D1.val; }

D → ε              { D.val = -5; }

H → "L" H1         { H.val = 5 * 10 + H1.val; }

H → ε              { H.val = -10; }

T → "C" T1         { T.val = 5 * 100 + T1.val; }

T → ε              { T.val = -5; }

U → "K"            { U.val = 5; }

Given "MMLK" as the input, which one of the
following options is the CORRECT value
computed by the SDD (in the attribute S.val)?

Consider the syntax directed translation given by the
following grammar and semantic rules. Here N,I,F
and B are non-terminals. N is the starting non-
terminal, and #, 0, and 1 are lexical tokens
corresponding to input letters "#", "0", and "1",
respectively. X.val denotes the synthesized attribute
(a numeric value) associated with a non-terminal X.I1
 and F1 denote occurrences of I and F on the right-
hand side of a production, respectively. For the tokens
0 and 1, 0.val=0 and 1.val= 1

N → I # F      N.val = I.val + F.val

I → I1 B       I.val = (2 I1.val) + B.val

I → B          I.val = B.val

F → B F1       F.val = 1⁄2 (B.val + F1.val)

F → B          F.val = 1⁄2 B.val

B → 0          B.val = 0.val

B → 1          B.val = 1.val

The value computed by the translation scheme for the
input string: 10#011

is ____________. (Rounded off to three decimal
places)

Consider the following grammar along with
translation rules.

S → S1 # T   { S.val = S1.val * T.val }

S → T        { S.val = T.val }

T → T1 % R   { T.val = T1.val + R.val }

T → R        { T.val = R.val }

R → id       { R.val = id.val }

Here # and % are operators and id is a token that
represents an integer and id.val represents the
corresponding integer value. The set of non-terminals
is {S, T, R, P} and a subscripted non-terminal
indicates an instance of the non-terminal.

Using this translation scheme, the computed value of
S.val for root of the parse tree for the expression
20#10%5#8%2%2 is ______

COMPILER DESIGN

Self-check

Revision card

References