CS374: Principles of Programming Languages - Lab: BNF Workshop (100 Points)

Purpose, Task, and Criteria

Purpose: To get early, low-stakes practice writing grammars — EBNF for two small languages, Chomsky-level classification, and a design-criteria argument — the skill the Parser stretch of the course leans on hardest.

Task: With a partner, write EBNF grammars for two toy languages, classify a set of sample languages by Chomsky level, and argue one syntax design choice against the readability/writability/reliability criteria.

Criteria: Assessed on correct and complete EBNF grammars, correct Chomsky classifications with reasons, and a criteria-grounded design argument, weighted 50/30/20 across the three parts; see the rubric below for the full breakdown.

Assignment Goals

The goals of this assignment are:
  1. To write EBNF grammars for small formal languages
  2. To classify languages by Chomsky hierarchy level and justify each classification
  3. To evaluate a syntax design choice against the readability, writability, and reliability criteria

Background Reading and References

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

The Assignment

This lab is your first grammar-writing rep, taken while the stakes are low: two small EBNF grammars, a Chomsky-classification exercise, and one design argument. Grammar-writing is the skill the Parser assignment leans on hardest, and the Grammar and Derivations Workshop later asks you to do this for the real class language — this lab is the warm-up on toy examples. It is entirely on paper (or in a markdown file); budget two to three hours with a partner.

Pair policy: this lab may be completed in pairs — one partner proposes a production, the other tries to break it with a string it mis-handles. Both partners submit the same document, each naming the other, and both earn the same grade. (You may also work alone.)

See the course schedule for the assigned and due dates. Derivation trees and ambiguity get their own treatment later, in class and in the Grammar and Derivations Workshop — here the job is just to write grammars that draw the right boundary.

Part 1: Two EBNF Grammars (50 points)

Write a complete EBNF grammar for each, in grammars.md, and verify each by hand with three accepted and two rejected strings:

  1. Phone directory entries — lines of the form NAME: (610) 555-0123 or NAME: 555-0123, where a name is one or more capitalized words. The area code is optional; the punctuation is not.
  2. A tiny configuration language — zero or more lines of key = value;, where a key is an identifier, and a value is an integer, a quoted string, or a bracketed comma-separated list of values (lists nest: themes = ["dark", ["contrast", "high"]];).

Use EBNF’s operators for repetition ({ }), optionality ([ ]), and grouping — the point of the exercise is expressing shape declaratively rather than in prose.

Part 2: Chomsky Classification (30 points)

For each language below, name the lowest Chomsky level that can describe it and give a one-sentence reason naming the structural property that forces it:

  1. Binary strings with an even number of 1s.
  2. Balanced parentheses.
  3. Your Part 1 configuration language (careful — the values nest).
  4. Identifiers matching [A-Za-z_][A-Za-z0-9_]*.
  5. Strings of the form a^n b^n c^n (equal counts of all three).

Close with one sentence each: which level do the class language’s tokens need, and which does its full syntax need — and what does that split tell you about why compilers have both a lexer and a parser?

Part 3: Design-Criteria Argument (20 points)

The configuration language’s designer proposes making the trailing ; optional. In one paragraph, evaluate the proposal against at least two of the readability, writability, and reliability criteria from the Evaluating Languages session — with a concrete consequence for each (what a programmer gains or loses) — state the tradeoff, and take a position.

Deliverables

Submit grammars.md containing all three parts, with both partners named at the top.

Grading Breakdown

Component Points
Part 1: EBNF Grammars 50
Part 2: Chomsky Classification 30
Part 3: Design-Criteria Argument 20
Total 100

Reflection Prompts

  • Which string broke your first draft of a grammar, and what production fixed it?
  • 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 Grammars (Goal 1) (50%) Grammars are missing or do not use BNF/EBNF notation One grammar is attempted but accepts clearly invalid strings or rejects clearly valid ones Both grammars are written and mostly correct, but one has an undefined nonterminal or accepts an edge case it should reject (or vice versa) Both grammars are complete and correct EBNF — every nonterminal defined, repetition and optionality expressed with EBNF operators rather than ad-hoc prose — and each is accompanied by three strings it accepts and two it rejects, verified by hand against the productions
Chomsky Classification (Goal 2) (30%) No classifications, or levels are assigned without reasons Some classifications are correct but reasons restate the level name rather than the structural property All classifications are correct but one or two reasons miss the structural property that forces the level (e.g., nesting requiring a stack) Every sample language is classified correctly with a one-sentence reason naming the structural property that forces its level (finite memory suffices; matching/nesting needs a stack; cross-serial constraints need more), and the writeup names which level the class language's tokens versus its full syntax will each need
Design-Criteria Argument (Goal 3) (20%) No argument, or the argument does not reference the course criteria The argument names a criterion but does not connect the syntax choice to a concrete consequence for programmers The argument connects the choice to two criteria with concrete consequences but does not acknowledge the tradeoff The argument evaluates the choice against at least two of readability, writability, and reliability with concrete programmer-facing consequences, states the tradeoff plainly, and takes a defensible position

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