Milestone 2: Interpreter

In this second milestone, you'll develop an interpreter for your spreadsheet. The interpreter will translate arbitrary source code from the spreadsheet programmer into the model classes that you wrote for milestone 1.

Grammar

Write in a plain text file the grammar for your spreadsheet's expression syntax in a plain text file. Use the BNF syntax discussed in the readings, lecture, and lab. It must be compatible with Treeformer. Attend to this grammar with utmost concern because it establishes the shape and behavior of your lexer and parser.

Your grammar should describe the structures of a program, with non-terminals for the various expression levels. There should be at least five levels in your precedence ladder. Start with non-terminal named expression that expands to level0 for the operations on the lowest (least-precedent) rung of your precedence ladder. Precedence gets higher with each succeeding level. The top rung of the ladder—levelN—includes the primitives, parenthesized expressions, and any other non-associative or highest-precedence structures. Include all the operators for which you created models in the first milestone.

Verify that your grammar is valid by pasting it in Treeformer and generating abstract syntax trees for two expressions that include several different kinds of operators. Place screenshots of the generated trees in a folder named grammar.

Lexer

Define a lexer that accepts an expression in text form and tokenizes it into a list of tokens. For example, lexing the expression 5 <= 32.0 yields this list in pseudocode:

[
  {type: :integer_literal, text: "5"},
  {type: :less_than_or_equal, text: "<="},
  {type: :float_literal, text: "32.0"}
]

[
  {type: :integer_literal, text: "5"},
  {type: :less_than_or_equal, text: "<="},
  {type: :float_literal, text: "32.0"}
]

Lexers can get messy and hard to maintain without good abstractions. Follow the strategy for designing lexers shown in lecture and the textbook using a big old if statement with loops and calls to has, capture, and emit_token. Reject solutions written by LLMs that obscure the lexing logic with lookup tables.

Do not assume that tokens are separated by whitespace. Calling a split method to divide up the source into tokens is not an appropriate alternative to the algorithm we discussed in class. Both 7+2 and 7 + 2 may be lexed with the algorithm with discussed, but not with a split.

Ensure that your lexer doesn't overstep its authority. It doesn't try to make sense of the tokens, doesn't ensure that they are in a particular order, doesn't reference any of your model classes, and doesn't construct or evaluate any abstract syntax trees. It just chunks characters into tokens. The lexer does not see any issue with the source code 62 =+[54,true^!~.

Parser

Define a parser that accepts a list of tokens and assembles an abstract syntax tree using the model abstractions you wrote in milestone 1. For example, parsing the expression 5 <= 32.0 yields this pseudocode structure:

new LessThanOrEqual(
  new IntegeralLiteral(5),
  new FloatLiteral(32.0)
)

new LessThanOrEqual(
  new IntegeralLiteral(5),
  new FloatLiteral(32.0)
)

There are several ways to write a parser. Follow the pattern shown in lecture and the reading.

Parsers sit at the boundary between the messy human and the exacting computer, so your implementation should detect and gracefully handle errors in the programmer's source code. If you encounter an unexpected token or run out of tokens early, throw an exception with an explanatory message. In milestone 3, you'll catch that exception and show the message to the user.

Write tests that lex and parse the source code for a variety of expressions, evaluate the ASTs, and assert that they produce the expected primitive values. Ensure that your parser doesn't overstep its authority. It doesn't try to perform any typechecking or evaluate any expressions. It only builds trees.

Submission

To submit your milestone, follow the instructions. In particular, do these three things:

• Submit your project to the official GitHub repository that your instructor made for you.
• Record a 3–5 minute screencast of you walking through your code and commenting on it. Do not exceed 5 minutes. Your instructor has many videos to watch. Post it to Canvas Studio according to the instructions.
• Complete the ready date submission form on Canvas.

In your video, show your AST screenshots in the grammar folder and demonstrate lexing, parsing, and evaluating many different expressions that include casting, cell references, and operators from different precedence levels. Include at least these expressions:

• Arithmetic: (5 + 2) * 3 % 4
• Boolean: true == !!!false
• Rvalue lookup and shift: #[0, 0] + 3
• Rvalue lookup and comparison: #[1 - 1, 0] < #[1 * 1, 1]
• Logic and comparison: (5 > 3) && !(2 > 8)
• Sum: 1 + sum([0, 0], [2, 1])
• Casting: float(10) / 4.0
• Exponentiation: 2 ** 3 ** 2
• Negation and bitwise and: 45 & ---(1 + 3)

Your syntax might differ from these examples.

Show also that malformed code yields meaningful error messages that the programmer can use to fix the problem. Include at least these failing expressions:

• Lexer fail: $money
• Lexer fail: 40ish
• Lexer or parser fail: 1.2.3.4.5
• Parser fail: #[5]
• Parser fail: 5 + 6 8
• Parser fail: ----
• Parser fail: ()
• Parser fail: sum()

Don't comment on or show every single line of code in your video. Select a few representative snippets. Do comment on programming language ideas that interest you or challenged you. If you use a language feature, algorithm, or data structure not discussed in class, as is likely if you use an LLM for assistance, you must explain how each deviation works and why it is better. If you do not include these explanations, your submission will not be accepted.

Be prepared to explain any code that you submit during the code review.