Minimal Imperative Language — Design and Implementation Task

Context

You are asked to design and implement a minimal imperative language and its tooling. The language supports integers, variables, arithmetic, comparisons, conditionals, loops, and printing. You must decide and document a concrete grammar, implement a tokenizer and recursive-descent parser that produce an AST, perform basic static checks, and execute programs.

Language Specification (to implement)

• Tokens: identifiers, integers, operators (+, -, *, /), comparisons (<, <=, >, >=, ==, !=), assignment (=), punctuation (;, (, ), {, }).
• Statements:
  1. Variable declaration: let x = expr;
  2. Assignment: x = expr;
  3. Conditional: if (expr) { ... } else { ... }
  4. Loop: while (expr) { ... }
  5. Print: print(expr);
• Expressions: integer arithmetic and parentheses.

Deliverables

1. Implement a tokenizer and a recursive-descent parser that builds an AST for a grammar you define.
2. Implement static checks for undefined variables and integer-only type consistency.
3. Implement either:
   • an AST interpreter, or
   • a bytecode compiler plus VM. Choose one, implement it, and justify the choice.

Design Extensions and Discussion

• How would you extend the design to support user-defined functions with lexical scoping and a call stack?
• How would you organize classes and interfaces (OOD) to make adding new statements/operators low-friction while keeping the interpreter/compiler cohesive?
• How will you implement syntax/semantic error reporting with line/column tracking and recovery to continue parsing?
• What are the time and space complexities of tokenization, parsing, and execution with respect to program length?