GATE CS & DA Preparation Guide Module 7 – Theory of computation and compiler design (CS sections 6-7)

SDT, runtime environments and data-flow analysis

Evaluate syntax-directed definitions, trace scoping and parameter passing, build DAGs and three-address code, and run liveness and constant propagation.

Advanced
20 minutes
Examples run with Python 3.14.8 and Pyodide 314.0.7
By MySmartCoPilot

Free: A synthesized attribute is computed after its children · Static scoping follows the program text, dynamic scoping the calls · Three-address code splits into basic blocks at its leaders · 2 more sections. With a pass: 3 in-depth parts and 3 interview answers, about 13 minutes.

What you will learn

Evaluate S- and L-attributed syntax-directed definitions on parse trees
Describe activation records, parameter passing and static versus dynamic scoping
Generate three-address code, quadruples, DAGs and SSA-style code for expressions and control flow
Run constant propagation, liveness analysis and common-subexpression elimination on basic blocks and control-flow graphs

Before you start

Lexing and parsing: FIRST, FOLLOW, LL(1) and LR

What you’ll learn · Before you start

What you will learn

Evaluate S- and L-attributed syntax-directed definitions on parse trees
Describe activation records, parameter passing and static versus dynamic scoping
Generate three-address code, quadruples, DAGs and SSA-style code for expressions and control flow
Run constant propagation, liveness analysis and common-subexpression elimination on basic blocks and control-flow graphs

Before you start

Lexing and parsing: FIRST, FOLLOW, LL(1) and LR

On this page

A parser can work out that the binary numeral 1011 is 11: attach N.val = 2 × N₁.val + B.val to the rule N → N B, and the values 1, 2, 5 and 11 appear as the rules are reduced. Syntax-directed translation (SDT) attaches such attributes to grammar symbols and semantic rules to productions, so that parsing also computes a value, a type or intermediate code. An S-attributed definition uses only synthesized attribute: An attribute of a parse-tree node computed from the attributes of its children, such as N.val = 2 × N₁.val + B.val. It is evaluated in post-order, as an LR parser reduces., computed from a node’s children, and can run during an LR parse. An L-attributed definition may also pass inherited attribute: An attribute of a parse-tree node computed from its parent or its siblings, which passes information down the tree, such as a declared type handed to a list of names. down from a parent and from left siblings, and runs in one depth-first, left-to-right walk.

Runtime environments keep each call’s data in an activation record: The memory one call of a procedure gets on the stack: its parameters, locals and temporaries, the return address, saved registers, and links to other records. on a stack: parameters, locals, the return address and links. The compiler then writes intermediate code, usually three-address code, splits it into basic block: A run of instructions that control enters only at the first and leaves only at the last. A block starts at a leader: the first instruction, a jump target or the instruction after a jump. and improves it with data-flow analysis, which computes facts such as the variables live variable: A variable is live at a point when some path from there reads it before any assignment to it. Liveness analysis computes this backward, combining paths with union. at each point. Every value below comes from a program you can run.

A synthesized attribute is computed after its children

An SDT is evaluated where a parser would evaluate it: a synthesized attribute after its children, which is post-order. Step through the tree of 1011:

Interactive · step by step N.val for 1011, evaluated in post-order Step through the evaluation. A node's second line shows its value once its children have theirs, as an LR parser reduces.

The drawing shows the whole scene; its 9 steps are listed below.

Every step as text

A tree that leans left. Each use of N → N B adds one bit on the right, so the first bit of 1011 is the deepest node and the last bit hangs from the root.
B → 1. Post-order starts at the deepest leaf. The first bit gives B.val = 1.
N → B. N → B copies its child's value, so N.val = 1 for the prefix 1.
B → 0. The next leaf in post-order is the second bit, B.val = 0.
N → N B. Both children of this N now have values, so N.val = 2 × 1 + 0 = 2 for the prefix 10.
B → 1. The third bit, B.val = 1.
N → N B. N.val = 2 × 2 + 1 = 5 for the prefix 101. Each new bit doubles what came before and adds itself.
B → 1. The last bit, B.val = 1.
The root, last. N.val = 2 × 5 + 1 = 11, the value of 1011. Every node got its value after its children, the order in which an LR parser reduces, which is why an S-attributed definition can run during the parse.

