ACompressed recap
🧾
Syntax-directed definitions build a syntax tree (operators inside, operands at leaves, no brackets or chain nodes) with rules like E.node = new Node('+', E₁.node, T.node); built at reductions, leaves first. Type checking computes a type for every expression from type expressions (basic types and constructors array, pointer, ×, →), inserts coercions (int → float) and reports type errors.
BMerged rule card
3.4 Applications: building syntax trees; basic type checking (brief)
- 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.
CInterleaved GATE-style questions
Q1NAT1 markNodes
How many nodes does the syntax tree of the journey line total = price * qty + 50 have (assignment as an operator node)?
Numerical answer: ________
Q2NAT2 marksNodes
In the grammar S → id = E, E → E + T | T, T → T * F | F, F → ( E ) | id | num, how many nodes does the parse tree of the journey line have?
Numerical answer: ________
Q3MCQ1 markOrder
Building the syntax tree of a − 4 + c bottom-up, the first node created is:
- (A) the + node
- (B) the − node
- (C) the leaf for a
- (D) the leaf for c
Q4MCQ1 markTypes
A function taking an int and a char and returning a float has type expression:
- (A) float → (int × char)
- (B) (int × char) → float
- (C) int → char → float
- (D) pointer(float)
Q5MCQ1 markType checking
For bool b and int i, b + i is:
- (A) int
- (B) float
- (C) a type error
- (D) bool
Q6MSQ2 marksSyntax trees
Which are true about syntax trees?
- (A) They omit parentheses.
- (B) They are produced by the lexer.
- (C) They can be built by an S-attributed SDD.
- (D) Each operator node has its operands as children.
Q7MCQ2 marksCoercion
Under widening rules, x = i + 2.5 with x float and i int requires:
- (A) no conversion
- (B) converting i to float
- (C) converting 2.5 to int
- (D) a type error
Q8NAT1 markCalls
Building the syntax tree of a − 4 + c, how many times is mkleaf called?
Numerical answer: ________
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 71 mark
=, total, +, *, price, qty, 50: 7.
Re-read: Lesson 3.4 — Applications: building syntax trees; basic type checking (brief)
Q2 Answer: 162 marks
Computed from the real parse tree: 16 (versus 7 in the syntax tree).
Re-read: Lesson 3.4 — Applications: building syntax trees; basic type checking (brief)
Q3 Answer: (C)1 mark
Leaves are created as their tokens are reduced, starting from the left.
- (A) is wrong: Created last.
- (B) is wrong: Created after a and 4.
- (D) is wrong: Created after −.
Re-read: Lesson 3.4 — Applications: building syntax trees; basic type checking (brief)
Q4 Answer: (B)1 mark
Domain → range, with a product for two arguments.
- (A) is wrong: Reversed.
- (C) is wrong: That is a curried function, a different type.
- (D) is wrong: Not a pointer.
Re-read: Lesson 3.4 — Applications: building syntax trees; basic type checking (brief)
Q5 Answer: (C)1 mark
No arithmetic rule for boolean operands.
- (A) is wrong: Needs both numeric.
- (B) is wrong: Needs numeric operands.
- (D) is wrong: Not a logical operator.
Re-read: Lesson 3.4 — Applications: building syntax trees; basic type checking (brief)
Q6 Answer: (A) (C) (D)2 marks
The parser and SDD build them, not the lexer.
Re-read: Lesson 3.4 — Applications: building syntax trees; basic type checking (brief)
Q7 Answer: (B)2 marks
int + float → float, so i is widened.
- (A) is wrong: Types differ.
- (C) is wrong: Narrowing is not automatic.
- (D) is wrong: It is legal with coercion.
Re-read: Lesson 3.4 — Applications: building syntax trees; basic type checking (brief)
Q8 Answer: 31 mark
a, 4, c: 3 (mknode twice).
Re-read: Lesson 3.4 — Applications: building syntax trees; basic type checking (brief)