Programming Languages and Translators

Lecture 15: Syntax-Directed Definitions

March 24, 2008

- Midterm solutions
- Syntax-directed definitions and translation schemes
- Synthesized and inherited attributes
- S-attributed SDDs
- L-attributed SDDs
- Reading

- A syntax-directed definition (SDD) is a context-free grammar with attributes attached to grammar symbols and semantic rules attached to the productions. The semantic rules define values for attributes associated with the symbols of the productions. These values can be computed by creating a parse tree for the input and then making a sequence of passes over the parse tree, evaluating some or all of the rules on each pass. SDDs are useful for specifying translations.
- A syntax-directed translation scheme (SDTS) is a context-free grammar with program fragments, called semantic actions, embedded within production bodies. SDTSs are useful for implementing translations.

- Attributes are values computed at the nodes of a parse tree.
*Synthesized attributes*are values that are computed at a node*N*in a parse tree from attribute values of the children of*N*and perhaps*N*itself. The identifiers $$, $1, $2, etc., in Yacc actions are synthesized attributes. Synthesized attributes can be easily computed by a shift-reduce parser that keeps the values of the attributes on the parsing stack. See Sect. 5.4.2 of ALSU.- An SDD is
*S-attributed*if every attribute is synthesized. *Inherited attributes*are values that are computed at a node*N*in a parse tree from attribute values of the parent of*N*, the siblings of*N*, and*N*itself.- An SDD is
*L-attributed*is every attribute is either synthesized or inherited from the left. See Sect. 5.2.4 of ALSU for details.

- Here is an S-attributed SDD for a simple desk calculator that just adds digits. It is based on an SLR(1) for arithmetic expressions.

```
E → E1 + T { E.val = E1.val + T.val; }
E → T { E.val = T.val; }
T → ( E ) { T.val = E.val; }
T → digit { T.val = digit.lexval; }
```

`E`

has the synthesized attributed `E.val`

and
`T`

the synthesized attribute `T.val`

.`E`

has the synthesized attributed `E.node`

and
`T`

the synthesized attribute `T.node`

.
`E.node`

and `T.node`

point to a node in the AST.
The function `node(op, left, right)`

returns a pointer to a node with three fields:
the first labeled `op`

, the second a pointer
to a left subtree, and the third a pointer to a right subtree.
The function `leaf(op, value)`

returns a pointer to a node
with two fields: the first labeled `op`

, the second the
value of the token. See Ex. 5.11 in ALSU.```
E → E1 + T { E.node = Node('+', E1.node, T.node); }
E → T { E.node = T.node; }
T → ( E ) { T.node = E.node; }
T → id { T.node = Leaf(id, id.entry); }
```

- Here is the same simple desk calculator specified as an L-attributed SDD
based on an LL(1) grammar.
`E`

and`T`

each have a synthesized attribute val.`A`

has two attributes: an inherited attribute`A.i`

and a synthesized attribute`A.s`

. See Ex. 5.3 in ALSU.

```
E → T A { A.i = T.val; E.val = A.s;}
A → + T A1 { A1.i = A.i + F.val; A.s = A1.s; }
A → e { A.s = A.i; }
T → ( E ) { T.val = E.val; }
T → digit { T.val = digit.lexval; }
```

```
E → T A { E.node = A.s;
A.i = T.node; }
A → + T A1 { A1.i = Node('+', A.i, T.node);
A.s = A1.s; }
A → e { A.s = A.i; }
T → ( E ) { T.node = E.node; }
T → id { T.node = Leaf(id, id.entry); }
```

- ALSU, Sections 5.1-5.4

aho@cs.columbia.edu