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:
-
Variable declaration:
let x = expr;
-
Assignment:
x = expr;
-
Conditional:
if (expr) { ... } else { ... }
-
Loop:
while (expr) { ... }
-
Print:
print(expr);
-
Expressions: integer arithmetic and parentheses.
Deliverables
-
Implement a tokenizer and a recursive-descent parser that builds an AST for a grammar you define.
-
Implement static checks for undefined variables and integer-only type consistency.
-
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?