CS374: Principles of Programming Languages - Lab: Parser Skeleton (100 Points)

Purpose, Task, and Criteria

Purpose: To stand up the first two tiers of the recursive descent ladder with a partner — the peek/decide/consume pattern that every remaining parsing function repeats — so the Parser assignment's midpoint finds you already climbing.

Task: With a partner, implement parse_primary and parse_unary over the Lexer interface, with tree-shape tests and one positioned parse error.

Criteria: Assessed on correct primary and unary parsing with passing tree-shape tests, and a positioned error on invalid input, weighted 70/30 across the two parts; see the rubric below for the full breakdown.

Assignment Goals

The goals of this assignment are:
  1. To implement the primary and unary tiers of a recursive descent parser over the Lexer's peek/advance/expect interface
  2. To verify parser output with tree-shape tests rather than string comparison
  3. To raise a positioned ParseError stating what was expected and what was found

Background Reading and References

Please refer to the following readings and examples offering templates to help get you started:

The Assignment

This lab builds the bottom of the recursive descent ladder — parse_primary and parse_unary — the two functions whose pattern (look at peek(), decide, consume with advance() or expect(), return a node) every other tier of the Parser assignment repeats. Landing this mid-assignment means the Parser’s hardest stretch starts from working code instead of a blank file. Budget two to three hours with a partner.

Use your own Lexer or the released Reference Lexer — either satisfies the interface contract, and this lab makes a good first test of whichever you plan to build the Parser assignment on.

Pair policy: this lab may be completed in pairs — driver/navigator works well, swapping between the two tiers. Both partners submit the same files, each naming the other, and both earn the same grade. (You may also work alone.) The Parser assignment remains individual work: you may both grow this shared skeleton there, but the remaining tiers are your own.

See the course schedule for the assigned and due dates.

Part 1: The First Two Tiers (70 points)

In parser_skeleton.py, define the AST node dataclasses you need (Num, Str, Bool, Var, Unary, plus a Grouping or pass-through for parentheses — match the node names your grammar work uses), then implement:

  • parse_primary — number, string, and boolean literals; identifiers; and ( expression ) (for this lab, a parenthesized expression may recurse into parse_unary — the full expression ladder arrives in the Parser assignment).
  • parse_unary — - and not, right-associative and nesting (--x, not not ok), delegating to parse_primary at the bottom.

Both functions consume tokens only through the Lexer’s peek/advance/expect — the discipline the whole ladder depends on.

Part 2: Tests and Errors (30 points)

In test_skeleton.py, write tree-shape tests — assert on node types and fields (isinstance(node, Unary), node.op == "-", node.operand.value == 42), never on printed strings — covering every primary form and at least two nested unary cases. Then make failure informative: parsing an input that cannot start an expression (e.g., ;) must raise a ParseError stating what was expected, what was found, and the line and column from the offending token.

Deliverables

Submit a ZIP containing parser_skeleton.py, test_skeleton.py with its passing output captured, and a readme line naming both partners and stating whether you built on your own Lexer or the reference.

Grading Breakdown

Component Points
Part 1: The First Two Tiers 70
Part 2: Tests and Errors 30
Total 100

Reflection Prompts

  • State the peek/decide/consume pattern in your own words — and name which remaining tier of the Parser assignment you expect to repeat it most times.
  • If you worked in a pair, who did what, and name one thing your partner caught that you would have missed. If you worked alone, note that instead.
  • AI disclosure: list any generative-AI tools you used, for what, and how you verified the results (or state ‘none’).
  • Approximately how many hours it took you to finish this lab (I will not judge you for this at all — I am simply using it to gauge if the labs are too easy or hard)?

Submission

In your submission, please include answers to any questions asked on the assignment page, as well as the questions listed below, in your README file. If you wrote code as part of this assignment, please describe your design, approach, and implementation in a separate document prepared using a word processor or typesetting program such as LaTeX. This document should include specific instructions on how to build and run your code, and a description of each code module or function that you created suitable for re-use by a colleague. In your README, please include answers to the following questions:
  • Describe what you did, how you did it, what challenges you encountered, and how you solved them.
  • Please answer any questions found throughout the narrative of this assignment.
  • If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
  • Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
  • Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
  • Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
  • Using the grading specifications on this page, discuss briefly the grade you would give yourself and why. Discuss each item in the grading specification.
  • Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).

Assignment Rubric

Description Pre-Emerging (< 50%) Beginning (50%) Progressing (85%) Proficient (100%)
The First Two Tiers (Goal 1) (70%) Neither tier runs, or the parser reads tokens without using the Lexer interface parse_primary handles literals but not identifiers or parenthesized expressions, or parse_unary cannot nest Both tiers work for the provided cases but one edge fails — e.g., double negation, or a parenthesized expression as a unary operand parse_primary handles number, string, boolean, identifier, and parenthesized expressions; parse_unary handles negation and logical not, nesting correctly (e.g., --x and not not x); both consume tokens only through peek/advance/expect; and the pattern is documented in one sentence per function
Tests and Errors (Goals 2-3) (30%) No tests, or tests compare printed strings instead of tree shapes Tree-shape tests exist for primaries only, and errors are bare Python exceptions Tree-shape tests cover both tiers but the parse error lacks position or the expected/found pair Tree-shape tests cover every primary form and nested unary cases, and an invalid input (e.g., a stray semicolon where an expression is required) raises a ParseError stating what was expected, what was found, and the line and column

Please refer to the Style Guide for code quality examples and guidelines.