Grades and deadlines

• Initial deadline: 23:59 on Tuesday 16 September

• How to submit: Turn in a completed lab2.1.yml file to the CS department submit system under SI413 / lab2.1

  If you used an AI tool to help with this lab (you should use Gemini), turn in a file aichat.md as well. Remember the course guidelines for the use of generative AI on labs.

  I recommend using the club tool to submit, by running

  club -cSI413 -plab2.1 lab2.1.yml aichat.md
  

• Grading:

  In this lab you will complete the following tasks:

  1. Design a programming language that handles basic string operations as before, plus boolean literals, boolean operations, and (unscoped) variables.
  2. Write an example program and test cases demonstrating how your language works.
  3. Write a token specification list for your language.
  4. Write a context-free grammar using those token types to formally specify your langauge’s syntax.
  5. Briefly describe the new semantics of your language
  6. Participate in peer review as both a reviewer and a reviewee

  If your submission meets all requirements, you will receive 7 points towards your total lab grade.

• Collaboration

  You can freely collaborate with any other students in SI413, as long as that collaboration is clearly documented and you all turn in a unique, original language spec.

• Resubmissions:

  We will follow the same resubmission policy for all labs this semester:

  def points_earned(deadline, max_points, previous_submission=None):
      while current_time() < deadline:
          wait()
      submission = get_from_submit_system()
      if meets_all_requirements(submission):
          return max_points
      elif significant_progress(previous_submission, submission):
          return points_earned(deadline + one_week, max_points, submission)
      else:
          return 0

YAML file to complete

Download the file lab2.1 and fill it in as you complete the tasks for the lab.

Task 1: Language Design

Ground rules

As before, source code should be plaintext using ASCII printable characters, space, and newline.

Your language may build off one or more of the languages from the previous unit, but it doesn’t need to do so. In particular, you can change anything about how those languages work if you want to, or you can start with something completely different. In either case, you need to include the complete specs for your new language in what you turn in for this lab.

Your language must be original and unique. It must have its own name and should not look and/or work quite the same as any other language.

Required capabilities

Your language needs to support all of the things from the previous unit:

• String literals
• String concatenation
• String reversal
• String input
• String printing
• Source code comments

Additionally, your language must also support:

• Boolean literals: Some way to specify a literal “true” or “false” value in source code

• Boolean logic operations: Logical AND and OR of two boolean values, and logical NOT of a single boolean value. (And of course, these operations can be nested arbitrarily.)

• String less-than: Testing whether one string comes before another one in lexicographic order, returning a boolean true/false

• String contains: Testing whether one string is a (contiguous) substring of another one, returning a boolean true/false

• Boolean printing: Printing out a boolean expression to standard out

• Variables: Let the programmer assign a name to the result of evaluating an expression, then use that name in later expressions

Tips

There is some syntax to figure out with boolean literals and the new operations, but you should be comfortable doing that already from previous weeks.

The really new things are variables and having two different types. Think about how you want to handle that in your language!

• Should there be a single print statement/command for both types, or two different commands for printing strings and booleans?

• What does it look like to declare a variable and assign it a value? Maybe these happen in a single statement, maybe not — up to you.

• Is the programmer allowed to re-assign a variable with a new value after assigning it initially?

• Variables values can either be strings or booleans. Should the programmer specify the type when declaring the variable (like in C, C++, Java)?

  Should there be special rules for what variable names are allowed to be for each type (Perl kind of does this with sigils)?

  Or should we let the programmer assign whatever type they want to whatever variable they want, like in Python?

All of this is up to you, and we expect to see a lot of different choices explored in what you turn in. (Ideas not listed above are also welcome!)

REQUIREMENTS

Fill in the language_name field in your YAML file with a name you choose for your programming language.

There is nothing else really to turn in for this part. But you should be sketching out ideas, writing small programs, starting to figure out what works and what doesn’t, as you narrow in on how your language will look and work.

To receive credit for this lab, your language needs to:

• Be original. The syntax and semantics should not be very similar to any single existing language, or to any of your classmates’ languages.

• Support the required capabilities

• Not have unnecessary extra features

Task 2: Example program

Write an example program that demonstrates all features of your language. Include input/output test cases that indicate the program is running correctly.

REQUIREMENTS

Fill in the complete source code (along with comments) under the example_program field in your YAML file.

Fill in your test cases under example_input_1, example_output_1, etc.

Your example program must:

• Demonstrate all of the capabilities that your language has in simple form, clearly demonstrating how your language is supposed to look and work.

• Demonstrate more complex parts to show how your language’s capabilities can be nested and combined.

• Make good use of code comments to explain clearly what your code means and what would happen if it were executed.

Task 3: Scanner specification

Now let’s start specifying the syntax of your language.

Give a table of token names (like STRLIT or ID or BOOLLIT) and corresponding regexes for all of the possible tokens in your language.

The list should be in order of highest to lowest precedence tokens. Regular expressions should use Java syntax.

Use the token name -- for regexes that should be ignored (like comments and whitespace).

REQUIREMENTS

Fill in the rest of the table in the tokens field of your YAML file.

Your tokens must:

• Cover every character in any valid source code for your language
• Use Java regex syntax
• Be properly ordered so that a scanner utilizing maximal munch and tie-breaking by priority will properly tokenize any valid source code in your language

Task 4: Parser specification

Complete the syntax spec for your language by providing a context-free grammar (CFG) for your language.

Use the token names from the token spec that you just wrote above. Each token name should be all caps and will constitute the terminal symbols in your grammar.

The nonterminals in your grammar should be written in lower case. The first nonterminal will be treated as the start symbol, which will be the root node of any correct parse tree for your language covering the complete program.

REQUIREMENTS

Fill in the grammar field of your YAML file with CFG production rules.

Your grammar must:

• Use the token types from the previous part as terminal symbols
• Allow any valid program in your language to parse as a single tree with the start symbol (first nonterminal) as the root

Task 5: Semantics specification

Indicate the meaning of any syntactically valid program in your language, answering questions such as:

• What do all the different operators do?
• What do “true” and “false” literals look like?
• How will boolean values get printed?
• How do variables work regarding types and reassignment (see discussion above)?

You can assume we all know what “string concatenation”, “reversal”, “lexicographical comparison”, etc., all mean. The question here is to connect the parts of your syntax with these meanings.

REQUIREMENTS

Fill in the semantics field of your YAML file with a specification of the language semantics, connecting the required capabilities to syntax in your particular language.

Your semantics spec must:

• Be clear and easy to understand
• Not be overly long or explain “obvious” aspects
• Make it possible for anyone to know exactly how a program in your language should behave

Task 6: Peer review

Everyone must be designated as the “final reviewer” of exactly one other student in your section. The easiest way to do this is to form groups of 2 and 3 and do the reviews in a “circle” within that group.

When reviewing someone’s spec, you should probably try writing a small program in that spec and see if it makes sense. Think hard about edge cases or ambiguities.

By indicating Y that your spec has passed “final review”, you are saying that the version you are turning in has been successfully reviewed and the reviewer agrees it covers all the requirements with no ambiguities or UB.

REQUIREMENTS

Fill in the last four questions in your YAML file, indicating whose spec you have or will review, who has reviewed your spec, and a clear Y or N indicating whether the reviewer agrees that the version you are turning in satisfies all the requirements of the language and is clearly presented.