Syntax directed translation
In syntax directed translation, along with the grammar we associate some informal notations and these
notations are called as semantic rules.
So we can say that
1. Grammar + semantic rule = SDT (syntax directed translation)
o In syntax directed translation, every non-terminal can get one or more than one attribute or
sometimes 0 attribute depending on the type of the attribute. The value of these attributes is
evaluated by the semantic rules associated with the production rule.
o In the semantic rule, attribute is VAL and an attribute may hold anything like a string, a number,
a memory location and a complex record
o In Syntax directed translation, whenever a construct encounters in the programming language
then it is translated according to the semantic rules define in that particular programming
language.
Example
Production Semantic Rules
E→E+T E.val := E.val + T.val
E→T E.val := T.val
T→T*F T.val := T.val + F.val
T→F T.val := F.val
F → (F) F.val := F.val
F → num F.val := num.lexval
E.val is one of the attributes of E.
num.lexval is the attribute returned by the lexical analyzer.
Syntax directed translation scheme
o The Syntax directed translation scheme is a context -free grammar.
o The syntax directed translation scheme is used to evaluate the order of semantic rules.
o In translation scheme, the semantic rules are embedded within the right side of the productions.
o The position at which an action is to be executed is shown by enclosed between braces. It is
written within the right side of the production.
Example
Production Semantic Rules
S→E$ { printE.VAL }
E→E+E {E.VAL := E.VAL + E.VAL }
E→E*E {E.VAL := E.VAL * E.VAL }
E → (E) {E.VAL := E.VAL }
E→I {E.VAL := I.VAL }
I → I digit {I.VAL := 10 * I.VAL + LEXVAL }
I → digit { I.VAL:= LEXVAL}
Implementation of Syntax directed translation on parse tree
Syntax direct translation is implemented by constructing a parse tree and performing the actions in a left
to right depth first order.
SDT is implementing by parse the input and produce a parse tree as a result.
Example
Production Semantic Rules
S→E$ { printE.VAL }
E→E+E {E.VAL := E.VAL + E.VAL }
E→E*E {E.VAL := E.VAL * E.VAL }
E → (E) {E.VAL := E.VAL }
E→I {E.VAL := I.VAL }
I → I digit {I.VAL := 10 * I.VAL + LEXVAL }
I → digit { I.VAL:= LEXVAL}
Parse tree for SDT:
Fig: Parse tree