The program runs the same definition, then a second one that prints as it reduces, for two made-up operators, # and &:

A value computed bottom-up, and the output of print actions Python · sdt_eval.py

"""Two S-attributed definitions, evaluated on parse trees in post-order, as a bottom-up parser would."""


# 1. Binary numerals: N -> N B { N.val = 2 * N1.val + B.val } | B { N.val = B.val }, B -> 0 | 1.
def binary_value(bits):
    value, steps = None, []
    for bit in bits:  # the tree of N -> N B leans left, so post-order visits the bits left to right
        b = int(bit)
        steps.append(f"B -> {bit}: B.val = {b}")
        if value is None:
            value = b
            steps.append(f"N -> B: N.val = {value}")
        else:
            value = 2 * value + b
            steps.append(f"N -> N B: N.val = 2 x {(value - b) // 2} + {b} = {value}")
    return value, steps


value, steps = binary_value("1011")
print("1011, attributes in the order they are computed:")
for step in steps:
    print("  " + step)


# 2. A translation scheme with print actions, for invented operators # and &:
#    E -> E # T { print '#' } | T     T -> T & F { print '&' } | F     F -> num { print num }
# & is lower in the grammar, so it binds more tightly; both operators group from the left.
def parse_and_print(tokens):
    printed = []
    pos = 0

    def factor():
        nonlocal pos
        printed.append(tokens[pos])  # F -> num { print num }
        pos += 1

    def term():
        nonlocal pos
        factor()
        while pos < len(tokens) and tokens[pos] == "&":
            pos += 1
            factor()
            printed.append("&")  # T -> T & F { print '&' }, run when the rule is reduced

    def expr():
        nonlocal pos
        term()
        while pos < len(tokens) and tokens[pos] == "#":
            pos += 1
            term()
            printed.append("#")  # E -> E # T { print '#' }

    expr()
    return " ".join(printed)


for text in ("2 # 3 & 4 # 5", "2 & 3 & 4 # 5", "7"):
    print(f"{text:15} prints {parse_and_print(text.split())}")

Output

1011, attributes in the order they are computed:
  B -> 1: B.val = 1
  N -> B: N.val = 1
  B -> 0: B.val = 0
  N -> N B: N.val = 2 x 1 + 0 = 2
  B -> 1: B.val = 1
  N -> N B: N.val = 2 x 2 + 1 = 5
  B -> 1: B.val = 1
  N -> N B: N.val = 2 x 5 + 1 = 11
2 # 3 & 4 # 5   prints 2 3 4 & # 5 #
2 & 3 & 4 # 5   prints 2 3 & 4 & 5 #
7               prints 7

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 sdt_eval.py

The print actions produce postfix: an action runs only when its rule is reduced, after both operands have been printed. Two facts about the grammar decide the order. & sits lower in the grammar, so it binds more tightly: 2 # 3 & 4 # 5 prints 2 3 4 & # 5 #. Both rules are left-recursive, so both operators group from the left, which is why 2 & 3 & 4 # 5 prints 2 3 & 4 & 5 #. A question on the output of an SDT is exactly this: find the parse tree, then read the actions in post-order.

Checkpoint

Check: Synthesized attributes in post-order

Question 1 of 2 In an S-attributed definition, when is the synthesized attribute of a node computed?
Choose one answer.

In any order, since attributes never depend on each other Only after the whole tree has been built Before its children, in pre-order After the attributes of all its children, in post-order

Show the answer: Question 1 of 2

Answer: After the attributes of all its children, in post-order

A synthesized attribute depends on the node's children, so a node is evaluated after them: post-order. In the parse of 1011 the values 1, 2, 5 and 11 appear in the order the rules are reduced.
Question 2 of 2 With E → E # T (print #), E → T, T → T & F (print &), T → F and F → num (print num), what is printed for 2 & 3 # 4 & 5?
Choose one answer.

