Type Checking, Error Reporting, and Expression Graphs in Compilers

In a typical compiler pipeline, type checking happens during semantic analysis after parsing (and often after name resolution). The compiler uses (1) the AST (syntax tree) to understand the structure of a program and (2) semantic/type rules to assign types to expressions and verify that operations are applied to compatible types. For error reporting, compilers track source locations (line/column spans) for tokens and AST nodes, then emit diagnostics with helpful context, often attempting recovery to continue compiling and report multiple errors in one pass.

This section focuses on two connected views of an expression statement:

• The syntax tree (AST) derived from the grammar, which preserves the original operator nesting and parentheses.
• The expression DAG (Directed Acyclic Graph), which can share common subexpressions to reduce recomputation, similar to what many optimizing compilers do (e.g., common subexpression elimination).

We will illustrate both for the statement:
$a = (a * b + c) \uparrow (b + c) * b + c$
where $\uparrow$ denotes an infix binary operator (e.g., some language-defined operator).

Key terms you’ll use repeatedly:

• type checking
• AST
• diagnostic
• semantic analysis

1) Where type checking fits in the compiler

A common high-level organization:

1. Lexing: turns source text into tokens, each with location spans.
2. Parsing: builds an AST (or parse tree) according to grammar.
3. Semantic analysis:
   • Name/scope resolution
   • Type checking
   • Additional legality checks (e.g., “operator applied to wrong kinds of operands”).
4. Intermediate representation (IR) generation / optimization:
   • Expression DAG building / common-subexpression sharing may occur here or earlier/later depending on compiler design.
5. Code generation

Type checking is typically syntax-directed: each AST node corresponds to type rules, and the compiler computes types bottom-up (postorder) or via constraints.

2) How type checking is performed (core mechanisms)

Most compilers implement type checking with one of these closely related approaches:

1. Attribute evaluation (syntax-directed translation)
   Each AST node synthesizes attributes like:

   • type(node)
   • isLValue(node)
   • constValue(node) (optional)

   Rules are driven by grammar productions; e.g., for a binary operator node E1 op E2, the checker:

   • checks type(E1) and type(E2)
   • applies operator typing rules to compute type(E1 op E2)
   • reports diagnostics if rules don’t match.

2. Constraint-based typing (unification / inference)
   For languages with type inference, nodes generate constraints like:

   • type(E1) = int
   • type(E2) = type(E1)
   • type(E1) -> type(E2) for function application, etc.

   A solver then finds consistent assignments. Errors can be reported when constraints become unsatisfiable.

3. Environment-driven checking
   For variables and function calls:

   • the checker queries a symbol table (environment) for declared types
   • then validates usage against expected signatures.

We’ll use the bottom-up, rule-based view since it naturally maps to building an AST and, optionally, to an expression DAG.

Key terms

• symbol table
• synthesized attribute
• constraint solver
• operator typing rule

3) Error reporting: what compilers typically include

A “good” compiler diagnostic often includes:

• Severity: error vs warning vs note
• Location: file, line, column, and sometimes a highlighted snippet
• Message: what went wrong (e.g., “operator * cannot be applied to bool and int”)
• Expected vs actual types (or expected operand categories)
• Related information:
  • notes pointing to the declaration of an identifier
  • additional context for overload resolution failures
• Recovery strategy:
  • local recovery (skip tokens or insert placeholder nodes)
  • panic-mode recovery (synchronize at statement boundaries)
  • continue to find more errors

These details require the AST (or parse tree) to preserve token spans and—during type checking—to keep both inferred and expected types available for messages.

Syntax tree (AST) for the statement

We assume standard precedence/associativity for binary operators * and +, and that $\uparrow$ binds less tightly than $*$ but more tightly than a following $+ c$ in this expression as written. Interpreting:

$a = (a * b + c) \uparrow (b + c) * b + c$

Inside the right-hand side:

1. Left operand of $\uparrow$: $(a * b + c)$
2. Right operand of $\uparrow$: $(b + c) * b$
3. Then the whole thing is added with $+ c$ (because there is a trailing $+ c$ after the $\uparrow$ expression)

So the RHS structure is: $(\ (a*b + c)\ \uparrow\ ((b+c)*b)\ ) + c$

AST (textual)

Let the node labels be:

• Assign
• Plus for +
• Times for *
• UpArrow for ↑

RHS AST:

• Plus
  • left: UpArrow
    • left: Plus
      • left: Times
        • a
        • b
      • right: c
    • right: Times
      • left: Plus
        • b
        • c
      • right: b
  • right: c

Mermaid diagram: AST shape

Expression DAG (common subexpression sharing)

In the AST, the subexpressions $(a*b)$ and $(b+c)$ each occur in multiple places (notably, $(b+c)$ appears inside $((b+c)*b)$, and $c$ appears repeatedly as a leaf). A DAG can share structurally identical subexpressions so that the compiler computes them once.

For this specific expression, the obvious repeated subexpression is $(b+c)$:

• It appears as the left child of the Times node in ((b+c)*b) only once as written, but it may still be shared with other identical occurrences if the overall program repeats it (or if the AST is built from a larger expression where (b+c) occurs multiple times).

To make the DAG meaningful for this single statement, we share at least:

• the leaf occurrences of identical variables (a, b, c) are conceptually shared,
• and we share the computed node for (b+c) if there were multiple uses—here, it has one use within ((b+c)*b). Still, we can express the DAG structure that would allow future reuse.

A more illustrative DAG would show sharing if the expression were, for example, (b+c) * b + (b+c) * b. Since it’s not, the DAG is mostly the same shape as the AST, but it still encodes identity of computed nodes.

DAG diagram