Semantic Analysis and SDT Formula Sheet and Revision Notes: Attributes, Type Rules and Worked Trace
Keep SDD, SDT, attribute flow, dependency order and type coercion straight with one worked assignment that ends at total = 13.0 and five TAC instructions.
KnowledgeGate Team
Exam prep & CS education

You may remember that synthesised attributes go up and inherited attributes come down, yet still confuse an SDD with an SDT, reverse a dependency arrow, or insert a conversion after the operator that needs it. Semantic analysis ties those distinctions to dependency order, type checking and TAC generation through one assignment. Keep one invariant in sight throughout: after legal widening and evaluation, the worked program must finish with total = 13.0.
Earlier concept-first traces use 3 * 5 + 4, binary numerals and inherited types. Read Semantic Analysis and SDT: 3 Worked GATE Examples and Attributes & SDT Types in Compiler Design: Worked Trace for those demonstrations; the dependency graph, explicit coercions and the float/int trace ending at total = 13.0 are developed below.
1. Semantic Analysis Formula Sheet: Input, Output and Static Checks
Semantic analysis checks meaning beyond grammar:
AST or parse tree + symbol table + language rules -> annotated tree or semantic diagnostics
Check | When to use it |
|---|---|
Declaration binding | Connect name and declaration. |
Nearest-visible-scope lookup | Select nearest visible declaration. |
Operand compatibility | Check operator operands. |
Assignment compatibility | Check RHS against LHS. |
Function-argument matching | Match actuals and formals. |
Lvalue check | Require a writable target. |
Return-type check | Match expression and function return types. |
Context check | Ensure |
The language decides conversions and context rules. Use float rate, total; int units, bonus; total = rate * units + bonus;. In scope B0: rate -> float, total -> float, units -> int, bonus -> int. For the separate value trace: rate = 2.5, units = 4, bonus = 3; total is unassigned. The dependency graph and worked trace below apply these bindings.
2. SDD Versus SDT: The Rule That Computes and the Action That Runs
SDD: syntax-directed definition | SDT: syntax-directed translation scheme |
|---|---|
A CFG plus attributes and semantic equations. Use it when values or types must be associated with parse-tree nodes. | Executable semantic actions placed inside production bodies. Use it when action timing or emitted output matters. |
An equation describes a dependency. An action's textual position constrains when it runs.
For 6 + 7, the SDD production E -> E1 + T has E.val = E1.val + T.val. With E1.val = 6 and T.val = 7, E.val = 6 + 7 = 13.
For postfix SDT, operand actions print 6 and 7, then E -> E1 + T { print('+') } prints the operator, producing 6 7 +. The action follows both operands because it needs their translations first. Semantic rules need not print or mutate state.
3. Attribute Rules: Synthesised, Inherited, S-Attributed and L-Attributed
Attribute or class | Rule and use |
|---|---|
Synthesised | Computed from children and permitted inherited context; conventionally moves upward. Use for values, types, code and |
Inherited | Receives parent or permitted sibling context; conventionally moves down or sideways. Use for declaration types, environments and offsets. |
S-attributed | Uses only synthesised attributes. Use for postorder evaluation or bottom-up reductions. |
L-attributed | In |
A terminal's literal value or symbol-table entry is an intrinsic input, not something the grammar magically computes. Every S-attributed definition is L-attributed under the standard rule.
Use this declaration SDD:
D -> T L L.in = T.type
T -> float T.type = float
L -> id R id.declType = L.in; R.in = L.in
R -> , id R1 id.declType = R.in; R1.in = R.in
R -> epsilonFor float rate, total, left-to-right context gives both identifiers declType = float.
4. Dependency Graph and Evaluation Order: Draw the Arrow From Cause to Result
Create one node for every attribute occurrence. Add x -> y whenever the equation computing y reads x. The arrow therefore runs from dependency to dependent. An acyclic graph has at least one topological evaluation order, which may not be unique. A directed cycle has no ordinary topological order. Production text order alone is not an SDD evaluation order.
For float rate, total, the six nodes end as T.type = float, L.in = float, rate.declType = float, R0.in = float, total.declType = float and R1.in = float. The edges are:
T.type -> L.in
L.in -> rate.declType
L.in -> R0.in
R0.in -> total.declType
R0.in -> R1.inOne valid order is T.type, L.in, rate.declType, R0.in, total.declType, R1.in. The rate.declType and R0.in steps may swap without breaking a dependency.

