Syntax-directed translation is a compiler technique in which semantic actions or attribute rules are associated with grammar productions so that translation is performed according to the syntactic structure of the source program.
Basic Idea
The parser recognizes the grammar structure, while semantic rules compute values, construct trees, generate intermediate code or update the symbol table.
Source Tokens
|
Parser
|
Grammar Productions
|
Semantic Rules / Actions
|
Translation Result
(Tree, Type, Value or Code)
Main Components
Context-free grammar
Attributes attached to grammar symbols
Semantic rules
Semantic actions
Evaluation order
Applications
Type checking
Syntax-tree construction
Postfix translation
Intermediate-code generation
Symbol-table creation
Expression evaluation
Example
Production:
E → E1 + T
Semantic Rule:
E.val = E1.val + T.val
The production defines syntax, while the semantic rule calculates the value of E.
Advantages
Clear relation between grammar and translation.
Modular specification of semantics.
Supports automatic compiler construction.
Useful in both top-down and bottom-up parsing.
Conclusion: Syntax-directed translation combines parsing with semantic processing and provides a systematic method for producing compiler outputs from grammatical structures.
2. Syntax-Directed Definition 14 Marks
A syntax-directed definition, or SDD, is a context-free grammar augmented with attributes and semantic rules associated with productions.
3. Attributes in Syntax-Directed Definitions 14 Marks
An attribute is a value associated with an occurrence of a grammar symbol in a parse tree.
Attribute Examples
Numerical value of an expression
Data type
Memory location
Generated code
Syntax-tree node pointer
Symbol-table entry
Major Types
Type
Information Direction
Typical Use
Synthesized
Children to parent
Expression value, generated code
Inherited
Parent or siblings to a node
Declared type, scope information
Attribute Evaluation
An attribute can be evaluated only after all attributes on which it depends have been computed. These dependencies are represented by a dependency graph.
4. Synthesized Attributes 14 Marks
A synthesized attribute of a node is computed from attributes of its children and sometimes from properties of the node itself.
Information Flow
Child Attributes
|
v
Parent Synthesized Attribute
Example
Production:
E → E1 + T
Rule:
E.val = E1.val + T.val
Here, E.val is synthesized from E1.val and T.val.
Properties
Information moves upward in the parse tree.
Natural for bottom-up evaluation.
Easy to evaluate by postorder traversal.
Commonly used for expression values and generated code.
Applications
Arithmetic evaluation
Syntax-tree creation
Code generation
Type calculation from operands
Advantage
Synthesized attributes are simple to implement in bottom-up parsers because the children are recognized before the parent reduction.
5. Inherited Attributes 14 Marks
An inherited attribute of a grammar symbol is computed from attributes of its parent or siblings.
Information Flow
Parent / Left Sibling Attributes
|
v
Child Inherited Attribute
Example: Declaration Type
Production:
D → T L
Rules:
L.in = T.type
T → int
T.type = integer
The type computed at T is passed to L through inherited attribute L.in.
Typical Uses
Passing declared type to identifier lists
Passing scope information
Passing symbol-table environment
Passing expected type
Passing offsets or addresses
Challenges
Evaluation order is more complex.
Cyclic dependencies must be avoided.
Not every inherited definition can be evaluated in one parsing pass.
6. S-Attributed Definitions 14 Marks
An S-attributed definition is an SDD that uses only synthesized attributes.
Removes unnecessary punctuation and grammar nodes.
Useful for semantic analysis.
Useful for optimization and code generation.
11. Syntax Tree and DAG 14 Marks
A DAG, or directed acyclic graph, is a compact representation that can share identical subexpressions, unlike an ordinary syntax tree.
Example
Expression: a + a * b + a * b
A tree repeats the subexpression a*b, while a DAG can store it once and share the node.
Comparison
Feature
Syntax Tree
DAG
Structure
Each occurrence has separate node
Common subexpressions can share nodes
Purpose
Program structure
Optimization
Memory
May use more nodes
More compact
Common expression detection
Not direct
Natural
12. Top-Down Translation 14 Marks
Top-down translation performs semantic actions while a top-down parser expands non-terminals and scans the input from left to right.
Translation Scheme
A translation scheme embeds semantic actions inside production bodies.
E → T { print(T.val); }
Action Positions
An action at the beginning executes before symbols are processed.
An action between symbols executes after left symbols and before right symbols.
An action at the end executes after the complete production body.
Example: Infix to Postfix
E → T E'
E' → + T { print('+'); } E'
| ε
T → id { print(id.lexeme); }
Working for a+b
Recognize a and print a.
Recognize +.
Recognize b and print b.
Execute action for +.
Output becomes ab+.
Conditions
Grammar should be suitable for top-down parsing.
Inherited attributes must satisfy L-attributed restrictions.
Actions must be placed after required values become available.
13. Postfix Notation 14 Marks
In postfix notation, an operator is written after its operands. It is also called Reverse Polish Notation.
Examples
Infix
Postfix
a + b
ab+
a + b * c
abc*+
(a + b) * c
ab+c*
Why Postfix Is Useful
No parentheses are required.
No precedence table is required during evaluation.
Easy stack-based evaluation.
Useful as an intermediate representation.
Syntax-Directed Translation
E → E1 + T { print('+'); }
E → E1 - T { print('-'); }
E → T
T → T1 * F { print('*'); }
T → F
F → ( E )
F → id { print(id.lexeme); }
Stack Evaluation
Scan postfix expression left to right.
Push operands onto stack.
On operator, pop required operands.
Apply operator and push result.
Final stack value is the answer.
Postfix: 23*4+ Evaluation: 2×3=6, then 6+4=10.
14. Bottom-Up Evaluation of S-Attributed Definitions 14 Marks
Bottom-up evaluation computes synthesized attributes during reductions in a shift-reduce parser.
Basic Principle
When a production A → XYZ is reduced, attributes of X, Y and Z are already available on the parsing stack. These values are used to calculate attributes of A.
Attribute Stack
State Stack: 0 X i Y j
Attribute Stack: X.val Y.val
Example
Production:
E → E1 + T
Semantic Rule:
E.val = E1.val + T.val
During reduction:
Pop E1.val, '+', T.val
Compute E.val
Push E.val with non-terminal E
Implementation with YACC-Style Actions
E : E '+' T { $$ = $1 + $3; }
| T { $$ = $1; }
;
T : NUM { $$ = $1; }
;
Notation
$$: attribute of production head.
$1, $2, $3: attributes of body symbols.
Advantages
Natural with LR parsing.
Attributes are evaluated at reduction time.
No separate parse-tree traversal is required.
Efficient for expression evaluation and code generation.
Limitation
Direct bottom-up evaluation is simplest for S-attributed definitions. Inherited attributes require special transformations or stack management.
15. Important Comparisons 14 Marks
Synthesized vs Inherited Attributes
Basis
Synthesized
Inherited
Computed from
Children
Parent or siblings
Direction
Upward
Downward or sideways
Natural parser
Bottom-up
Top-down
Example
Expression value
Declared type
SDD vs Translation Scheme
Basis
SDD
Translation Scheme
Form
Grammar plus semantic rules
Grammar with embedded actions
Nature
Declarative
Implementation oriented
Order
Derived from dependencies
Influenced by action position
Unit 3 Quick Revision
Syntax-directed translation associates semantic processing with grammar productions.
An SDD contains grammar, attributes and semantic rules.
Synthesized attributes flow upward.
Inherited attributes receive information from parent or siblings.
S-attributed definitions use only synthesized attributes.
Syntax trees provide compact program representation.
Postfix notation places operators after operands.
Bottom-up parsers evaluate synthesized attributes during reductions.
Important RGPV Exam Questions
Long Answer Questions
Define syntax-directed translation and explain its applications.
Explain syntax-directed definitions with an example.
Explain synthesized and inherited attributes with suitable examples.
Explain S-attributed definitions and their evaluation.
Explain L-attributed definitions and their restrictions.
Compare S-attributed and L-attributed definitions.
Explain dependency graph construction and attribute evaluation order.
Explain construction of syntax trees using semantic rules.
Differentiate between parse tree, syntax tree and DAG.
Explain top-down translation with an example.
Explain conversion of infix expressions to postfix notation using syntax-directed translation.
Explain bottom-up evaluation of S-attributed definitions.
Explain attribute-stack implementation in a shift-reduce parser.
Short Answer Questions
Define an attribute grammar.
What is a synthesized attribute?
What is an inherited attribute?
Define S-attributed SDD.
Define L-attributed SDD.
What is a dependency graph?
What is a circular SDD?
Define annotated parse tree.
What is postfix notation?
What does $$ represent in YACC?
Exam Strategy: Attribute questions should include a production, semantic rules, information-flow diagram, annotated tree or dependency graph and a final comparison table.
Download Study Resources
Unit 3 PDF
Printable detailed notes will be uploaded soon.
Coming Soon
Attribute Problems
Practice questions will be available soon.
Coming Soon
PYQ Analysis
Repeated Unit 3 questions will be added soon.
Coming Soon
Frequently Asked Questions
It is a translation method in which semantic actions or attribute rules are associated with grammar productions.
Only synthesized attributes are used.
They support restricted inherited attributes and can be evaluated in a left-to-right traversal, making them suitable for top-down translation.
An edge X to Y means that attribute Y depends on attribute X and X must be evaluated first.
It removes the need for parentheses and explicit precedence during stack-based evaluation.