CS 432

P3: Static Analysis

Objective

The goal of our semester-long project is to gain experience in compiler implementation by constructing a simple compiler. In this phase you will add static analysis — type inference, type checking, and other semantic verification — as the third pass of your compiler.

Introduction

Add semantic analysis to your compiler. Drop the test-p3/ folder into your project and extend your compiler so that, after parsing, it verifies that the program is a valid Decaf program per the "Type Checking" section of the language reference. Unlike lexing and parsing, semantic errors are usually not fatal to further checking, so the usual approach is to collect as many errors as possible in one pass and report them all.

The rules in the Project Overview apply here as always. For P3 the graded contract is exit status only: your compiler must exit 0 for a valid program and non-zero for one containing any semantic error (checked with --stop-after-analysis). There are no expected-output files for this phase. Error messages should be sent to standard error; they are not graded automatically so they don't need to match the reference compiler's output, though they must still be descriptive (and will be spot-checked by hand). How you build symbol tables, infer types, and traverse the AST is up to you, although I recommend reading the language specification carefully.

Symbol tables and scope

You will need a notion of symbol tables — registries that map names to type information, one per scope. In Decaf the natural scopes are the whole program (global variables and functions), each function (its parameters), and each block (its local variables); every scope also links to its enclosing scope so that a lookup can walk outward. You are free to design these structures however you like.

The three built-in output functions are provided by the Decaf runtime and are not declared in any program, so your global scope must treat them as predeclared:

print_str : STR -> VOID
print_int : INT -> VOID
print_bool : BOOL -> VOID

Assignment

Perform type inference and type checking over the AST, plus any other semantic checks needed to confirm the program obeys the language reference (paying particular attention to the type rules). Report at least one error for every invalid program and no errors for any valid program. Two checks you do not need to perform: verifying that every path through a function returns (this needs control-flow analysis, which is hard on an AST), and verifying that array accesses are in bounds (this is undecidable in general).

When behavior is underspecified, match the reference compiler (decaf-ref); its --fdump-tables flag prints the AST annotated with symbol tables and inferred types, which is useful for debugging your own analysis even though that output is not graded.

Sample

A well-formed program (e.g. an int main() that declares and uses variables consistently) analyzes cleanly and exits 0. A program with a semantic error — for instance

def int main()
{
    int a;
    a = true;      // type mismatch: assigning bool to int on line 4
    return a;
}

is rejected with a non-zero exit status and a descriptive message naming the offending line (w/ line number).

Submission

Submit your entire project directory: run /cs/students/cs432/f26/submit.sh p3 from your project root and confirm the P3 assignment on Canvas. There is no code review for P3 (code reviews follow P0, P2, and P4).

Grading

This checkpoint is autograded on the tier rubric below; your grade is the highest tier whose requirements all pass. Tests are cumulative and mostly not provided to you in advance, so write your own.

Grade	Description	Requirements
A	Exceptional	Handle all edge cases correctly (e.g., zero-size arrays) No compiler warnings or memory leaks All of the below
B	Good	Reject all kinds of type mismatch errors requiring full type inference Reject duplicate symbols within a particular symbol table Reject array accesses without an index Report descriptive error messages w/ debug info (assessed manually) All of the below
C	Satisfactory	Reject any type mismatch errors that require only literal and location type inference Reject `return` statements that do not match their function's return type Reject `break` and `continue` statements outside a loop All of the below
D	Deficient	Reject `VOID` variables Reject undefined variables in locations Reject programs with missing or incorrect '`main`' function Accept all otherwise valid programs
F	Unacceptable	Some evidence of a good-faith attempt

Array semantic checks are tiered within this phase: the no-index and index-type checks are B-level, while the zero-size-array edge case is A-level. Array support is deliberately tiered differently across phases — array parsing is C-level (P2) and array code generation is A-level (P4). The rubric shows the base grade possible if your submission meets the criteria listed; most items are assessed by automated testing using cases mostly NOT provided in advance.

I will also examine your submission manually for acceptable style and documentation and for the use of any unsafe functions. Deficiencies may earn a numerical deduction, and egregious ones a half- or full-letter deduction. If you are unsure of my standards, review the style guide and list of unsafe functions from CS 261.

Compilers - Fall 2026