Syntax-Directed Translation and Semantic Analysis (part 1: 4.1–4.4)
Open in the Padhaiko app4.1 Syntax-directed definitions (SDD) and syntax-directed translation (SDT)
While a context-free grammar specifies the syntactic structure of a programming language, it cannot by itself specify meaning, type rules, or target code generation. Syntax-directed translation attaches semantic information (attributes) and translation actions directly to grammar productions so that parsing and semantic processing proceed in a unified framework.
Syntax-Directed Definition (SDD)
A Syntax-Directed Definition (SDD) is a context-free grammar together with attributes and semantic rules.
- Attributes are associated with grammar symbols (terminals and nonterminals) and hold computed semantic values such as types, numerical values, memory offsets, or code fragments.
- Semantic rules are associated with grammar productions and express how the attribute values of symbols in the production relate to one another, without prescribing a rigid execution order.
Syntax-Directed Translation Scheme (SDT)
A Syntax-Directed Translation Scheme (SDT) is a context-free grammar in which program fragments (called semantic actions) are embedded directly inside the right-hand sides of productions, enclosed in curly braces { ... }. Unlike an SDD, an SDT explicitly specifies the exact order in which semantic actions are executed relative to parsing steps (typically left-to-right during a depth-first traversal).
| Aspect | Syntax-Directed Definition (SDD) | Syntax-Directed Translation Scheme (SDT) |
|---|---|---|
| Specification Style | Declarative: rules state what attribute values mean without fixing evaluation order | Procedural: semantic actions are placed at specific positions inside production RHS |
| Side Effects | Best suited for pure functional computations (minimal or implicit side effects) | Directly supports side effects such as emitting code, updating symbol tables, or printing |
| Implementation | Evaluated via dependency graphs, topological sorting, or specialized evaluator passes | Implemented directly inside recursive-descent or LR shift-reduce parsers |
| Readability | Higher-level and easier for humans to verify mathematically | Closer to actual compiler implementation |
4.1.1 Annotated Parse Trees and Dependency Graphs
When semantic rules are evaluated for an input string, each node in the parse tree is decorated with its computed attribute values, forming an annotated parse tree.
- Dependency Graph: A directed graph whose vertices represent all attribute instances in the parse tree. If rule defines attribute from , a directed edge is drawn for each .
- Evaluation Order: Any topological sort of the dependency graph yields a valid order in which attributes can be evaluated without referencing an uncomputed value. If the dependency graph contains a cycle, no valid evaluation order exists and the SDD is ill-defined for that input.
4.1.2 Classes of SDDs: S-Attributed and L-Attributed
Evaluating arbitrary dependency graphs at compile time is expensive. Practical compilers restrict SDDs to two well-behaved subclasses that allow single-pass evaluation during parsing:
| Property | S-Attributed SDD | L-Attributed SDD |
|---|---|---|
| Allowed Attributes | Only synthesized attributes | Synthesized attributes, plus inherited attributes restricted to depend only on left siblings and parent |
| Information Flow | Strictly bottom-up (children to parent) | Left-to-right and top-down/bottom-up |
| Evaluation Strategy | Single bottom-up pass (post-order traversal of parse tree) | Single depth-first left-to-right traversal of parse tree |
| Parser Compatibility | Natural fit for LR (bottom-up) parsers using a value stack | Natural fit for LL (top-down) parsers; convertible for LR if actions appear at production ends or via marker nonterminals |
4.2 Synthesized and inherited attributes
Attributes attached to a grammar symbol in a parse tree are partitioned into two disjoint classes according to how their values are computed.
Synthesized and Inherited Attributes
- Synthesized Attribute: An attribute at parse-tree node (labeled ) is synthesized if its value is computed solely from the attribute values of the children of and of itself. For a production , a rule defining has the form:
- Inherited Attribute: An attribute at parse-tree node (labeled ) is inherited if its value is computed from the attribute values of the parent of , the siblings of , and itself. For a production , a rule defining uses attributes of and .
4.2.1 Synthesized Attributes in Practice
Synthesized attributes naturally express bottom-up computations such as evaluating arithmetic expressions:
| Production | Semantic Rule |
|---|---|
4.2.2 Inherited Attributes and the L-Attributed Condition
Inherited attributes are essential when context flows downward or left-to-right in the parse tree:
- Type Declarations: In
int a, b, c;, the keywordintappears on the left, while the identifier lista, b, clies in a subtree to the right. An inherited attribute passes the base type down the list: - Top-Down Expression Evaluation (Eliminating Left Recursion): After eliminating left recursion from , the transformed grammar , separates the left operand from the operator and right operand . An inherited attribute carries the accumulated left operand down into :
Formal L-Attributed Rule: In a production , an inherited attribute in an L-attributed SDD may depend only on:
- Inherited attributes of the parent .
- Any attributes (inherited or synthesized) of symbols strictly to the left of .
- Attributes of itself, provided they form no cycle among 's own attributes.
| Aspect | Synthesized Attributes | Inherited Attributes |
|---|---|---|
| Direction of Flow | Bottom-up (from children to parent) | Top-down and sideways (from parent or siblings to child) |
| Primary Use Cases | Expression evaluation, AST construction, type inference of expressions | Propagating declaration types, passing left operands after left-recursion removal, scope context |
| Start Symbol | Can have synthesized attributes | Cannot receive inherited attributes from a parent (root has no parent) |
| Terminal Symbols | Supplied by lexical analyzer (lexval) | Not applicable (terminals have no inherited attributes) |
4.2.3 Side Effects and Controlled Evaluation
Semantic rules sometimes invoke helper routines with side effects—for example, addType(id.entry, L.in) inserts a variable's type into the symbol table. In an SDD, side effects are safe only when they do not alter attributes read elsewhere or when evaluation order is fixed (e.g., converted to an SDT where the action executes at a precise point in a left-to-right depth-first parse).
4.3 Syntax tree construction
A parse tree contains redundant grammar scaffolding (unit productions such as and punctuation tokens). Compilers discard this clutter and build a compact Abstract Syntax Tree (AST) or Directed Acyclic Graph (DAG).
4.3.1 Constructor Functions for Syntax Trees
An SDD constructs syntax-tree nodes bottom-up using two standard helper functions:
mknode(op, left, right): Creates an interior operator node labeledopwith child pointersleftandright, and returns a pointer to the new node.mkleaf(id, entry)/mkleaf(num, val): Creates a leaf node for an identifier (pointing to its symbol tableentry) or a numeric constant (storingval), and returns a pointer to the leaf.
| Production | Semantic Rule |
|---|---|
For top-down () parsing without left recursion (, ), an L-attributed SDD passes the partial subtree down via :
Notice how each operator node is built immediately in left-associative order as tokens are consumed left-to-right.
4.3.2 Directed Acyclic Graphs (DAGs) for Expressions
A DAG generalizes a syntax tree by identifying and sharing common subexpressions within an expression or basic block. Instead of allocating a duplicate subtree whenever the same subexpression recurs, mknode (and mkleaf) checks an existing node table—often using a value-numbering hash table keyed by (op, left, right):
- If a node with identical
(op, left, right)already exists, return its pointer rather than creating a new node. - Otherwise, allocate the new node and record it in the table.
Syntax Tree (13 nodes) DAG (9 nodes, shared subexpressions)
(+) (+)
/ \ / \
(+) (*) (+) (*)
/ \ / \ / \ / \
a (*) (-) d | (*) | d
/ \ / \ | / \ |
a (-) b c a / (-)
/ \ / / \
b c b c4.4 Intermediate code generation
After syntax and semantic analysis, the compiler front-end lowers the AST/DAG into an Intermediate Representation (IR) before the back-end generates target assembly or machine code.
4.4.1 Role and Benefits of Intermediate Code
- Retargetability ( instead of ): Supporting source languages across target architectures without an IR requires monolithic compilers. With a shared IR, only front-ends and back-ends are needed ( components).
- Machine-Independent Optimization: Common subexpression elimination, dead-code elimination, and loop optimizations are implemented once on the IR rather than duplicated per CPU architecture.
- Abstraction Gap Bridging: High-level control constructs (
for,switch, nested expressions) are flattened into simple linear instructions suitable for instruction selection and register allocation.
4.4.2 Forms of Intermediate Representation
- Graphical Representations: Abstract Syntax Trees (ASTs) and DAGs capture hierarchical nesting and subexpression sharing.
- Postfix Notation (Reverse Polish Notation): Linearizes an expression by placing each operator immediately after its operands (e.g.,
(a + b) * cbecomesa b + c *), enabling stack-based evaluation without parentheses. - Three-Address Code (TAC): A linearized sequence of instructions resembling generic assembly language with explicit temporary variables.
Three-Address Code (TAC)
Three-Address Code (TAC) is a linear intermediate representation in which every instruction has at most one operator on the right-hand side and involves at most three addresses (two source operands and one destination result), typically of the form:
Complex expressions are decomposed into elementary steps using compiler-generated temporaries ().
Common Three-Address Instructions
- Binary assignment:
x = y op z(arithmetic or logical operatorop). - Unary assignment:
x = op y(e.g., unary minusuminus, logical negation, type conversion). - Copy statement:
x = y. - Unconditional jump:
goto L. - Conditional jump:
if x relop y goto LorifFalse x goto L. - Procedure call & return:
param x,call p, n,y = call p, n,return y. - Indexed & pointer assignments:
x = y[i],x[i] = y,x = &y,x = *y,*x = y.
4.4.3 Representations of Three-Address Code
In memory, a sequence of TAC statements is commonly stored using one of three tabular data structures:
| Representation | Fields per Instruction | How Temporary Results Are Referenced | Strengths & Weaknesses |
|---|---|---|---|
| Quadruples | (op, arg1, arg2, result) | Explicit temporary names (t1, t2) stored in the result field | Easy to reorder or delete instructions during optimization because moving an instruction does not break operand references; uses extra symbol-table space for temporaries |
| Triples | (op, arg1, arg2) | Implicitly by the statement index (0), (1) of the instruction that computes the value | Avoids generating explicit temporary names in the symbol table; hard to reorder instructions during optimization because moving a statement invalidates all index pointers |
| Indirect Triples | Triple table (op, arg1, arg2) plus a separate pointer list statement[i] | Operand fields point to fixed triple entries, while statement[] records execution order | Combines compact triple storage (no temporary names) with easy instruction reordering by swapping pointers in statement[] |
4.4.4 Translation of Control Flow and Backpatching
Translating boolean expressions and control-flow statements (if, if-else, while) into TAC requires jump targets (goto L) that may not yet be known when a branch instruction is first emitted (forward jumps).
Backpatching solves this in a single pass by maintaining lists of instruction indices whose jump targets remain unfilled:
makelist(i): Creates a new list containing only instruction indexiand returns a pointer to it.merge(p1, p2): Concatenates the lists pointed to byp1andp2and returns the combined list.backpatch(p, target): Insertstargetas the destination label for every jump instruction whose index appears in listp.
Each boolean expression carries two synthesized lists: (jumps taken when evaluates to true) and (jumps taken when evaluates to false). A marker nonterminal records the address of the next emitted instruction, allowing if, if-else, and while constructs to emit short-circuit jumping code in one pass without creating symbolic labels.
Worked Examples
1
Consider the L-attributed SDD for left-recursion-free arithmetic expressions:
Trace the top-down depth-first attribute evaluation for the expression (3 + 5) * 2 + 4 and verify the final .
Evaluating the Parenthesized Subexpression (3 + 5): In , the inner expression evaluates 3 + 5:
- Leftmost gives , so sets . Since , , giving .
- At : .
- In : evaluates
5(). Thus . - At : .
- Returning to the outer : .
Evaluating Multiplication (3 + 5) * 2:
- At outer : .
- At : , so .
- At : .
Evaluating Outer Addition + 4:
- At outer : .
- At : , so .
- At : .
Using left-to-right L-attributed evaluation, the subexpressions yield and via inherited attributes and , producing the final synthesized root value .
2
Construct both the Abstract Syntax Tree (AST) and the Directed Acyclic Graph (DAG) for the arithmetic expression:
List the sequence of mkleaf and mknode calls used to build the DAG via value numbering, and compute the percentage reduction in total nodes achieved by the DAG compared to the AST.
Counting Nodes in the Abstract Syntax Tree (AST): Without node sharing, every occurrence of an identifier and operator creates a distinct node:
- Leaf occurrences: .
- Operator occurrences: first , first , first , second , second , second .
- Total AST nodes .
Constructing the DAG via Value Numbering: Scanning the expression in bottom-up evaluation order (left-to-right):
- — creates node 1 (
a). - — hits existing node (shared).
- — creates node 2 (
b). - — creates node 3 (
c). - — creates node 4 (
b - c). - — creates node 5 (
a * (b - c)). - — creates node 6 (
a + a * (b - c)). - returns ; returns ; hits existing node (shared).
- — creates node 7 (
d). - — creates node 8 (
(b - c) * d). - — creates node 9 (root
+).
Total DAG nodes ( distinct leaves: ; distinct interior nodes).
Percentage Reduction in Node Count:
The AST requires nodes, whereas the DAG reduces the representation to nodes by sharing a and (b - c)—a reduction in node count.
3
Translate the assignment statement into Three-Address Code (TAC), and represent the resulting code using:
- Quadruples
- Triples
- Indirect Triples
Generating Three-Address Code (TAC): Breaking the expression into unary and binary operations with temporary variables:
(0) t1 = uminus c
(1) t2 = b * t1
(2) t3 = uminus c
(3) t4 = b * t3
(4) t5 = t2 + t4
(5) a = t5(Note: without DAG common-subexpression elimination, the two b * -c subexpressions produce distinct temporaries t1–t4.)
Quadruples Table: Each entry stores (op, arg1, arg2, result) with explicit temporary names:
| Index | op | arg1 | arg2 | result |
|---|---|---|---|---|
| 0 | uminus | c | — | t1 |
| 1 | * | b | t1 | t2 |
| 2 | uminus | c | — | t3 |
| 3 | * | b | t3 | t4 |
| 4 | + | t2 | t4 | t5 |
| 5 | = | t5 | — | a |
Triples and Indirect Triples: In triples, temporary names are dropped and results are referenced by instruction index (k):
| Index | op | arg1 | arg2 |
|---|---|---|---|
| (0) | uminus | c | — |
| (1) | * | b | (0) |
| (2) | uminus | c | — |
| (3) | * | b | (2) |
| (4) | + | (1) | (3) |
| (5) | = | a | (4) |
For Indirect Triples, we keep the same triple entries (0)–(5) and add an execution pointer array statement:
| Execution Step | Pointer to Triple |
|---|---|
statement[0] | (0) |
statement[1] | (1) |
statement[2] | (2) |
statement[3] | (3) |
statement[4] | (4) |
statement[5] | (5) |
The TAC instructions map directly into Quadruples (using t1–t5), Triples (using positional pointers (0)–(4)), and an Indirect Triple table pairing the triple array with the statement[0..5] pointer list.
Exercises
Practice Exercises — SDT and Intermediate Code Generation
Distinguish between an S-attributed definition and an L-attributed definition. Why can every S-attributed SDD be evaluated directly during bottom-up LR parsing, whereas an arbitrary L-attributed SDD may require grammar or parser adjustments?
Comparing S-Attributed and L-Attributed Definitions:
- An S-attributed SDD uses only synthesized attributes; information flows strictly from child nodes upward to parent nodes.
- An L-attributed SDD permits both synthesized attributes and inherited attributes, provided each inherited attribute of symbol in depends only on attributes of and of symbols to the left of .
Bottom-Up LR Compatibility: In an LR shift-reduce parser, the stack holds the symbols of the current right-hand side until a reduction occurs. At the moment of reduction, all synthesized attributes of the children in reside on the top of the value stack, making 's synthesized attributes trivial to compute. By contrast, an L-attributed rule for needs its value before is reduced—while is just beginning to be parsed—requiring either top-down LL parsing or marker nonterminals () in an LR grammar to trigger inherited-attribute actions early.
S-attributed SDDs use only synthesized attributes (strictly bottom-up), whereas L-attributed SDDs also allow left-to-right inherited attributes. Bottom-up LR parsers evaluate S-attributed rules cleanly upon reduction, while L-attributed rules align naturally with top-down LL parsing or require marker nonterminals in LR parsers.
Using an L-attributed SDD with positional bit weights—where integer bits at position contribute and fractional bits at depth to the right of . contribute —trace the synthesized and inherited attributes to evaluate the binary string 101.11 into decimal.
Evaluating the Integer Part 101: For the integer prefix 101 (bits at positions ):
- Leftmost bit
1: - Middle bit
0: - Rightmost bit
1: - Synthesized integer value: .
Evaluating the Fractional Part .11:
- An inherited depth attribute starts at immediately after the radix point
.:- First fractional bit
1at : contributes . - Passes inherited depth to the next bit
1: contributes . - Synthesized fractional value: .
- First fractional bit
Combining at Root :
The inherited positional attribute guides bit weights across the radix point, yielding , , and final decimal value .
Construct the Abstract Syntax Tree (AST) and the Directed Acyclic Graph (DAG) for the expression:
Determine how many nodes exist in the AST, how many exist in the DAG, and the percentage of nodes saved by sharing common subexpressions.
Counting Nodes in the AST: Without subexpression sharing, every token operand and operator generates a separate node:
- Leaves:
x,y,x,y,zleaf nodes. - Interior operator nodes: left
+, right+,*, root-operator nodes. - Total AST nodes .
Constructing the DAG: Applying mkleaf and mknode with value numbering:
- (node 1)
- (node 2)
- (node 3, represents
x + y) - Second
(x + y)reuses , , and returns existing node (shared). - (node 4)
- (node 5, represents
(x + y) * z) - (node 6, root)
Total DAG nodes ( distinct leaves and interior operator nodes).
Percentage of Nodes Saved:
The AST has nodes and the DAG has nodes, saving nodes ( reduction) by sharing x + y.
Translate the statement into Three-Address Code (without common-subexpression elimination), and write its Quadruples and Triples representations.
Generating Three-Address Code:
(0) t1 = a + b
(1) t2 = c - d
(2) t3 = t1 * t2
(3) t4 = a + b
(4) t5 = t3 + t4
(5) t = t5Quadruples and Triples Tables:
| Index | op | arg1 | arg2 | result |
|---|---|---|---|---|
| 0 | + | a | b | t1 |
| 1 | - | c | d | t2 |
| 2 | * | t1 | t2 | t3 |
| 3 | + | a | b | t4 |
| 4 | + | t3 | t4 | t5 |
| 5 | = | t5 | — | t |
| Index | op | arg1 | arg2 |
|---|---|---|---|
| (0) | + | a | b |
| (1) | - | c | d |
| (2) | * | (0) | (1) |
| (3) | + | a | b |
| (4) | + | (2) | (3) |
| (5) | = | t | (4) |
The -instruction TAC translates directly into Quadruple rows (using explicit temporaries t1–t5) and Triple rows (referencing prior instructions by (0)–(4)).
Explain the three helper operations used in backpatching (makelist, merge, and backpatch), and generate three-address code starting at address 100 for the control-flow statement: while (a < b) { if (c < d) x = y + z; else x = y - z; }
Backpatching Operations:
makelist(i): Creates a new list containing only the instruction indexi.merge(p1, p2): Combines the jump listsp1andp2into a single list.backpatch(p, target): Fillstargetas the jump destination address for every instruction in listp.
Generating Three-Address Code Starting at Address 100:
100: if a < b goto 102
101: goto 110
102: if c < d goto 104
103: goto 107
104: t1 = y + z
105: x = t1
106: goto 100
107: t2 = y - z
108: x = t2
109: goto 100
110: (next statement after while)Here backpatch(B1.truelist, 102) fills 100, backpatch(B2.truelist, 104) fills 102, backpatch(B2.falselist, 107) fills 103, backpatch(S.nextlist, 100) fills 106 and 109, and backpatch(B1.falselist, 110) fills 101.
Backpatching resolves forward jump targets in a single pass via makelist, merge, and backpatch, producing the compact -instruction TAC sequence from address 100 to 109 with loop exit at 110.