Applications: building syntax trees; basic type checking (brief)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Where should the action computing an inherited attribute of X go in a translation scheme? from Lesson 3.3
• Which attributes flow up the tree, and which can come from the left sibling? from Lesson 3.1
• In E → E + T | T, T → T * F | F, which operator binds tighter, and why? from Lesson 2.1.2

1 · The Story

📖

An outline without the scaffolding

Kabir’s family charts are faithful but cluttered: boxes for every rule step, brackets, chains like E above T above F above a number. Dev in the Drafting Room says: “I only need who operates on whom.”

Anaya writes a compact outline instead: each operator is a box with its operands underneath; numbers and names are leaves; brackets and chain boxes vanish, because the shape already shows the grouping.

While building it, she checks units. Rupees plus rupees is rupees. Rupees times a count is rupees. Rupees plus kilograms is nonsense: she complains. When a whole number meets a decimal, she quietly turns the whole number into a decimal first.

2 · Predict First

🤔

How many nodes does the compact outline of a − 4 + c have, compared with its parse tree in E → E + T | E − T | T, T → ( E ) | id | num? Write your guess down. The answer is in the vault.

3 · Core Concept

Syntax trees

A syntax tree (abstract syntax tree) keeps only the essential structure: interior nodes are operators, children are operands. Unlike a parse tree it has no chain nodes (E → T → F), no brackets and no nonterminals. It is the structure the next phases translate.

Building one with an SDD

E → E₁ + T   E.node = new Node('+', E₁.node, T.node)
E → E₁ − T   E.node = new Node('−', E₁.node, T.node)
E → T        E.node = T.node
T → ( E )    T.node = E.node
T → id       T.node = new Leaf(id, id.entry)
T → num      T.node = new Leaf(num, num.val)

This is S-attributed, so an LR parser builds the tree at its reductions. (Older books write mknode(op, left, right) and mkleaf(id, entry).) For a grammar without left recursion, E → T E′, the left operand is passed down as an inherited attribute of E′: an L-attributed version.

Type expressions

A type expression describes a type: basic types (integer, float, char, boolean, void), and constructors applied to type expressions:

• array(n, t): an array of n elements of type t; int a[3][4] is array(3, array(4, integer));
• pointer(t);
• t₁ × t₂ (a pair or record of fields);
• t₁ → t₂ (a function from t₁ to t₂).

Two types are structurally equivalent if they are built the same way; name equivalent if they have the same declared name.

Basic type checking

The type checker is an SDD over the syntax tree or parse tree:

E → E₁ + E₂   if E₁.type = integer and E₂.type = integer then E.type = integer
              else if both are integer or float then E.type = float   (convert the integer)
              else E.type = type_error
E → id        E.type = lookup(id.entry)
S → id = E    if id.type = E.type (or E can be widened to it) then ok else type_error

Converting an integer to a float automatically is a coercion (widening). The checker inserts the conversion, as in the journey line’s inttofloat(qty).

Story → compiler term

4 · Visual

Parse tree of a − 4 + c: 11 nodes.

Syntax tree: 5 nodes, built by the SDD (p1 … p5 below).

p1 = mkleaf(id, a)
p2 = mkleaf(num, 4)
p3 = mknode(−, …)
p4 = mkleaf(id, c)
p5 = mknode(+, …)

Syntax tree of the journey line total = price * qty + 50: 7 nodes (its parse tree in an expression grammar with S → id = E has 16).

5 · Worked Examples

Example 1 Easy

Build the syntax tree of a − 4 + c with the SDD above and list the node creations in order.

Solution

p1 = mkleaf(id, a); p2 = mkleaf(num, 4); p3 = mknode(−, …); p4 = mkleaf(id, c); p5 = mknode(+, …). Leaves come first because the rules run at reductions (bottom-up). Five creations, five nodes, Anaya’s outline.

Example 2 Medium

With price float, qty int and 50 an integer constant, what is the type of price * qty + 50, and which conversions are inserted?

Solution

price * qty: float × integer → float, with inttofloat(qty). Then float + integer → float, converting 50 to 50.0. Type: float. These are exactly the conversions Anaya inserted in the journey line in Lesson 0.1.3.

Example 3 GATE

Give the type expression of int a[10][20] and of a function float f(int, char). Is i + b legal if i is int and b is boolean?

Solution

a: array(10, array(20, integer)). f: (integer × char) → float. i + b: integer + boolean has no rule, so the checker reports a type error, a semantic error found with the symbol table (Lesson 0.1.3).

6 · Shortcuts

⚡

Syntax-tree node count = operators + operands (leaves), ignoring brackets and chain productions. Valid when: counting nodes created by mknode/mkleaf.

⚡

Mixed int/float arithmetic → float with one conversion per int operand; any non-numeric operand → type error. Valid when: basic type-checking questions.

7 · GATE Traps

⚠️

• A syntax tree has no nonterminal nodes and no brackets; a parse tree has both.
• Leaves are created before the operator node that uses them (bottom-up evaluation).
• array(3, array(4, int)) is the type of int a[3][4]: the outer dimension is first.
• Coercion int → float is automatic; float → int usually is not.
• A type mismatch is a semantic error, not a syntax error.

8 · Memory Hook

🧠

Parse tree = how it was read; syntax tree = what it means.

9 · Connect the Dots

Phase 3 is complete: the program is parsed, checked and summarised in a syntax tree. Phase 4 turns that tree into simple, explicit intermediate code, the Drafting Room’s job, starting with a structure that shares repeated computations.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markNodes

How many nodes does the syntax tree of ( a + 4 ) − c have (using the mknode/mkleaf SDD)?

Numerical answer: ________

Q2MCQ1 markSyntax tree

Compared with a parse tree, a syntax tree:

• (A) has more nodes
• (B) keeps every nonterminal
• (C) has operators as interior nodes and no brackets
• (D) is the same tree

Q3MCQ1 markType expressions

The type expression of int a[3][4] is:

• (A) array(4, array(3, integer))
• (B) array(3, array(4, integer))
• (C) array(12, integer)
• (D) pointer(array(3, integer))

Q4MCQ1 markType checking

If i is int and x is float, the type of i * x + i under the usual rules is:

• (A) int
• (B) float
• (C) type_error
• (D) boolean

Q5MSQ1 markFacts

Which are true?

• (A) The syntax-tree SDD with E.node = new Node(…) is S-attributed.
• (B) Leaves are created before the operators that use them when built by an LR parser.
• (C) Coercion from int to float is a semantic action of the type checker.
• (D) Structural and name equivalence always agree.

11 · Rule Card

• Syntax tree: operators inside, operands at leaves; no chains, no brackets.
• SDD: E.node = new Node(op, E₁.node, T.node); leaves new Leaf(id/num); S-attributed.
• Type expressions: basic types; array(n, t), pointer(t), t₁ × t₂, t₁ → t₂.
• Structural vs name equivalence.
• int op float → float (coercion); incompatible operands → type_error.

12 · Concept Ledger

syntax tree (abstract syntax tree)Node / Leaf (mknode / mkleaf)type expressionarray(n, t), pointer(t), t₁ × t₂, t₁ → t₂structural equivalencename equivalencetype checkercoercion (widening)type_error

13 · Answer Vault