Semantic Analysis and Syntax-Directed Translation: Worked Examples for GATE CS

A parser can accept a sequence of tokens without proving that the program makes sense. The same grammatical statement may use an undeclared name, combine incompatible types, or call a function with the wrong arguments. Semantic analysis supplies the missing bridge from structure to meaning. The exam-level difficulty is preserving dependency order: identify which fact exists first, evaluate each attribute only after its inputs, and execute each SDT action at its written position.

Where semantic analysis and SDT sit in the compiler

A useful local view of compilation is:

characters -> tokens -> parse tree -> annotated tree -> intermediate code

Lexical analysis in compiler design handles characters -> tokens. Parsing handles tokens -> parse tree. Once the grammar supplies structure, semantic analysis checks it against the language's meaning rules. Syntax-directed translation then uses that structure and its attributes to produce a translation.

Consider x = y + 1;. The statement may fit the assignment grammar perfectly, yet the semantic analyser must reject it if y has no visible declaration. Its main inputs are the parse tree or abstract syntax tree (AST) and the symbol table. Its outputs are an annotated tree, where nodes carry facts such as types, plus diagnostics for invalid constructs.

Semantic checks that give a parse tree meaning

Semantic analysis checks declaration before use, scope resolution, operand types, permitted conversions, function arguments, and l-values. An l-value check prevents assignment to an expression that does not denote a writable location.

Use this symbol-table snapshot at scope depth 0:

Now trace total = count + rate * 2.5. In this toy language, implicit int -> float widening is allowed, but implicit float -> int narrowing is not.

1. rate has type float, and 2.5 has type float.

2. Therefore, rate * 2.5 has type float.

3. count has type int, so it widens to float for the addition.

4. count + rate * 2.5 consequently has type float.

5. total expects float, so the assignment succeeds.

By contrast, count = total tries to place a float value into an int location. It fails unless the programmer writes an explicit permitted conversion. These conversion rules belong to this worked language, not to every programming language.

SDD, SDT, synthesized attributes, and inherited attributes

A syntax-directed definition (SDD) is a context-free grammar equipped with attributes and semantic rules. The rules specify attribute values and their dependencies. A syntax-directed translation scheme (SDT) places executable semantic actions inside production bodies, so their written positions also determine when they run during parsing.

A synthesized attribute flows from children to a parent. An inherited attribute reaches a child from its parent or a permitted left sibling. An S-attributed definition uses only synthesized attributes. An L-attributed definition permits inherited dependencies evaluated from left to right. Every S-attributed definition is L-attributed, but the reverse is false, and not every attribute grammar is L-attributed.

Worked example 1: synthesized attributes evaluate a binary numeral

Use this SDD for a binary numeral:

B -> B1 bit { B.val = 2 * B1.val + bit.lexval }
B -> bit    { B.val = bit.lexval }

Trace 1011 from left to right. The first bit gives B.val = 1. Appending 0 gives 2 * 1 + 0 = 2. Appending the next 1 gives 2 * 2 + 1 = 5. Appending the final 1 gives 2 * 5 + 1 = 11. The root attribute therefore stores the decimal value 11.

This definition is S-attributed because every B.val is synthesized from child values. Each reduction has both inputs available before it computes the parent, producing the dependency order 1, 2, 5, 11.

Worked example 2: an inherited attribute propagates a type

Now use this definition:

D -> T L       { L.in = T.type }
T -> float     { T.type = float }
L -> id R      { addType(id.entry, L.in); R.in = L.in }
R -> , id R1   { addType(id.entry, R.in); R1.in = R.in }
R -> epsilon

Trace float a, b, c from left to right. First, T.type = float, so the rule for D sets L.in = float. The action in L records a:float and passes R.in = float. The first R records b:float, then passes R1.in = float. The next R records c:float, and the final epsilon production ends the chain.

The dependency is L-attributed because each inherited value is available through a parent or left-to-right dependency when it is needed. The example is not S-attributed because in is inherited rather than synthesized.

Worked example 3: action placement in an SDT

This postfix SDT emits an operand when it is recognised and emits an operator after its operands:

E -> E + T { emit('+') } | T
T -> T * F { emit('*') } | F
F -> id    { emit(id.lexeme) }

For a + b * c, the exact output trace is:

1. Recognise a and emit a.

2. Recognise b and emit b, giving ab.

3. Recognise c and emit c, giving abc.

4. Reduce the multiplication and emit *, giving abc*.

5. Reduce the addition and emit +, giving abc*+.

Action placement is operational. Moving an action changes when it executes and may change the translation even if the grammar is unchanged. Continue with syntax-directed translation and code optimization to carry this idea into three-address code and optimization.

How exam-style questions test semantic analysis and SDT

Common practice questions ask you to compute a root attribute such as 11, classify an attribute as synthesized or inherited, decide whether a definition is S-attributed or L-attributed, find a valid dependency order, identify a semantic type error, or execute embedded actions to obtain abc*+. KnowledgeGate has over 700 Compiler Design questions live in its practice bank, so you can practise these forms without treating any one of them as a guaranteed official distribution.

Keep these traps separate:

• Parse success does not imply semantic correctness.

• An inherited attribute is not simply any value drawn downward. Its source and dependency restrictions matter.

• Every S-attributed definition is L-attributed, but the reverse is false.

• An SDD specifies dependencies, but it is not automatically an execution schedule.

• In the binary-numeral trace, each prefix value must be available before the next reduction can produce 1, 2, 5, 11.

The short version and the next practice step

Use this five-line recall sequence:

1. The symbol table supplies declared facts.

2. Semantic rules check constructs and annotate the tree.

3. Synthesized values move upward.

4. Inherited values move down or across under dependency restrictions.

5. SDT actions execute at their written positions.

Your three self-check answers are 11, the entries a:float, b:float, c:float, and the postfix output abc*+. For sequenced Compiler Design study, use GATE Guidance by Sanchit Sir. The GATE Test Series is the matching option for topic-wise testing, while the GATE category gives the broader preparation path.

Reproduce the binary-value sequence and redraw the attribute-dependency diagram from memory. Then solve one classification question and one SDT trace without notes.