Compilers

What does the abstract syntax tree for the expression 2 + 3 * 4 look like?

  1. AThe root is a + node whose right child is a * node representing 3 * 4
  2. BThe root is a * node whose left child is a + node representing 2 + 3
  3. CThe five nodes 2, 3, 4, + and * all sit directly under the root
Show answer and explanation

Answer: A. The root is a + node whose right child is a * node representing 3 * 4

Multiplication has higher precedence than addition, so the expression means 2 + (3 * 4). In an AST, operations computed first sit lower, so the root is +, its left child is 2 and its right child is a * node with children 3 and 4. Evaluating bottom-up computes 3 * 4 = 12 first, then 2 + 12 = 14. A * root corresponds to (2 + 3) * 4, and a flat list cannot express evaluation order.

  • A. Correct. The higher-precedence * sits lower, and the root is +.
  • B. A * root corresponds to (2 + 3) * 4.
  • C. A flat arrangement cannot express evaluation order.
Practice this topic Back to topic

More Compilers questions

  1. Which describes three-address code, a kind of intermediate representation?
  2. What does liveness analysis, done in preparation for register allocation, determine?
  3. In a function, at most five values are live at the same time. In a simple case where the interference graph imposes no further constraints, how many registers are needed at minimum to hold every value without spilling?
  4. If a loop with 100 iterations is unrolled by replicating its body four times, how many counter checks and branches remain? (Assume 100 is divisible by 4.)
  5. What is the usual sequence for producing an executable from a C program?