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

Updated 6 Nov 20266 min read
Semantic Analysis and SDT Formula Sheet and Revision Notes: Attributes, Type Rules and Worked Trace

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 break is permitted.

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 place.

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 -> X1 X2 ... Xn, an inherited attribute of Xi may use inherited context of A and attributes of X1 ... X(i-1), never a right sibling. Use for left-to-right evaluation.

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:

Code
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 -> epsilon

For 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:

Code
T.type -> L.in
L.in -> rate.declType
L.in -> R0.in
R0.in -> total.declType
R0.in -> R1.in

One 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.

Dependency graph for float rate,total: a parse tree beside six attribute boxes linked by arrows from T.type through L.in to declaration types and R1.in.

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, join returns float.

  • An int may widen to float through an explicit inttofloat node.

  • Assignment accepts equal types or int -> float, but rejects implicit float -> 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.

Annotated assignment tree for total = 13.0, showing float widening of units and bonus, intermediate values 10.0 and 3.0, and final addition.

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:

Code
t1 = inttofloat units
t2 = rate * t1
t3 = inttofloat bonus
t4 = t2 + t3
total = t4

Trace 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:

  1. SDD is not synonymous with SDT.

  2. Inherited does not automatically mean L-attributed.

  3. Every S-attributed definition is L-attributed under the standard definition.

  4. Dependency arrows run from input to result.

  5. A topological order may be non-unique.

  6. Parsing success does not guarantee type correctness.

  7. 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

  1. tree + symbols + rules -> annotated tree or error.

  2. SDD states equations.

  3. SDT places actions.

  4. Synthesised information moves towards a parent.

  5. Inherited information obeys dependency restrictions.

  6. Draw dependency -> dependent.

  7. An acyclic graph has a topological order.

  8. 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.