SYNTAX DIRECTED
TRANSLATION
Definition of SDT(syntax directed
translation)
Syntax-directed translation refers to a method of compiler implementation where the
source language translation is completely driven by the parser.
SDT is a method used in compilers where the translation of a source program is
driven by the syntax of the language. It involves associating semantic actions with
the grammar rules of a language, which are executed during parsing to produce
intermediate code, generate error messages, or perform other tasks. some other
.tasks can also be done in parallel like code generation, intermediate code generation
expression evaluation etc…
How SDT Works
SDT works by attaching semantic rules to the productions of a context-free
grammar. These semantic rules specify how to compute the attributes of the non-
terminal symbols in the grammar. The attributes can be either synthesized or
inherited.
Example:
Consider a simple grammar for arithmetic expressions:
1. E→E1+T
2. E→T
3. T→T1∗F
4. T→F
5. F→(E)
6. F→id
PRODUCTION RULE
A PRODUCTION RULE in the context of a grammar is a formal rule that defines how a
non-terminal symbol can be replaced by a sequence of non-terminal and/or terminal
symbols. Production rules are used to generate strings in a language.
Example: Consider a simple grammar for arithmetic expressions:
1. E→E+T
2. E→T
3. T→T∗F
4. T→F
5. F→(E)
6. F→id
In this example, each line represents a production rule that defines how the non-
terminal symbols E, T, and F can be expanded.
Semantic Rule
A semantic rule is associated with a production rule and specifies how to compute the
attributes of the non-terminal symbols in the production. These rules are used to perform
semantic actions during parsing, such as type checking, intermediate code generation, or
symbol table management.
Example: Let's attach semantic rules to the production rules for arithmetic expressions to
compute the value of an expression:
1. E→E1+T { E.val = E1.val+ T.val }
2. E→T { E.val = T.val}
3. T→T1∗F { T.val = T1.val * F.val }
4. T→F { T.va l= F.val }
5. F→(E) { F.val = E.val }
6. F→id { F.val=id.val }
In this example, the semantic rules specify how to compute the value attribute
(valval) for each non-terminal symbol based on the values of its children
KEY PURPOSES OF SYNTAX-DIRECTED TRANSLATION
Key Purposes of Syntax-Directed Translation
Intermediate Code Generation: SDT helps in generating intermediate code that is
easier to optimize and translate into machine code.
Error Detection and Reporting: SDT can be used to detect and report errors during
parsing.
Type Checking: SDT can perform type checking by attaching type information to the
grammar symbols.
Symbol Table Management: SDT can manage the symbol table by inserting and
looking up symbols as needed.
Code Optimization: SDT can perform optimizations by analyzing and transforming
the intermediate code.
Attributes in
SDT
Attributes in SDT can be classified into two types: synthesized attributes and
inherited attributes.
Synthesized attributes: are those attributes that are passed up a parse tree, i.e., the
left side attribute is computed from the right-side attributes. The lexical analyzer usually
supplies the attributes of terminals and the synthesized ones are built up for the
nonterminal and passed up the tree. In other word synthesized attributes can take value
from their child .
ATTRIBUTES IN SDT
Inherited attributes are computed from the attributes of the parent and/or sibling nodes in
the parse tree. They are typically used to pass information down and across the parse tree. In
other word inherited attributes can take value from parents, itself and siblings.
Additional Details
Semantic Actions: These are the actions specified in the semantic rules that are
executed when a particular production is used in the derivation of a string. They
can include operations like type checking, symbol table management, and
intermediate code generation.
Parse Tree: The parse tree is a hierarchical structure that represents the
syntactic structure of the input according to the grammar. SDT uses the parse
tree to evaluate the semantic rules and compute the attributes.
Evaluation Order: The order in which the attributes are evaluated is crucial.
For synthesized attributes, a bottom-up evaluation is typically used, while for
inherited attributes, a top-down or mixed evaluation order may be required.
Structure of an SDD:
• A production with semantic rules looks like this:
Production: A → B C
Semantic Rule: A.attr = B.attr + C.attr
Components of SDD:
1. Attributes: Values associated with symbols.
2. Semantic Rules: Define how to compute attribute values.
Example:
For evaluating the arithmetic expression 3 + 5 * 2:
Productions:
1. E → E1 + T { E.val = E1.val + T.val }
2. E → T { E.val = T.val }
3. T → T1 * F { T.val = T1.val * F.val }
4. T → F { T.val = F.val }
5. F → digit { F.val = digit.lexval }
3. Types of Syntax-Directed Definitions
SDDs are classified based on the type of attributes and how they are evaluated.
Two Main Types of SDDs:
1. S-Attributed Definitions:
O An SDD that uses only synthesized attributes.
Example:
Production: E → E1 + T
Rule: E.val = E1.val + T.val
2.L-Attrbuted Definitions:
An SDD that uses both synthesized and inherited attributes, with restrictions:
Inherited attributes can only depend on:
Attributes of the parent node.
Attributes of siblings to the left.
Can be evaluated during a top-down traversal (left-to-right).
Example:
Production: D → T L Rule: L.in = T.type
A dependency graph is used to represent the flow of information among the attributes in a
parse tree. In a parse tree, a dependency graph basically helps to determine the evaluation
order for the attributes. The main aim of the dependency graphs is to help the compiler to
check for various types of dependencies between statements in order to prevent them from
being executed in the incorrect sequence
Evaluation of Semantic Rules
Definition
Semantic rules in a Syntax-Directed Definition (SDD) specify how the attributes
of grammar symbols are computed.
The evaluation of semantic rules involves determining the correct order in which
these rules are executed to ensure
all dependencies are satisfied.
Key Concepts
1.Dependency Graphs:
•Represent the relationships (dependencies) between attributes in a grammar.
•Nodes represent attributes, and directed edges represent dependencies between them.
2.Evaluation Order:
•A valid order of evaluation ensures that no attribute is computed before its dependencies.
•Determined using Topological Sorting of the dependency graph.
Evaluation Strategies
1. Bottom-Up Evaluation (Synthesized Attributes):
o Evaluates attributes starting from the leaf nodes and working up the parse tree.
o Suitable for S-Attributed Definitions.
o Example: Arithmetic expression evaluation.
Step-by-Step Example:
o Grammar Production: E → E1 + T
Semantic Rule: E.val = E1.val + T.val
o Parse Tree
E
/ | \
E1 + T
| |
3 5
.
· Evaluation:
1. Assign E1.val = 3 (leaf node).
2. Assign T.val = 5 (leaf node).
3. Compute E.val = E1.val + T.val = 3 + 5 = 8.
· Top-Down Evaluation (Inherited Attributes):
Evaluates attributes starting from the root node and working down the parse tree.
Suitable for L-Attributed Definitions.
Example: Type checking in declarations
Step-by-Step Example:
• Grammar Production: D → T L
Semantic Rule: L.in = T.type
• Parse Tree:
D
/\
T L
| |
int x
Evaluation:
1. Assign T.type = int (parent node).
2.Pass L.in = T.type = int (downward to child node).
Challenges in Evaluation
•Circular Dependencies:
Occur when attributes depend on each other in a cycle, making evaluation impossible.
Example: A.attr = B.attr + 1, B.attr = A.attr + 1.
•Solution:
Use a dependency graph to detect cycles before evaluation.
Here’s a detailed explanation of Evaluation of Semantic Rules and Abstract Syntax Tree (AST) with
examples and key references to help you understand and present these topics effectively.
________________________________________
Evaluation of Semantic Rules
Definition
Semantic rules in a Syntax-Directed Definition (SDD) specify how the attributes of grammar
symbols are computed. The evaluation of semantic rules involves determining the correct order in
which these rules are executed to ensure all dependencies are satisfied.
Key Concepts
1. Dependency Graphs:
Represent the relationships (dependencies) between attributes in a
grammar.
Nodes represent attributes, and directed edges represent dependencies
between them.
2. Evaluation Order:
A valid order of evaluation ensures that no attribute is computed
before its dependencies.
Determined using Topological Sorting of the dependency graph.
________________________________________
Evaluation Strategies
1. Bottom-Up Evaluation (Synthesized Attributes):
Evaluates attributes starting from the leaf nodes and working up the
parse tree.
Suitable for S-Attributed Definitions.
Example: Arithmetic expression evaluation.
Step-by-Step Example:
Grammar Production: E → E1 + T
Semantic Rule: E.val = E1.val + T.val
Parse Tree:
markdown
Copy code
E
/ | \
E1 + T
| |
3 5
Evaluation:
1.Assign E1.val = 3 (leaf node).
2.Assign T.val = 5 (leaf node).
3.Compute E.val = E1.val + T.val = 3 + 5 = 8.
2.Top-Down Evaluation (Inherited Attributes):
Evaluates attributes starting from the root node and working down the parse
tree.
Suitable for L-Attributed Definitions.
Example: Type checking in declarations
Step-by-Step Example:
Grammar Production: D → T L
Semantic Rule: L.in = T.type
Parse Tree:
arduino
Copy code
D
/\
T L
| |
int x
Evaluation:
1.Assign T.type = int (parent node).
2.Pass L.in = T.type = int (downward to child node).
Challenges in Evaluation
Circular Dependencies:
Occur when attributes depend on each other in a cycle, making evaluation
impossible.
Example: A.attr = B.attr + 1, B.attr = A.attr + 1.
•Solution:
Use a dependency graph to detect cycles before evaluation.
