The back end of a compiler is where a parse tree stops being a grammar exercise and starts becoming a program that runs fast. Two ideas carry most of the weight there: syntax-directed translation, which attaches meaning and code to the grammar, and code optimization, which rewrites that code to do the same work with fewer instructions. Both are heavily tested and both reward understanding the mechanics rather than memorising names. Let us build them up in order.
Where syntax-directed translation sits in the compiler
After lexical analysis produces tokens and the parser builds a parse tree, the compiler still has to check that the program means something and then generate code for it. Syntax-directed translation is the framework for doing that work while walking the parse tree. You attach attributes to grammar symbols and semantic rules to productions, and the values flow through the tree as it is traversed.
A syntax-directed definition (SDD) is the grammar plus those attributes and rules. A syntax-directed translation scheme (SDT) is the same idea with the semantic actions written inline inside the production, at the exact position they should execute. An SDD says what to compute; an SDT says what to compute and when.
Synthesized vs inherited attributes
Every attribute in an SDD is one of two kinds, and telling them apart is the single most tested distinction in this topic.
A synthesized attribute at a node is computed from the attributes of that node's children. Value flows up the tree, from leaves toward the root. The classic example is the value of an arithmetic expression: a plus node computes its value from the values of its two operands.
An inherited attribute at a node is computed from the attributes of its parent and its siblings. Value flows down or across the tree. The classic example is propagating a declared type to a list of identifiers: in `int a, b, c` the type `int` is inherited by each identifier from the declaration above.
A grammar whose SDD uses only synthesized attributes is called S-attributed, and it can be evaluated in a single bottom-up pass, which is why parser generators love it. A grammar that also uses inherited attributes in a restricted, left-to-right-computable way is called L-attributed. Every S-attributed definition is also L-attributed.
SDD and SDT: an annotated parse tree
Take the tiny grammar for adding and multiplying numbers, with a synthesized attribute `val`:
`E -> E1 + T` with rule `E.val = E1.val + T.val`
`E -> T` with rule `E.val = T.val`
`T -> T1 * F` with rule `T.val = T1.val * F.val`
`T -> F` with rule `T.val = F.val`
`F -> digit` with rule `F.val = digit.lexval`
Now annotate the parse tree for the input `3 * 5 + 4`. The leaves carry their `lexval`, and each internal node computes its `val` from its children.
Reading the annotations bottom-up, the multiplication node gets `val = 15`, the standalone `4` gets `val = 4`, and the addition at the root gets `val = 19`. That upward flow is exactly what "synthesized" means, and the annotated tree is the picture examiners draw when they ask you to evaluate one.
Three-address code: the intermediate representation
Before optimization, the compiler lowers the tree into an intermediate representation. The most common one is three-address code, where every instruction has at most one operator and at most three addresses, two operands and one result. Complex expressions are broken into temporaries.
For the assignment `a = b * c + b * d`, the three-address code is:
t1 = b * c
t2 = b * d
t3 = t1 + t2
a = t3Each line is simple enough for a machine to translate almost directly, and the flat, uniform shape is what makes the optimizer's job tractable. Three-address code is usually stored as quadruples or triples, and questions on those representations are common.
Machine-independent optimizations
Machine-independent optimizations improve the intermediate code without knowing anything about the target processor. Four of them appear again and again. Here is a single before-and-after that contains all four.
Before optimization:
a = 3 + 4
b = a * k
c = a * k
d = 0
L1: t = b + 2
s[i] = t + c
i = i + 1
if i < n goto L1After optimization:
a = 7
b = a * k
c = b
t = b + 2
L1: s[i] = t + c
i = i + 1
if i < n goto L1Constant folding evaluated `3 + 4` at compile time, so `a = 7`.
Common subexpression elimination noticed that `a * k` is computed twice with no change in between, so `c` simply reuses the value already in `b`.
Loop-invariant code motion saw that `t = b + 2` does not depend on the loop variable `i`, so it hoisted the computation out of the loop, where it runs once instead of every iteration.
Dead code elimination removed `d = 0`, because `d` is never read again and the assignment cannot affect the result.
Two more you should know by name are strength reduction, replacing an expensive operation with a cheaper one such as turning a multiplication inside a loop into repeated addition, and copy propagation, replacing uses of a copied variable with the original. Each optimization must be safe: it may never change what the program computes.
How this is tested in GATE
GATE Computer Science treats compilers as a scoring subject, and syntax-directed translation plus optimization are its most reliable question sources. Expect to be handed an SDD and asked for the value an attribute takes at the root, or to classify attributes as synthesized or inherited, or to say whether a grammar is S-attributed or L-attributed. Optimization questions typically show a code fragment and ask which instructions a specific optimization would remove or move, or how many are left after dead code elimination. The KnowledgeGate published question bank carries more than 700 Compiler Design questions, with dedicated pools on semantic analysis and SDT, intermediate code generation, and code optimization, so there is plenty to drill on exactly these patterns.
The short version
Attributes carry meaning through the parse tree: synthesized values flow up from children, inherited values flow down from parents. Three-address code flattens expressions into simple instructions, and machine-independent optimizations rewrite those instructions to do less work while computing the same result. Learn to annotate a parse tree by hand and to spot the four core optimizations in a fragment, and this becomes marks you can count on.
Work the topic with solved examples on the code optimization learn module and the semantic analysis and SDT module.
For the whole GATE CS syllabus in sequence, GATE Guidance by Sanchit Sir places compilers alongside theory of computation and the rest.
Grammars sit underneath parsing, so pair this with our context-free grammars and pushdown automata deep-dive, and browse more explainers on the CS Fundamentals category.
