Semantic Analysis and SDT in Compiler Design: Attributes, Worked Examples, and How GATE Tests It

Semantic analysis is where compiler design stops being definitions and becomes computation. A question gives you a grammar with rules and expects a number, printed string, or decision about evaluability. Getting there means knowing which attribute flows up, which flows down, and exactly when each action fires.

Where semantic analysis sits and what it checks

Lexical analysis turns characters into tokens, as explained in Lexical Analysis in Compiler Design: Tokens to DFA Scanner. Syntax analysis checks those tokens against a grammar and builds a parse tree. Semantic analysis asks whether the syntactically legal program has valid meaning.

Its checks include:

• Type checking: Are operands compatible? Can a value be assigned to the target type? Does a function call use the right argument types and count?

• Declaration and scope checking: Was a name declared before use, and which declaration does it refer to in the current scope?

• Flow checking: Does break occur inside a loop or another construct where it is allowed?

These are static checks. Array bounds are checked dynamically in many languages. The phase produces an annotated syntax tree and updates the symbol table.

A syntax-directed definition, or SDD, attaches rules to grammar productions and says what to compute. A syntax-directed translation scheme, or SDT, embeds actions in production bodies and also fixes when they run.

Synthesized, inherited, S-attributed, and L-attributed definitions

A synthesized attribute is computed from a node's children, so information flows upward. A digit token's lexval is synthesized by convention. An inherited attribute comes from the parent and possibly left siblings, so information flows down or across.

An S-attributed SDD uses only synthesized attributes. It can be evaluated bottom-up during LR reductions. In an L-attributed SDD, each inherited attribute depends only on the parent's inherited attributes and symbols to its left. One left-to-right, depth-first traversal can evaluate it, which fits LL parsing.

Every S-attributed definition is therefore L-attributed. The converse is false because an L-attributed definition may use inherited attributes.

For a general SDD, build a dependency graph over attribute instances. An edge means one must be known before another. Evaluate in topological order; a cycle means no order exists. The attributes ride on the tree built during Parsing in Compiler Design: Top-Down and Bottom-Up Explained.

Worked example 1: evaluate 3 * 5 + 4

Use this S-attributed grammar:

E -> E1 + T  { E.val = E1.val + T.val }
E -> T       { E.val = T.val }
T -> T1 * F  { T.val = T1.val * F.val }
T -> F       { T.val = F.val }
F -> ( E )   { F.val = E.val }
F -> digit   { F.val = digit.lexval }

For 3 * 5 + 4, multiplication is at the T level and addition at the E level. The grammar groups the expression as (3 * 5) + 4.

Evaluate from the leaves upward:

1. The three digit tokens supply F.val = 3, F.val = 5, and F.val = 4.

2. On the left, T -> F first gives T.val = 3.

3. At T -> T1 * F, compute T.val = 3 * 5 = 15.

4. On the right branch, T -> F gives T.val = 4.

5. E -> T promotes the left subtree unchanged, so E1.val = 15.

6. At the root, E -> E1 + T computes E.val = 15 + 4 = 19.

The root holds 19. This is post-order evaluation: children before parent.

Worked example 2: inherited types and embedded actions

Now let type information flow down a declaration:

D -> T L     { L.inh = T.type }
T -> int     { T.type = integer }
T -> float   { T.type = float }
L -> L1 , id { L1.inh = L.inh; addType(id.entry, L.inh) }
L -> id      { addType(id.entry, L.inh) }

For float x, y, z, T.type = float, so the root receives L.inh = float. The root L spans the whole list and holds z, so the inherited value reaches z's node first, then y's, then x's, as each nested L1 copies it down. The addType calls run the other way. Each one sits at the end of its production, so the deepest node finishes first and the symbol table records x, then y, then z. A bottom-up parser agrees, because it reduces L -> id for x before either L -> L1 , id.

This is L-attributed because each inherited value depends only on its parent, but not S-attributed because L.inh is inherited. Bottom-up evaluation needs extra techniques such as marker nonterminals.

The second common SDT shape prints output. Consider an infix-to-postfix scheme:

E -> E + T { print("+") }
E -> T
T -> T * F { print("*") }
T -> F
F -> ( E )
F -> digit { print(digit.lexval) }

On 3 * 5 + 4, the actions print 3, 5, *, 4, then +. The exact output is 3 5 * 4 +.

An action runs when the parser reaches its position. These actions appear at the end, so they fire after their children. A mid-production action would run before symbols to its right. That position is the whole difference between an SDD and an SDT: both describe the same postfix string here, but only the SDT fixes the moment each print happens.

From attributes to syntax trees, DAGs, and three-address code

Semantic rules can build an intermediate representation. For example, E.node = new Node('+', E1.node, T.node) constructs an abstract syntax tree.

For a = b * c + b * c, a tree has two b * c subtrees. A DAG stores that common subexpression once. The tree translation produces:

t1 = b * c
t2 = b * c
t3 = t1 + t2
a = t3

Reusing the DAG node produces:

t1 = b * c
t2 = t1 + t1
a = t2

That is four instructions reduced to three, and three temporaries reduced to two. Quadruples and triples store three-address code; target-code generation belongs to the next phase.

Traps that cost marks

• Inherited does not mean non-L-attributed. L-attributed definitions allow inherited attributes under the parent-and-left restriction.

• S-attributed is a subset of L-attributed. The reverse claim is wrong.

• digit.lexval is synthesized. It is attached to a leaf and flows upward.

• Do not evaluate example 1 in-order. That can produce 3 * (5 + 4) = 27; post-order gives 19.

• Respect action position. A mid-production action fires before the remaining symbols are processed.

• Do not give an LR parser arbitrary inherited work. Inherited values need extra techniques.

• Coercion is not automatically an error. A checker may insert an allowed widening conversion such as integer to floating point.

• Keep static and dynamic checks separate. Bounds are commonly checked at runtime; declarations, scopes, and types at compile time.

• The symbol table is not owned by the parser. Multiple compiler phases create, query, and update it.

How GATE and interviews test semantic analysis and SDT

The question shapes are narrow. Compute an attribute's value at the root, trace what an embedded action prints, classify an SDD as S-attributed or L-attributed, collapse a repeated subexpression into a DAG, or write out three-address code. Check the exact syllabus and paper pattern on the official GATE website and in the organising institute's information brochure for that cycle.

Interviewers ask where an undeclared variable is caught, why a symbol table is needed, or how an expression becomes three-address code. Trace the worked tree aloud to make those answers concrete.

For timed practice, use the GATE Test Series: Mocks & Topic-wise Tests. The optimizer's side of this pipeline, including constant folding and common subexpression elimination applied to the three-address code you just generated, is worked through in Syntax-directed translation and code optimization in compilers explained.

The short version and your next step

Semantic analysis validates meaning through types, declarations, scopes, and the symbol table. SDDs attach computations to productions; SDTs also position their actions. Synthesized attributes flow up, while inherited attributes flow down and across. S-attributed definitions fit LR evaluation, and L-attributed definitions fit left-to-right LL evaluation. Follow post-order for values and dependency order for everything else.

Work both examples again on paper without the steps. Then study compiler design in sequence with Zero to Hero Complete CS Course, where semantic analysis sits inside the full pipeline.