# & 2 3 & 4 5 2 & 3 2 3 & 4 5 & 2 3 4 5 &

Show the answer: Question 2 of 2

Answer: 2 3 & 4 5 &

T → T & F groups the & terms first: (2 & 3) and (4 & 5). Then E → E # T joins them. Post-order prints 2 3 &, then 4 5 &, then #.

Static scoping follows the program text, dynamic scoping the calls

Each call gets an activation record, pushed on the stack when the call starts and popped when it returns. It holds the actual parameters, the local variables and temporaries, the return address, saved registers, a control link to the caller’s record and, in languages with nested procedures, an access link to the record of the enclosing procedure. Runtime environments also fix the scoping rule for names a procedure uses but does not declare. Under static scoping such a name refers to the declaration that encloses the procedure in the program text. Under dynamic scoping it refers to the most recent binding still active on the call stack. Step through one lookup by each rule:

Interactive · step by step Where show finds x, by each scoping rule Step through the call of change. show uses x without declaring it, and the two rules look it up along different links.

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text

change declares its own x. The global x is 10. The program calls change, whose activation record holds its own x = 20.
change calls show. show prints x but declares none. Its record has a control link to its caller, change. show was declared at the top level, so its defining environment is the global one.
Static scoping. Static scoping follows the program text, from show to where it was defined, so x is the global x and show prints 10.
Dynamic scoping. Dynamic scoping follows the calls instead. The most recent binding of x still on the stack is change's, so show prints 20.
reset assigns x = 5. change then calls reset, which assigns x = 5 without declaring x. Static scoping assigns the global x; dynamic scoping assigns change's x. The second show prints 5 under both rules.
After change returns. change's record is popped, and its x with it. The program's last show prints the global x, 5 under static scoping and 10 under dynamic scoping, which never touched it.

One program, static scoping against dynamic scoping Python · scoping.py

"""One invented program, run by a small interpreter under static scoping and under dynamic scoping."""
import re

PROGRAM = """
var x = 10
proc show { print x }
proc reset { x = 5 }
proc change { var x = 20 ; show ; reset ; show }
proc outer { var x = 30 ; proc inner { print x } ; change ; inner }
change
outer
show
"""


def parse(tokens):
    # statements: var NAME = NUMBER | NAME = NUMBER | proc NAME { ... } | print NAME | NAME (a call)
    body = []
    while tokens and tokens[0] != "}":
        t = tokens.pop(0)
        if t in (";", "\n"):
            continue
        if t == "var":
            name, _, value = tokens.pop(0), tokens.pop(0), tokens.pop(0)
            body.append(("var", name, int(value)))
        elif t == "proc":
            name, _ = tokens.pop(0), tokens.pop(0)
            body.append(("proc", name, parse(tokens)))
            tokens.pop(0)  # the closing brace
        elif t == "print":
            body.append(("print", tokens.pop(0)))
        elif tokens and tokens[0] == "=":
            tokens.pop(0)
            body.append(("set", t, int(tokens.pop(0))))
        else:
            body.append(("call", t))
    return body


def lookup(env, name):
    while name not in env["vars"]:
        env = env["parent"]
    return env


def run(body, env, scoping, out):
    for stmt in body:
        kind, name = stmt[0], stmt[1]
        if kind in ("var", "proc"):
            env["vars"][name] = stmt[2] if kind == "var" else (stmt[2], env)  # a procedure keeps its definer
        elif kind == "set":
            lookup(env, name)["vars"][name] = stmt[2]
        elif kind == "print":
            out.append(lookup(env, name)["vars"][name])
        else:
            proc_body, defined_in = lookup(env, name)["vars"][name]
            parent = defined_in if scoping == "static" else env  # the one line where the two rules differ
            run(proc_body, {"vars": {}, "parent": parent}, scoping, out)


for scoping in ("static", "dynamic"):
    out = []
    tokens = re.findall(r"[A-Za-z]+|\d+|[{};=\n]", PROGRAM)
    run(parse(tokens), {"vars": {}, "parent": None}, scoping, out)
    print(f"{scoping:8} scoping prints: {' '.join(map(str, out))}")

Output

