Design a mini compiler/interpreter
Problem Description
Design and implement a mini compiler/interpreter for a small expression language.
The input is a program provided as a string, potentially spanning multiple lines. The language features include:
- Integer literals (e.g.,
42) - Variables and assignment (e.g.,
x = 3 + 4) - Standard arithmetic operators:
+,-,*,/, respecting standard precedence rules and supporting parentheses for grouping. - Unary minus (e.g.,
-x) - A
print(expr)statement that outputs the integer result of an expression.
Task
The core task is to build a processing pipeline consisting of three main stages:
- Tokenization (Lexer): Convert the input program string into a sequence of tokens.
- Parsing (Parser): Transform the token sequence into an Abstract Syntax Tree (AST).
- Evaluation (Interpreter): Traverse and evaluate the AST to produce the ordered output from all
printstatements.
Clarifications and Constraints
- Integer division must truncate towards zero.
- All variables are global in scope.
- Any invalid syntax encountered should result in a clear error being raised.
Example
Program:
x = 10
print(x + 2 * 3)
print(-(x - 7))
Expected Output:
16
-3
AI interview prep
Core dilemma
Ensuring correctness and robustness across all stages of the compilation pipeline (lexing, parsing, evaluation) while accurately handling language specificities like operator precedence, variable scope, and providing clear error reporting.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Design a mini compiler/interpreter
Problem Description
Design and implement a mini compiler/interpreter for a small expression language.
The input is a program provided as a string, potentially spanning multiple lines. The language features include:
- Integer literals (e.g.,
42) - Variables and assignment (e.g.,
x = 3 + 4) - Standard arithmetic operators:
+,-,*,/, respecting standard precedence rules and supporting parentheses for grouping. - Unary minus (e.g.,
-x) - A
print(expr)statement that outputs the integer result of an expression.
Task
The core task is to build a processing pipeline consisting of three main stages:
- Tokenization (Lexer): Convert the input program string into a sequence of tokens.
- Parsing (Parser): Transform the token sequence into an Abstract Syntax Tree (AST).
- Evaluation (Interpreter): Traverse and evaluate the AST to produce the ordered output from all
printstatements.
Clarifications and Constraints
- Integer division must truncate towards zero.
- All variables are global in scope.
- Any invalid syntax encountered should result in a clear error being raised.
Example
Program:
x = 10
print(x + 2 * 3)
print(-(x - 7))
Expected Output:
16
-3