CS374: Principles of Programming Languages - Lab: Grammar and Derivations Workshop (15 Points)

Purpose, Task, and Criteria

Purpose: To complete the Parser assignment's grammar work with a partner: write a full EBNF grammar for the class language, derive programs that prove it produces what you expect, and settle 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 show how the grammar's shape enforces precedence and associativity.

Criteria: I grade this on a complete and correct EBNF grammar, correct derivations with matching parse trees, and a demonstrated precedence and ambiguity analysis, weighted 50/25/25 across the three parts. The rubric below has the details.

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. You write the EBNF grammar that your recursive-descent parser will transcribe function by function. Getting the grammar right on paper first pays off more than anything else you do in the Parser assignment, because every parsing function you write there is one production from this document. The lab is due mid-assignment, before the parsing code gets serious.

Pair policy. You may do this lab in pairs. Grammar design benefits from argument: one partner proposes a production (a single grammar rule), and the other tries to break it with a program the rule derives wrongly. Turn in the same document, each of you naming the other, and you will both get the same grade. Working alone is allowed. The Parser assignment remains individual work: you may both build on this shared grammar, but your parsers are your own.

Part 0: Before You Start - Derivations, Ambiguity, and Precedence (10%)

Do this part first, before the rest of the lab. You may do it alone even though the rest of this lab is pair work.

A grammar is ambiguous when one string has two different parse trees. Precedence says which operator binds tighter; associativity says how a chain of the same operator groups. Ambiguity stops being subtle the moment you have drawn it twice. Draw both trees, then rewrite the grammar until only one drawing survives. That rewrite is the whole technique, and doing it once by hand teaches more than reading three descriptions of it.

Show that a given expression grammar is ambiguous by drawing two distinct parse trees for one string.
Rewrite the grammar to encode precedence and associativity so the ambiguity is gone. Mark the place where encoding precedence made a rule harder to read. That cost is real, and Part 3 will ask you to defend paying it.
Take 2 - 3 - 4 and draw the parse tree that makes subtraction left-associative, then the one that makes it right-associative. Which does your favorite language use? Confirm it in a REPL rather than guessing.

If the rewrite fell apart on you, bring it anyway. Where it fell apart is what the discussion is for.

Part 1: The EBNF Grammar (45%)

Write the complete EBNF grammar for the class language used across the Lexer, Parser, and Interpreter assignments. Cover these constructs:

let, assignment, and print statements
if/else
while with blocks
expressions over numbers, strings, booleans, identifiers, calls, and the arithmetic, comparison, and 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. This is exactly the shape the Parser assignment’s Part 2 transcribes into functions.

Part 2: Derivations and Parse Trees (23%)

Produce a leftmost derivation and the matching parse tree for each of these two programs. Cite the production applied at every step of each derivation.

let x = 1 + 2 * 3;
while x < 10 { x = x + 1; }

Part 3: Precedence and Ambiguity (22%)

Using your derivation of program 1, explain which productions force * to bind tighter than +. Show the wrong second tree that 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

This lab is worth 15 points, as the course schedule states. Each part’s weight below is a percentage of those 15 points, and the rubric rows use the same percentages.

Component	Weight
Part 0: Derivations, Ambiguity, and Precedence	10%
Part 1: EBNF Grammar	45%
Part 2: Derivations and Parse Trees	23%
Part 3: Precedence and Ambiguity Analysis	22%
Total	100% (15 points)

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%)

Part 0: Before You Start - Derivations, Ambiguity, and Precedence (10%) No parse trees are drawn One parse tree is drawn, so the ambiguity is asserted rather than shown Two distinct parse trees are drawn for one string, but the grammar is not rewritten to remove the ambiguity, or the associativity trees are missing Two distinct parse trees are drawn for one string of an ambiguous grammar; the grammar is rewritten so only one survives, with the place marked where encoding precedence made a rule harder to read; and both the left- and right-associative trees for 2 - 3 - 4 are drawn, with your language's actual choice confirmed in a REPL

EBNF Grammar (Goal 1) (45%) 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, with no precedence levels, 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) (23%) 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) (22%) 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.

Description	Pre-Emerging (< 50%)	Beginning (50%)	Progressing (85%)	Proficient (100%)
Part 0: Before You Start - Derivations, Ambiguity, and Precedence (10%)	No parse trees are drawn	One parse tree is drawn, so the ambiguity is asserted rather than shown	Two distinct parse trees are drawn for one string, but the grammar is not rewritten to remove the ambiguity, or the associativity trees are missing	Two distinct parse trees are drawn for one string of an ambiguous grammar; the grammar is rewritten so only one survives, with the place marked where encoding precedence made a rule harder to read; and both the left- and right-associative trees for 2 - 3 - 4 are drawn, with your language's actual choice confirmed in a REPL
EBNF Grammar (Goal 1) (45%)	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, with no precedence levels, 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) (23%)	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) (22%)	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