static   scoping prints: 10 5 5 5 30 5
dynamic  scoping prints: 20 5 20 5 30 10

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 scoping.py

The interpreter’s two rules differ in one line: a new environment’s parent is the defining environment, or the caller’s. Under static scoping, show and reset always use the global x, so reset changes it to 5 for good. Under dynamic scoping they use the x of change, the most recent binding, so the first show prints 20 and the global x is still 10 at the end. inner prints 30 under both rules, because outer is both its definer and its caller.

Activation records also hold the parameters, and the parameter-passing mode decides what each one is bound to. By value it is a copy; by reference, the argument’s location; by value-result, a copy written back on return; by name, the argument’s text, evaluated at every use.

Checkpoint

Check: Activation records, parameters and scoping

Question 1 of 2 A program declares var x = 1 at the top level, then proc p { print x } and proc q { var x = 2 ; p }, and calls q. What does it print under static scoping and under dynamic scoping?
Choose one answer.

1 under both rules 2 under both rules 1 under static scoping, 2 under dynamic scoping 2 under static scoping, 1 under dynamic scoping

Show the answer: Question 1 of 2

Answer: 1 under static scoping, 2 under dynamic scoping

The same shape as the lesson's program: p uses x without declaring it. Its definer is the top level, where x = 1, and its caller is q, where x = 2. Static scoping prints 1 and dynamic scoping prints 2.
Question 2 of 2 In a language with nested procedures, which part of an activation record does static scoping follow to find a variable declared in an enclosing procedure?
Choose one answer.

The access link The saved registers The control link The return address

Show the answer: Question 2 of 2

Answer: The access link

An activation record has a control link to the caller and, with nested procedures, an access link to the record of the enclosing procedure. Static scoping follows the access link; dynamic scoping follows the control links.

Three-address code splits into basic blocks at its leaders

Three-address code has at most one operator per instruction, such as t1 = b + c, with temporaries for intermediate values.
Quadruples store each instruction as operator, two arguments and a result; triples drop the result and refer to earlier instructions by number.
A DAG of a basic block gives each distinct computation one node, so repeated subexpressions appear once.
SSA form gives every assignment a new variable name and merges names at join points with φ-functions.
Basic blocks start at leaders, the first instruction, every jump target and every instruction after a jump, and a control-flow graph joins them by their jumps.

Step through the leaders of a summing loop, then see its blocks as a graph:

Interactive · stage by stage Four leaders split the summing loop into four blocks Step through the three rules for leaders. Each leader starts a basic block that runs to the next leader.

The drawing shows the whole scene; its 5 steps are listed below.

Every step as text

Eight instructions. The loop of the diagram below as three-address code. The two jumps are drawn on the right; every other instruction falls through to the next one.
The first instruction. Rule 1. The first instruction is a leader, so 0 starts a block.
Jump targets. Rule 2. Every target of a jump is a leader. goto 2 makes 2 a leader, and the conditional jump makes 7 a leader.
After a jump. Rule 3. The instruction right after a jump is a leader. After the conditional jump at 2 that is 3; after goto 2 at 6 it is 7, a leader already.
Four basic blocks. The leaders 0, 2, 3 and 7 start four blocks, B1 = 0 to 1, B2 = 2, B3 = 3 to 6 and B4 = 7, the four boxes of the control-flow graph below.

The four basic blocks of a summing loop and the edges between them

Text description of the diagram

The diagram shows four boxes joined by arrows:

B1 sets i = 0 and s = 0, and leads to B2.
B2 tests whether i < n. Its "true" edge leads to B3 and its "false" edge to B4.
B3 computes t = i * 2, then s = s + t, then i = i + 1, and a back edge leads from it to B2.
B4 prints s, and the program ends there.

Each box is a basic block: it starts at a leader and runs to the next one, and control enters it only at its first statement.

Checkpoint

Check: Three-address code and basic blocks

Question 1 of 2 How many basic blocks does this code have? (0) x = 0 (1) y = 1 (2) if x > 9 goto 6 (3) x = x + y (4) if y > 3 goto 2 (5) y = y + 1 (6) print x
Type a number.
Your answer blocks

