Syntax Directed Definition
Syntax Directed Definitions
- A Syntax Directed Definition (SSD) is a generalization of a context-free grammar in which each grammar symbol has an associated set of attributes, partitioned into two subsets called the synthesized and inherited attributes of that grammar symbol.
- An attribute can represent a string, a number, a type, a memory location, or whatever. The value of an attribute at a parse-tree node is defined by a semantic rule associated with the production used at that node.
- Attributes are divided into two types:
- Synthesized Attributes are computed from the values of the attributes of the children nodes.
- Inherited Attributes are computed from the values of the attributes of both the siblings and the parent nodes.
Syntax Directed Definitions
- For Example, Each production, A → α, is associated with a set of semantic rules: b := f(c1, c2, . . . , ck), where f is a function.
- b is a synthesized attribute of A, and c1, c2, . . . , ck are attributes of the grammar symbols of the production
- b is an inherited attribute of a grammar symbol in α, and c1, c2, . . . , ck are attributes of grammar symbols in α or attributes of A.
Types of Attributes
Example :
- Let us consider the grammar for arithmetic expressions. The Syntax Directed Definition associates to each non terminal a synthesized attribute called val. The semantic rule computes the value of attribute val for the nonterminal on the left side from the values of val for the nonterminals on the right side.
| Production | Semantic rule |
|---|---|
| L -> En | Print(E.val) |
| E -> E1 + T | E.val : = E1.val + T.val |
| E -> T | E.val : = T.val |
| T -> T1 * F | T.val : = T.val * F.val |
| T -> F | T.val : = F.val |
| F -> (E) | F.val : = E.val |
| F -> digit | F.val : = digit.lexval |
Synthesized Attribute
Syntax Directed Translation Schemes
An annotated parse tree for the input string 3 * 5 + 4 n,
- A parse tree showing the values of attributes at each node is called an annotated parse tree.
- The process of computing the attributes values at the nodes is called annotating of the parse tree.
Annotated Parse Tree for 3 * 5 + 4 n
S & L Attributed Definitions
- We will look at two sub-classes of the syntax-directed definitions:
- S-Attributed Definitions : Only synthesized attributes are used in the syntax-directed definitions.
- L-Attributed Definitions : Both synthesized and inherited attributes are used in a restricted fashion.
Syntax Directed Definitions Example