Project 2a

Due Date: Mon 14 Nov

Pair Project

Objectives

  • Design patterns
    • Composite
    • Visitor
    • Interpreter
    • Factory method
  • Programming language design and constructs
    • simple imperative constructs
    • nested records
  • Programming language implementation tools and techniques
    • lexical analysis
    • syntax analysis (parsing)
    • read-eval-print loop (REPL)
    • abstract syntax trees
    • static operations on abstract syntax trees: validity checkers
    • dynamic operations on abstract syntax trees: interpreters
    • runtime representations

Description

Your job is to build an interactive interpreter for a simple imperative language with nested records.

Syntax

Please look at the sample test cases linked below to get an idea of the concrete syntax of our mini-language. The grammar for this syntax is as follows; keywords and symbols are indicated in bold.
  • program = declaration* statement
  • declaration = vardecl | typedecl
  • vardecl = var JavaIdentifier
  • typedecl = struct JavaIdentifier { JavaIdentifier ( , JavaIdentifier )* }
  • statement = assignment | whileloop | sequence | expression
  • whileloop = while ( statement ) statement
  • sequence = { statement ( , statement )* }
  • assignment = statement = statement
  • expression = arithexpr | selection | newexpr
  • arithexpr = please see example from class
  • selection = statement . JavaIdentifier
  • newexpr = new JavaIdentifier
Your job is to implement a parser for this concrete syntax that constructs suitable abstract syntax trees. (It is our job as a group to iron out any bugs in this grammar, such as left-recursion!)

Semantics

Semantics refers to the meaning of a document in a language, such as a program. We distinguish between static semantics (compile-time type checking, other kinds of validation) and dynamic (= runtime) semantics. In this simple language, we do not have explicit compile-time type information, but there are other kinds of validation we can explore, e.g., ensuring that the left side of an assignment is a proper l-value (something we can assign to, such as a standalone variable or a member variable of a struct).

Because our language is a fragment of C, very loosely speaking, we can informally define the semantics of our language as "whatever the program would do if we treated it as a C program". It is also possible to provide a formal definition of the semantics of our language: imperative structs But we will keep this discussion largely informal and go into more detail in class. In particular, in following C tradition, an assignment evaluates to the assigned value (r-value); in following functional language tradition, a sequence evaluates to its last value and a while loop evaluates to nothing.

Your job is to implement a simple static validator and a complete interpreter.

Static Validator

The purpose of this validator is to check the sanity of some aspects of a program in this language without actually executing the program. In particular, the validator ensures that
  • only statements that evaluate to a number are used as loop conditions:
    • arithmetic expressions (including constants and variables)
    • assignments whose right side evaluates to a number
    • selections
    • sequences whose last statement can evaluate to a number
  • only statements that evaluate to an l-value are used as left sides of assignments:
    • variables
    • selections
    • sequences whose last statement evaluates to an l-value
    • in particular, assignment statements themselves cannot be used as l-values (only as r-values)
As you notice, this validator is not perfect (because it allows selections) but catches some of the cases that would otherwise lead to errors. You should come up with at least two additional test cases for the validator.

Runtime Representation

The interpreter will rely on certain runtime constructs.
  • A value is a number or an instance.
  • An instance is a map from names to variables.
  • A store is an instance.
  • A variable holds a value, which can be changed.

REPL

Once you have a working parser, validator, and interpreter, exposing these as a REPL is easy: Repeatedly prompt for input strings until you see the interactive termination character (in our case, a semicolon). Parse the resulting concatenation, validate it, interpret it, and print the result, if any.

Special commands for the REPL include
  • help;
  • quit;
  • clear; for resetting the store
  • dump; for displaying the contents of the store

Nonfunctional Requirements

  • Try to adhere to the Scala coding guidelines.
  • More importantly, continue to follow test-driven development (TDD) by creating automated unit tests for your various program components: 
  • You will need a symbol table where the parser stores struct definitions for the interpreter to use. You should use simple dependency injection techniques to share this symbol table between the parser and the interpreter.

Submission

Comments