Show the answer: Question 1 of 2

Answer: 5 blocks

The leaders are 0 (the first instruction), 2 and 6 (jump targets), and 3 and 5 (each follows a conditional jump). Five leaders start five blocks: 0 to 1, 2, 3 to 4, 5 and 6.
Question 2 of 2 What do triples leave out that quadruples keep?
Choose one answer.

The operator The result field; a later instruction refers to an earlier one by its number The second argument Nothing; triples and quadruples hold the same fields

Show the answer: Question 2 of 2

Answer: The result field; a later instruction refers to an earlier one by its number

Quadruples store operator, two arguments and a result; triples drop the result and refer to earlier instructions by number, so an argument such as (0) means the value of instruction 0.

Data-flow analysis repeats its equations until nothing changes

Data-flow analysis computes a set of facts at the entry and exit of every block of such a graph and repeats its equations until no set changes. For liveness the equations are in[B] = use[B] ∪ (out[B] − def[B]) and out[B] = the union of in[S] over the successors S of B, where use holds the variables read before any assignment in B and def the variables assigned in it. The syllabus’s three analyses differ in their direction and in how they combine facts that arrive along several paths.

The three data-flow analyses of the syllabus
Criterion	Liveness	Available expressions	Constant propagation
A fact is	A variable used later before it is redefined	An expression computed on every path, operands unchanged	A variable's value, if it is the same constant on every path
Direction	Backward	Forward	Forward
Paths combined by	Union	Intersection	The lattice meet: equal constants stay, others become not a constant
When to choose	Register allocation, dead-code removal	Global common-subexpression elimination	Folding constants, removing dead branches

Key idea

Liveness looks ahead to later uses, so it runs backward and one path is enough; available expressions and constant propagation look back at what came before, so they run forward and every path must agree.

Checkpoint

Check: Data-flow equations and their direction

Question 1 of 2 A block runs x = y + z, then y = x * 2, then z = w. Which variables are in its use set, the variables read before any assignment in the block?
Choose every answer that is right.

x w y z
Show the answer: Question 1 of 2
Answer:
- w
- y
- z
Walk the block in order and keep the variables read before the block assigns them: y and z in the first statement, nothing new in the second, w in the third. So use = {w, y, z} and def = {x, y, z}.
Question 2 of 2 To remove a second computation of a + b, a compiler must know that every path to it has computed a + b with unchanged operands. Which analysis answers this, and how does it combine paths?
Choose one answer.

Constant propagation, forward, with the lattice meet Liveness, backward, with union Available expressions, forward, with intersection Available expressions, forward, with union

Show the answer: Question 2 of 2

Answer: Available expressions, forward, with intersection

An expression is available when every path has computed it and none has changed an operand since. All paths must agree, so the meet is intersection, and the facts flow forwards from the computations.

Practise: leaders, scopes and data flow

Exercise · Easy · Python

Find the leaders of three-address code

Write leaders(code), which returns the indices of the leaders of a list of three-address instructions, in increasing order. Each leader starts a basic block, which runs up to the next leader.

An instruction is a leader when it is:

the first instruction of the code;
the target of a jump, written goto N or if ... goto N, where N is an index in the list;
the instruction right after a jump, whether the jump is conditional or not.

leaders(["i = 0", "if i >= n goto 4", "i = i + 1", "goto 1", "print i"])   # [0, 1, 2, 4]

Starter code · leaders.py

import re


def leaders(code):
    """The indices of the leaders of a list of three-address instructions, in increasing order.

    `code` is a list of strings. A jump is written "goto N" or "if ... goto N", where N is
    the index of the target instruction in the list.
    """
    # Replace this line with your code.
    return []

The sample tests · test_leaders.py

from leaders import leaders

LOOP = [
    "i = 0",                 # 0
    "if i >= n goto 6",      # 1
    "t = i * 4",             # 2
    "s = s + t",             # 3
    "i = i + 1",             # 4
    "goto 1",                # 5
    "print s",               # 6
]