5. Fully Worked Semantic Trace: Type rate * units + bonus and Get 13.0
First fix the rules of this deliberately small teaching language. They are not universal programming-language rules.
join(int,int) = int.If either numeric operand is
float,joinreturnsfloat.An
intmay widen tofloatthrough an explicitinttofloatnode.Assignment accepts equal types or
int -> float, but rejects implicitfloat -> int.
Multiplication binds before addition, so the tree shape is =(total, +(*(rate, units), bonus)).
Now type it bottom-up. rate is float and units is int, so insert inttofloat(units). Their product is float. The product is then combined with bonus:int, so insert inttofloat(bonus). The addition is float, and its type matches total:float. The exact annotated tree is:
=(total:float, +:float(*:float(rate:float, inttofloat(units:int)), inttofloat(bonus:int)))
The compiler can determine these types and conversions while translating, but it cannot know the sample runtime values. Trace those separately: rate = 2.5; inttofloat(units) = 4.0; therefore 2.5 * 4.0 = 10.0. Next, inttofloat(bonus) = 3.0, so 10.0 + 3.0 = 13.0. Assignment is legal, giving total = 13.0.
Contrast units = rate * 2;. Under the same rules, the right side is float, with sample value 2.5 * 2.0 = 5.0. Assigning it to units:int would require forbidden implicit narrowing. A parser can accept the grammar while semantic analysis rejects the statement.

6. Turn the Same Rules Into an SDT and Five Lines of TAC
Use type for result type, place for its location and code for generated instructions. newtemp() creates a temporary. emit() adds one TAC instruction. coerce(x, int, float) emits inttofloat, then returns the float temporary.
For a binary operator, translate both children, find their join type, coerce a narrower operand, then emit the operator. For assignment, check compatibility before the final copy. A postfix action for synthesised results follows the right-hand-side symbols it reads. An inherited-value action precedes the symbol that needs it.
The assignment generates exactly five instructions:
t1 = inttofloat units
t2 = rate * t1
t3 = inttofloat bonus
t4 = t2 + t3
total = t4Trace runtime values separately: t1 = 4.0; t2 = 2.5 * 4.0 = 10.0; t3 = 3.0; t4 = 10.0 + 3.0 = 13.0; total = 13.0. Each conversion precedes the arithmetic instruction that consumes it. The names and mnemonics are teaching choices, not universal notation.
7. How Questions Test the Sheet, Plus Seven Traps to Audit
Questions may ask: compute a root attribute, annotate a tree, classify an SDD, direct dependency edges, find an order or cycle, place an action, insert coercions, detect a semantic error or generate TAC.
For A -> B C, B.in = A.in can satisfy the L-attributed restriction. B.in = C.syn violates it because C is a right sibling.
Audit seven traps:
SDD is not synonymous with SDT.
Inherited does not automatically mean L-attributed.
Every S-attributed definition is L-attributed under the standard definition.
Dependency arrows run from input to result.
A topological order may be non-unique.
Parsing success does not guarantee type correctness.
Conversion legality comes from the stated language, not personal habit.
KnowledgeGate has over 50 practice questions for this topic. Use Attributes and SDT Types MCQs for classification and evaluation-order practice.
8. The Five-Minute Semantic Analysis and SDT Revision Card
tree + symbols + rules -> annotated tree or error.SDD states equations.
SDT places actions.
Synthesised information moves towards a parent.
Inherited information obeys dependency restrictions.
Draw
dependency -> dependent.An acyclic graph has a topological order.
Coerce before emitting the operator.
Check 2.5 * 4.0 + 3.0 = 13.0 and five TAC lines. The short version: classify dependencies first, then type and translate. Use the Compiler Design course for structured study, or browse GATE, PSU and Technical Exams for CS fundamentals.
Keep learning
Semantic Analysis and SDT in Compiler Design: Attributes, Worked Examples, and How GATE Tests It
Learn how semantic analysis validates meaning, how SDDs and SDTs evaluate attributes, and how to trace two common exam-style problems to their final answers.
Intro to Compilers Formula Sheet and Revision Notes: Six Phases in One Worked Trace
Revise the compiler pipeline as one connected system. This formula sheet follows a C-style statement from preprocessing and tokens to typed IR, optimisation and target code.
Top-Down Syntax Analysis Formula Sheet: FIRST, FOLLOW, LL(1) and Predictive Parsing Revision Notes
Revise top-down parsing as one connected workflow, from grammar rewriting and FIRST/FOLLOW sets to an LL(1) table and a complete stack trace.
Lexical Analysis Formula Sheet: Tokens, Regular Expressions and DFA Revision Notes
Keep the rules that matter under time pressure in one place, then apply them to regex counting, DFA construction, a 17-character scanner trace, and fallback.





