CS 432

P2: Decaf Parser

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 syntax analysis: transform the Decaf grammar into an LL(1) grammar and implement a recursive-descent parser as the second pass of your compiler.

Introduction

Add a parser to the compiler you began in P1. Drop the test-p2/ folder into your project beside test-p1/ and extend your compiler so that it parses the token stream into whatever internal representation you choose. Read the "Syntax" section of the Decaf language reference carefully first.

As always, the rules in the Project Overview (command-line contract, cumulative grading, distribution, submission) apply and are not repeated here.

Assignment

Your parser must accept every valid Decaf program and reject every program that violates the syntax in section 3 of the reference, reporting the earliest error with a descriptive message and line number to standard error. Internally you should build some form of abstract syntax tree, but its structure is up to you and is not graded directly. However, you should design it carefully because the next two projects will build upon it. There is a recommended structure in the language reference.

Two observable behaviors are graded:

• Validity — compiler exit status (0 = accepted, non-zero = rejected).
• Expression structure — a canonical --fdump-expr rendering of each expression, which tests operator precedence, associativity, and literal values without constraining your internal representation.

The --fdump-expr format is fully-parenthesized prefix (Polish / S-expression) notation, printed one expression per line with single spaces and no trailing whitespace, and compared character-by-character. This is the complete specification:

• Binary operation: (OP left right), where OP is the source operator token — one of + - * / % < <= > >= == != && ||.
• Unary operation: (- operand) or (! operand), again using the source operator.
• Integer literal: its decimal value, so 0x10 prints as 16.
• Boolean literal: printed literally (true, false, or the name).
• String literal: printed with its surrounding double quotes, escape sequences shown as written — e.g. "hi\n".
• Array access: (index name subscript).
• Function call: (call name arg …).
• Source parentheses are ignored unless they are required to disambiguate the parse tree, so e.g. ((2) + 3) * 4 → (* (+ 2 3) 4).

Here are some examples:

Writing this small prefix serializer is itself a required part of P2. Note that you should also parse token text into values while building the tree: convert integer literals to an integer type, and strip the quotes and expand the escape codes of string literals. Each AST node must also record source line information (the line of the first token belonging to that node or any descendant); line numbers are required and are spot-checked by hand on the error-case tests.

This is a large project — you will write a routine for almost every non-terminal in the grammar — so start early. Keep an eye out for places where the reference grammar is not LL(1) so you can plan around it. A good way to begin is with a much-reduced grammar and grow it; for instance the following is a complete language that is a subset of Decaf:

Program -> VarDecl*
VarDecl -> Type IDENTIFIER ';'
Type -> 'int' | 'bool' | 'void'

Work tier by tier (D, then C, …), testing incrementally. When behavior is underspecified, match decaf-ref; its --fdump-tree flag prints a full AST for comparison-based debugging (that dump is not graded — only --fdump-expr and validity are).

HINT: the simple expression parser demo (/cs/students/cs432/f26/expr_parser.tar.gz on stu) illustrates the basic recursive descent technique for the expression grammar.

Sample

For the program:

def int main()
{
    int a;
    a = 3;
    return a + 4 * 2;
}

the compiler accepts the program (exit 0), and --fdump-expr renders its expressions in prefix form:

3
(+ a (* 4 2))

Submission

Submit your entire project directory: run /cs/students/cs432/f26/submit.sh p2 from your project root and confirm the P2 assignment on Canvas. This project requires significantly more code than P1, so aim to reach "C" or "B" by the milestone date (about a week before the deadline). If you submit by the milestone, I will run the full suite and give you informal feedback before the final deadline.

Code Reviews

After this project you will review two other students' submissions and offer constructive feedback per the given rubric, graded separately for effort (see the syllabus). Submit your review on Canvas by the date given in the corresponding assignment.

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.

Array parsing is a C-level requirement here. Array support is deliberately tiered differently in each phase: parsing array declarations and locations is C-level (P2); the array semantic checks are B-level and A-level (P3); 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.