def test_loop():
    """the first instruction, the jump targets 1 and 6, and the instruction after the jump at 1"""
    assert leaders(LOOP) == [0, 1, 2, 6]


def test_straight_line():
    """code without jumps is one basic block"""
    assert leaders(["a = 1", "b = a + 2", "c = b * b"]) == [0]


def test_jump_back_to_the_start():
    """a jump to instruction 0 adds nothing new, and the instruction after the jump leads"""
    assert leaders(["x = x - 1", "if x > 0 goto 0", "y = x"]) == [0, 2]


def test_jump_at_the_end():
    """a jump that is the last instruction has no instruction after it"""
    assert leaders(["a = 1", "b = 2", "goto 1"]) == [0, 1]


def test_empty():
    """no instructions, no leaders"""
    assert leaders([]) == []

A hint

Collect the leaders in a set, starting with 0 when the code is not empty. For each instruction, look for goto N with re.search(r"\bgoto (\d+)", line); when there is one, add N and, if the jump is not the last instruction, the index after it. Return the sorted set.

The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Intermediate code worked: DAGs, quadruples, triples and SSA Pro: opens with a Pro, Premium or Ultimate pass

Intermediate-code questions ask for node counts, instruction counts and the code that remains after optimisation. This part builds the DAG of an invented block by value numbering, writes one statement as quadruples and triples, puts a branch into SSA form and shows what a real compiler emits.

In this part:

A basic block as a DAG, and the code it gives back
Quadruples, triples and indirect triples for one statement
SSA form at a branch, worked
What a real compiler emits: stack code, and why it keeps both a + b

2 runnable examples (Python) · about 4 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Data-flow analyses run to a fixed point, with iteration tables Pro: opens with a Pro, Premium or Ultimate pass

Data-flow questions give a control-flow graph and ask for one set at one point, and the safe way to answer is to run the equations to a fixed point. This part runs liveness, available expressions and constant propagation on invented graphs, round by round.

In this part:

Liveness, round by round
Available expressions and global common subexpressions
Constant propagation on its lattice
One framework behind all three

3 runnable examples (Python) · about 6 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Runtime environments in depth: parameter passing, recursion and scoping, reproduced Pro: opens with a Pro, Premium or Ultimate pass

Output questions on runtime environments hinge on what a parameter is bound to and which record a name is found in. This part runs one procedure under four parameter-passing modes, counts the activation records of a recursion and traces the access links behind static scoping.

In this part:

Four parameter-passing modes on one call
Activation records of a recursion, counted
Access links and the scoping trap in nested procedures

2 runnable examples (Python) · about 4 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Interview questions

Fresher · Warm-up

What is the difference between S-attributed and L-attributed definitions?

An S-attributed definition uses synthesized attributes only: each node's attributes are computed from its children, so the definition is evaluated bottom-up, in post-order, for example while an LR parser reduces. An L-attributed definition also allows inherited attributes, provided each depends only on the parent's inherited attributes and on the attributes of siblings to its left. One depth-first walk from left to right then evaluates everything, which suits recursive-descent parsers, for example to pass a declared type down a list of names. Every S-attributed definition is L-attributed. A definition in which an attribute depends on a sibling to its right is neither, and needs a dependency graph to order its evaluation.
Fresher to mid

A short program prints different values under static and under dynamic scoping. Explain how each rule finds a variable that a procedure uses but does not declare, trace an example of your own with three procedures, and say why almost every modern language uses static scoping.

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Mid to senior

A loop on your hot path spills registers. How does liveness analysis tell you how many values need registers at each point? Compute the live sets of a small loop of your own, and say how the result guides the register allocator.

Model answer, Pro. First step and follow-ups
Fresher to mid

When may a compiler replace a second computation of a + b with the result of the first? Compare local elimination with a DAG and global elimination with available expressions, using an example where the global analysis must refuse.

Model answer, Pro. First step and follow-ups

Key takeaways

An S-attributed definition is evaluated in post-order, as an LR parser reduces; print actions in such a definition produce postfix order.
An activation record holds parameters, locals, the return address and links; static scoping finds an undeclared name in the enclosing text, dynamic scoping in the most recent active binding.
Leaders start basic blocks: the first instruction, every jump target and every instruction after a jump.
Liveness runs backward with union, available expressions forward with intersection, and constant propagation forward with the meet of its lattice.

