Compiler Design
Syntax Directed Translation (SDT)
Syntax Directed Translation Schemes (SDT)
A Syntax Directed Translation Scheme (SDT) is a context-free grammar with semantic actions embedded directly inside the production bodies. These actions are enclosed in curly braces { } and execute at specific points during parsing.
While an SDD acts as a pure mathematical specification (defining what to compute), an SDT serves as an implementation recipe (defining when to compute).
Key Distinction
- SDD: Semantic rules are listed separately from the grammar. No execution order is enforced.
- SDT: Semantic actions are embedded in the production bodies. Their exact position determines when they execute during a traversal of the parse tree.
SDT for Boolean Expressions with Backpatching
In intermediate code generation, boolean expressions are often translated to jumping code (conditional branches). Backpatching is a technique where placeholder jump targets are filled in later when the target labels become known.
We use three functions:
makelist(quad): Creates a new list containing only the indexquad.merge(list1, list2): Concatenates two lists and returns the merged list.backpatch(list, target): Fills intargetas the destination label for all instructions inlist.
| Production | Embedded Actions |
|---|---|
| B → B_1 or M B_2 | backpatch(B_1.falselist, M.quad); B.truelist = merge(B_1.truelist, B_2.truelist); B.falselist = B_2.falselist; |
| B → B_1 and M B_2 | backpatch(B_1.truelist, M.quad); B.truelist = B_2.truelist; B.falselist = merge(B_1.falselist, B_2.falselist); |
| B → not B_1 | B.truelist = B_1.falselist; B.falselist = B_1.truelist; |
| B → true | B.truelist = makelist(nextquad); emit('goto _'); |
| B → false | B.falselist = makelist(nextquad); emit('goto _'); |
| M → ε | M.quad = nextquad; |