Scribd
Upload
29 views4 pages

Attributed Grammar

The document explains two types of attributes in programming languages: synthesized attributes, which derive values from child nodes, and inherited attributes, which derive values from parent or sibling nodes. It provides examples and outlines the computation methods for both types, including the construction of Syntax Directed Definitions (SDD) and the generation of annotated parse trees. The document illustrates these concepts with example grammars and input strings to demonstrate the computation of attribute values.

Uploaded by

karanamdhanunjay2004
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
29 views4 pages

Attributed Grammar

The document explains two types of attributes in programming languages: synthesized attributes, which derive values from child nodes, and inherited attributes, which derive values from parent or sibling nodes. It provides examples and outlines the computation methods for both types, including the construction of Syntax Directed Definitions (SDD) and the generation of annotated parse trees. The document illustrates these concepts with example grammars and input strings to demonstrate the computation of attribute values.

Uploaded by

karanamdhanunjay2004
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Types of attributes – There are two types of attributes:

1. Synthesized Attributes – These are those attributes which derive their values from their
children nodes i.e. value of synthesized attribute at node is computed from the values of
attributes at children nodes in parse tree.
Example:
E --> E1 + T {E.val = E1.val + T.val}
In this, E.val derive its values from E 1.val and T.val
Computation of Synthesized Attributes –
 Write the SDD using apppropriate semantic rules for each production in given grammar.
 The annotated parse tree is generated and attribute values are computed in bottom up
manner.
 The value obtained at root node is the final output.
Example: Consider the following grammar
S --> E
E --> E1 + T
E --> T
T --> T1 * F
T --> F
F --> digit
The SDD for the above grammar can be written as follow

Let us assume an input string 4 * 5 + 6 for computing synthesized attributes. The annotated
parse tree for the input string is
For computation of attributes we start from leftmost bottom node. The rule F –> digit is used to
reduce digit to F and the value of digit is obtained from lexical analyzer which becomes value
of F i.e. from semantic action F.val = digit.lexval. Hence, F.val = 4 and since T is parent node
of F so, we get T.val = 4 from semantic action T.val = F.val. Then, for T –> T 1 * F production,
the corresponding semantic action is T.val = T 1.val * F.val . Hence, T.val = 4 * 5 = 20
Similarly, combination of E 1.val + T.val becomes E.val i.e. E.val = E 1.val + T.val = 26. Then,
the production S –> E is applied to reduce E.val = 26 and semantic action associated with it
prints the result E.val . Hence, the output will be 26.
2. Inherited Attributes – These are the attributes which derive their values from their parent
or sibling nodes i.e. value of inherited attributes are computed by value of parent or sibling
nodes.
Example:
A --> BCD { C.in = A.in, C.type = B.type }
Computation of Inherited Attributes –
 Construct the SDD using semantic actions.
 The annotated parse tree is generated and attribute values are computed in top down
manner.
Example: Consider the following grammar
S --> T L
T -->int
T --> float
T --> double
L --> L1, id
L --> id
The SDD for the above grammar can be written as follow

Let us assume an input string int a, c for computing inherited attributes. The annotated parse
tree for the input string is
The value of L nodes is obtained from T.type (sibling) which is basically lexical value
obtained as int, float or double. Then L node gives type of identifiers a and c. The computation
of type is done in top down manner or preorder traversal. Using function Enter_type the type
of identifiers a and c is inserted in symbol table at corresponding id.entry.

You might also like