Terms in this lesson

activation record: The memory one call of a procedure gets on the stack: its parameters, locals and temporaries, the return address, saved registers, and links to other records.
basic block: A run of instructions that control enters only at the first and leaves only at the last. A block starts at a leader: the first instruction, a jump target or the instruction after a jump.
inherited attribute: An attribute of a parse-tree node computed from its parent or its siblings, which passes information down the tree, such as a declared type handed to a list of names.
live variable: A variable is live at a point when some path from there reads it before any assignment to it. Liveness analysis computes this backward, combining paths with union.
synthesized attribute: An attribute of a parse-tree node computed from the attributes of its children, such as N.val = 2 × N₁.val + B.val. It is evaluated in post-order, as an LR parser reduces.

References

GATE 2027 syllabus, Computer Science and Information Technology (section 7, compiler design) (Indian Institute of Technology Madras (GATE 2027))
Semantics of context-free languages (D. E. Knuth) (Mathematical Systems Theory)
A unified approach to global program optimization (G. A. Kildall) (ACM, Symposium on Principles of Programming Languages)
Global data flow analysis and iterative algorithms (J. B. Kam and J. D. Ullman) (Journal of the ACM)
Efficiently computing static single assignment form and the control dependence graph (R. Cytron and others) (ACM Transactions on Programming Languages and Systems)
LLVM language reference manual (introduction: an SSA-based representation) (LLVM Project)
dis: disassembler for Python bytecode (Python Software Foundation)
Revised report on the algorithmic language ALGOL 60 (J. W. Backus and others, ed. P. Naur): call by name (Communications of the ACM)
Thunks: a way of compiling procedure statements (P. Z. Ingerman) (Communications of the ACM)
Using the GNU Compiler Collection: options that control optimization (-fgcse) (GNU Project, Free Software Foundation)
Bash reference manual: shell functions (local variables and dynamic scoping) (GNU Project, Free Software Foundation)
perlsub: temporary values via local() (Perl.org)
Common Lisp HyperSpec: declaration SPECIAL (LispWorks (the ANSI Common Lisp standard in hypertext))

Report a problem with this lesson

In this module: Theory of computation and compiler design (CS sections 6-7)

Regular languages: DFAs, NFAs, regex and pumping Free core, Pro depth: 7 of 20 minutes free
Context-free languages, PDAs, Turing machines Free core, Pro depth: 7 of 20 minutes free
Lexing and parsing: FIRST, FOLLOW, LL(1) and LR Free core, Pro depth: 7 of 20 minutes free
SDT, runtime environments and data-flow analysis Free core, Pro depth: 7 of 20 minutes free

Your country

SDT, runtime environments and data-flow analysis

What you will learn

Before you start

What you will learn

Before you start

A synthesized attribute is computed after its children

Static scoping follows the program text, dynamic scoping the calls

Three-address code splits into basic blocks at its leaders

Data-flow analysis repeats its equations until nothing changes

Practise: leaders, scopes and data flow

Find the leaders of three-address code

Results of the sample tests

Intermediate code worked: DAGs, quadruples, triples and SSA Pro: opens with a Pro, Premium or Ultimate pass

Data-flow analyses run to a fixed point, with iteration tables Pro: opens with a Pro, Premium or Ultimate pass

Runtime environments in depth: parameter passing, recursion and scoping, reproduced Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

What is the difference between S-attributed and L-attributed definitions?

A short program prints different values under static and under dynamic scoping. Explain how each rule finds a variable that a procedure uses but does not declare, trace an example of your own with three procedures, and say why almost every modern language uses static scoping.

A loop on your hot path spills registers. How does liveness analysis tell you how many values need registers at each point? Compute the live sets of a small loop of your own, and say how the result guides the register allocator.

When may a compiler replace a second computation of a + b with the result of the first? Compare local elimination with a DAG and global elimination with available expressions, using an example where the global analysis must refuse.

Key takeaways

References

Related tools