CS374: Principles of Programming Languages - Lab: Grammar and Derivations Workshop (100 Points)
Purpose, Task, and Criteria
Purpose: To complete the Parser assignment's grammar work with a partner — a full EBNF grammar for the class language, derivations that prove it produces the programs you expect, and precedence decisions you can defend.
Task: With a partner, write the EBNF grammar the Parser assignment's Part 1 requires, produce leftmost derivations and parse trees for two worked programs, and demonstrate how the grammar's shape enforces precedence and associativity.
Criteria: Assessed on a complete and correct EBNF grammar, correct derivations with matching parse trees, and a demonstrated precedence/ambiguity analysis, weighted 50/25/25 across the three parts; see the rubric below for the full breakdown.
Assignment Goals
The goals of this assignment are:- To write a complete EBNF grammar for the class language's expressions and statements
- To construct leftmost derivations and parse trees that verify the grammar against concrete programs
- To explain how grammar structure (the expression ladder) enforces precedence and associativity and eliminates ambiguity
Background Reading and References
Please refer to the following readings and examples offering templates to help get you started:The Assignment
This lab is the Parser assignment’s Part 1, done early and with a partner: the EBNF grammar that your recursive-descent parser will transcribe function-by-function. Getting the grammar right on paper first is the highest-leverage two hours of the whole Parser assignment — every parsing function you write in the Parser assignment is one production from this document. Budget two to three hours; it is due mid-assignment, before the parsing code gets serious.
Pair policy: this lab may be completed in pairs. Grammar design benefits from argument — one partner proposes a production, the other tries to break it with a program it mis-derives. Both partners submit the same document, each naming the other, and both earn the same grade. (You may also work alone.) The Parser assignment remains individual work: you may both build on this shared grammar, but your parsers are your own.
Part 1: The EBNF Grammar (50 points)
Write the complete EBNF grammar for the class language used across the Lexer, Parser, and Interpreter assignments: let/assignment/print statements, if/else, while with blocks, and expressions over numbers, strings, booleans, identifiers, calls, and the arithmetic/comparison/logical operators. Structure the expression productions as a ladder — one production per precedence level, from or at the top down through and, comparison, additive, multiplicative, unary, and primary — exactly the shape the Parser assignment’s Part 2 transcribes into functions.
Part 2: Derivations and Parse Trees (25 points)
Produce a leftmost derivation (every step citing the production applied) and the matching parse tree for both:
let x = 1 + 2 * 3;while x < 10 { x = x + 1; }
Part 3: Precedence and Ambiguity (25 points)
Using your derivation of program 1, explain which productions force * to bind tighter than +, and show the (wrong) second tree a flat single-level expression grammar would also permit. Then state how your grammar makes 1 - 2 - 3 associate left, and verify with a three-line derivation sketch.
Deliverables
Submit grammar.md containing all three parts, with both partners named at the top. Bring it to the Parser assignment: its Part 1 asks you to include (and refine, if the coding surfaces issues) exactly this grammar.
Grading Breakdown
| Component | Points |
|---|---|
| Part 1: EBNF Grammar | 50 |
| Part 2: Derivations and Parse Trees | 25 |
| Part 3: Precedence and Ambiguity Analysis | 25 |
| Total | 100 |
Reflection Prompts
- Which production went through the most revisions before your partner could no longer break it, and what broke it last?
- 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%) |
|---|---|---|---|---|
| EBNF Grammar (Goal 1) (50%) | The grammar is missing most constructs or does not use EBNF notation | The grammar covers expressions or statements but not both, or several productions reference undefined nonterminals | The grammar is complete but flat — precedence levels are missing, so it is ambiguous for arithmetic | The grammar covers every expression and statement form of the class language in correct EBNF, with a tiered expression ladder (one production per precedence level) and no undefined nonterminals |
| Derivations and Parse Trees (Goal 2) (25%) | No derivation is attempted, or the derivations do not follow the submitted grammar | One program is derived but with skipped steps, or the parse tree does not match the derivation | Both programs are derived with matching trees, but one derivation has a misapplied production | Both worked programs have complete leftmost derivations, every step citing the production applied, with parse trees that match the derivations exactly |
| Precedence and Ambiguity Analysis (Goal 3) (25%) | No analysis, or the analysis restates notes without using the submitted grammar | The analysis asserts precedence works but shows no derivation-level evidence | The analysis shows the correct tree for the precedence example but does not explain which grammar feature forces it | The analysis derives the precedence example, names the exact productions that force multiplication to bind tighter than addition and subtraction to associate left, and shows what a flat one-level grammar would have permitted instead |
Please refer to the Style Guide for code quality examples and guidelines.