Scribd
Upload
2 views2 pages

09 Syntax Directed Grammar

The document discusses syntax-directed translation in compilers, emphasizing the importance of attributes associated with programming constructs for generating code. It explains semantic rules that compute attribute values based on grammar productions and introduces concepts like synthesized and inherent attributes. Additionally, it describes the use of dependency graphs to manage attribute inter-dependencies during translation processes.

Uploaded by

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

09 Syntax Directed Grammar

The document discusses syntax-directed translation in compilers, emphasizing the importance of attributes associated with programming constructs for generating code. It explains semantic rules that compute attribute values based on grammar productions and introduces concepts like synthesized and inherent attributes. Additionally, it describes the use of dependency graphs to manage attribute inter-dependencies during translation processes.

Uploaded by

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

Syntax-Directed Translation

21 April, 2026

Attributes

# To translate a programming language construct, a compiler may need to keep track of many
quantities besides the code generated for the construct. E.g. the compiler may need to know the
type of the construct or the location of the first instruction in the target code or the number of
instructions.
# We can define attributes associated with the constructs. An attribute may represent any quantity.
E.g. a string, a type, a memory location, etc.

Semantic rules

# We associate information with programming language construct by attaching attributes to the


grammar symbols representing the constructs. Values for attributes are computed by semantic
rules (associated with the grammar productions).
# For example, an infix-to-postfix translator might have the following production and rule:
Production Semantic rule
𝐸 → 𝐸1 + 𝑇 𝐸.code = 𝐸1 .code ‖ 𝑇 .code ‖ +

The production has two non-terminals, 𝐸 and 𝑇 (the subscript in 𝐸1 is used to distinguish the 𝐸
in head from the 𝐸 in body). Both 𝐸 and 𝑇 have attribute code. The semantic rule specifies that
the code of 𝐸 can be formed by concatenating the code of the 𝐸 in body, the code of 𝑇 and +.

Syntax-directed definition

# This specifies the translation of a construct in terms of attributes associated with its syntactic
components.
# It uses a context-free grammar to specify the syntactic structure of the input.
# With each grammar symbol, it associates a set of attributes and with each production, a set of
semantic rules for computing the values of the attributes associated with the symbols appearing in
that production.
# A parse tree showing the attribute values at each node is called annotated.

Synthesized attributes
# An attribute is said to be synthesized if its values at a parse tree node is computed/determined
from attribute values at the children of the node in the parse tree.

Inherent attributes
# An inherent attribute is one whose value is computed from the attribute values at the parent and/
or siblings of that node.

1
Example

Dependency Graph

# If an attribute 𝑏 at a node in a parse tree depends on an attribute 𝑐, then the semantic rule for 𝑏 at
that node must be evaluated after the semantic rule that defines 𝑐.
# The inter-dependencies among the inherited and synthesized attributes at the nodes in a parse
tree can be depicted by a directed graph called a dependency graph.
# Example: Consider the production and a corresponding semantic rule:
𝐸 → 𝐸1 + 𝐸2

𝐸.val = 𝐸1 .val + 𝐸2 .val

𝐸.val is synthesized from 𝐸1 .val and 𝐸2 .val. Draw the dependency graph for the parse tree.
# The translation steps are:
1. Construct the parse tree by using the grammar.
2. Construct the dependency graph.
3. Obtain the evaluation order.
4. Evaluate the semantic rules for translation of the input string.

You might also like