CS 432

P1: Decaf Lexer

Objective

The goal of our semester-long project is to gain experience in compiler implementation by constructing a simple compiler. In this first phase you will implement the compiler's lexer, using regular expressions to turn Decaf source text into a stream of tokens for later phases.

Introduction

This is the first compiler checkpoint, so you start from the provided scaffold that already parses the command-line parameters, plus the P1 public test suite. Everything else — how you scan, store, and emit tokens — is your design. Before coding, read the "Lexical Considerations" section of the Decaf language reference and skim the grammar that follows it.

First read the Project Overview on the assignments page. It describes the command-line contract, the cumulative-grading rules, what you receive, and how to submit; those rules apply to every checkpoint and are not repeated here. If it has been a while since you wrote C, the C for CS 432 guide reviews some language features you may find useful when designing your own data structures.

Getting Started

The starter files are posted in subfolders of /cs/students/cs432/f26 on stu (the student server). The P1 distribution includes two folders: 1) skeleton, a minimal scaffold (a Makefile and a src/main.c that already parses the command-line contract required by the project overview and leaves each phase as a TODO), and 2) test-p1/, the public test suite along with the reference compiler binary decaf-ref.

Recommended setup commands :

    mkdir cs432 && cd cs432
    mkdir decaf && cd decaf
    cp -r /cs/students/cs432/f26/skeleton/* .
    cp /cs/students/cs432/f26/skeleton/.gitignore .
    cp -r /cs/students/cs432/f26/test-p1 .

At this point, you should be able to build and run the minimal scaffold:

    make
    ./decaf test-p1/inputs/D_level.decaf

Compare against the reference compiler output:

    test-p1/decaf-ref --fdump-tokens --stop-after-lex test-p1/inputs/D_level.decaf

Run the provided public P1 test suite using make test.

Once you have created a stub repository on Github, connect it using the following commands:

    git init
    git add .
    git commit -m "Initial commit"
    git remote add origin git@github.com:USERNAME/REPONAME.git
    git branch -M main
    git push -u origin main

Assignment

Implement lexical analysis: read Decaf source text and produce the token stream defined in the "Lexical Considerations" section of the language reference. Your compiler must print that stream when run with --fdump-tokens (the format is fixed by the reference and compared byte-for-byte — see the sample output below), and must exit with a non-zero status on input that cannot be lexed. How you represent tokens internally is up to you.

Suggested approach: process the input by repeatedly matching regular expressions (roughly one per token type) against the front of the remaining input (anchor with ^); taking the highest-priority match, until the input is consumed or nothing matches (a lex error). Do not split the input on spaces or other delimiters; that approach cannot handle Decaf and leads to hard-to-manage edge-case workarounds. The POSIX regex facilities (man 7 regex on stu) are one convenient option.

As in every phase, your compiler must never crash or segfault on bad input: validate its arguments, and report a lexing problem with a descriptive error message and line number printed to stderr rather than aborting abnormally. Where the specification and this description do not fully pin down some behavior, match the reference compiler (decaf-ref in the test folder); run it with --fdump-tokens --stop-after-lex to see the expected token dump.

HINT: Use the rubric (see "Grading" below) as a to-do list. Complete the "D" requirements first, then "C", and so on, testing thoroughly and incrementally as you go.

Sample Input

def int main()
{
    int a;
    a = 4 + 5;
    return a;
}

Sample Output

(produced by decaf --fdump-tokens)

KEYWORD  [line 001]  def
KEYWORD  [line 001]  int
ID       [line 001]  main
SYMBOL   [line 001]  (
SYMBOL   [line 001]  )
SYMBOL   [line 002]  {
KEYWORD  [line 003]  int
ID       [line 003]  a
SYMBOL   [line 003]  ;
ID       [line 004]  a
SYMBOL   [line 004]  =
DECLIT   [line 004]  4
SYMBOL   [line 004]  +
DECLIT   [line 004]  5
SYMBOL   [line 004]  ;
KEYWORD  [line 005]  return
ID       [line 005]  a
SYMBOL   [line 005]  ;
SYMBOL   [line 006]  }

Submission

Submit your entire project directory by running /cs/students/cs432/f26/submit.sh p1 from your project root, and confirm the P1 assignment on Canvas. Verify that make builds ./decaf from a clean copy first. See the Project Overview for the per-checkpoint AI-use disclosure and other submission details.

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. There is no code review for P1 (code reviews follow P0, P2, and P4).

Rubric:

The above 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 to you in advance (so write your own tests!).

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.