Formula Sheets: Syntax Directed Translation | Compiler Design - Computer Science Engineering (CSE) PDF Download

 Page 1


S yntax Directed Tr anslation F ormula Sheet
1. S yntax-Directed Definitions (SDD)
• Definition : An SDD is a context-free gr ammar augmented with attributes and
semantic rules.
• Components :
– Attributes : V ariables associated with gr ammar symbols (terminals or non-
terminals).
– Semantic Rules : Define how attribute values are computed for each pro-
duction.
• Types of Attributes :
– S ynthesized : V alue computed from children of a node in parse tree. F or
productionA?a ,A.a =f(a
1
.a
1
,...,a
n
.a
n
) .
– Inherited : V alue computed from parent or siblings. F or productionA ?
aBß ,B.b =f(A.a,a.a
1
,...,ß.b
m
) .
2. S yntax-Directed Tr anslation (SD T)
• Definition : Tr anslation scheme embedding semantic actions within produc-
tions to compute attributes during parsing.
• Semantic A ctions : Code fr agments (e.g., { print(e.val)} ) executed at specific
points in parse tree tr aversal.
• Tr anslation Scheme : CFG with actions, e.g.,A?{ action
1
}B{ action
2
}C .
3. Dependency Gr aphs
• Definition : Directed gr aph showing dependencies between attributes in a parse
tree.
• Nodes : Attributes of gr ammar symbols.
• Edges : From attributeX.a toY.b ifY.b depends onX.a (via semantic rule).
• Use : Determines evaluation order; must be acyclic for valid SDD .
4. Attribute Evaluation
• S-Attributed SDD : Only synthesized attributes.
– Evaluation: Bottom-up, during parsing (e.g., LR parsing).
– Time Complexity : O(|w|) , where|w| is input string length.
• L-Attributed SDD : Attributes are synthesized or inherited, but inherited at-
tributes depend only on left siblings or parent.
1
Page 2


S yntax Directed Tr anslation F ormula Sheet
1. S yntax-Directed Definitions (SDD)
• Definition : An SDD is a context-free gr ammar augmented with attributes and
semantic rules.
• Components :
– Attributes : V ariables associated with gr ammar symbols (terminals or non-
terminals).
– Semantic Rules : Define how attribute values are computed for each pro-
duction.
• Types of Attributes :
– S ynthesized : V alue computed from children of a node in parse tree. F or
productionA?a ,A.a =f(a
1
.a
1
,...,a
n
.a
n
) .
– Inherited : V alue computed from parent or siblings. F or productionA ?
aBß ,B.b =f(A.a,a.a
1
,...,ß.b
m
) .
2. S yntax-Directed Tr anslation (SD T)
• Definition : Tr anslation scheme embedding semantic actions within produc-
tions to compute attributes during parsing.
• Semantic A ctions : Code fr agments (e.g., { print(e.val)} ) executed at specific
points in parse tree tr aversal.
• Tr anslation Scheme : CFG with actions, e.g.,A?{ action
1
}B{ action
2
}C .
3. Dependency Gr aphs
• Definition : Directed gr aph showing dependencies between attributes in a parse
tree.
• Nodes : Attributes of gr ammar symbols.
• Edges : From attributeX.a toY.b ifY.b depends onX.a (via semantic rule).
• Use : Determines evaluation order; must be acyclic for valid SDD .
4. Attribute Evaluation
• S-Attributed SDD : Only synthesized attributes.
– Evaluation: Bottom-up, during parsing (e.g., LR parsing).
– Time Complexity : O(|w|) , where|w| is input string length.
• L-Attributed SDD : Attributes are synthesized or inherited, but inherited at-
tributes depend only on left siblings or parent.
1
– Evaluation: Left-to-right, depth-first tr aversal (e.g., LL parsing).
– Time Complexity : O(|w|) .
• Evaluation Order : T opological sort of dependency gr aph.
5. Tr anslation for Simple Expressions
• Example Gr ammar : E ?E
1
+T |T ,T ?T
1
*F |F ,F ? (E)| num.
• S-Attributed SDD Example :
– E ?E
1
+T{E.val =E
1
.val+T.val}
– E ?T{E.val =T.val}
– T ?T
1
*F{T.val =T
1
.val×F.val}
– T ?F{T.val =F.val}
– F ? (E){F.val =E.val}
– F ? num{F.val = num.lexval}
• SD T Example :
– E ?E
1
+T{E.val =E
1
.val+T.val; print(E.val)}
– A ctions embedded to emit code (e.g., postfix notation).
6. Implementation
• Parse-Time Evaluation :
– S-Attributed: Stack-based, integr ated with LR parser .
– L-Attributed: Integr ated with LL parser , evaluate during recursive de-
scent.
• Stor age : Attributes stored in parse t ree nodes or stack (for bottom-up parsing).
• S ymbol T able : Used to store inherited attributes (e.g., variable types).
7. Time Complexities
• Attribute Evaluation : O(|w|) for S-attributed and L-attributed during parsing.
• Dependency Gr aph Construction : O(|P|) , where|P| is number of productions
in parse tree.
• T opological Sort : O(V +E) , whereV is number of attributes,E is number of
dependencies.
2